Other meanings of Learning with errors
Cryptography
Learning with errors (LWE) is a computational problem in cryptography that asks to recover a secret vector from noisy linear equations. It is the foundation of many post-quantum cryptographic schemes, including the NIST-selected Kyber and Dilithium, because it is believed to be hard even for quantum computers. The problem was introduced by Oded Regev in 2005, who also proved that it is as hard as worst-case lattice problems, giving it strong theoretical security guarantees. LWE has become a central building block for encryption, key exchange, digital signatures, and fully homomorphic encryption.
The LWE problem is defined over a finite field, typically integers modulo q. Given a matrix A and a vector b = A·s + e, where s is a secret vector and e is a vector of small errors drawn from a distribution (often a discrete Gaussian), the goal is to recover s. The decisional variant asks to distinguish such pairs from uniformly random ones. Regev's original paper established a quantum reduction from worst-case lattice problems, such as GapSVP and SIVP, to LWE, showing that solving LWE is at least as hard as approximating these lattice problems within polynomial factors. This reduction is a cornerstone of its cryptographic credibility.
LWE underpins a wide range of cryptographic primitives. Public-key encryption schemes like Regev's original construction and the NIST-standardized Kyber (now ML-KEM) rely on the hardness of LWE or its ring variant (Ring-LWE). Digital signatures such as Dilithium (ML-DSA) use LWE in the Fiat-Shamir framework. Fully homomorphic encryption (FHE), first realized by Gentry, often uses LWE-based schemes like BGV and BFV, enabling computation on encrypted data. LWE also enables advanced protocols like oblivious transfer, private information retrieval, and secure multi-party computation. Its versatility stems from the ability to add errors and the algebraic structure that supports homomorphic operations.
To improve efficiency, several variants have been introduced. Ring-LWE and Module-LWE (MLWE) replace vectors with elements of polynomial rings or modules, reducing key sizes and speeding up operations. These variants are used in Kyber and Dilithium. Other variants include LWE over the integers, binary LWE, and sparse LWE, each with different security and performance trade-offs. The choice of error distribution and modulus affects both security and efficiency; for instance, small moduli like powers of two allow fast arithmetic but may require careful analysis. Researchers have also studied the hardness of LWE with small secrets, which is relevant for certain attacks and parameter selection.
Beyond the mainstream, LWE has surprising connections. It is equivalent to the problem of decoding random linear codes, linking it to coding theory. The hardness of LWE is also related to the learning parity with noise (LPN) problem, which is a special case with modulus 2. In 2016, Peikert showed that LWE is as hard as worst-case lattice problems even with a quantum reduction, but classical reductions remain an open question. LWE has also been used in obfuscation candidates and in constructing pseudorandom functions. A notable edge case is the 'noise flooding' technique, where errors are made large to hide structure, but this can reduce efficiency. Additionally, the 'LWE with side information' model considers attackers who have partial knowledge of the secret, leading to refined security analyses.
LWE's hardness is based on worst-case lattice problems, making it a conservative but robust assumption for post-quantum security.
Help improve the encyclopedia. Reports go straight to the site manager.