Lattice-Based Cryptography and the Learning with Errors Problem

Lattice-Based Cryptography and the Learning with Errors Problem

-
Oded Regev, Courant Institute of Mathematical Sciences, New York University
Fine Hall 214

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.

Oded Regev is a professor in the Courant Institute of Mathematical Sciences of New York University. Prior to joining NYU, he was affiliated with Tel Aviv University and the École Normale Supérieure, Paris under the French National Centre for Scientific Research (CNRS). He received his Ph.D. in computer science from Tel Aviv University in 2001. He is the recipient of the 2018 Gödel Prize, as well as best paper awards in STOC 2003 and Eurocrypt 2006. He was awarded a European Research Council(ERC) Starting Grant in 2008. His main research areas include theoretical computer science, cryptography, quantum computation and complexity theory. A main focus of his research is in the area of lattice-based cryptography, where he introduced several key concepts, including the Learning with Errors (LWE) problem and the use of Gaussian measures.