6.876J Advanced Topics in Cryptography: Lattices (Fall 2015)
|INSTRUCTOR|| Vinod Vaikuntanathan
E-mail: vinodv at mit
(Location on the MIT map)
|TIME||MW 2:30 - 4pm ,
Office Hours by appointment
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 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 3 (Sep 16)||Computational Problems on Lattices -- the Shortest Vector Problem and friends, the LLL algorithm.||
|Lecture 4 (Sep 21)||LLL algorithm (contd.) and analysis. Exact shortest vector in 2O(n2) time. Babai's approximate closest vector algorithms.||
|Lecture 5 (Sep 23)||Coppersmith's Method: Finding small Solutions to polynomial equations, Breaking various special cases of the RSA encryption.||
|Lecture 6 (Sep 28)||Goldreich-Goldwasser coAM Protocol for GapCVP||
|Lecture 7 (Sep 30)||Ajtai-Kumar-Sivakumar Algorithm for Exact Shortest Vectors.||
|Lecture 8 (Oct 5)||
Micciancio-Voulgaris CVP algorithm.
Lattice Algorithms: Summary and Open Problems
|Lecture 9 (Oct 7)||Complexity of Lattice Problems: NP-hardness of (approximate) CVP.||
|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 12 (Oct 21)||The Smoothing Lemma. One-way and Collision-resistant Hash functions.||
|Lecture 13 (Oct 26)||Learning with Errors (LWE), Search and Decisional versions of LWE and a Reduction.||
|Lecture 14 (Oct 28)||Fully Homomorphic Encryption.||
|Lecture 15 (Nov 2)||Worst-case to Average-case Reduction for LWE||
|Lecture 16 (Nov 4)||Trapdoors for Lattices.||
|Lecture 17 (Nov 9)||Gaussian Sampling and Digital Signatures.||
|Nov 11||Veterans' Day (No Classes)||Lecture 18 (Nov 16)||Identity-based Encryption.||
|Lecture 19 (Nov 18)||Attribute-based Encryption.||
|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 --|