Computer Sciences Colloquium - Lattice-Based Cryptography and the Learning with Errors Problem

Most of the cryptographic protocols used in everyday life are 
based on number theoretic problems such as integer factoring. We will 
give an introduction to lattice-based cryptography, a form of 
cryptography offering many advantages over the traditional 
number-theoretic-based ones, including conjectured security against 
quantum computers. The talk will mainly focus on the so-called Learning 
with Errors (LWE) problem. This problem has turned out to be an 
amazingly versatile basis for cryptographic constructions, with hundreds 
of applications, including recent breakthrough work on fully homomorphic 
encryption by Gentry and others. In addition to applications, we will 
also mention work on using algebraic number theory for making 
cryptographic constructions more efficient, as well as some very recent 
work on quantum algorithms for related algebraic problems.