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



Announcements

Course Information

INSTRUCTOR Vinod Vaikuntanathan
Office: 32-G696
E-mail: vinodv at mit
LOCATION 34-303
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
References
Lecture 3 (Sep 25) Smoothing Parameter and Worst-case to Average-case Reduction for SIS. Notes1 and Notes2 from 2015
and Oded Regev's notes
Lecture 4 (Oct 2) Reductions for LWE (worst-to-average case, search-to-decision etc.) Papers to read:
Oded Regev's 2005 Quantum reduction
Peikert's Classical Reduction
BLPRS Classical Reduction
Oct 9 Columbus Day (No Class)
Lecture 5 (Oct 16) Efficient Lattice-based Crypto: Ring-SIS, Ideal Lattices, Worst-case to average-case reductions, collision-resistant hashing. Lecture and notes by Noah SD.
Lecture 6 (Oct 23) Ring-LWE, Worst-case to average-case reduction, Decision-to-search reduction. The NTRU Cryptosystem. Lecture and notes by Noah SD.
Lecture 7 (Oct 30) Advanced Cryptographic Primitives I: Fully Homomorphic Encryption 2012 survey by Vaikuntanathan
2018 survey by Brakerski
Lecture 8 (Nov 6) Tools: Lattice Trapdoors and Discrete Gaussian Sampling. Applications: Digital Signatures. Papers:
Micciancio-Peikert trapdoor generation
Gentry-Peikert-Vaikuntanathan discrete Gaussian sampling
Lecture 9 (Nov 13) Advanced Cryptographic Primitives II: Identity-based Encryption, Chosen Ciphertext Secure (CCA Secure) Encryption. Papers:
GPV IBE
CHKP IBE
ABB IBE
Lecture 10 (Nov 20) Advanced Cryptographic Primitives III: Attribute-based Encryption and Predicate Encryption
Lecture 11 (Nov 27) Pseudorandom Functions and Variants, Constrained Pseudorandom Functions.
Lecture 12 (Dec 4) Lattices and Quantum Computing: LWE and the Dihedral Hidden Coset Problem, Regev's Worst-case to Average-case Reduction.
Lecture 13 (Dec 11) Project Presentations.


Project Ideas

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

References

 Courses Elsewhere:

Lecture 2