โ† Wiki Index / Computation & Algorithms / Learning With Errors
๐Ÿ’ป Computation & Algorithms

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

FormulationMathematical DomainPublic Key SizeHardness ReductionPrimary Application
Standard LWEIntegers modulo q (โ„คq)Large (O(n2))Worst-case general latticesFully Homomorphic Encryption (TFHE)
Ring-LWEPolynomial Ring โ„คq[x]/(xn+1)Compact (O(n))Worst-case ideal latticesHomomorphic Encryption (CKKS, BGV)
Module-LWEModules over Polynomial Rings (Rq)kHighly flexible (O(k2 n))Worst-case module latticesNIST Standards: ML-KEM, ML-DSA

References

  1. Regev, O. (2009). On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6), 1-40.
  2. Lyubashevsky, V., Peikert, C., & Regev, O. (2013). On ideal lattices and learning with errors over rings. Journal of the ACM, 60(6), 1-35.
  3. 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.
  4. Langlois, A., & Stehlรฉ, D. (2015). Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3), 565-599.
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision