About
The study of integer lattices serves as a bridge between number theory and geometry and has for centuries received the attention of illustrious mathematicians, including Lagrange, Gauss, Dirichlet, Hermite, and Minkowski. In computer science, lattices made a grand appearance in 1982 with the celebrated work of Lenstra, Lenstra, and Lovász, who developed the celebrated LLL algorithm to find short vectors in integer lattices. The role of lattices in cryptography has been equally, if not more, revolutionary and dramatic, with lattices first playing a destructive role as a potent tool for breaking cryptosystems and later serving as a new way to realize powerful and game-changing notions such as fully homomorphic encryption. These exciting developments over the last two decades have taken us on a journey through such diverse areas as quantum computation, learning theory, Fourier analysis, and algebraic number theory.
We stand today at a turning point in the study of lattices. The promise of practical lattice-based cryptosystems together with their apparent quantum resistance is generating a tremendous amount of interest in deploying these schemes at Internet scale. However, before lattice cryptography goes live, we need major advances in understanding the hardness of lattice problems that underlie the security of these cryptosystems. Significant, groundbreaking progress on these questions requires a concerted effort by researchers from many areas: (algebraic) number theory, (quantum) algorithms, optimization, cryptography, and coding theory.
The goal of this program was to bring together experts in these areas to attack some of the main outstanding open questions and to discover new connections among lattices, computer science, and mathematics. The need to thoroughly understand the computational landscape and cryptographic capabilities of lattice problems is greater now than ever given the possibility that secure communication on the Internet and secure collaboration on the cloud might soon be powered by lattices.
This program was supported in part by the Alfred P. Sloan Foundation.
Vinod Vaikuntanathan taught a graduate course on Lattices, Learning with Errors and Post-Quantum Cryptography in the Berkeley EECS department parallel to this program, which addressed many of the program’s central themes. The course materials are viewable here.
