Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-133 | 20th November 2007 00:00

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

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