Beyond the Bootcamp:
CS 294168 Lattices, Learning with Errors and PostQuantum Cryptography
Course Description
The study of integer lattices, discrete additive subgroups of R^{n}, 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.The role of lattices in cryptography has been revolutionary and dramatic. In the 80s and the early 90s, lattices served as a destructive force, giving the cryptanalysts some of their most potent attack tools.
In the last two decades, the Learning with Errors (LWE) Problem, whose hardness is closely related to lattice problems, has revolutionized modern cryptography by giving us (a) a basis for "postquantum" cryptography, (b) a dizzying variety of cryptographic primitives such as fully homomorphic encryption and signatures, attributebased and functional encryption, a rich set of pseudorandom functions, various types of program obfuscation and much more; and finally, (c) a unique source of computational hardness with worstcase to averagecase connections. This course explores the various facets of lattices, the LWE problem and their applications in cryptography.
The course is intended to complement the Spring'20 Simons Institute program on Lattices. In particular, to get more out of the course, the students are encouraged to attend the bootcamp and the workshops of the program.
Prerequisites: This is an advanced course, intended for beginning graduate students and upper level undergraduates in CS and Math. Mathematical maturity and comfort with linear algebraic notions is the most important prerequisite, followed by courses in the theory of computation (CS 172 or equivalent) and cryptography (CS 171 or CS 276).
Course Information
INSTRUCTOR  Vinod Vaikuntanathan
Email: vinodv at berkeley dot edu 
LOCATION  Soda 320

TIME  M 5pm  7:30pm (with a break in between),
Office Hours by appointment 
TEXTBOOK  There are no required textbooks. Instead, we will use lecture notes and papers from the references listed below, as well as instructor's notes. 
GRADING  Based on (a) class participation (come to class; attend a talk of your choice in each of the three workshops, and write a short email to the instructor with a review of the talk, including a summary, what you liked/disliked and any ideas you got from watching it) and (b) a final project (either come up with a new result  talk to the instructor for project ideas  or write a short survey on a topic that will be useful to future researchers). 
Announcements
 The first class is on Monday Jan 27, 2020.
 Starting March 15, we are moving the class online. Lectures will be on zoom.
 Lecture notes for the class are here (all in one file).
Schedule (tentative and subject to change)
Lecture  Topic  References 
Lecture 1 (Jan 27)  Introduction to SIS and LWE. Basic properties and cryptographic applications: public and privatekey encryption and collisionresistant hashing.  Instructor notes 
Lecture 2 (Feb 3)  Algorithms for LWE. Introduction to Lattices. 
Instructor notes References 
Lecture 3 (Feb 10)  Smoothing Parameter and Worstcase to Averagecase Reduction for SIS. 
Instructor notes References 
Feb 17  President's Day (No Class)  
Lecture 4 (Feb 24)  Reductions for LWE (Worsttoaverage case, Searchtodecision) 
Instructor notes (updated 3/2) References 
Lecture 5 (Mar 2)  Pseudorandom Functions and Learning with Rounding. 
Instructor notes References 
Lecture 6 (Mar 9) 
Lattice Trapdoors and Discrete Gaussian Sampling. Digital Signatures. 
Instructor notes References 
Mar 16  Class canceled  
Mar 23  Spring Break (No Class)  
Lecture 7 (Mar 30)  Identitybased Encryption and Hierarchical IBE. 
Instructor notes References 
Lecture 8 (Apr 6)  Fully Homomorphic Encryption. The key equation and applications to attributebased encryption, fully homomorphic signatures and constrained pseudorandom functions. 
Instructor notes References 
Lecture 9 (Apr 13)  The GGH15 Multilinear Map and Applications. 
Instructor notes References 
Lecture 10 (Apr 20)  Ideal Lattices and Ring Learning with Errors. 
Instructor notes References 
Lecture 11 (Apr 27)  AMA on lattices with Vinod.  
Lecture 12 (May 4)  Lattices and Quantum Computing. 
Instructor notes References 
References
Courses Elsewhere: A precursor of this course at MIT: Fall 2015 and Fall 2017 and Fall 2018.
 Oded Regev's course at TelAviv University.
 Daniele Micciancio's course at UCSD.
 Cynthia Dwork's course at Stanford.
 Chris Peikert's course at Michigan/Georgia Tech.
Lecture 2
 The AroraGe paper: https://users.cs.duke.edu/~rongge/LPSN.pdf
 The original BKW paper (with an algorithm for LPN): https://arxiv.org/abs/cs/0010022
 Adaptation of BKW for LWE: https://eprint.iacr.org/2012/636.pdf
 Further improvements on BKWLWE: https://arxiv.org/abs/1506.02717
 Lattice attacks against LWE (LindnerPeikert): https://web.eecs.umich.edu/~cpeikert/pubs/lweanalysis.pdf
Lecture 3
 Regev's lecture notes.
 MicciancioRegev paper.
 GentryPeikertVaikuntanathan that improves the modulus q in the SIS reduction.
 Further improvements by Micciancio and Peikert.
 Forthcoming: BrakerskiStephensDavidowitzVaikuntanathan on exponential reductions from $\sqrt{n}$approximate SIVP to $k$SUM, a parameterized version of SIS.
Lecture 4
Lecture 5
 GGM (GoldreichGoldwasserMicali) paper.
 BPR12 (BanerjeePeikertRosen) paper.
 BLMR (BonehLewiMontgomeryRaghunathan) paper.
 BP14 (BanerjeePeikert) paper.
Lecture 6
 Ajtai99 paper on trapdoor sampling.
 GentryPeikertVaikuntanathan Gaussian sampling and signatures.
 MicciancioPeikert trapdoor sampling paper.
Lecture 7
 GentryPeikertVaikuntanathan for IBE.
 CashHofheinzKiltzPeikert for standard model IBE.
 AgrawalBonehBoyen for (a different) standard model IBE.
 Another ABB paper on hierarchical IBE.
Lecture 8
 GentrySahaiWaters FHE Scheme.
 BonehGorbunovGentryHaleviNikolaenkoSegevVaikuntanathanVinayagamurthy (BGG+) ABE Scheme.
 BrakerskiVaikuntanathan Constrained PRF.
 GorbunovVaikuntanathanWichs Fully Homomorphic Signature.
 Hoeteck Wee's excellent tutorial on the key equation.
Lecture 9
 GentryGorbunovHalevi15 Multilinear maps.
 CanettiChen17.
 ChenVaikuntanathanWee18.
 GoyalKoppulaWaters18 and WichsZirdelis18.
Lecture 10
 NTRU paper.
 Micciancio cyclic lattices paper.
 PeikertRosen and LyubashevskyMicciancio on RingSIS.
 LyubashevskyPeikertRegev 2010 RingLWE paper.
Lecture 12
 Kuperberg's Algorithm: Algorithm for dihedral HSP.
 Kuperberg's better algorithm
 Regev's "Quantum Computation and Lattice Problems" paper: Reduction from LWE to dihedral HSP.
 A modern version of Regev's reduction