Spring 2020

Lattices: Algorithms, Complexity, and Cryptography

Jan. 14May 15, 2020
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.


Shafi Goldwasser (UC Berkeley; co-chair), Vinod Vaikuntanathan (Massachusetts Institute of Technology; co-chair), Daniele Micciancio (UC San Diego), Oded Regev (Courant Institute of Mathematical Sciences, New York University), Hoeteck Wee (CNRS and ENS)

Long-Term Participants (including Organizers):

Shweta Agrawal (IIT Madras), Martin Albrecht (Royal Holloway, University of London), Prabhanjan Ananth (University of California, Santa Barbara), Jean-Francois Biasse (University of South Florida), Dan Boneh (Stanford University), Elette Boyle (IDC Herzliya), Zvika Brakerski (Weizmann Institute of Science), Yilei Chen (Visa Research), Alessandro Chiesa (UC Berkeley), Ilaria Chillotti (KU Leuven), Daniel Dadush (Centrum Wiskunde & Informatica), Nico Döttling (CISPA Helmholtz Center), Pierre-Alain Fouque (Rennes University), Sanjam Garg (UC Berkeley), Shafi Goldwasser (UC Berkeley; co-chair), Sergey Gorbunov (University of Waterloo), Siyao Guo (Northeastern University), Nadia Heninger (UCSD), Yuval Ishai (Technion - Israel Institute of Technology), Ravi Kannan (Microsoft Research India), Elena Kirshanova (Immanuel Kant Baltic Federal University), Thijs Laarhoven (Eindhoven University of Technology), Tanja Lange (Technische Universiteit Eindhoven), Tancrède Lepoint (Google LLC), Rachel Lin (University of Washington), Arya Mazumdar (University of Massachusetts Amherst), Daniele Micciancio (UC San Diego), Phong Nguyen (DIENS and Inria), Chris Peikert (University of Michigan, Ann Arbor), Alice Pellet-Mary (KU Leuven), Raluca Popa (UC Berkeley), Alon Rosen (IDC Herzliya), Amit Sahai (UCLA), Sina Shiehian (University of Michigan, Ann Arbor), Alice Silverberg (University of California, Irvine), Damien Stehlé (École Normale Supérieure de Lyon), Stefano Tessaro (University of Washington), Vinod Vaikuntanathan (Massachusetts Institute of Technology; co-chair), Prashant Vasudevan (UC Berkeley), Umesh Vazirani (UC Berkeley), Michael Walter (IST Austria), Brent Waters (UT Austin and NTT Research), Hoeteck Wee (CNRS and ENS), Daniel Wichs (Northeastern University), David Wu (University of Virginia), Shota Yamada (AIST)

Research Fellows:

Léo Ducas (Centrum Wiskunde & Informatica; VMware Research Fellow), Rishab Goyal (UT Austin; Apple Research Fellow), Justin Holmgren (Princeton University; Google Research Fellow), Dakshita Khurana (University of Illinois Urbana-Champaign; Google Research Fellow), Sam Kim (Stanford University; Ripple Research Fellow), Venkata Koppula (Weizmann Institute of Science), Oxana Poburinnaya (Boston University), Fang Song (Texas A&M U), Noah Stephens-Davidowitz (Massachusetts Institute of Technology; Microsoft Research Fellow)

Visiting Graduate Students and Postdocs:

Huck Bennett (University of Michigan), Nina Bindel (University of Waterloo), Katharina Boudgoust (Rennes University), Pedro Branco (CISPA Helmholtz Center), Koen de Boer (CWI), Leo de Castro (MIT), Rachit Garg (University of Texas at Austin), Ashrujit Ghoshal (University of Washington), Aayush Jain (UCLA), Ruta Jawale (UIUC), Changmin Lee (ENS Lyon), Jiahui Liu (University of Texas Austin), Alex Lombardi (MIT), Ji Luo (University of Washington), Fermi Ma (Princeton University), Lorenz Panny (Eindhoven University of Technology), Eamonn Postlethwaite (Royal Holloway, University of London), Sihang Pu (CISPA Helmholtz Center), Willy Quach (Northeastern University), Jessica Sorrell (UC San Diego), Katerina Sotiraki (MIT), George Sullivan (UC San Diego), Herve Tale Kalachi (ENS Lyon), Rotem Tsabary (Weizmann Institute), Wessel van Woerden (CWI), Fernando Virdia (Royal Holloway, University of London), Satya Vusirikala (University of Texas at Austin), Giorgos Zirdelis (Northeastern University)


Tuesday, Jan. 21Friday, Jan. 24, 2020


Vinod Vaikuntanathan (Massachusetts Institute of Technology; chair), Shafi Goldwasser (UC Berkeley), Daniele Micciancio (UC San Diego), Oded Regev (Courant Institute of Mathematical Sciences, New York University), Hoeteck Wee (CNRS and ENS)
Tuesday, Feb. 18Friday, Feb. 21, 2020


Daniele Micciancio (UC San Diego; chair), Daniel Dadush (Centrum Wiskunde & Informatica), Chris Peikert (University of Michigan, Ann Arbor)
Saturday, Feb. 22Monday, Feb. 24, 2020


Stacey Jeffery (Centrum Wiskunde & Informatica), Elena Kirshanova (Immanuel Kant Baltic Federal University), Vadim Lyubashevsky (IBM Research)
Monday, Mar. 23Friday, Mar. 27, 2020


Hoeteck Wee (CNRS and ENS; chair), Shweta Agrawal (IIT Madras), Zvika Brakerski (Weizmann Institute of Science)
Monday, Apr. 27Friday, May 1, 2020


Vadim Lyubashevsky (IBM Research; chair), Shai Halevi (IBM Research), Damien Stehlé (École Normale Supérieure de Lyon), Vinod Vaikuntanathan (Massachusetts Institute of Technology)
Monday, Jun. 14Wednesday, Jun. 16, 2021


Shafi Goldwasser (UC Berkeley; co-chair), Vinod Vaikuntanathan (Massachusetts Institute of Technology; co-chair), Daniele Micciancio (UC San Diego), Oded Regev (Courant Institute, NYU)

 Subscribe to the program calendar.

Past Internal Program Activities

Tuesday, April 21st, 9:30 am11:00 am
James Bartusek (UC Berkeley)
Thursday, April 16th, 9:30 am11:00 am
Tuesday, April 14th, 9:30 am11:00 am
Tuesday, April 7th, 11:00 am12:00 pm
Nicholas Genise (UC San Diego)
Friday, April 3rd, 9:00 am10:00 am
Thursday, March 5th, 10:00 am12:00 pm
Tuesday, February 4th, 10:00 am12:00 pm
Huck Bennett, University of Michigan