6.876J Advanced Topics in Cryptography Fall 2018
Learning with Errors and PostQuantum Cryptography
INSTRUCTOR  Vinod Vaikuntanathan
Office: 32G696 Email: vinodv at mit 
LOCATION  34303

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 12 problem sets and a final project. 
Lecture  Topic  References 
Lecture 1 (Sep 11)  Introduction to SIS and LWE. Basic properties and cryptographic applications: public and privatekey encryption and collisionresistant hashing.  Instructor notes 
Lecture 2 (Sep 18)  Algorithms for LWE  algebraic, combinatorial and geometric. 
Instructor notes References 
Lecture 3 (Sep 25)  Smoothing Parameter and Worstcase to Averagecase Reduction for SIS. 
Notes1 and Notes2 from 2015 and Oded Regev's notes 
Lecture 4 (Oct 2)  Reductions for LWE (worsttoaverage case, searchtodecision 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 Latticebased Crypto: RingSIS, Ideal Lattices, Worstcase to averagecase reductions, collisionresistant hashing.  Lecture and notes by Noah SD. 
Lecture 6 (Oct 23)  RingLWE, Worstcase to averagecase reduction, Decisiontosearch 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: MicciancioPeikert trapdoor generation GentryPeikertVaikuntanathan discrete Gaussian sampling 
Lecture 9 (Nov 13)  Advanced Cryptographic Primitives II: Identitybased Encryption, Chosen Ciphertext Secure (CCA Secure) Encryption. 
Papers: GPV IBE CHKP IBE ABB IBE 
Lecture 10 (Nov 20)  Advanced Cryptographic Primitives III: Attributebased 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 Worstcase to Averagecase Reduction.  
Lecture 13 (Dec 11)  Project Presentations. 