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 which 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 collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

REFERENCES

• 1: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 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: W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625--635, 1993.
• 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: 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]
• 7: O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, 1996.
• 8: 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
• 9: 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
• 10: 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
• 11: R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199--216, 1996.
• 12: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann., 261(4):515--534, 1982.
• 13: 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
• 14: 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
• 15: 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]
• 16: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 17: Oded Regev, Quantum Computation and Lattice Problems, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.520-529, November 16-19, 2002

INDEX TERMS

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

General Terms:
Algorithms, Theory

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