6.876J Advanced Topics in Cryptography: Lattices (Fall 2017)


Course Information

INSTRUCTOR Vinod Vaikuntanathan
Office: 32-G696
E-mail: vinodv at mit
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 2-3 problem sets and a final project.

The course counts for Grad-H Credit as well as the M.Eng. Theory of Computation Concentration.

Course Description

Integer lattices are powerful mathematical objects that have found applications in many diverse facets of computer science, most notably in the areas of cryptography and combinatorial optimization. This course gives an introduction to the theory of integer lattices -- their algorithms and applications to combinatorial optimization, their recent use in cryptography culminating in the first construction of a fully homomorphic encryption scheme, and the fascinating complexity landscape associated with lattice problems. We will discuss the recent exciting developments in these areas, as well as a number of open problems.

Prerequisites: 6.045 and 6.046 (or equivalent). Basic Linear Algebra. Knowledge of basic cryptography is a plus.

Project Ideas

We will maintain the list of open problems and project ideas here. This will be updated frequently -- please check back often.

Schedule (subject to change)

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) LLL Continued.
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
Attribute-based Encryption.
Lecture 11 (Nov 28) Ideal Lattices, Ring SIS and Ring LWE.
Lecture 12 (Dec 5)
Lecture 13 (Dec 12)


For the first half of the course (Foundations, Algorithms and Complexity of Lattice Problems):

Lecture 3

Lecture 5

Lectures 7 and 8

Major Open Questions: Integer programming in 2^{O(n)} time, Shortest Vectors in n^{o(n)} time and 2^{o(n)} space.

Lectures 9 and 10