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

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²) and encrypting a message increases its size by a factor of Õ(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: Aharonov, D. and Regev, O. 2005. Lattice problems in NP intersect coNP. J. ACM 52, 5, 749--765. (Preliminary version in FOCS'04.)
• 2: Ajtai, M. 2004. Generating hard instances of lattice problems. In Complexity of Computations and Proofs. Quad. Mat., vol. 13. Dept. Math., Seconda Univ. Napoli, Caserta, 1--32. (Preliminary version in STOC 1996.)
• 3: Ajtai, M. 2005. Representing hard lattices with O(n log n) bits. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 94--103.
• 4: Ajtai, M., and Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 284--293.
• 5: Ajtai, M., Kumar, R., and Sivakumar, D. 2001. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 601--610.
• 6: Akavia, A., Goldwasser, S., and Vaikuntanathan, V. 2009. Simultaneous hardcore bits and cryptography against memory attacks. In Proceedings of the 6th IACR Theory of Cryptography Conference (TCC). Springer-Verlag, Berlin, Germany, 474--495.
• 7: Alekhnovich, M. 2003. More on average case vs approximation complexity. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 298--307.
• 8: Babai, L. 1986. On Lovasz' lattice reduction and the nearest lattice point problem. Combinatorica 6, 1, 1--13.
• 9: Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 4, 625--635.
• 10: Blum, A., Furst, M., Kearns, M., and Lipton, R. J. 1994. Cryptographic primitives based on hard learning problems. In Advances in cryptology—CRYPTO '93. Lecture Notes in Computer Science, vol. 773. Springer-Verlag, Berlin, Germany, 278--291.
• 11: Blum, A., Kalai, A., and Wasserman, H. 2003. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50, 4, 506--519.
• 12: Cai, J.-Y., and Nerurkar, A. 1997. An improved worst-case to average-case connection for lattice problems. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 468--477.
• 13: Cash, D., Peikert, C., and Sahai, A. 2009. Efficient circular-secure encryption from hard learning problems. Submitted.
• 14: Ebeling, W. 2002. Lattices and Codes, revised ed. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, Germany. (A course partially based on lectures by F. Hirzebruch.)
• 15: Feige, U. 2002. Relations between average case complexity and approximation complexity. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 534--543.
• 16: Gentry, C., Peikert, C., and Vaikuntanathan, V. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC). ACM, New York, 197--206.
• 17: Goldreich, O., Micciancio, D., Safra, S., and Seifert, J.-P. 1999. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Proc. Lett. 71, 2, 55--61.
• 18: Grover, L., and Rudolph, T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. In quant-ph/0208112, http://xxx.lanl.gov.
• 19: Impagliazzo, R., and Zuckerman, D. 1989. How to recycle random bits. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 248--253.
• 20: Katz, J., and Lindell, Y. 2008. Introduction to modern cryptography. Chapman & Hall/CRC Cryptography and Network Security. Chapman & Hall/CRC, Boca Raton, FL.
• 21: Kawachi, A., Tanaka, K., and Xagawa, K. 2007. Multi-bit cryptosystems based on lattice problems. In Public Key Cryptography -- PKC 2007. Lecture Notes in Comput. Sci., vol. 4450. Springer, Berlin, 315--329.
• 22: Klivans, A. R., and Sherstov, A. A. 2009. Cryptographic hardness for learning intersections of halfspaces. J. Comput. System Sci. 75, 1, 2--12. (Preliminary version in FOCS'06.)
• 23: Kumar, R., and Sivakumar, D. 2001. On polynomial approximation to the shortest lattice vector length. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 126--127.
• 24: Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 4, 515--534.
• 25: Liu, Y.-K., Lyubashevsky, V., and Micciancio, D. 2006. On bounded distance decoding for general lattices. In International Workshop on Randomization and Computation - Proceedings of RANDOM 2006. Lecture Notes in Computer Science, vol. 4110. Springer-Verlag, Berlin, Germany, 450--461.
• 26: Lyubashevsky, V., and Micciancio, D. 2009. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Manuscript.
• 27: Micciancio, D. 2004. Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM Journal on Computing 34, 1, 118--169. (Preliminary version in STOC 2002.)
• 28: Micciancio, D., and Goldwasser, S. 2002. Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston, MA.
• 29: Micciancio, D., and Regev, O. 2007. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37, 1, 267--302.
• 30: Moore, C., Russell, A., and Vazirani, U. 2007. A classical one-way function to confound quantum adversaries. In quant-ph/0701115, http://xxx.lanl.gov.
• 31: Nielsen, M. A., and Chuang, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, MA.
• 32: Peikert, C. 2008. Limits on the hardness of lattice problems in l_p norms. Comput. Complexity 17, 2, 300--351. (Preliminary version in CCC'07.)
• 33: Peikert, C. 2009. Public-key cryptosystems from the worst-case shortest vector problem. In Proc. 41st ACM Symp. on Theory of Computing (STOC). ACM, New York, 333--342.
• 34: Peikert, C., Vaikuntanathan, V., and Waters, B. 2008. A framework for efficient and composable oblivious transfer. In Advances in cryptology—CRYPTO '08. Lecture Notes in Computer Science, vol. 5157. Springer-Verlag, Berlin, Germany, 554--571.
• 35: Peikert, C., and Waters, B. 2008. Lossy trapdoor functions and their applications. In Proceedings of the 40th ACM Symposium on Theory of Computing (STOC). ACM, New York, 187--196.
• 36: Regev, O. 2004. New lattice based cryptographic constructions. J. ACM 51, 6, 899--942. (Preliminary version in STOC'03.)
• 37: Regev, O. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC). ACM, New York, 84--93.
• 38: Schnorr, C.-P. 1987. A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 2-3, 201--224.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Algorithms, Theory

Keywords:
Lattice, average-case hardness, cryptography, public key encryption, quantum computation