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 shortest nonzero vector to within small factors). The applications include trapdoor functions with \emph{preimage sampling}, simple and efficient ``hash-and-sign'' digital signature schemes, universally composable oblivious transfer, 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 Gaussian-like probability distribution whose standard deviation is essentially the length of the longest vector in the basis. In particular, the 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

Date: received 19 Nov 2007

Contact author: cpeikert at alum mit edu

Available formats: PDF | BibTeX Citation

Version: 20071124:104109 (All versions of this report)

Discussion forum: Show discussion | Start new discussion