Trapdoors for hard lattices and new cryptographic constructions

ABSTRACT

We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of trapdoor function with preimage sampling, simple and efficient "hash-and-sign" digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a discrete Gaussian probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.

REFERENCES

• 1: Dorit Aharonov , Oded Regev, A Lattice Problem in Quantum NP, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.210, October 11-14, 2003
• 2: Dorit Aharonov , Oded Regev, Lattice problems in NP ∩ coNP, Journal of the ACM (JACM), v.52 n.5, p.749-765, September 2005 [doi>10.1145/1089023.1089025]
• 3: 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]
• 4: Miklós Ajtai, Generating Hard Instances of the Short Basis Problem, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.1-9, July 11-15, 1999
• 5: 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]
• 6: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 7: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 8: W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625-635, 1993.
• 9: W. Banaszczyk. Inequalites for convex bodies and polar reciprocal lattices in Rⁿ. Discrete & Computational Geometry, 13:217-231, 1995.
• 10: Mihir Bellare , Silvio Micali, How to sign given any trapdoor permutation, Journal of the ACM (JACM), v.39 n.1, p.214-233, Jan. 1992 [doi>10.1145/147508.147537]
• 11: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 12: M. Bellare and P. Rogaway. The exact security of digital signatures - how to sign with RSA and Rabin. In EUROCRYPT, pages 399-416, 1996.
• 13: D. J. Bernstein. Proving tight security for Rabin/Williams signatures. In EUROCRYPT, 2008.
• 14: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 15: Dan Boneh , Craig Gentry , Michael Hamburg, Space-Efficient Identity Based EncryptionWithout Pairings, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.647-657, October 21-23, 2007 [doi>10.1109/FOCS.2007.64]
• 16: Jin-Yi Cai, A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Theoretical Computer Science, v.207 n.1, p.105-116, Oct. 28, 1998 [doi>10.1016/S0304-3975(98)00058-9]
• 17: 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
• 18: Clifford Cocks, An Identity Based Encryption Scheme Based on Quadratic Residues, Proceedings of the 8th IMA International Conference on Cryptography and Coding, p.360-363, December 17-19, 2001
• 19: Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.229-235, August 20-24, 2000
• 20: Jean-Sébastien Coron, Optimal Security Proofs for PSS and Other Signature Schemes, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.272-287, May 02, 2002
• 21: Ronald Cramer , Victor Shoup, Signature schemes based on the strong RSA assumption, ACM Transactions on Information and System Security (TISSEC), v.3 n.3, p.161-185, Aug. 2000 [doi>10.1145/357830.357847]
• 22: W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644-654, 1976.
• 23: Y. Dodis and L. Reyzin. On the power of claw-free permutations. In SCN, pages 55-73, 2002.
• 24: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 25: R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In EUROCRYPT, pages 123-139, 1999.
• 26: C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, 2008. Full version available at http://eprint.iacr.org/2007/432.
• 27: O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. Electronic Colloquium on Computational Complexity (ECCC), 3(42), 1996.
• 28: 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
• 29: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 30: J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSIGN: Digital signatures using the NTRU lattice. In CT-RSA, pages 122-140, 2003.
• 31: Jonathan Katz , Nan Wang, Efficiency improvements for signature schemes with tight security reductions, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948132]
• 32: Philip Klein, Finding the closest lattice vector when it's unusually close, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.937-941, January 09-11, 2000, San Francisco, California, United States
• 33: A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, December 1982.
• 34: Y.-K. Liu, V. Lyubashevsky, and D. Micciancio. On bounded distance decoding for general lattices. In APPROX-RANDOM, pages 450-461, 2006.
• 35: V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144-155, 2006. Full version in ECCC Report TR05-142.
• 36: V. Lyubashevsky and D. Micciancio. Asymptotically efficient lattice-based digital signatures. In TCC, pages 37-54, 2008.
• 37: Daniele Micciancio, Almost Perfect Lattices, the Covering Radius Problem, and Applications to Ajtai's Connection Factor, SIAM Journal on Computing, v.34 n.1, p.118-169, 2005 [doi>10.1137/S0097539703433511]
• 38: Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions, Computational Complexity, v.16 n.4, p.365-411, December 2007 [doi>10.1007/s00037-007-0234-9]
• 39: Daniele Micciancio , S. Goldwasser, Complexity of Lattice Problems, Kluwer Academic Publishers, Norwell, MA, 2002
• 40: Daniele Micciancio , Oded Regev, Worst-Case to Average-Case Reductions Based on Gaussian Measures, SIAM Journal on Computing, v.37 n.1, p.267-302, April 2007 [doi>10.1137/S0097539705447360]
• 41: D. Micciancio and S. P. Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In CRYPTO, pages 282-298, 2003.
• 42: M. Naor , M. Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.33-43, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73011]
• 43: P. Q. Nguyen and O. Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In EUROCRYPT, pages 271-288, 2006.
• 44: P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2008. To appear.
• 45: Chris Peikert, Limits on the Hardness of Lattice Problems in \ell _p Norms, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.333-346, June 13-March 16, 2007 [doi>10.1109/CCC.2007.12]
• 46: C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pages 145-166, 2006. Full version in ECCC Report TR05-158.
• 47: Chris Peikert , Alon Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250860]
• 48: C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer. Cryptology ePrint Archive, Report 2007/348, 2007. Available at http://eprint.iacr.org/2007/348.
• 49: Chris Peikert , Brent Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374406]
• 50: O. Regev. Lecture notes on lattices in computer science, 2004. Available at http://www.cs.tau.ac.il/~odedr/teaching/ lattices_fall_2004/index.html, last accessed 28 Feb 2008.
• 51: Oded Regev, New lattice-based cryptographic constructions, Journal of the ACM (JACM), v.51 n.6, p.899-942, November 2004 [doi>10.1145/1039488.1039490]
• 52: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 53: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 54: J. Rompel, One-way functions are necessary and sufficient for secure signatures, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.387-394, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100269]
• 55: C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8]
• 56: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 57: B. Waters. Efficient identity-based encryption without random oracles. In EUROCRYPT, pages 114-127, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
lattice-based cryptography, trapdoor functions