Oded Regev
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 Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).
- D. Aharonov and O. Regev. Lattice problems in NP intersect coNP. In Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 362--371, 2004. Google Scholar
Digital Library
- M. Ajtai. Generating hard instances of lattice problems. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, 1996.Google Scholar
- M. Ajtai. Representing hard lattices with O(n log n) bits. In Proc. 37th Annual ACM Symp. on Theory of Computing (STOC), 2005. Google ScholarDigital Library
- M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In Proc. 29th Annual ACM Symp. on Theory of Computing (STOC), pages 284--293, 1997. Google ScholarDigital Library
- M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd ACM Symp. on Theory of Computing, pages 601--610, 2001. Google ScholarDigital Library
- M. Alekhnovich. More on average case vs approximation complexity. In Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 298--307, 2003. Google ScholarDigital Library
- A. Blum, M. Furst, M. Kearns, and R. J. Lipton. Cryptographic primitives based on hard learning problems. In Advances in cryptology---CRYPTO '93 (Santa Barbara, CA, 1993), volume 773 of Lecture Notes in Comput. Sci., pages 278--291. Springer, Berlin, 1994. Google ScholarDigital Library
- A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506--519, 2003. Google ScholarDigital Library
- J.-Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In Proc. 38th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pages 468--477, 1997. Google ScholarDigital Library
- W. Ebeling. Lattices and codes. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, revised edition, 2002. A course partially based on lectures by F. Hirzebruch. Google ScholarDigital Library
- U. Feige. Relations between average case complexity and approximation complexity. In Proc. 34th Annual ACM Symp. on Theory of Computing (STOC), pages 534--543, 2002. Google ScholarDigital Library
- R. Kumar and D. Sivakumar. On polynomial approximation to the shortest lattice vector length. In Proc. 12th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 126--127, 2001. Google ScholarDigital Library
- D. Micciancio. Improved cryptographic hash functions with worst-case/average-case connection. In Proc. 34th Annual ACM Symp. on Theory of Computing (STOC), pages 609--618, 2002. Google ScholarDigital Library
- D. Micciancio. Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM Journal on Computing, 2004. Accepted for publication. Available from author's web page at URL http://www.cse.ucsd.edu/users/daniele. Google ScholarDigital Library
- D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, Mar. 2002. Google ScholarDigital Library
- D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. In Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS), 2004. Google ScholarDigital Library
- O. Regev. New lattice based cryptographic constructions. In Proc. 35th Annual ACM Symp. on Theory of Computing (STOC), pages 407--416, 2003. Google ScholarDigital Library
Index Terms
- On lattices, learning with errors, random linear codes, and cryptography
Recommendations
On Ideal Lattices and Learning with Errors over Rings
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent ...
On lattices, learning with errors, random linear codes, and cryptography
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 ...
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 ...
Comments