ECCC-Report TR07-133https://eccc.weizmann.ac.il/report/2007/133Comments and Revisions published for TR07-133en-usSun, 16 Dec 2007 05:07:39 +0200
Paper TR07-133
| Trapdoors for Hard Lattices and New Cryptographic Constructions |
Craig Gentry,
Chris Peikert,
Vinod Vaikuntanathan
https://eccc.weizmann.ac.il/report/2007/133We 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.
Sun, 16 Dec 2007 05:07:39 +0200https://eccc.weizmann.ac.il/report/2007/133