MIT 6.875 / Berkeley CS 276
Graduate 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 graduate course, intended for beginning graduate students and upper level undergraduates in CS and Math. The required background is general ease with algorithms, elementary number theory and discrete probability equivalent to Berkeley's CS 170, and MIT's 6.042 and 6.046).

Lectures

Welcome to 6.875/CS 276! Lectures will start at 9:30am PT / 12:30pm ET going forward. The Zoom links for lectures will be available on the course Piazza for registered students (including listeners). If you are not already on the course Piazza, please email 6-875-fa20@lists.csail.mit.edu to be added.

Course Information

INSTRUCTORS Raluca Ada Popa
Email: raluca at eecs dot berkeley dot edu

Shafi Goldwasser
Email: shafi at csail dot mit dot edu OR shafi at berkeley dot edu

Vinod Vaikuntanathan
Email: vinodv at csail dot mit dot edu
TAs Ofer Grossman
Email: ogrossma at mit dot edu

Saleet Mossel
Email: saleet at mit dot edu

Nick Ward
Email: npward at berkeley dot edu

Lisa Yang
Email: lisayang at mit dot edu

Rachel Zhang
Email: rachelyz at mit dot edu
LOCATION Zoom link available for registered students
TIME TuTh 12:30-2pm ET / 9:30-11am PT.
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 0 (Tr Aug 27)
Berkeley-only lecture
Introduction
Lecture 1 (Tu Sep 1) Shannon, perfect security and the one-time pad
Lecture Slides
A Communication Theory of Secrecy Systems (by Claude Shannon)
New Directions in Cryptography (by Whitfield Diffie and Martin E. Hellman)
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 Slides (PPTX version)
Lecture 3 (Tu Sep 8) The tool: One-way functions, hard core bits, GL theorem
Lecture Slides (PPTX version)
Goldreich Chapter 2 - Computational Difficulty
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 25 (Th Dec 3) GMW two-party computation
Lecture 26 (Tu Dec 8)
optional for Berkeley
Practical machine learning with MPC