Oded Regev
Skip Abstract Section
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 Õ(n2) and encrypting a message increases its size by a factor of Õ(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).
- Aharonov, D. and Regev, O. 2005. Lattice problems in NP intersect coNP. J. ACM 52, 5, 749--765. (Preliminary version in FOCS'04.) Google Scholar
Digital Library
- 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.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Babai, L. 1986. On Lovasz' lattice reduction and the nearest lattice point problem. Combinatorica 6, 1, 1--13. Google ScholarDigital Library
- Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 4, 625--635.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Cash, D., Peikert, C., and Sahai, A. 2009. Efficient circular-secure encryption from hard learning problems. Submitted.Google Scholar
- 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.)Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Grover, L., and Rudolph, T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. In quant-ph/0208112, http://xxx.lanl.gov.Google Scholar
- 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. Google ScholarDigital Library
- Katz, J., and Lindell, Y. 2008. Introduction to modern cryptography. Chapman&Hall/CRC Cryptography and Network Security. Chapman&Hall/CRC, Boca Raton, FL. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 4, 515--534.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Lyubashevsky, V., and Micciancio, D. 2009. On bounded distance decoding, unique shortest vectors, and the minimum distance problem. Manuscript.Google Scholar
- 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.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Micciancio, D., and Regev, O. 2007. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37, 1, 267--302. Google ScholarDigital Library
- 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.Google Scholar
- Nielsen, M. A., and Chuang, I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, MA. Google ScholarDigital Library
- Peikert, C. 2008. Limits on the hardness of lattice problems in l<sub>p</sub> norms. Comput. Complexity 17, 2, 300--351. (Preliminary version in CCC'07.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Regev, O. 2004. New lattice based cryptographic constructions. J. ACM 51, 6, 899--942. (Preliminary version in STOC'03.) Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Schnorr, C.-P. 1987. A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 2-3, 201--224.Google ScholarCross Ref
Index Terms
- On lattices, learning with errors, random linear codes, and cryptography
Recommendations
New lattice-based cryptographic constructions
We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic ...
On lattices, learning with errors, random linear codes, and cryptography
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingOur 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 ...
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 ...
Comments