Cryptology ePrint Archive: Report 2007/432

Trapdoors for Hard Lattices and New Cryptographic Constructions

Craig Gentry and Chris Peikert and Vinod Vaikuntanathan

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 \emph{preimage sampleable} functions, 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 \emph{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.

Category / Keywords: public-key cryptography / Lattice-based cryptography, trapdoor functions, signatures, identity-based encryption

Publication Info: STOC 2008

Date: received 19 Nov 2007, last revised 16 Jun 2010

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20100617:023101 (All versions of this report)

Short URL: ia.cr/2007/432