MIT 6.5630/6.876 (Fall 2024)
Advanced Topics in Cryptography: From Lattices to Program Obfuscation

Course Description

This is a fast-paced advanced graduate course in cryptography, covering two areas that revolutionized the field of cryptography in the last two decades. The first part of the course will develop the modern toolkit of lattice-based cryptography: we will start from the basics and go all the way to the recent results, including constructions of fully homomorphic encryption and attribute-based encryption. The second part of the course will explore definitions, constructions and applications of program obfuscation, culminating in the construction of an indistinguishability obfuscation scheme.

Prerequisites: We will assume fluency in basic cryptography (equivalent to 6.5620). Abundant athematical maturity and an ease with writing mathematical proofs will also be assumed starting from the very first lecture.

Course Information

INSTRUCTOR Vinod Vaikuntanathan
Email: vinodv at csail dot mit dot edu
Office hours: By appointment in 32-G696.
LOCATION AND TIME Monday 1:00-4:00pm (with a coffee break in between) in 34-301
TA Rahul Ilango
Email: rilango at mit dot edu
Office hours: Tuesday 1-2pm. Location: Whiteboard area outside of 32-G696.
RESOURCES The main references will be the course materials, mainly lecture notes. We will also post relevant papers before every lecture. Here are a few supplementary references for the entire course material.

Books and Surveys
  1. A Decade of Lattice Cryptography: Survey by Chris Peikert
  2. Basic Lattice Cryptography: The concepts behind Kyber and Dilithium: Survey by Vadim Lyubashevsky.
Courses and Lecture Notes
  1. Fall 2023 course on the Foundations of Cryptography
  2. Goldreich's "Foundations of Cryptography" Volumes 1 and 2
          for basic cryptographic definitions and theorems.
  3. Oded Regev's 2004 course on lattices at Tel-Aviv University.
  4. Spring 2020 Berkeley course on Lattices, Learning with Errors and Post-Quantum Cryptography
  5. Fall 2015 course on Lattices: Algorithms for and Complexity Theory of Lattice Problems.
ASSIGNMENTS AND GRADING Grading will be based on the problem sets and class participation. There will be 3 problem sets.

Submitting psets:
  • You should typeset your pset answers in LaTeX.
  • PDFs should be e-mailed to advancedcrypto42@gmail.com on or before 11:59:59pm ET on the due date.
Released problem sets: (template files 1 and 2)
  • PSET 1 (PDF | TEX) | Due: Oct 7
  • PSET 2 (PDF | TEX) | Due: Nov 25
  • PSET 3 (PDF) | Due: Dec 11
COLLABORATION POLICY Collaboration is permitted and encouraged in small groups of at most two students. You are free to collaborate in discussing answers, but you must write up solutions on your own, and must specify in your submission the names of any collaborators. Do not copy any text from your collaborators; the writeup must be entirely your work. Do not write down solutions on a board and copy it verbatim into Latex; again, the writeup must be entirely your own words and your own work and should demonstrate clear understanding of the solution. Additionally, you may make use of published material, provided that you acknowledge all sources used. Of course, scavenging for solutions from prior years is forbidden.

Schedule (tentative and subject to change)

Lecture Topic
Part 1: Lattices in Cryptography
Lecture 1 (Mon Sep 9)
Lecturer: Vinod 		Topics covered:
  • The Learning with Errors (LWE) and Short Integer Solutions (SIS) problems
  • Basic Cryptographic Applications: Private-key and Public-key Cryptography, Collision-Resistant Hashing.
References:
Lecture 2 (Mon Sep 16)
Lecturer: Vinod 		Topics covered:
  • Introduction to Lattices.
  • Minkowski's Theorems.
  • LWE, SIS and Lattice Problems.
  • LLL Algorithm for approximate shortest vectors.
References:
Lecture 3 (Mon Sep 23)
Lecturer: Vinod 		Topics covered:
  • Smoothing Lemma.
  • Ajtai's Worst-case to Average-case Reduction for SIS.
  • Regev's Worst-case to Average-case Reduction for LWE.
References:
Lecture 4 (Mon Sep 30)
Lecturer: Vinod 		Topics covered:
  • Fully Homomorphic Encryption.
  • Lattice Trapdoors.
  • Gaussian Sampling.
References:
Lecture 5 (Mon Oct 7)
Lecturer: Vinod 		Topics covered:
  • Digital Signatures and Identity-Based Encryption.
References:
Part 2: Program Obfuscation
Lecture 6 (Mon Oct 21)
Lecturer: Rahul 		Topics covered:
  • Program Obfuscation: Definitions, Impossibility Results.
  • Indistinguishability Obfuscation and Applications Part 1
References:
Lecture 7 (Mon Oct 28)
Lecturer: Vinod 		Topics covered:
  • Applications of Indistinguishability Obfuscation Part 2: The Puncturing Paradigm
References:
Lecture 8 (Mon Nov 4)
Lecturer: Vinod 		Topics covered:
  • The Many Shades of Functional Encryption.
  • Attribute-based Encryption from LWE: the BGG+ Construction
  • Predicate Encryption: Weak and Strong
  • Weak Predicate Encrytion from LWE: the AFV and GVW Constructions
  • Strong Predicate Encryption = Functional Encryption
  • The Notion of XIO; Functional Encryption Implies XIO.
References:
Lecture 9 (Mon Nov 18)
Lecturer: Vinod 		Topics covered:
  • Bootstrapping IO: The AJ/BV Compiler
References:
Lecture 10 (Mon Nov 25)
Lecturer: Vinod 		Topics covered:
  • Jain-Lin-Sahai Construction of IO.
Lecture 11 (Mon Dec 2)
Lecturer: Vinod 		Topics covered:
  • Towards Constructing IO: Bilinear maps and Quadratic Functional Encryption.
Lecture 12 (Mon Dec 9)
Lecturer: Rahul 		Topics covered:
  • Indistinguishability Obfuscation and Complexity Theory.