Lattice-Based Cryptography


March 3, 2009


Chris Peikert




Most modern cryptography, and “public-key” crypto in particular, is based on mathematical problems that are conjectured to be infeasible (e.g., factoring large integers). Unfortunately, standard public-key techniques are often too inefficient to be employed in many environments; moreover, all commonly used schemes can in principle be broken by quantum computers.

This talk will review my recent work on developing new mathematical foundations for cryptography, using geometric objects called lattices. Compared to more conventional proposals, lattice-based schemes offer a host of potential advantages: they are simple and highly parallelizable, they can be proved secure under mild “worst-case” hardness assumptions, and they remain unbroken by quantum algorithms. Due to the entirely different underlying mathematics, however, realizing even the most basic cryptographic notions has been a major challenge.

Surprisingly, I will show that lattice-based schemes are also remarkably flexible and expressive, and that many important cryptographic goals can be achieved — sometimes even more simply and efficiently than with conventional approaches. Some of our schemes provide interesting twists on old and cherished cryptographic notions, while others introduce entirely new concepts altogether.


Chris Peikert

Chris Peikert received his PhD in Computer Science from MIT in 2006, following undergraduate studies in CS and Mathematics (also at MIT). His research interests include cryptography, computational complexity, and algorithms, especially as they relate to lattices and error-correcting codes. He is currently a researcher at SRI (Stanford Research Institute), and is the PI of an NSF CyberTrust grant on lattice-based cryptography.