Monday, October 15, 2007
4:00 PM
315 Upson Hall
  Theory Seminar
Fall 2007
CS 789

Vinod Vaikuntanathan


The Unreasonable Effectiveness of Lattices in Cryptography

Integer lattices have emerged to be a powerful alternative to number-theory as a source of hard problems for use in cryptography. An alluring feature of lattices is that they provide us with *average-case* hard problems which are as hard as certain well-studied *worst-case* hard problems.

Lattices have so far been used to construct relatively simple, albeit fundamental, cryptographic primitives such as one-way functions, collision-resistant hash functions and public-key encryption. In this talk, we will present new tools for lattice-based cryptography and (using them) new constructions of powerful cryptographic primitives.

Based on joint work with Craig Gentry, Chris Peikert and Brent Waters.