On lattices, learning with errors, random linear codes, and cryptography
Top Cited Papers
- 8 September 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 56 (6), 1-40
- https://doi.org/10.1145/1568318.1568324
Abstract
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ( n 2 ) and encrypting a message increases its size by a factor of Õ( n ) (in previous cryptosystems these values are Õ( n 4 ) and Õ( n 2 ), respectively). In fact, under the assumption that all parties share a random bit string of length Õ( n 2 ), the size of the public key can be reduced to Õ( n ).Keywords
Funding Information
- Sixth Framework Programme (15848)
- Army Research Office (DAAD19-03-1-0082)
This publication has 27 references indexed in Scilit:
- Cryptographic hardness for learning intersections of halfspacesJournal of Computer and System Sciences, 2009
- Worst‐Case to Average‐Case Reductions Based on Gaussian MeasuresSIAM Journal on Computing, 2007
- Lattice problems in NP ∩ coNPJournal of the ACM, 2005
- New lattice-based cryptographic constructionsJournal of the ACM, 2004
- Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection FactorSIAM Journal on Computing, 2004
- Noise-tolerant learning, the parity problem, and the statistical query modelJournal of the ACM, 2003
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectorsInformation Processing Letters, 1999
- New bounds in some transference theorems in the geometry of numbersMathematische Annalen, 1993
- A hierarchy of polynomial time lattice basis reduction algorithmsTheoretical Computer Science, 1987
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982