TR07-133 Authors: Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

Publication: 16th December 2007 05:07

Downloads: 2807

Keywords:

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.