postquantum.wiki

Learning With Errors (LWE)

GlossaryUpdated July 11, 2026179 words3 sources

Learning With Errors (LWE) is the computational problem of recovering a secret vector from noisy linear equations over a finite field. Given many samples (a, b), where b equals the inner product of a with a hidden secret plus a small random error, finding the secret is believed hard for both classical and quantum computers, which makes LWE the foundation of most lattice-based cryptography.

Why the noise matters

Without the error term, the secret follows immediately from Gaussian elimination. The small errors turn an easy linear-algebra task into one that appears to require solving hard lattice problems. Oded Regev introduced LWE in 2005 and proved a worst-case to average-case reduction: solving random LWE instances is at least as hard as approximating worst-case lattice problems (Regev, JACM 2009).

Structured variants

Plain LWE keys are large, so deployed schemes use algebraically structured versions that shrink keys and speed arithmetic (Peikert, 2015): Ring-LWE and Module-LWE. Module-LWE underlies the standardized ML-KEM KEM, while the Short Integer Solution problem is the dual assumption used for signatures.

Sources

  1. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (Journal of the ACM, 2009)
  2. A Decade of Lattice Cryptography (IACR ePrint Archive, 2015)
  3. FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard (NIST, 2024)

latticelwehardness-assumptionpqc

Cite this entry
"Learning With Errors (LWE)." postquantum.wiki. Updated July 11, 2026. https://postquantum.wiki/lwe@misc{pqwiki-lwe, title = {Learning With Errors (LWE)}, howpublished = {\url{https://postquantum.wiki/lwe}}, year = {2026}, note = {postquantum.wiki, updated 2026-07-11} }

Related entries

Lattice-based cryptography

Lattice-based cryptography builds encryption and signatures on hard lattice problems such as LWE and underpins the NIST standards ML-KEM and ML-DSA.

Foundations

Module Learning With Errors (Module-LWE)

Module-LWE is the structured lattice assumption behind ML-KEM and ML-DSA, tuning algebraic structure by module rank to reach each NIST security level.

Glossary

Ring Learning With Errors (Ring-LWE)

Ring-LWE is the polynomial-ring variant of Learning With Errors, trading extra algebraic structure for the compact keys and fast arithmetic PQ schemes need.

Glossary

ML-KEM (FIPS 203)

ML-KEM is the module-lattice key-encapsulation mechanism of FIPS 203, formerly CRYSTALS-Kyber, and the default post-quantum key establishment method.

Standards

Short Integer Solution (SIS) problem

The Short Integer Solution (SIS) problem seeks a short vector a random matrix maps to zero, the dual of LWE that underlies lattice-based signatures.

Glossary