Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR07-133 | 20th November 2007 00:00

#### Trapdoors for Hard Lattices and New Cryptographic Constructions

TR07-133
Authors: Craig Gentry, Chris Peikert, Vinod Vaikuntanathan
Publication: 16th December 2007 05:07
Keywords:

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.

ISSN 1433-8092 | Imprint