Chris Peikert
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.
- M. Ajtai. Generating hard instances of the short basis problem. In ICALP, pages 1--9, 1999. Google Scholar
Digital Library
- M. Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1--32, 2004. Preliminary version in STOC 1996. Google ScholarDigital Library
- M. Ajtai and C. Dwork. A public--key cryptosystem with worst-case/average-case equivalence. In STOC, pages 284--293, 1997. Google ScholarDigital Library
- 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.Google Scholar
- M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In STOC, pages 601--610, 2001. Google ScholarDigital Library
- A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, pages 474--495, 2009. Google ScholarDigital Library
- J. Alwen and C. Peikert. Generating shorter bases for hard random lattices. In STACS, pages 75--86, 2009.Google Scholar
- L. Babai. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1--13, 1986. Google ScholarDigital Library
- J.-Y. Cai. A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theor. Comput. Sci., 207(1):105--116, 1998. Google ScholarDigital Library
- D. Cash, C. Peikert, and A. Sahai. Efficient circular-secure encryption from hard learning problems. Manuscript, 2009.Google Scholar
- N. Gama and P. Q. Nguyen. Predicting lattice reduction. In EUROCRYPT, pages 31--51, 2008. Google ScholarDigital Library
- C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197--206, 2008. Google ScholarDigital Library
- O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci., 60(3):540--563, 2000. Google ScholarDigital Library
- O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO, pages 112--131, 1997. Google ScholarDigital Library
- O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In STOC, pages 25--32, 1989. Google ScholarDigital Library
- S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270--299, 1984.Google ScholarCross Ref
- R. Impagliazzo. A personal view of average-case complexity. In Structure in Complexity Theory Conference, pages 134--147, 1995. Google ScholarDigital Library
- A. Kawachi, K. Tanaka, and K. Xagawa. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography, pages 315--329, 2007. Google ScholarDigital Library
- A. R. Klivans and A. A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. In FOCS, pages 553--562, 2006. Google ScholarDigital Library
- A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515--534, December 1982.Google ScholarCross Ref
- V. Lyubashevsky and D. Micciancio. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Manuscript, 2009.Google Scholar
- D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267--302, 2007. Preliminary version in FOCS 2004. Google ScholarDigital Library
- C. Peikert. Limits on the hardness of lattice problems in lp norms. Computational Complexity, 17(2):300--351, May 2008. Preliminary version in CCC 2007. Google ScholarDigital Library
- C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. Electronic Colloquium on Computational Complexity (ECCC), 15(100), 2008.Google Scholar
- C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, pages 554--571, 2008. Google ScholarDigital Library
- C. Peikert and B. Waters. Lossy trapdoor functions and their applications. In STOC, pages 187--196, 2008. Google ScholarDigital Library
- 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.Google Scholar
- O. Regev. New lattice-based cryptographic constructions. J. ACM, 51(6):899--942, 2004. Google ScholarDigital Library
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84--93, 2005. Google ScholarDigital Library
- O. Regev, December 2008. Personal communication.Google Scholar
- A. Rosen and G. Segev. Chosen-ciphertext security via correlated products. In TCC, pages 419--436, 2009. Google ScholarDigital Library
Index Terms
- Public-key cryptosystems from the worst-case shortest vector problem: extended abstract
Recommendations
Securely combining public-key cryptosystems
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications SecurityIt is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an RSA key pair should be used only for public-key encryption or only for digital signatures, and not for both.In this paper we show ...
Public-Key encryption from ID-Based encryption without one-time signature
OTM'06: Proceedings of the 2006 international conference on On the Move to Meaningful Internet Systems: AWeSOMe, CAMS, COMINF, IS, KSinBIT, MIOS-CIAO, MONET - Volume Part IDesign a secure public key encryption scheme and its security proof are one of the main interests in cryptography In 2004, Canetti, Halevi and Katz [8] constructed a public key encryption (PKE) from a selective identity-based encryption scheme with a ...
Secure public-key encryption scheme without random oracles
Since the first practical and secure public-key encryption scheme without random oracles proposed by Cramer and Shoup in 1998, Cramer-Shoup's scheme and its variants remained the only practical and secure public-key encryption scheme without random ...
Comments