6.876J Advanced Topics in Cryptography: Lattices (Fall 2017)
INSTRUCTOR  Vinod Vaikuntanathan
Office: 32G696 Email: vinodv at mit 
LOCATION  4237

TIME  T 10am  12:30pm (with a break in between),
Office Hours by appointment 
TEXTBOOK 
There are no required textbooks.
Instead, we will use: (a) material from the references listed below. (b) chapters from a monograph in preparation; and (c) for the first few lectures, the book Complexity of Lattice Problems: A Cryptographic Perspective by Daniele Micciancio and Shafi Goldwasser. (available online from MIT libraries) 
GRADING  Based on 23 problem sets and a final project. 
Lecture  Topic  Scribe Notes (Unedited) 
Lecture 1 (Sep 12)  Overview of the Course, Definitions of Lattices, Minkowski's Theorems, GramSchmidt Orthogonalization and a Lower Bound on λ_{1}, some applications in Number Theory.  
Lecture 2 (Sep 19) 
Computational Problems on Lattices. Easy Lattice Problems. Hard Lattices Problems: Shortest Vectors and Closest Vectors. The Gauss algorithm and the LLL algorithm. 

Lecture 3 (Sep 26) 
LLL Continued. Babai's approximate closest vector algorithms. Finding exact shortest vectors: enumeration in 2^{O(n^2)} time. 

Lecture 4 (Oct 3) 
GoldreichGoldwasser coAM Protocol for GapCVP AjtaiKumarSivakumar Algorithm for Exact Shortest Vectors. MicciancioVoulgaris CVP algorithm. Lattice Algorithms: Summary and Open Problems 

Oct 10  Columbus Day (No Class)  
Lecture 5 (Oct 17) 
Complexity of Lattice Problems: NPhardness of (approximate) CVP. NPhardness of (approximate) SVP, SETHhardness and open problems. 

Lecture 6 (Oct 24) 
Averagecase Hardness of Lattice Problems, Ajtai's Worstcase to Averagecase Reduction. The Smoothing Lemma. Oneway and Collisionresistant Hash functions. 

Lecture 7 (Oct 31) 
Learning with Errors (LWE), Search and Decisional versions of LWE and a Reduction. Worstcase to Averagecase Reduction for LWE 

Lecture 8 (Nov 7)  Publickey Encryption. Fully Homomorphic Encryption.  
Lecture 9 (Nov 14) 
Trapdoors for Lattices. Gaussian Sampling and Digital Signatures. 

Lecture 10 (Nov 21) 
Identitybased Encryption and Attributebased Encryption. 

Lecture 11 (Nov 28)  Ideal Lattices, Ring SIS and Ring LWE.  
Lecture 12 (Dec 5)  
Lecture 13 (Dec 12) 