6.876J Advanced Topics in Cryptography: Lattices (Fall 2017)
|INSTRUCTOR|| Vinod Vaikuntanathan
E-mail: vinodv at mit
|TIME||T 10am - 12:30pm (with a break in between),
Office Hours by appointment
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 2-3 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, Gram-Schmidt 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)||
Babai's approximate closest vector algorithms.
Finding exact shortest vectors: enumeration in 2O(n^2) time.
|Lecture 4 (Oct 3)||
Goldreich-Goldwasser coAM Protocol for GapCVP
Ajtai-Kumar-Sivakumar Algorithm for Exact Shortest Vectors. Micciancio-Voulgaris CVP algorithm.
Lattice Algorithms: Summary and Open Problems
|Oct 10||Columbus Day (No Class)||Lecture 5 (Oct 17)||
Complexity of Lattice Problems: NP-hardness of (approximate) CVP.
NP-hardness of (approximate) SVP,
SETH-hardness and open problems.
|Lecture 6 (Oct 24)||
Average-case Hardness of Lattice Problems,
Ajtai's Worst-case to Average-case Reduction.
The Smoothing Lemma. One-way and Collision-resistant Hash functions.
|Lecture 7 (Oct 31)||
Learning with Errors (LWE),
Search and Decisional versions of LWE and a Reduction.
Worst-case to Average-case Reduction for LWE
|Lecture 8 (Nov 7)||Public-key Encryption. Fully Homomorphic Encryption.||Lecture 9 (Nov 14)||
Trapdoors for Lattices.
Gaussian Sampling and Digital Signatures.
|Lecture 10 (Nov 21)||
Identity-based Encryption and
|Lecture 11 (Nov 28)||Ideal Lattices, Ring SIS and Ring LWE.||Lecture 12 (Dec 5)||Lecture 13 (Dec 12)|