Craig Gentry
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.
- D. Aharonov and O. Regev. A lattice problem in quantum NP. In FOCS, pages 210-219, 2003. Google Scholar
Digital Library
- D. Aharonov and O. Regev. Lattice problems in NP ¿ coNP. J. ACM, 52(5):749-765, 2005. Google ScholarDigital Library
- M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108, 1996. Google ScholarDigital Library
- M. Ajtai. Generating hard instances of the short basis problem. In ICALP, pages 1-9, 1999. Google ScholarDigital Library
- M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC, pages 284-293, 1997. Google ScholarDigital Library
- M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In STOC, pages 601-610, 2001. Google ScholarDigital Library
- L. Babai. On Lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13, 1986. Google ScholarDigital Library
- W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, 296(4):625-635, 1993.Google ScholarCross Ref
- W. Banaszczyk. Inequalites for convex bodies and polar reciprocal lattices in R<sup>n</sup>. Discrete & Computational Geometry, 13:217-231, 1995.Google ScholarDigital Library
- M. Bellare and S. Micali. How to sign given any trapdoor permutation. J. ACM, 39(1):214-233, 1992. Google ScholarDigital Library
- M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In ACM CCS, pages 62-73, 1993. Google ScholarDigital Library
- M. Bellare and P. Rogaway. The exact security of digital signatures - how to sign with RSA and Rabin. In EUROCRYPT, pages 399-416, 1996. Google ScholarDigital Library
- D. J. Bernstein. Proving tight security for Rabin/Williams signatures. In EUROCRYPT, 2008. Google ScholarDigital Library
- D. Boneh and M. K. Franklin. Identity-based encryption from the Weil pairing. SIAM J. Comput., 32(3):586-615, 2003. Google ScholarDigital Library
- D. Boneh, C. Gentry, and M. Hamburg. Space-efficient identity based encryption without pairings. In FOCS, pages 647-657, 2007. Full version at http://eprint.iacr.org/2007/177. Google ScholarDigital Library
- J.-Y. Cai. A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theor. Comput. Sci., 207(1):105-116, 1998. Google ScholarDigital Library
- J.-Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In FOCS, pages 468-477, 1997. Google ScholarDigital Library
- C. Cocks. An identity based encryption scheme based on quadratic residues. In IMA Int. Conf., pages 360-363, 2001. Google ScholarDigital Library
- J.-S. Coron. On the exact security of full domain hash. In CRYPTO, pages 229-235, 2000. Google ScholarDigital Library
- J.-S. Coron. Optimal security proofs for PSS and other signature schemes. In EUROCRYPT, pages 272-287, 2002. Google ScholarDigital Library
- R. Cramer and V. Shoup. Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur., 3(3):161-185, 2000. Google ScholarDigital Library
- W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644-654, 1976.Google ScholarDigital Library
- Y. Dodis and L. Reyzin. On the power of claw-free permutations. In SCN, pages 55-73, 2002. Google ScholarDigital Library
- A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186-194, 1986. Google ScholarDigital Library
- R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In EUROCRYPT, pages 123-139, 1999. Google ScholarDigital Library
- 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.Google Scholar
- O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. Electronic Colloquium on Computational Complexity (ECCC), 3(42), 1996.Google Scholar
- O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO, pages 112-131, 1997. Google ScholarDigital Library
- S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281-308, 1988. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. Katz and N. Wang. Efficiency improvements for signature schemes with tight security reductions. In ACM Conference on Computer and Communications Security, pages 155-164, 2003. Google ScholarDigital Library
- P. N. Klein. Finding the closest lattice vector when it's unusually close. In SODA, pages 937-941, 2000. Google ScholarDigital Library
- A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, December 1982.Google ScholarCross Ref
- Y.-K. Liu, V. Lyubashevsky, and D. Micciancio. On bounded distance decoding for general lattices. In APPROX-RANDOM, pages 450-461, 2006. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- V. Lyubashevsky and D. Micciancio. Asymptotically efficient lattice-based digital signatures. In TCC, pages 37-54, 2008. Google ScholarDigital Library
- D. Micciancio. Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor. SIAM J. Comput., 34(1):118-169, 2004. Google ScholarDigital Library
- D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365-411, Dec. 2007. Preliminary version in FOCS 2002. Google ScholarDigital Library
- D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, 2002. Google ScholarCross Ref
- D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput., 37(1):267-302, 2007. Preliminary version in FOCS 2004. Google ScholarDigital Library
- D. Micciancio and S. P. Vadhan. Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In CRYPTO, pages 282-298, 2003.Google ScholarCross Ref
- M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In STOC, pages 33-43, 1989. Google ScholarDigital Library
- P. Q. Nguyen and O. Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In EUROCRYPT, pages 271-288, 2006. Google ScholarDigital Library
- P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2008. To appear.Google ScholarCross Ref
- C. Peikert. Limits on the hardness of lattice problems in l<inf>p</inf> norms. In IEEE Conference on Computational Complexity, pages 333-346, 2007. Full version in ECCC Report TR06-148. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. In STOC, pages 478-487, 2007. Full version in ECCC Report TR06-147. Google ScholarDigital Library
- 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.Google Scholar
- C. Peikert and B. Waters. Lossy trapdoor functions and their applications. In STOC, 2008. Google ScholarDigital Library
- 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.Google Scholar
- O. Regev. New lattice-based cryptographic constructions. J. ACM, 51(6):899-942, 2004. Google ScholarDigital Library
- O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84-93, 2005. Google ScholarDigital Library
- R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120-126, 1978. Google ScholarDigital Library
- J. Rompel. One-way functions are necessary and sufficient for secure signatures. In STOC, pages 387-394, 1990. Google ScholarDigital Library
- C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci., 53:201-224, 1987.Google ScholarCross Ref
- A. Shamir. Identity-based cryptosystems and signature schemes. In CRYPTO, pages 47-53, 1984. Google ScholarDigital Library
- B. Waters. Efficient identity-based encryption without random oracles. In EUROCRYPT, pages 114-127, 2005. Google ScholarDigital Library
Index Terms
- Trapdoors for hard lattices and new cryptographic constructions
Recommendations
Identity-Based Encryption from Lattices Using Approximate Trapdoors
Information Security and PrivacyAbstractPractical implementations of advanced lattice-based constructions have received much attention since the first practical scheme instantiated over lattices, proposed by Prest et al. (Asiacrypt 2014). They are using powerful lattice-based ...
On Structure-Preserving Cryptography and Lattices
Public-Key Cryptography – PKC 2024AbstractThe Groth-Sahai proof system is a highly efficient pairing-based proof system for a specific class of group-based languages. Cryptographic primitives that are compatible with these languages (such that we can express, e.g., that a ciphertext ...
Policy-based signature scheme from lattices
Policy-based signature, introduced by Bellare and Fuchsbauer at PKC 2014, is a new type of digital signature in which a signer is only allowed to sign messages satisfying certain policy specified by the authority, but the signatures should not reveal ...
Comments