[GPV08] Trapdoors for Hard Lattices and New Cryptographic Constructions

Authors: Craig Gentry, Chris Peikert, Vinod Vaikuntanathan | Venue: STOC 2008 | Source

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 preimage sampleable functions, simple and efficient lattice-based hash-and-sign digital signature schemes, and a new construction of such functions (based on hard lattice problems). In addition, we show how to construct identity-based encryption, collision-resistant hash functions, “lossy” trapdoor functions, and oblivious transfer protocols from worst-case lattice problems. Many of our results are based on a new, simple abstraction that we call “preimage sampleable functions,” which provides a unified framework for describing and analyzing the diverse lattice-based constructions.

BibTeX

Copy

@Inproceedings{STOC:GenPeiVai08,
  author = {Craig Gentry and Chris Peikert and Vinod Vaikuntanathan},
  title = {Trapdoors for hard lattices and new cryptographic constructions},
  pages = {197--206},
  editor = {Richard E. Ladner and Cynthia Dwork},
  booktitle = {40th Annual {ACM} Symposium on Theory of Computing},
  address = {Victoria, BC, Canada},
  month = {may~17--20},
  publisher = {{ACM} Press},
  year = {2008},
  doi = {10.1145/1374376.1374407},
}