Learning with errors
This article may be too technical for most readers to understand.(October 2018)
Learning with errors (LWE) is the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus be useful in cryptography.
More precisely, the LWE problem is defined as follows. Let denote the ring of integers modulo and let denote the set of -vectors over . There exists a certain unknown linear function , and the input to the LWE problem is a sample of pairs , where and , so that with high probability . Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function , 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.
Denote by the additive group on reals modulo one. Let be a fixed vector. Let be a fixed probability distribution over . Denote by the distribution on obtained as follows.
- Pick a vector from the uniform distribution over ,
- Pick a number from the distribution ,
- Evaluate , where is the standard inner product in , the division is done in the field of reals (or more formally, this "division by " is notation for the group homomorphism mapping to ), and the final addition is in .
- Output the pair .
The learning with errors problem is to find , given access to polynomially many samples of choice from .
For every , denote by the one-dimensional Gaussian with zero mean and variance , that is, the density function is where , and let be the distribution on obtained by considering modulo one. The version of LWE considered in most of the results would be
The LWE problem described above is the search version of the problem. In the decision version (DLWE), the goal is to distinguish between noisy inner products and uniformly random samples from (practically, some discretized version of it). Regev showed that the decision and search versions are equivalent when is a prime bounded by some polynomial in .
Solving decision assuming search
Intuitively, if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision problem to the solver for the search problem. Denote the given samples by . If the solver returns a candidate , for all , calculate . If the samples are from an LWE distribution, then the results of this calculation will be distributed according , but if the samples are uniformly random, these quantities will be distributed uniformly as well.
Solving search assuming decision
For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover one coordinate at a time. To obtain the first coordinate, , make a guess , and do the following. Choose a number uniformly at random. Transform the given samples as follows. Calculate . Send the transformed samples to the decision solver.
If the guess was correct, the transformation takes the distribution to itself, and otherwise, since is prime, it takes it to the uniform distribution. So, given a polynomial-time solver for the decision problem that errs with very small probability, since is bounded by some polynomial in , it only takes polynomial time to guess every possible value for and use the solver to see which one is correct.
After obtaining , we follow an analogous procedure for each other coordinate . Namely, we transform our samples the same way, and transform our samples by calculating , where the is in the coordinate.
Peikert showed that this reduction, with a small modification, works for any that is a product of distinct, small (polynomial in ) primes. The main idea is if , for each , guess and check to see if is congruent to , and then use the Chinese remainder theorem to recover .
Average case hardness
So, suppose there was some set such that , and for distributions , with , DLWE was easy.
Then there would be some distinguisher , who, given samples , could tell whether they were uniformly random or from . If we need to distinguish uniformly random samples from , where is chosen uniformly at random from , we could simply try different values sampled uniformly at random from , calculate and feed these samples to . Since comprises a large fraction of , with high probability, if we choose a polynomial number of values for , we will find one such that , and will successfully distinguish the samples.
Thus, no such 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.
For a n-dimensional lattice , let smoothing parameter denote the smallest such that where is the dual of and is extended to sets by summing over function values at each element in the set. Let denote the discrete Gaussian distribution on of width for a lattice and real . The probability of each is proportional to .
The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of is given by an -dimensional lattice and a number . The goal is to output a sample from . Regev shows that there is a reduction from to for any function .
Regev then shows that there exists an efficient quantum algorithm for given access to an oracle for for integer and such that . This implies the hardness for LWE. Although the proof of this assertion works for any , for creating a cryptosystem, the has to be polynomial in .
Peikert proves that there is a probabilistic polynomial time reduction from the problem in the worst case to solving using samples for parameters , , and .
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 (for as above) and with ). In 2009, Peikert 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 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 system is characterized by and a probability distribution on . The setting of the parameters used in proofs of correctness and security is
- , usually a prime number between and .
- for an arbitrary constant
- for , where is a probability distribution obtained by sampling a normal variable with mean and standard variation and reducing the result modulo .
The cryptosystem is then defined by:
- Private key: Private key is an chosen uniformly at random.
- Public key: Choose vectors uniformly and independently. Choose error offsets independently according to . The public key consists of
- Encryption: The encryption of a bit is done by choosing a random subset of and then defining as
- Decryption: The decryption of is if is closer to than to , and 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: an algorithm for distinguishing between encryptions (with above parameters) of and can be used to distinguish between and the uniform distribution over
This section needs expansion. You can help by adding to it. (December 2009)
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.
- Post-quantum cryptography
- Lattice-based cryptography
- Ring learning with errors key exchange
- Short integer solution (SIS) problem
- Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography". Journal of the ACM. 56 (6): 1–40. doi:10.1145/1568318.1568324. S2CID 207156623.
- Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
- Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333–342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
- Peikert, Chris (2014-10-01). "Lattice Cryptography for the Internet". In Mosca, Michele (ed.). Post-Quantum Cryptography. Lecture Notes in Computer Science. 8772. Springer International Publishing. pp. 197–219. CiteSeerX 10.1.1.800.4743. doi:10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.
- Chris Peikert and Brent Waters, “Lossy trapdoor functions and their applications,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.
- Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.
- Lin, Jintai Ding, Xiang Xie, Xiaodong (2012-01-01). "A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem". Cite journal requires
- Peikert, Chris (2014-01-01). "Lattice Cryptography for the Internet". Cite journal requires
- Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (2015-01-01). "Post-quantum key exchange - a new hope". Cite journal requires
- "Experimenting with Post-Quantum Cryptography". Google Online Security Blog. Retrieved 2017-02-08.