MIT 6.5620/6.875/18.425 (Fall 2023)
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. Together, they 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 Office hours: Fridays, 4-5pm. Location: 32-G696.
LOCATION AND TIME	Monday and Wednesday 1:00-2:30pm in 1-190
TAs	Chirag Falor Email: cfalor at mit dot edu Office hours: Sun 11-12 noon. Location: 24-307. Neekon Vafa Email: nvafa at mit dot edu Office hours: Tuesdays 5:30-7:30pm. Location: 36-155. Hanshen Xiao Email: hsxiao at mit dot edu Office hours: Mon 4-6 pm. Location: 36-155.
RECITATIONS	Probability review: Friday, September 8, 4-5:30pm in 4-159. Probability theory handout \| Video Complexity and reductions review: Friday, September 15, 4-5:30pm in 4-159. Complexity theory and reductions handout, updated \| Video Number theory review: Friday, October 6, 4-5:30pm in 4-159. Number theory handout \| Dana Angluin's notes \| Keith Conrad's note on the cyclicity of Zp*
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 Fall 2022 course website Mike Rosulek's book "The Joy of Cryptography" Goldreich's "Foundations of Cryptography" Volumes 1 and 2 Textbooks Katz-Lindell Boneh-Shoup Pass-Shelat book 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, midterm exam, and class participation. 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 on or before 11:59:59pm ET on the due date. The Gradescope access code is available on the course information page on Piazza. Solutions will be posted on piazza. Released problem sets: PSET 1 (PDF), (Source) \| Released: Sep 06, 11:59pm \| Due: Sep 20, 11:59pm ET PSET 2 (PDF), (Source) \| Released: Sep 20, 11:59pm \| Due: Oct 04, 11:59pm ET PSET 3 (PDF), (Source) \| Released: Oct 04, 11:59pm \| Due: Oct 18, 11:59pm ET PSET 4 (PDF), (Source) \| Released: Oct 18, 11:59pm \| Due: Nov 08, 11:59pm ET (Because of the midterm, you have three weeks instead of the usual two.) PSET 5 (PDF), (Source) \| Released: Nov 9, 11:59pm \| Due: Nov 20, 11:59pm ET (Because of the Thanksgiving, HW5 is due 2 days earlier than usual.) PSET 6 (PDF), (Source) \| Released: Nov 20, 11:59pm \| Due: Dec 4, 11:59pm ET
COLLABORATION POLICY	Collaboration is permitted and encouraged in small groups of at most three 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
	Module 1: Basics and Private-Key Cryptography
Lecture 1 (Wed Sep 6) HW #1 out	Resources: Slides, Slides (PDF), and lecture video. 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 The Cryptographic Lens: Visions of our Past and Future by Shafi Goldwasser \| Slides 2011 Kilian Prize Lecture at MIT: "The Growth of Cryptography" by Ron Rivest
Lecture 2 (Mon Sep 11)	Resources: Slides, Slides (PDF), and lecture video. 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: How to Generate Cryptographically Strong Sequences of Pseudo-random Bits by Manuel Blum and Silvio Micali Chapter 3 of Goldreich's "Foundations of Cryptography".
Lecture 3 (Wed Sep 13)	Resources: Slides, Slides (PDF), and lecture video. 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 18)	Resources: Slides, Slides (PDF), and lecture video. Topics covered: Formal definition of PRF security. The Goldreich-Goldwasser-Micali (GGM) PRF construction. Definition of IND-CPA secure encryption. Recommended reading: Pseudorandom Functions: Three Decades Later by Andrej Bogdanov and Alon Rosen. Advanced reading: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata by Michael Kearns and Leslie Valiant. Natural Proofs by Alexander Razborov and Steven Rudich
Lecture 5 (Wed Sep 20) HW #1 due, HW #2 out	Resources: Slides, Slides (PDF), and lecture video. Topics covered: Identification protocols. Authentication and message-authentication codes (MAC). Chosen ciphertext secure symmetric key encryption. Recommended reading: XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions by Mihir Bellare, Roch Guerin, Phillip Rogaway.
Lecture 6 (Mon Sep 25)	Resources: Slides, Slides (PDF), and lecture video. Topics covered: One-way functions and its properties. Hard core bits and PRG. Goldreich-Levin theorem. Recommended reading: A generic hardcore predicate for any one-way function Oded Goldreich and Leonid Levin Goldreich's "Foundations of Cryptography" Volume 1, Chapter 2.5 Advanced reading List Decoding: Algorithms and Applications by Madhu Sudan. (See Page 3 for a construction of hardcore predicates from any list-decodable code.) A Pseudorandom Generator from any One-way Function by Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby. Counting Unpredictable Bits: A Simple PRG from One-way Functions by Noam Mazor and Rafael Pass. Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions by Salil Vadhan and Colin Jia Zheng.
Lecture 7 (Wed Sep 27)	Resources: Slides, Slides (PDF), and lecture video. Topics covered: Goldreich-Levin Theorem (contd.) A TCS perspective on GL theorem: local list decoding (if time permits).
	Module 2: Public-Key Cryptography
