6.876J Advanced Topics in Cryptography: Lattices (Fall 2017)
Old Website: No Longer Maintained

# 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 λ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)

# 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

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