MIT 6.875 (Fall 2021)
Foundations of Cryptography

Course Description

The field of cryptography gives us a technical language to define important real-world problems such as security, privacy and integrity, a mathematical toolkit to construct mechanisms such as encryption, digital signatures, zero-knowledge proofs, homomorphic encryption and secure multiparty computation, and a complexity-theoretic framework to prove security using reductions that together help us enforce the rules of the road in digital interactions.

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. For example, cryptography is abuzz with solutions to long-standing open problems such as fully homomorphic encryption and software obfuscation that use an abundance of data for public good without compromising security.

The course will explore the rich theory of cryptography all the way from the basics to the recent developments.

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). Mathematical maturity and an ease with writing mathematical proofs will be assumed starting from the first lecture.

Course Information

INSTRUCTOR	Vinod Vaikuntanathan Email: vinodv at csail dot mit dot edu
LOCATION AND TIME	Monday and Wednesday 1:00-2:30pm in 4-237
TAs	Lali Devadas Email: lali at mit dot edu Office hours: Monday 5-6pm in 24-310, Tuesday 10-11am in 34-304 Sacha Servan-Schreiber Email: 3s at mit dot edu Office hours: Tuesday 6-7pm in 24-310, Friday 12-1pm in 24-310 Aparna Gupte Email: agupte at mit dot edu Office hours: Wednesday 12-1pm in 26-314
RECITATIONS	Probability review: Friday September 10 12-1pm in 24-310 [Probability theory handout] Complexity and reductions review: Friday September 17 12-1pm in 24-310 [Complexity theory handout] Number theory review: Friday October 1 12-1pm in 24-310 [Number theory handout]
RESOURCES	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. Lecture notes Pass-shelat Textbooks Katz-Lindell Boneh-Shoup Goldreich Rosulek Lindell's advanced tutorial on the foundations of crypto.
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. You have a total of 10 late days to use across the 6 psets (max of 5 late days for any single pset). You can use these late days however you like; we will use the timestamp of your Gradescope submission to calculate the number of late days. Submitting psets: You should typeset your pset answers in LaTeX. PDFs are to be submitted via Gradescope. Here is a LaTeX template you can use.
COLLABORATION POLICY	Collaboration is permitted and encouraged in smallgroups of at most three. You are free to collaborate 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
	Module 1.
Lecture 1 (Wed Sep 8) HW #1 out	Resources: Lecture video and slides. Topics covered: Introduction to cryptography. Secure Communication and Shannon’s definitions of perfect secrecy. The One-time pad construction. Shannon’s lower bound. Recommended reading: Communication Theory of Secrecy Systems by Claude Shannon
Lecture 2 (Mon Sep 13)	Resources: Lecture video and slides. Topics covered: How to circumvent Shannon’s lower bound: the computational adversary. Definition of computational security. The definition of pseudorandom generators (PRG). Pseudorandom generators imply (stateful) secret-key encryption. Recommended reading: New Directions in Cryptography by Whitfield Diffie and Martin Hellman
Lecture 3 (Wed Sep 15)	Resources: Lecture video and slides. Topics covered: The Hybrid Argument. An application: PRG length extension. The notion of pseudorandom functions: Definition, motivation, discussion and comparison with PRGs. PRFs imply secret-key encryption. Recommended reading: How to Generate Cryptographically Strong Sequences of Pseudo-random Bits by Manuel Blum and Silvio Micali How To Construct Random Functions by Oded Goldreich, Shafi Goldwasser, and Silvio Micali
Lecture 4 (Mon Sep 20)	Resources: Lecture video and slides. Topics covered: The Goldreich-Goldwasser-Micali (GGM) PRF construction. TOC (Theory of Computation) perspectives on pseudorandomness (if time permits). Recommended reading: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata by Michael Kearns and Leslie Valiant. Pseudorandom Functions: Three Decades Later by Andrej Bogdanov and Alon Rosen. Advanced reading: Natural Proofs by Alexander Razborov and Steven Rudich
Lecture 5 (Wed Sep 22) HW #2 out	Resources: Lecture video and slides and lecture notes. Topics covered: Authentication and message-authentication codes (MAC). Universal hash functions and one-time MAC. Pseudorandom functions and many-time MAC. Chosen ciphertext secure symmetric key encryption. Recommended reading: Lecture Notes on the Complexity of Some Problems in Number Theory by Dana Angluin. Advanced reading: Generating Random Factored Numbers, Easily by Adam Kalai. PRIMES in P by Manindra Agrawal, Neeraj Kaya, and Nitin Saxena.
HW #1 due Fri Sep 24	Module 2.
Lecture 6 (Mon Sep 27)	Resources: Lecture video and lecture notes. Topics covered: The tool: One-way functions and its properties. Hard core bits and PRG. Goldreich-Levin theorem. A TCS perspective on GL theorem: local list decoding (if time permits) An example: factoring which leads us to weak OWF and hardness amplification. Recommended reading (same as last time): Lecture Notes on the Complexity of Some Problems in Number Theory by Dana Angluin. Advanced reading (same as last time): Generating Random Factored Numbers, Easily by Adam Kalai. PRIMES in P by Manindra Agrawal, Neeraj Kaya, and Nitin Saxena.
Lecture 7 (Wed Sep 29)	Resources: Lecture video and slides. Topics covered: Primes, Z_p* and its properties. Computations: what is easy and what is hard. The Discrete log problem and a candidate OWF. Hardcore bit of Diffie-Hellman. A TCS perspective: Random self-reduction and Hardness amplification. Diffie-Hellman assumption and PRGs. Diffie-Hellman and PRFs --- Naor-Reingold.
	Module 3.
