New lattice-based cryptographic constructions

ABSTRACT

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 constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n^1.5) instead of O(n⁷)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.

REFERENCES

• 1: Ajtai, M. 1996. Generating hard instances of lattice problems. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports.
• 2: 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]
• 3: Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Annal. 296, 4, 625--635.
• 4: Jin-Yi Cai, Applications of a New Transference Theorem to Ajtai's Connection Factor, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.205, May 04-06, 1999
• 5: Jin-yi Cai , Ajay P. Nerurkar, An Improved Worst-Case to Average-Case Connection for Lattice Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.468, October 19-22, 1997
• 6: Wolfgang Ebeling , Friedrich Hirzebruch, Lattices and Codes: A Course Partially Based on Lectures by F. Hirzebruch, Informatica International, Incorporated, 1994
• 7: Mark Ettinger , Peter Høyer, On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics, v.25 n.3, p.239-251, Oct. 2000 [doi>10.1006/aama.2000.0699]
• 8: Katalin Friedl , Gábor Ivanyos , Frédéric Magniez , Miklos Santha , Pranab Sen, Hidden translation and orbit coset in quantum computing, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780544]
• 9: Goldreich, O., Goldwasser, S., and Halevi, S. 1996. Collision-free hashing from lattice problems. In ECCCTR: Electronic Colloquium on Computational Complexity (technical reports).
• 10: Oded Goldreich , Shafi Goldwasser , Shai Halevi, Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.105-111, August 17-21, 1997
• 11: 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
• 12: O. Goldreich , D. Micciancio , S. Safra , J. -P. Seifert, Approximating shortest lattice vectors is not harder than approximating closet lattice vectors, Information Processing Letters, v.71 n.2, p.55-61, July 30, 1999 [doi>10.1016/S0020-0190(99)00083-6]
• 13: Michelangelo Grigni , Leonard Schulman , Monica Vazirani , Umesh Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.68-74, July 2001, Hersonissos, Greece [doi>10.1145/380752.380769]
• 14: Sean Hallgren , Alexander Russell , Amnon Ta-Shma, Normal subgroup reconstruction and quantum computation using group representations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.627-635, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335392]
• 15: Jeffrey Hoffstein , Jill Pipher , Joseph H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.267-288, June 21-25, 1998
• 16: Impagliazzo, R., and Naor, M. 1996. Efficient cryptographic schemes provably as secure as subset sum. J. Crypt. 9, 4, 199--216.
• 17: Johannes Köbler , Uwe Schöning , Jacobo Torán, The graph isomorphism problem: its structural complexity, Birkhauser Verlag, Basel, Switzerland, 1994
• 18: Kuperberg, G. 2003. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In quant-ph/0302112, http://xxx.lanl.gov.
• 19: Lenstra, A. K., Lenstra, Jr., H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 4, 515--534.
• 20: Daniele Micciancio, Improving Lattice Based Cryptosystems Using the Hermite Normal Form, Revised Papers from the International Conference on Cryptography and Lattices, p.126-145, March 29-30, 2001
• 21: Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.356-365, November 16-19, 2002
• 22: Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509995]
• 23: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 24: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.372-381, October 17-19, 2004 [doi>10.1109/FOCS.2004.72]
• 25: Oded Regev, Quantum Computation and Lattice Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 2002
• 26: Rötteler, M., and Beth, T. 1998. Polynomial-time solution to the hidden subgroup problem for a class of non-Abelian groups. In quant-ph/9812070, http://xxx.lanl.gov.
• 27: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 28: Štefankovič, D. 2003 Fourier transforms in computer science. Master's Thesis TR-2002-03. Dept. Comput. Sci., University of Chicago, Chicago, Ill.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Theory

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