6.876J Advanced Topics in Cryptography: Lattices (Fall 2015)
INSTRUCTOR | Vinod Vaikuntanathan
Office: 32-G696 E-mail: vinodv at mit |
LOCATION | (Location on the MIT map) |
TIME | MW 2:30 - 4pm ,
Office Hours by appointment |
TEXTBOOK |
There are no required textbooks.
Instead, we will use material from the
references listed below. In addition, for the first few lectures, we may refer to the book Complexity of Lattice Problems: A Cryptographic Perspective by Daniele Micciancio and Shafi Goldwasser. (available online from MIT libraries) |
GRADING | Based on 1-2 problem sets, Scribing 1-2 Lectures and a Final Project. |
Lecture | Topic | Scribe Notes (Unedited) |
Lecture 1 (Sep 9) | Overview of the Course, Definitions of Lattices, Minkowski's Convex Body Theorem, Minkowski's First Theorem. |
Lecture 1 |
Lecture 2 (Sep 14) | Minkowski's Second Theorem. Gram-Schmidt Orthogonalization and a Lower Bound on λ1. Applications in Number Theory. Hermite Normal Form and Easy Lattice Problems. |
Lecture 2 |
Lecture 3 (Sep 16) | Computational Problems on Lattices -- the Shortest Vector Problem and friends, the LLL algorithm. |
Lecture 3 Itay Berman |
Lecture 4 (Sep 21) | LLL algorithm (contd.) and analysis. Exact shortest vector in 2O(n2) time. Babai's approximate closest vector algorithms. |
Lecture 4 Akshay Degwekar |
Lecture 5 (Sep 23) | Coppersmith's Method: Finding small Solutions to polynomial equations, Breaking various special cases of the RSA encryption. |
Lecture 5 Rio LaVigne |
Lecture 6 (Sep 28) | Goldreich-Goldwasser coAM Protocol for GapCVP |
Lecture 6 Gaurav Singh |
Lecture 7 (Sep 30) | Ajtai-Kumar-Sivakumar Algorithm for Exact Shortest Vectors. |
Lecture 7 Adam Sealfon |
Lecture 8 (Oct 5) |
Micciancio-Voulgaris CVP algorithm. Lattice Algorithms: Summary and Open Problems |
Lecture 8 Ofer Grossman |
Lecture 9 (Oct 7) | Complexity of Lattice Problems: NP-hardness of (approximate) CVP. |
Lecture 9 Adam Suhl |
Lecture 10 (Oct 14) | Complexity of Lattice Problems: NP-hardness of (approximate) SVP, and open problems. |
Lecture 10 Lauren de Meyer and Prashant Vasudevan |
Lecture 11 (Oct 19) | Average-case Hardness of Lattice Problems, Ajtai's Worst-case to Average-case Reduction. |
Lecture 11 Tianren Liu |
Lecture 12 (Oct 21) | The Smoothing Lemma. One-way and Collision-resistant Hash functions. |
Lecture 12 Srinivasan Raghuraman |
Lecture 13 (Oct 26) | Learning with Errors (LWE), Search and Decisional versions of LWE and a Reduction. |
Lecture 13 Sunoo Park |
Lecture 14 (Oct 28) | Fully Homomorphic Encryption. |
Lecture 14 Victor Balcer |
Lecture 15 (Nov 2) | Worst-case to Average-case Reduction for LWE |
Lecture 15 Asra Ali |
Lecture 16 (Nov 4) | Trapdoors for Lattices. |
Lecture 16 Aloni Cohen |
Lecture 17 (Nov 9) | Gaussian Sampling and Digital Signatures. |
Lecture 17 Alex Grinman |
Nov 11 | Veterans' Day (No Classes) | Lecture 18 (Nov 16) | Identity-based Encryption. |
Lecture 18 Adam Hesterberg |
Lecture 19 (Nov 18) | Attribute-based Encryption. |
Lecture 19 Adam Hesterberg |
Lecture 20 (Nov 23) | No Lecture; Office Hours in G-696. | NA |
Nov 25 | Thanksgiving (No Lecture) | Lecture 21 (Nov 30) | Key-Homomorphic Functions and Predicate Encryption. | Farhana Khan | Lecture 22 (Dec 2) | Ideal Lattices, Ring SIS and Ring LWE. | Omer Cerrahoglu and Jeffrey Shen |
Lecture 23 (Dec 7) | project presentations 2:30-5pm. | |
Lecture 24 (Dec 9) | -- ditto -- |