SPEAKER:
Joël Alwen

TITLE:
Trapdoors for Hard Lattices and New Cryptographic Constructions

AUTHORS:
Craig gentry, Chris Peikert, Vino Vaikuntanathan (Proc. of STOC 2008)

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 length of the shortest nonzero vector
to within certain polynomial factors). Our contributions include a new notion of preimage sampleable
functions, simple and efficient “hash-and-sign” digital signature schemes, 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 discrete Gaussian probability distribution whose standard
deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security
property is that the output distribution of the algorithm is oblivious to the particular geometry of the given
basis.

ONLINE VERSION:
http://people.csail.mit.edu/cpeikert/pubs/trap_lattice.pdf

SLIDES:
http://people.csail.mit.edu/cpeikert/pubs/slides-trap.pdf