Learning With Errors

Learning With Errors (LWE) is a computational problem that serves as the foundation for post-quantum cryptography. Introduced by Oded Regev in 2005, LWE asks an adversary to distinguish a set of linear equations with small additive noise from truly random equations. The problem is believed to be hard for both classical and quantum computers, making it a cornerstone of cryptographic schemes designed to resist quantum attacks.

The mathematical formulation is deceptively simple. Given a secret vector s and a matrix A, the adversary receives pairs (a, b) where b = ⟨a, s⟩ + e mod q, with e drawn from a small error distribution. The task is to recover s. Without the error e, this is linear algebra and efficiently solvable. With the error, the problem becomes a closest-vector problem in lattices — believed to be intractable for large dimensions.

What makes LWE remarkable is its worst-case to average-case reduction: Regev proved that solving LWE on average is at least as hard as solving certain lattice problems in the worst case. This is one of the few problems with such a reduction, providing a stronger theoretical foundation than most cryptographic assumptions. The reduction connects the average-case hardness of LWE to the worst-case hardness of the Shortest Vector Problem and Shortest Independent Vectors Problem in lattices.

LWE has enabled practical cryptographic constructions including fully homomorphic encryption, allowing computation on encrypted data without decryption, and lattice-based key exchange protocols that resist quantum attacks. The NIST post-quantum cryptography standardization process has selected LWE-based schemes as finalists.

From a systems perspective, LWE represents a shift from number-theoretic cryptography (factoring, discrete logarithm) to geometric cryptography (lattices, norms, distances). The security of LWE does not depend on the structure of prime numbers but on the geometry of high-dimensional spaces — a fundamentally different source of computational hardness.