MIT 6.875
Foundations of Cryptography

Course Description

The last few years have witnessed dramatic developments in the foundations of cryptography as well as its applications to real-world privacy and security problems. On the one hand, security and privacy are of paramount importance in the age of big data and mass surveillance. On the other hand, cryptography is abuzz with solutions to long-standing open problems such as fully homomorphic encryption and software obfuscation that use the abundance of data for public good without compromising security. The course will explore both the rich theory of cryptography as well as its real-world applications.

Prerequisites: This is an introductory, but fast-paced, graduate course, intended for beginning graduate students and upper level undergraduates in CS and Math. We will assume fluency in algorithms (equivalent to 6.046), complexity theory (equivalent to 6.045) and discrete probability (equivalent to 6.042).

Course Information

INSTRUCTORS Vinod Vaikuntanathan
Email: vinodv at csail dot mit dot edu
TAs Lalita Devadas
Email: lali at mit dot edu

Sacha Servan-Schreiber
Email: 3s at mit dot edu
LOCATION 4-237
TIME Monday-Wednesday 1:00-2:30pm ET .
Office Hours by appointment
TEXTBOOKS The main references will be the course materials including lecture notes, slides and/or videos. We will also post relevant papers after every lecture. Here are a few supplementary references for the entire course material.
  1. Goldreich, Vol. 1 and 2 (this is a very in-depth study)
  2. Katz-Lindell
  3. Pass-Shelat
