In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms.
[1] It is based on the idea of representing secret information as a set of equations with errors.
In other words, LWE is a way to hide the value of a secret by introducing noise to it.
[2] In more technical terms, it refers to the computational problem of inferring a linear
The LWE problem is conjectured to be hard to solve,[1] and thus to be useful in cryptography.
Subsequently, the LWE problem has been used as a hardness assumption to create public-key cryptosystems,[3][4] such as the ring learning with errors key exchange by Peikert.
In the decision version (DLWE), the goal is to distinguish between noisy inner products and uniformly random samples from
For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover
So, given a polynomial-time solver for the decision problem that errs with very small probability, since
[3] Peikert[4] showed that this reduction, with a small modification, works for any
Regev[3] showed the random self-reducibility of the LWE and DLWE problems for arbitrary
, with high probability, if we choose a polynomial number of values for
The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of
Regev then shows that there exists an efficient quantum algorithm for
Peikert proves[4] that there is a probabilistic polynomial time reduction from the
In 2009, Peikert[4] proved a similar result assuming only the classical hardness of the related problem
The disadvantage of Peikert's result is that it bases itself on a non-standard version of an easier (when compared to SIVP) problem GapSVP.
Regev[3] proposed a public-key cryptosystem based on the hardness of the LWE problem.
The cryptosystem as well as the proof of security and correctness are completely classical.
The setting of the parameters used in proofs of correctness and security is The cryptosystem is then defined by: The proof of correctness follows from choice of parameters and some probability analysis.
The proof of security is by reduction to the decision version of LWE: an algorithm for distinguishing between encryptions (with above parameters) of
Peikert[4] proposed a system that is secure even against any chosen-ciphertext attack.
The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security.
The paper[8] appeared in 2012 after a provisional patent application was filed in 2012.
The security of the protocol is proven based on the hardness of solving the LWE problem.
In 2014, Peikert presented a key-transport scheme[9] following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used.
The "new hope" implementation[10] selected for Google's post-quantum experiment,[11] uses Peikert's scheme with variation in the error distribution.
Main article: Ring learning with errors signature A RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital signature in 2011 by Lyubashevsky.
The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems."
These papers laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.