Lecture 8 (Mon Oct 2)	Public-Key Cryptography I: Key Exchange Resources: Slides, Slides (PDF) and lecture video. Advanced reading: Generating Random Factored Numbers, Easily by Adam Kalai.
Lecture 9 (Wed Oct 4) HW #2 due, HW #3 out	Public-Key Cryptography II: Key Exchange Resources: Slides, Slides (PDF) and lecture video. Advanced reading: RSA and Rabin Functions: Certain Parts Are as Hard as the Whole by Werner Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr.
No lecture (Mon Oct 9) Indigenous Peoples' Day
Lecture 10 (Wed Oct 11)	Public-Key Cryptography III Resources: Slides, Slides (PDF) and lecture video.
Lecture 11 (Mon Oct 16)	Digital Signatures I Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Lecture Notes on the Leftover Hash Lemma by Ronitt Rubinfeld.
Lecture 12 (Wed Oct 18) HW #3 due, HW #4 out	Digital Signatures II (+Collision-Resistant Hash Functions) . Resources: Slides, Slides (PDF) and lecture video.
Lecture 13 (Mon Oct 23)	Digital Signatures III Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Secure Hash-and-Sign Signatures without the Random Oracle by Rosario Gennaro, Shai Halevi and Tal Rabin. Random Oracles are Practical: A Paradigm for Designing Efficient Protocols by Mihir Bellare and Phillip Rogaway. Advanced reading: Short signatures from the Weil pairing by Dan Boneh, Ben Lynn, and Hovav Shacham. Short and Stateless Signatures from the RSA Assumption by Susan Hohenberger and Brent Waters.
Midterm (Wed Oct 25)	No class. Midterm Exam 7-9pm in 1-190, covering material upto (and including) Lecture 12
	Module 3: Zero Knowledge
Lecture 14 (Mon Oct 30)	Zero knowledge I: Definitions and Examples. Resources: Slides, Slides (PDF) and lecture video. Recommended reading: The knowledge complexity of interactive proof-systems by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. Chapters 4.1-4.3 of Oded Goldreich's "Foundations of Cryptography" (Volume 1).
Lecture 15 (Wed Nov 1)	Zero knowledge II: NP in ZK Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Proofs that Yield Nothing But Their Validity or All Langauges in NP Have Zero-Knowledge Proof Systems by Oded Goldreich, Silvio Micali, and Avi Wigderson. Chapters 4.4 of Oded Goldreich's "Foundations of Cryptography" (Volume 1). Advanced reading: Alex Lombardi's Course on Cryptographic Proofs (Fall 2019).
Lecture 16 (Mon Nov 6)	Zero knowledge III: Non-Interactive ZK and Applications Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Non-interactive Zero Knowldege by Manuel Blum, Alfredo De Santis and Silvio Micali. Non-Malleable Cryptography by Danny Dolev, Cynthia Dwork and Moni Naor. Advanced reading: Alex Lombardi's Course on Cryptographic Proofs (Fall 2019).
	Module 4: Secure Computation
Lecture 17 (Wed Nov 8) HW #4 due, HW #5 out	Secure Computation. Tools: Secret Sharing and Oblivious Transfer Resources: Slides, Slides (PDF) and lecture video.
Lecture 18 (Mon Nov 13)	Goldreich-Micali-Wigderson (GMW) Secure Two-Party and Multi-Party Computation Protocol. Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Chapter 7 of Oded Goldreich's "Foundations of Cryptography" (Volume 2) Advanced reading: Bar-Ilan Winter School on MPC
Lecture 19 (Wed Nov 15)	Secure Two-Party Computation (Continued), Malicious Security. Resources: Slides, Slides (PDF) and lecture video. Advanced reading: Limits on the Security of Coin Flips When Half the Processors are Faulty How to play any mental game
Lecture 20 (Mon Nov 20) HW #5 due, HW #6 out	Yao's Garbled Circuits. Resources: Slides, Slides (PDF) and lecture video. Recommended reading: Additional material on garbled circuits from last year's class (from Matthew Hong): Slides, PDF Andrew Yao's original paper on garbled circuits and Yehuda Lindell and Benny Pinkas' formal proof of security.
Lecture 21 (Wed Nov 22)	Merkle Trees and Oblivious RAM. [Given by TA Neekon Vafa] Resources: Slides (Keynote), Slides (PDF) and lecture video.
Lecture 22 (Mon Nov 27)	Fully Homomorphic Encryption (Part 1) Resources: Slides, Slides (PDF) and lecture video.
Lecture 23 (Wed Nov 29)	Fully Homomorphic Encryption (Part 2) Resources: Slides, Slides (PDF) and lecture video. [Same slides as last lecture.]
Lecture 24 (Mon Dec 4) HW #6 due	Succinct ZK arguments. Resources: Lecture video. Recommended reading: A note on efficient zero-knowledge proofs and arguments by Joe Killian Universal arguments and their applications by Boaz Barak and Oded Goldreich On interactive proofs with a laconic prover by Oded Goldreich, Salil Vadhan and Avi Wigderson
	Module 5: Advanced Topics
Lecture 25 (Wed Dec 6)	Program Obfuscation Resources: Main slides (Keynote), Main slides (PDF), Part 2 slides (Powerpoint), Part 2 slides (PDF) and lecture video. Recommended reading: Vinod's STOC tutorial slides on obsufcation (Powerpoint, PDF). Advanced reading: On the (Im)possibility of Obfuscating Programs by Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. Indistinguishability Obfuscation from LPN over F_p, DLIN, and PRGs in NC^0 by Aayush Jain, Huijia Lin, and Amit Sahai.
Lecture 26 (Mon Dec 11)	Guest Lecture: Tina Zhang on Quantum Cryptography Resources: Lecture video.
Lecture 27 (Wed Dec 13)	Guest Lecture: Rahul Ilango on The Complexity-Theoretic Foundations of Cryptography Resources: Lecture video.