Lecture 8 (Mon Oct 4)	Resources: Lecture video and slides. Topics covered: Public-key Encryption and Key exchange. Definitions: Semantic Security and IND-CPA. Trapdoor permutations.
Lecture 9 (Wed Oct 6) HW #2 due, HW #3 out	Resources: Lecture video and slides. Topics covered: Composites, factoring. RSA, trapdoor permutations and another public-key cryptosystem. QRA, Goldwasser-Micali and Homomorphism. Advanced reading: A Minimalist Proof of the Law of Quadratic Reciprocity by Bogdan Veklych. Probabilistic Encryption by Shafi Goldwasser and Silvio Micali.
No lecture (Mon Oct 11) Indigenous Peoples' Day
Lecture 10 (Wed Oct 13)	Resources: Lecture video and slides. Topics covered: Motivation for Digital Signatures. Definition: EUF-CMA Security One-time signatures or, how to sign a single bit: Lamport’s Scheme. Collision-resistant hashing and how to sign polynomially many bits, once.
Lecture 11 (Mon Oct 18)	Resources: Lecture video and slides. Topics covered: Many-time, stateful, signature schemes. Naor-Yung construction: stateless EUF-CMA-secure signature schemes. Recommended reading (same as last time): Goldwasser-Micali-Rivest Signature Scheme by Shafi Goldwasser, Silvio Micali, and Ron Rivest. Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme by Oded Goldreich Universal One-way Hash Functions and their Cryptographic Applications by Moni Naor and Moti Yung. Advanced reading: SPHINCS: ractical stateless hash-based signatures. by Bernstein et al. (A modern version of the signature scheme from this lecture.) Post-Quantum Cryptography by NIST. See also: SPHINCS+
Lecture 12 (Wed Oct 20)	Resources: Lecture video and slides. Topics covered: Direct Constructions: Trapdoor Permutation and the Hash-and-Sign Paradigm. Random Oracles.
	Module 4.
Lecture 13 (Mon Oct 25)	Resources: Lecture video and slides. Topics covered: Zero knowledge I, definitions and example
Lecture 14 (Wed Oct 27) HW #3 due, HW #4 out	Resources: Lecture video and slides.
Lecture 15 (Mon Nov 1)	Resources: Lecture video and slides. Recommended reading: ZK for NP by Oded Goldreich, Silvio Micali, and Avi Wigderson. Efficient Signature Generation by Smart Cards by C.P. Schnorr. Advanced reading: How to Prove Yourself by Amos Fiat and Adi Shamir. On the Composition of Zero-Knowledge Proof Systems by Oded Goldreich and Hugo Krawczyk. Constant-round ZK for NP by Oded Goldreich and Ariel Kahan. On Defining Proofs of Knowledge by Mihir Bellare and Oded Goldreich.
Lecture 16 (Wed Nov 3)	Resources: Lecture video and slides. Recommended reading: Non-interactive Zero-knowledge by Manuel Blum, Alfredo se Santis, Silvio Micali, and Giuseppe Persiano. E-mail and the unexpected power of interaction by Laszlo Babai.
Lecture 17 (Mon Nov 8)	Resources: Lecture video and slides and lecture notes. Recommended reading: New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs by Mihir Bellare and Shafi Goldwasser. Non-Malleable Cryptography by Danny Dolev, Cynthia Dwork and Moni Naor .
	Module 5.
Lecture 18 (Wed Nov 10) HW #4 due, HW #5 out	Resources: Lecture video and slides and lecture notes. Advanced reading: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography by Oded Regev.
Lecture 19 (Mon Nov 15)	Resources: Lecture video and slides and lecture notes. Advanced reading: Efficient Fully Homomorphic Encryption from (Standard) LWE by Zvika Brakerski and Vinod Vaikuntanathan. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based by Craig Gentry, Amit Sahai and Brent Waters. Hardness of LWE on General Entropic Distributions by Zvika Brakerski and Nico Döttling. Delegating Computation: Interactive Proofs for Muggles by Shafi Goldwasser, Yael Kalai and Guy Rothblum. Homomorphic Encryption: from Private-Key to Public-Key by Ron Rothblum.
Lecture 20 (Wed Nov 17)	Resources: Lecture video and slides.
	Module 6.
Lecture 21 (Mon Nov 22) HW #5 due, HW #6 out	Resources: Lecture video and slides. Topics covered: Oblivious Transfer. Private Information Retrieval. Recommended reading: How to Exchange and Generate Secrets by Andrew Chi-Chih Yao Private Information Retrieval by Benny Chor Oded Goldreich Eyal Kushilevitz and Madhu Sudan
Lecture 22 (Mon Nov 29)	Resources: Lecture video and slides. Recommended reading: How To Play Any Mental Game by Oded Goldreich, Silvio Micali, and Avi Wigderson Extending Oblivious Transfers Efficiently by Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank Correlated Pseudorandomness and the Complexity of Private Computations by Donald Beaver Advanced reading: Bar-Ilan Winter School on MPC
Lecture 23 (Wed Dec 1)	Resources: Lecture video and slides. Recommended reading: Simplified VSS and Fast-track Multiparty Computations with Applications to Threshold Cryptography by Rosario Gennaro, Michael O. Rabin, and Tal Rabin Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation by Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson NIST Kick-Starts ‘Threshold Cryptography’ Development Effort
Lecture 24 (Mon Dec 6) HW #6 due	Resources: Lecture video.
Lecture 25 (Wed Dec 8)