PIAZZA We will use Piazza for class communication. Our class Piazza is here. Please ask your questions there, so that other students can see the questions and answers.
ASSIGNMENTS AND GRADING Grading will be based on the problem sets (95%) and class participation (5%). There will be 6 problem sets and your top 5 scores will count towards your grade.
Late day policy: You have a total of 10 late days to use across the 6 psets (max of 5 late days for a single pset). You can use these late days however you'd like - we will use the timestamp of your Gradescope submission to calculate the number of late days.
Submitting psets: Typesetting your pset answers in LaTeX is strongly encouraged. PDFs are to be submitted via Gradescope. Here is a LaTeX template you can use.
COLLABORATION POLICY You are free to collaborate with other students on the homework in discussing answers, but you must write up solutions on your own, and specify in your submission the names of any collaborators. Do not copy any text from your collaborators; the writeup must be entirely your work. 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
Lecture 1 (Tu Sep 1) Shannon, perfect security and the one-time pad
Lecture 2 (Th Sep 3) The computational adversary, definition of computational security, definition of pseudo random generators (informally), and pseudo random generators implies symmetric encryption
Lecture 3 (Tu Sep 8) The tool: One-way functions, hard core bits, GL theorem
Lecture 4 (Th Sep 10) Pseudorandom generators: definition, construction, properties
Lecture Slides (PPTX version)
Goldreich Chapter 3 - Pseudorandom Generators
Pseudorandom Generators notes
Pseudorandom Generators from OWF notes
Blum-Micali paper on cryptographically strong PRG
HILL paper showing OWF implies PSRG
Lecture 5 (Tu Sep 15) Pseudorandom functions: definition, construction, properties
Lecture Slides (PPTX version)
How to Construct Pseudorandom Functions (by Oded Goldreich, Shafi Goldwasser, and Silvio Micali)
How to Construct Pseudorandom Permutations (by Michael Luby and Charles Rackoff)
Lecture 6 (Th Sep 17) Pseudorandom permutations and AES, symmetric key encryption via cipher chaining modes
Lecture Slides
Section 3.7 (on PRPs) of Goldreich Chapter 3
Lecture 7 (Tu Sep 22) Number theory 1: discrete log and MSB (bit), QR, etc.
Lecture Slides (PPTX version)
Number Theory notes (by Dana Angluin)
Generating Random Factored Numbers, Easily (by Adam Kalai)
Lecture 8 (Th Sep 24) Number theory 2: factoring, RSA
Lecture Slides
Blum-Micali paper on cryptographically strong PRG
Shoup paper on finding elliptic curve order
How discreet is the discrete log? (by Avi Widgerson)
Probabilistic encryption (by Shafi Goldwasser and Silvio Micali)
RSA paper
Provable Security notes (by Dana Angluin)
Lecture 9 (Tu Sep 29) Public key encryption I: definition and construction from RSA and Quadratic Residuosity
Lecture Slides (PPTX version)
RSA paper
Diffie-Hellman paper
Merkle paper
Goldwasser-Micali paper
Lecture 10 (Th Oct 1) Public key encryption II: construction from Diffie-Hellman and Learning with Errors
Lecture Slides (PPTX version)
The Learning With Errors Problem (by Oded Regev)
Lecture 11 (Tu Oct 6) Digital signatures and MACs I
Lecture Slides
RSA paper
Lecture 12 (Th Oct 8) Digital signatures and MACs II
Lecture Slides
Lamport's one-time signatures
Naor-Yung signatures
Rompel signatures from OWF
Incremental signatures (by Bellare, Goldreich, and Goldwasser)
Goldwasser-Micali-Rivest signature scheme
Cramer-Shoup signature scheme
Lecture 12b (Tu Oct 13)
Berkeley-only lecture
Merkle Trees and Certificate Transparency
Lecture Slides
Boneh-Shoup notes (Merkle Trees are discussed in Sec. 8.9)
Google talk on Certificate Transparency (video)
The RFC for Certificate Transparency
Lecture 13 (Th Oct 15) Proof of Work, consensus, cryptographic transactions, Bitcoin application
Lecture Slides
The Bitcoin Whitepaper
How the Bitcoin Protocol actually works (optional)
Lecture 14 (Tu Oct 20) Zero knowledge I: definitions and examples
Lecture Slides
Lecture 15 (Th Oct 22) Zero knowledge II: NP in ZK
Lecture Slides
GMR paper
GMW paper
ZK arguments by Brassard et al
ZK proof systems (from Oded Goldreich's book)
Probabilistic Proof Systems by Oded Goldreich
Incremental Cryptography paper
Lecture 16 (Tu Oct 27) NIZK
Lecture Slides (PPTX version)
NIZK paper by Blum, Micali, et al
Multiple NIZK from general assumptions (Feige, Lapidot, Shamir)
New Techniques for NIZK (Groth, Ostrovsky, Sahai)
Fiat-Shamir practice to theory (Canetti, Lombardi, Wichs)
NIZK from LWE (Peikert and Shiehian)
Lecture 17 (Th Oct 29) CCA
Lecture Slides (PPTX version)
CCA Attacks on RSA (Bleichenbacher)
Non-Malleable Cryptography (Dolev, Dwork, Naor)
Lecture 18 (Tu Nov 3) Zcash: privacy-preserving cryptocurrency with zero-knowledge proofs
Lecture Slides
Zerocash (Sections I, II, III-A, III-B, IV)
Lecture 19 (Th Nov 5) Specialized homomorphic encryption, and applications
Lecture Slides
zkLedger (optional reading)
Lecture 20 (Tu Nov 10) Lattices and Learning with Errors
Lecture Slides (PPTX version)
Lecture 21 (Th Nov 12) Fully homomorphic encryption
Lecture Slides (PPTX version)
Vinod's Lecture Notes on Lattices
Lecture 22 (Tu Nov 17) PIR (single-server PIR from FHE)
Lecture Slides (PPTX version)
Lecture 23 (Th Nov 19) Secret sharing
Lecture Slides
Sections 13.3.1 and 13.3.2 (pp. 501-5) of Modern Cryptography by Katz and Lindell — available in Resources (General Resources section) on Piazza
Lecture 24 (Tu Dec 1) Garbled circuits and Yao's two-party computation protocol
Lecture Slides
Proof of Yao's Protocol for Secure 2PC
Lecture 25 (Th Dec 3) GMW two-party computation
Lecture Slides
A Pragmatic Introduction to Secure Multi-Party Computation (see sections 3.2 and 6.5.1)
BGW88 MPC Paper
Lecture 26 (Tu Dec 8)
optional for Berkeley
Practical machine learning with MPC
Lecture Slides
Helen: Maliciously Secure Coopetitive Learning for Linear Models