Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

ABSTRACT

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

REFERENCES

• 1: Miklós Ajtai, Generating Hard Instances of the Short Basis Problem, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.1-9, July 11-15, 1999
• 2: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 3: 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]
• 4: M. Ajtai and C. Dwork. The first and fourth public-key cryptosystems with worst-case/average-case equivalence. Electronic Colloquium on Computational Complexity (ECCC), 14(97), 2007.
• 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: Adi Akavia , Shafi Goldwasser , Vinod Vaikuntanathan, Simultaneous Hardcore Bits and Cryptography against Memory Attacks, Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, p.474-495, March 15-17, 2009, San Francisco, CA [doi>10.1007/978-3-642-00457-5_28]
• 7: J. Alwen and C. Peikert. Generating shorter bases for hard random lattices. In STACS, pages 75--86, 2009.
• 8: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 9: Jin-Yi Cai, A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Theoretical Computer Science, v.207 n.1, p.105-116, Oct. 28, 1998 [doi>10.1016/S0304-3975(98)00058-9]
• 10: D. Cash, C. Peikert, and A. Sahai. Efficient circular-secure encryption from hard learning problems. Manuscript, 2009.
• 11: N. Gama and P. Q. Nguyen. Predicting lattice reduction. In EUROCRYPT, pages 31--51, 2008.
• 12: Craig Gentry , Chris Peikert , Vinod Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374407]
• 13: Oded Goldreich , Shafi Goldwasser, On the limits of nonapproximability of lattice problems, Journal of Computer and System Sciences, v.60 n.3, p.540-563, June 2000 [doi>10.1006/jcss.1999.1686]
• 14: Oded Goldreich , Shafi Goldwasser , Shai Halevi, Public-Key Cryptosystems from Lattice Reduction Problems, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.112-131, August 17-21, 1997
• 15: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 16: S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270--299, 1984.
• 17: R. Impagliazzo, A personal view of average-case complexity, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.134, June 19-22, 1995
• 18: A. Kawachi, K. Tanaka, and K. Xagawa. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography, pages 315--329, 2007.
• 19: Adam R. Klivans , Alexander A. Sherstov, Cryptographic Hardness for Learning Intersections of Halfspaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.553-562, October 21-24, 2006 [doi>10.1109/FOCS.2006.24]
• 20: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515--534, December 1982.
• 21: V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Manuscript, 2009.
• 22: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, SIAM Journal on Computing, v.37 n.1, p.267-302, April 2007 [doi>10.1137/S0097539705447360]
• 23: Chris Peikert, Limits on the Hardness of Lattice Problems in lp Norms, Computational Complexity, v.17 n.2, p.300-351, May 2008 [doi>10.1007/s00037-008-0251-3]
• 24: C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. Electronic Colloquium on Computational Complexity (ECCC), 15(100), 2008.
• 25: Chris Peikert , Vinod Vaikuntanathan , Brent Waters, A Framework for Efficient and Composable Oblivious Transfer, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_31]
• 26: Chris Peikert , Brent Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374406]
• 27: O. Regev. Lecture notes on lattices in computer science, 2004. Available at http://www.cs.tau.ac.il/odedr/teaching/lattices_fall_2004/index.html, last accessed 28 Feb 2008.
• 28: Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
• 29: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 30: O. Regev, December 2008. Personal communication.
• 31: Alon Rosen , Gil Segev, Chosen-Ciphertext Security via Correlated Products, Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, p.419-436, March 15-17, 2009, San Francisco, CA [doi>10.1007/978-3-642-00457-5_25]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory

Keywords:
cryptography, lattices