6.876J Advanced Topics in Cryptography Fall 2018
Learning with Errors and Post-Quantum Cryptography


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 lecture notes and papers from the references listed below, and the instructor's notes.
GRADING Based on 1-2 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

The Learning with Errors (LWE) Problem has revolutionized modern cryptography by giving us (a) a basis for post-quantum cryptography, (b) a dizzying variety of cryptographic primitives such as fully homomorphic encryption and signatures, attribute-based and functional encryption, a rich set of pseudorandom functions, various types of program obfuscation and much more; and finally, (c) a unique source of computational hardness with worst-case to average-case connections. This course explores the various facets of the LWE problems and its applications in cryptography.

Prerequisites: 6.045 and 6.046 (or equivalent). Basic Linear Algebra. Knowledge of basic cryptography at the level of 6.875.

Schedule (subject to change)

Lecture Topic References
Lecture 1 (Sep 11) Introduction to SIS and LWE. Basic properties and cryptographic applications: public and private-key encryption and collision-resistant hashing. Instructor notes
Lecture 2 (Sep 18) Algorithms for LWE -- algebraic, combinatorial and geometric. Instructor notes
Lecture 3 (Sep 25)
Lecture 4 (Oct 2)
Oct 9 Columbus Day (No Class)
Lecture 5 (Oct 16)
Lecture 6 (Oct 23)
Lecture 7 (Oct 30)
Lecture 8 (Nov 6)
Lecture 9 (Nov 13)
Lecture 10 (Nov 20)
Lecture 11 (Nov 27)
Lecture 12 (Dec 4)
Lecture 13 (Dec 11)

Project Ideas

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


Courses Elsewhere:

Lecture 2