Paper 2007/432

Trapdoors for Hard Lattices and New Cryptographic Constructions

Craig Gentry, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. STOC 2008
Keywords
Lattice-based cryptographytrapdoor functionssignaturesidentity-based encryption
Contact author(s)
cpeikert @ alum mit edu
History
2010-06-17: revised
2007-11-24: received
See all versions
Short URL
https://ia.cr/2007/432
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/432,
      author = {Craig Gentry and Chris Peikert and Vinod Vaikuntanathan},
      title = {Trapdoors for Hard Lattices and New Cryptographic Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2007/432},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/432}},
      url = {https://eprint.iacr.org/2007/432}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.