Learning with Errors (LWE)

Core Idea

The Learning with Errors (LWE) problem asks: given pairs (a_i, b_i) where b_i = <a_i, s> + e_i mod q (inner product with a secret vector s, plus small random noise e_i), find s — or even distinguish these pairs from uniformly random. Regev (2005) proved that LWE is as hard as worst-case lattice problems (with a quantum reduction). LWE underpins most modern lattice-based cryptography: Regev encryption, key exchange (Kyber/ML-KEM), FHE (BGV, BFV, CKKS), and more. Ring-LWE and Module-LWE use polynomial ring structure for efficiency. The noise is essential — without it, the problem reduces to linear algebra (Gaussian elimination).

Explainer

The Learning with Errors (LWE) problem, introduced by Oded Regev in 2005, is arguably the most important computational assumption in modern cryptography. The problem is simple to state: you are given many samples of the form (a_i, b_i) where a_i is a random vector in Z_qⁿ and b_i = <a_i, s> + e_i mod q — the inner product of a_i with a secret vector s, plus a small random error e_i drawn from a discrete Gaussian distribution. Your task is to find s (search LWE) or even just to distinguish these noisy linear equations from completely random pairs (decisional LWE).

Without the noise term e_i, LWE would be trivial: collect n linearly independent samples and solve the linear system As = b via Gaussian elimination. The small noise transforms the problem fundamentally. Gaussian elimination on noisy equations amplifies errors catastrophically — the resulting "solution" bears no resemblance to s. Instead, solving noisy linear equations requires finding a lattice point close to a target vector, which connects LWE to the Closest Vector Problem (CVP) on lattices. Regev proved that LWE is at least as hard as worst-case lattice problems (specifically, approximate GapSVP and SIVP), using a quantum reduction. This means that any efficient algorithm for LWE — classical or quantum — would yield an efficient quantum algorithm for worst-case lattice problems, which are widely believed to be hard.

LWE-based encryption (Regev encryption) encodes a message bit in the "most significant" part of a noisy inner product. The ciphertext (a, b) sets b = <a, s> + e + m * floor(q/2), encoding message m in the large gap between 0 and q/2. Decryption computes b - <a, s> = e + m * floor(q/2); since the error e is small, rounding recovers m. This is the template for all LWE-based encryption: information is hidden in noise, and the secret key enables noise removal to recover the plaintext. The same principle extends to key exchange (Kyber/ML-KEM), signatures (Dilithium/ML-DSA), and fully homomorphic encryption (where the noise grows with computation but can be refreshed via bootstrapping).

For efficiency, Ring-LWE replaces the random matrix with structured polynomial multiplication in R_q = Z_q[x]/(xⁿ + 1). This reduces key sizes from O(n²) to O(n) and computation from O(n²) to O(n log n) via the Number Theoretic Transform (NTT). Module-LWE, used in NIST's ML-KEM standard, operates on small k x k matrices over the ring — a middle ground between the strong theoretical guarantees of unstructured LWE and the full efficiency of Ring-LWE. The ML-KEM standard (previously Kyber) uses Module-LWE with dimensions k = 2, 3, or 4 for different security levels, achieving public key sizes around 800-1500 bytes and encapsulation times under a millisecond. The transition from RSA/ECDH to LWE-based key exchange is the defining infrastructural change of post-quantum cryptography.