Learning With Errors
Learning With Errors is an average-case mathematical problem in lattice-based cryptography that serves as the hardness assumption for post-quantum key encapsulation and digital signature standards.
Learning With Errors (LWE) is a foundational average-case computational problem in computation and algorithms that serves as the central hardness assumption for modern lattice-based cryptography, post-quantum encryption standards, and fully homomorphic encryption. Introduced in 2005 by Israeli-American computer scientist Oded Regev, LWE established a bridge between high-dimensional geometric lattice theory and practical cryptographic engineering.
From a mathematical perspective, LWE can be conceptualized as the task of solving a system of noisy linear equations over a finite field. While solving exact linear systems of equations A s = b mod q is trivial in polynomial time using Gaussian elimination, introducing small random errors into each equation renders the problem computationally intractable for classical and quantum algorithms.
Mathematical Formulation: Search and Decision LWE
Let n and m be positive integers representing the security parameter and number of samples, let q โฅ 2 be a prime modulus, and let chi be an error probability distribution over โคq (typically a rounded discrete Gaussian distribution with mean 0 and standard deviation sigma = alpha ยท q).
The LWE framework is formalized through two equivalent formulations:
1. Search-LWE
Let s โ โคqn be a secret vector sampled uniformly at random. An adversary receives m independent linear equation samples of the form (ai, bi), where each ai is drawn uniformly from โคqn and:
bi = โฉai, sโช + ei mod q
where each error ei is sampled independently from the noise distribution chi. In matrix notation:
b = A s + e mod q
The Search-LWE problem requires the algorithm to recover the exact secret vector s given the public matrix A โ โคqm ร n and the noisy vector b โ โคqm.
2. Decision-LWE
The Decision-LWE problem asks an algorithm to distinguish between two probability distributions over โคqn ร โคq:
- Distribution DLWE: Pairs of the form (a, โฉa, sโช + e mod q).
- Distribution DUniform: Pairs (a, u) drawn uniformly at random from โคqn ร โคq.
Regev proved that Search-LWE and Decision-LWE are computationally equivalent through polynomial-time search-to-decision reductions: any algorithm capable of distinguishing LWE samples from uniform noise can be employed as a subroutine to recover the secret vector s bit by bit.
Quantum and Classical Worst-Case Reductions
The theoretical robustness of LWE stems from Regev's celebrated Worst-Case Quantum Reduction. Regev proved that for any modulus q and Gaussian error parameter alpha ยท q > 2โn:
If there exists an efficient polynomial-time algorithm (classical or quantum) that solves Decision-LWE or Search-LWE on average, then there exists an efficient quantum algorithm that solves the Shortest Independent Vectors Problem (SIVP) and the approximation variant of the Shortest Vector Problem (GapSVP) on any arbitrary n-dimensional lattice in the worst case to within an approximation factor of:
gamma = O(n / alpha)
In 2009, Chris Peikert formulated the first purely classical reduction from GapSVP to LWE, confirming that LWE's hardness does not strictly depend upon quantum mechanical arguments.
Algebraic Generalizations: Ring-LWE and Module-LWE
While standard LWE provides unassailable theoretical security, practical public-key implementations suffer from large key sizes: transmitting the random matrix A โ โคqm ร n requires O(n2 log q) storage bits. To optimize communication throughput, cryptographers developed structured algebraic generalizations:
Ring-LWE
Introduced in 2010 by Vadim Lyubashevsky, Chris Peikert, and Oded Regev, Ring-LWE replaces integer vectors with elements of a polynomial quotient ring:
Rq = โคq[x] / (xn + 1)
where n is a power of two. The equation becomes b(x) = a(x) ยท s(x) + e(x). Because multiplication in Rq corresponds to cyclic convolution, a single polynomial represents an entire circulant matrix, reducing public key and ciphertext sizes from O(n2) to O(n).
Module-LWE
Introduced by Adeline Langlois and Damien Stehlรฉ in 2015, Module-LWE generalizes Ring-LWE by considering vectors and matrices of polynomials over Rq. Module-LWE strikes an optimal engineering compromise:
- Unlike Ring-LWE, which fixes the algebraic ring degree n, Module-LWE allows designers to scale security up or down simply by altering the matrix dimensions k ร k over a fixed ring, avoiding structural vulnerabilities in specialized number fields.
- Module-LWE forms the mathematical foundation for both ML-KEM (Kyber) and ML-DSA (Dilithium).
Regev's Canonical Encryption Scheme
To illustrate how LWE enables public-key encryption, consider Regev's original cryptosystem:
- Key Generation: Sample secret vector s โ โคqn. Generate public matrix A โ โคqm ร n and error vector e โ chim. Compute public key vector b = A s + e mod q. The public key is (A, b).
- Encryption: To encrypt a single bit m โ {0, 1}, the sender chooses a random binary vector r โ {0, 1}m and computes:
u = AT r mod q v = โฉb, rโช + m ยท floor(q / 2) mod q
The ciphertext is the pair (u, v).
- Decryption: The recipient computes:
v โ โฉu, sโช = (โฉA s + e, rโช + m ยท floor(q / 2)) โ โฉAT r, sโช = โฉe, rโช + m ยท floor(q / 2) mod q
Because the coordinates of e and r are small, the noise term |โฉe, rโช| is much smaller than q / 4. If the result is closer to floor(q / 2) than to 0, the bit is decoded as 1; otherwise, it is decoded as 0.
Comparison of LWE Variants
| Formulation | Mathematical Domain | Public Key Size | Hardness Reduction | Primary Application |
|---|---|---|---|---|
| Standard LWE | Integers modulo q (โคq) | Large (O(n2)) | Worst-case general lattices | Fully Homomorphic Encryption (TFHE) |
| Ring-LWE | Polynomial Ring โคq[x]/(xn+1) | Compact (O(n)) | Worst-case ideal lattices | Homomorphic Encryption (CKKS, BGV) |
| Module-LWE | Modules over Polynomial Rings (Rq)k | Highly flexible (O(k2 n)) | Worst-case module lattices | NIST Standards: ML-KEM, ML-DSA |
References
- Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 1-40.
- Lyubashevsky, V., Peikert, C., & Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6), 1-35.
- Peikert, C. (2009). Public-key cryptosystems from the worst-case shortest vector problem. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 333-342.
- Langlois, A., & Stehlรฉ, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565-599.