Announcements

Problem set 1 is posted; due October 24. [pdf | tex | style file]

Course Information

INSTRUCTOR	Vinod Vaikuntanathan Office: 32-G696 E-mail: vinodv at mit
LOCATION	4-237
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 λ₁, 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)	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)

References

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

Oded Regev's course at Tel-Aviv University. The material in this course will be our primary reference.
Daniele Micciancio's course at UCSD.
Cynthia Dwork's course at Stanford.
Chris Peikert's course at Georgia Tech.

Lecture 3

The "LLL+25" book commemmorating the 25th anniversary of the LLL algorithm is available via MIT libraries. Check it out for several cool papers on the state of the art (ca. 2007) in lattice basis reduction and the complexity of lattice problems.
The Goldreich-Micciancio-Safra-Seifert paper on an approximation preserving reduction from SVP to CVP.
Micciancio's reductions paper from SODA is cool and has a comprehensive overview of reductions between several lattice problems.

Lecture 5

Dan Boneh's Survey on Cryptanalysis of RSA variants
Alexander May's survey is a bit more up to date. This is also a chapter in the LLL+25 book.
Coppersmith's original paper.

Lectures 7 and 8

The Voronoi Walk SVP algorithm of Micciancio and Voulgaris.
Shorter paths on the Voronoi graph.
Two new papers (from STOC and FOCS this year) that solve Shortest and Closest Vectors respectively in 2^n time.
Two heuristic algorithms (here and here) for SVP and CVP that are conjectured to run better than 2^n.

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

Haviv-Regev randomized quasi-NP-hardness of SVP within 2^{(log n)^1-ε} factor.
Dinur-Kindler-Raz-Safra NP-hardness of CVP within 2^{(log n)^1-ε} factor.
Towards derandomizing the SVP NP-hardness reduction.