International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Trapdoors for Hard Lattices and New Cryptographic Constructions

Craig Gentry
Chris Peikert
Vinod Vaikuntanathan
Search ePrint
Search Google
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.
  title={Trapdoors for Hard Lattices and New Cryptographic Constructions},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Lattice-based cryptography, trapdoor functions, signatures, identity-based encryption},
  note={ 13836 received 19 Nov 2007},
  author={Craig Gentry and Chris Peikert and Vinod Vaikuntanathan},