Wikipedia / Learning with errors
Wikipedia / Learning with errors
In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. 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. In more technical terms, it refers to the computational problem over a finite ring some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.
denote the ring of integers modulo-vectors, or some close approximation thereof, with high probability.
The LWE problem was introduced by Oded Regev in 2005 (who won the 2018 Gödel Prize for this work); it is a generalization of the parity learning problem. Regev showed that the LWE problem is as hard to solve as several worst-case lattice problems. Subsequently, the LWE problem has been used as a hardness assumption to create public-key cryptosystems, such as the ring learning with errors key exchange by Peikert.
Definition
the additive group on reals modulo one obtained as follows.
,
,
, the division is done in the field of reals.
.
The learning with errors problem.
the one-dimensional Gaussian
Decision version
The LWE problem described above is the search version of the problem. In the decision version (DLWE (practically, some discretized version of it). Regev showed that the decision and search.
Solving decision assuming search
, but if the samples are uniformly random, these quantities will be distributed uniformly as well.
Solving search assuming decision
. Send the transformed samples to the decision solver.
and use the solver to see which one is correct.
coordinate.
Peikert, and then use the Chinese remainder theorem.
Average case hardness
Regev showed the random self-reducibility of the LWE and DLWE.
, DLWE was easy.
will successfully distinguish the samples.
can exist, meaning LWE and DLWE are (up to a polynomial factor) as hard in the average case as they are in the worst case.
Hardness results
Regev's result
For a n, let smoothing parameter.
The discrete Gaussian sampling problem.
Regev then shows that there exists an efficient quantum algorithm.
Peikert's result
Peikert proves that there is a probabilistic polynomial time reduction from the \operatorname{GapSVP}_{\zeta,\gamma}.
Use in cryptography
The LWE problem serves as a versatile problem used in construction of several cryptosystems. In 2005, Regev showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems). In 2009, Peikert proved a similar result assuming only the classical hardness of the related problem \mathrm{GapSVP}_{\zeta,\gamma}. 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.
Public-key cryptosystem
Regev proposed a public-key cryptosystem based on the hardness of the LWE. The setting of the parameters used in proofs of correctness and security is
, usually a prime number.
.
The cryptosystem is then defined by:
Private key chosen uniformly at random.
Public key
Encryption as
Decryption otherwise.
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
CCA-secure cryptosystem
Peikert proposed a system that is secure even against any chosen-ciphertext attack.
Key exchange
The idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper 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 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 selected for Google's post-quantum experiment, uses Peikert's scheme with variation in the error distribution.
Ring learning with errors signature (RLWE-SIG)
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.