Vinod Vaikuntanathan  
IBM Watson

Trapdoors for Hard Lattices and New Cryptographic Constructions

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.