Public-key encryption, signatures and homomorphic encryption whose security rests on Learning With Errors, the basis of the NIST post-quantum standards ML-KEM and ML-DSA.
ML-KEM (FIPS 203) and ML-DSA (FIPS 204) are built on module-LWE and are being deployed to replace RSA and elliptic-curve key exchange and signatures; fully homomorphic encryption schemes rest on the same assumption.
Secret codes built on a puzzle about noisy equations, believed hard even for quantum computers.
1Quantum computers threaten today's locks
2Noise hides a secret in equations
3Breaking it would solve hard lattice puzzles
4Used to build encryption and signatures
5Now part of official standards
Lattices. A lattice is the set of all integer combinations of n linearly independent vectors in Rn; picture a regular grid of points, possibly slanted. The same lattice has many different bases, some short and nearly perpendicular (good), some long and skewed (bad). Natural problems: the Shortest Vector Problem (SVP) asks for the shortest nonzero lattice vector; its approximation versions allow a slack factor γ. For slack factors polynomial in n, no polynomial-time algorithm is known, classical or quantum. The best known algorithms take exponential time in .
Go deeper
The full technical text.
Lattices and the LWE problem
A lattice is the set of integer combinations of n linearly independent vectors in Rn. Natural computational problems on lattices include the Shortest Vector Problem (SVP: find a shortest nonzero vector), its approximation version GapSVP, and the Shortest Independent Vectors Problem (SIVP). For approximation factors that are polynomial in none of them has a known polynomial-time algorithm, classical or quantum; the best algorithms take time exponential in .
Gupte, Ragavan and Zhandry argued that the algorithm cannot extract the least-significant bit of the DCP secret and proved a broader no-go result for algorithms following Regev's template, with Lean 4 code; Simon revised his preprint on 7 October in response. Unresolved.
Simon (AWS) claimed a polynomial-time quantum algorithm for the dihedral coset problem, which via known reductions would give quantum approximate SVP within about √n·polylog n and attacks on LWE in a corresponding regime; unrefereed and contested.
Learning With Errors. Regev (2005) introduced LWE. Fix a dimension n, a modulus q and a noise distribution (typically a discrete Gaussian). Choose a secret vector s modulo q. An instance is a list of pairs (ai,bi) where ai is a random vector and bi=⟨ai,s⟩+e, with a small random error ei. Search-LWE asks for s. Decision-LWE asks to tell such samples apart from uniformly random ones. With no error, Gaussian elimination recovers s. With error, no efficient algorithm is known.
Why it is trusted. Regev proved that solving LWE on random instances would give a quantum algorithm for worst-case lattice problems (approximate SVP and a cousin called SIVP). Later work gave classical reductions under extra conditions on parameters. So an attack on LWE would be an algorithmic breakthrough for lattice problems that have been studied for a long time. This worst-case to average-case link is unusual among assumptions used in cryptography.
Structured variants. Plain LWE needs large keys. Variants with extra algebraic structure (Ring-LWE and Module-LWE) shrink keys and speed up operations, at the price of relying on structured lattices that are less studied.
Deployed standards. NIST's August 2024 post-quantum standards include ML-KEM (key exchange, FIPS 203) and ML-DSA (signatures, FIPS 204), both built on module-lattice assumptions. Concrete parameters are chosen from the estimated cost of the best known attacks, which are lattice-reduction and sieving algorithms with exponential running time (roughly 20.29n classically; quantum versions shave the exponent slightly).
Beyond encryption. LWE also supports fully homomorphic encryption, which lets a server compute on data it cannot read.
Open questions include whether a polynomial-time quantum algorithm for LWE exists (Chen's April 2024 claim was withdrawn after a bug was found; Simon's August 2026 unrefereed claim for the related dihedral coset problem is disputed), whether the structured variants are weaker than plain LWE, and how safe the concrete parameter choices are.
γ
n
n
Learning With Errors (LWE), introduced by Regev in 2005, is the average-case problem used in cryptography. Fix a dimension n, a modulus q and an error distribution χ (typically a discrete Gaussian of width αq). A secret s∈Zqn is chosen uniformly. An instance is a list of samples (ai,bi=⟨a with ai uniform and ei←χ. Search-LWE asks for s; decision-LWE asks to distinguish the samples from uniform ones. Without the noise ei the secret is recovered by Gaussian elimination; with it, no efficient algorithm is known.
Why it is trusted
Regev showed (STOC 2005; J. ACM 2009) that for suitable parameters, solving LWE on random instances would give a quantum algorithm for worst-case GapSVPγ and SIVP with γ=O~(n/α). Classical reductions exist under further restrictions on parameters (Peikert 2009; Brakerski, Langlois, Peikert, Regev and Stehlé 2013). So an efficient attack on LWE would be an algorithmic breakthrough for lattice problems that have been studied for decades. This worst-case-to-average-case link is unusual among cryptographic assumptions.
Structured variants and deployed schemes
Plain LWE needs public keys of size quadratic in n. Ring-LWE (Lyubashevsky, Peikert and Regev) and module-LWE add algebraic structure over polynomial rings, shrinking keys and speeding up arithmetic, at the price of a hardness argument that now refers to ideal or module lattices. The NIST standards published on 13 August 2024 use module-LWE: ML-KEM (FIPS 203, from CRYSTALS-Kyber) has parameter sets ML-KEM-512, ML-KEM-768 and ML-KEM-1024, and ML-DSA (FIPS 204, from CRYSTALS-Dilithium) is the signature standard. A third lattice standard, FN-DSA (FIPS 206, based on Falcon), had been announced but was not listed among NIST's final FIPS as of October 2026. In March 2025 NIST also selected HQC, a code-based key-encapsulation mechanism, as a non-lattice backup to ML-KEM; NIST presented its planned standard (FIPS 207, HQC-KEM) in September 2025, and no final version had been published as of October 2026. LWE also underlies fully homomorphic encryption, which computes on encrypted data.
How security is estimated
Concrete parameters are chosen from the cost of the best known attacks: lattice basis reduction (BKZ) with a sieving or enumeration subroutine, hybrid and dual attacks, and combinatorial algorithms such as BKW and Arora–Ge for special parameter ranges. Estimates of these costs are refined every few years, and the security margins of the standardised parameter sets rest on them. Heuristic sieving solves SVP in dimension n in time about 20.292n classically (Becker, Ducas, Gama and Laarhoven, 2016) and about 20.257n with quantum random walks (Chailloux and Loyer, 2021), so known quantum speedups only shrink the constant in the exponent.
Quantum attacks: what has and has not happened
The central open question is whether quantum computers can do much better. The natural route is through the dihedral coset problem (DCP): Regev showed in 2002 that an efficient quantum algorithm for DCP (tolerating some failure probability) would solve the unique shortest vector problem for polynomial factors, and Kuperberg's algorithm solves DCP in subexponential time 2O(logN), where N is the order of the cyclic group. In April 2024 Yilei Chen posted a claimed polynomial-time quantum algorithm for LWE with polynomial modulus-to-noise ratio; within days the author reported a bug in the analysis that he could not repair, and withdrew the main claim. In June 2025 Bai, Jangir, Kirshanova, Ngo and Youmans (CRYPTO 2025) gave a quasi-polynomial quantum algorithm for an extrapolated variant of DCP over power-of-two moduli; it needs quasi-polynomially many samples, and the authors state that it therefore does not affect LWE with standard parameters. In August 2026 Daniel Simon posted an unrefereed preprint claiming a polynomial-time quantum algorithm for DCP; a preprint arguing that the algorithm cannot work followed twelve days later, and the dispute is unresolved (see the problem entry).
What to take away
LWE is the best-studied assumption among the post-quantum options, but it is an assumption: there is no proof that lattice problems are hard, and the standards were chosen with the explicit expectation that cryptanalysis will continue.
Puts lattices in context with the other candidate approaches.
Hair and Sahai obtained deterministic hardness within 2^((log n)^(1−o(1))) for all finite ℓp, including ℓ2, under the assumption NP ⊄ ∩_δ DTIME(exp(n^δ)) (preprint, unrefereed).
Bai et al. solved the extrapolated dihedral coset problem for power-of-two moduli in quasi-polynomial time; the authors state it does not affect standard LWE.
After a fourth evaluation round NIST selected HQC for standardisation; it would be the second KEM standard after ML-KEM and does not depend on lattices.
Claimed quantum LWE algorithm, withdrawn within days
Chen's ePrint 2024/555 claimed a polynomial-time quantum algorithm for LWE with polynomial modulus-to-noise ratio. On 18 April the author reported a bug in Step 9 (found by Hongxun Wu and, independently, Thomas Vidick) and withdrew the main claim.
Regev's STOC 2005 paper defined Learning With Errors and gave the quantum reduction from worst-case lattice problems; the journal version appeared in J. ACM in 2009.
What to read before Lattice-based cryptography (LWE) (left), and what builds on it: entries that depend on it and the open problems it hosts (right). Every box links to its page.