On lattices, learning with errors, random linear codes, and cryptography

ABSTRACT

Our main result is a reduction from worst-case lattice problems such as SVP 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 SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n²) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n⁴) and Õ(n²), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n²), the size of the public key can be reduced to Õ(n).

REFERENCES

• 1: Dorit Aharonov , Oded Regev, Lattice Problems in NP " coNP, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.362-371, October 17-19, 2004 [doi>10.1109/FOCS.2004.35]
• 2: M. Ajtai. Generating hard instances of lattice problems. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, 1996.
• 3: Miklós Ajtai, Representing hard lattices with O(n log n) bits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060604]
• 4: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 5: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 6: Michael Alekhnovich, More on Average Case vs Approximation Complexity, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.298, October 11-14, 2003
• 7: Avrim Blum , Merrick L. Furst , Michael J. Kearns , Richard J. Lipton, Cryptographic Primitives Based on Hard Learning Problems, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, p.278-291, August 22-26, 1993
• 8: Avrim Blum , Adam Kalai , Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, Journal of the ACM (JACM), v.50 n.4, p.506-519, July 2003 [doi>10.1145/792538.792543]
• 9: Jin-yi Cai , Ajay P. Nerurkar, An Improved Worst-Case to Average-Case Connection for Lattice Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.468, October 19-22, 1997
• 10: Wolfgang Ebeling , Friedrich Hirzebruch, Lattices and Codes: A Course Partially Based on Lectures by F. Hirzebruch, Informatica International, Incorporated, 1994
• 11: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 12: Ravi Kumar , D. Sivakumar, On polynomial approximation to the shortest lattice vector length, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.126-127, January 07-09, 2001, Washington, D.C., United States
• 13: Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509995]
• 14: Daniele Micciancio, Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor, SIAM Journal on Computing, v.34 n.1, p.118-169, 2005 [doi>10.1137/S0097539703433511]
• 15: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 16: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.372-381, October 17-19, 2004 [doi>10.1109/FOCS.2004.72]
• 17: Oded Regev, New lattice based cryptographic constructions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780603]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Security, Theory

Keywords:
computational learning theory, cryptography, lattices, public key encryption, quantum computing, statistical queries