Instructors
Vinod Vaikuntanathan
vinodv at csail dot mit dot edu
Office hours: Mon · 2:30–3:30 PM · 32-G696
Shafi Goldwasser
shafi at csail dot mit dot edu
Office hours: By appointment (send an email).
Massachusetts Institute of Technology
Fall 2026 · Graduate course
MIT 6.5620 / 6.875 / 18.425
Foundations of Cryptography
01
About the course
Cryptography gives us a precise technical language to define important notions such as security, privacy and integrity; a mathematical toolkit to construct mechanisms for 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.
This fast-paced graduate course travels from the classical
foundations to recent developments. The emphasis is not only on
constructing mechanisms, but on learning how to state what security
means—and how to prove that a construction achieves it.
Prerequisites: Fluency in algorithms (6.1220), complexity theory (6.1400), and
discrete probability (6.1200). Mathematical maturity and comfort
writing proofs are assumed right from the first lecture.
02
Course information
Teaching assistants
-
Noga Amit
nogamit at mit dot edu
Office hours: Mon · 5:00–6:00 PM · 2-332
-
Zoe Xi
zoexi at mit dot edu
Office hours: Every other Thursday, beginning Sep 24 · 4:30–5:30 PM · 38-166
Review Material
- Sep 10
- Sep 18
- Oct 02
03 Assignments & grading
Grading is based on five problem sets (10%), a midterm exam (30%), a final exam (40%), an oral problem-set review (10%), and class participation (10%).
Oral problem-set review
Each student will meet individually with an instructor to present one problem selected by the instructors from any previously assigned problem set. The problem will not be announced in advance. Students may use their notes during the review. Oral reviews will be scheduled after the midterm and before the final exam.
Problem set
01- Released
- Sep 09
- Due
- Sep 23
Problem set
02- Released
- Sep 23
- Due
- Oct 07
Problem set
03- Released
- Oct 07
- Due
- Oct 28
Problem set
04- Released
- Oct 28
- Due
- Nov 18
Problem set
05- Released
- Nov 18
- Due
- Dec 02
PDF
TeX
Midterm
Fall 2026 midterm
Practice midterm
Submission
Solutions should be typeset in LaTeX and submitted as PDF by 11:59:59 PM ET on the due date.
Late days
Students have ten total late days, with at most five used on any one problem set.
Collaboration
Discussion in groups of up to three is encouraged. Every student must write their own solution and name all collaborators. The final write-up must be entirely in their own words.
Attribution
Published material may be used when acknowledged. Looking for or using solutions from previous years is not permitted.
For the use of AI tools on problem sets, see the AI use policy above.
04
Schedule
Six modules, twenty-five lectures, one midterm exam, and a final exam. Fall classes begin September 9; this course’s final meeting is December 9. Topics remain tentative.
Module 01
Basics & private-key cryptography
Perfect secrecy, computational security, pseudorandomness, and the foundations of symmetric encryption.
Lecture 01
Wed · Sep 09
Introduction & perfect secrecy
Secure communication, Shannon’s definition, the one-time pad, and Shannon’s lower bound.
Additional readings:
- Communication Theory of Secrecy Systems by Claude Shannon
Lecture 02
Mon · Sep 14
Computational security & PRGs
Computational adversaries, pseudorandom generators, and stateful secret-key encryption.
Additional readings:
- How to Generate Cryptographically Strong Sequences of Pseudo-random Bits by Manuel Blum and Silvio Micali
Lecture 03
Wed · Sep 16
Hybrids, PRGs & PRFs
The hybrid argument, PRG length extension, pseudorandom functions, and encryption from PRFs.
Additional readings:
- How To Construct Random Functions by Oded Goldreich, Shafi Goldwasser, and Silvio Micali
Lecture 04
Mon · Sep 21
Pseudorandom functions
Formal PRF security, the GGM construction, and the definition of IND-CPA security.
Additional readings:
- Pseudorandom Functions: Three Decades Later by Andrej Bogdanov and Alon Rosen
Lecture 05
Wed · Sep 23
Hardcore Bits and the Goldreich-Levin Theorem
Hard-core bits, pseudorandom generators, and the Goldreich–Levin theorem.
Additional readings:
- A Generic Hardcore Predicate for Any One-Way Function by Oded Goldreich and Leonid Levin
- List Decoding: Algorithms and Applications by Madhu Sudan (see page 3 for a construction of hardcore predicates from any list-decodable code)
- (advanced) A Pseudorandom Generator from any One-way Function by Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby
Lecture 06
Mon · Sep 28
Secret Key Encryption in Practice
A PRF Construction: The Advanced Encryption Standard (AES). Chosen Ciphertext Security.
Additional readings:
- XOR MACs: New Methods for Message Authentication Using Finite Pseudorandom Functions by Mihir Bellare, Roch Guerin, and Phillip Rogaway
Module 02
Public-key cryptography
Key exchange, public-key encryption, digital signatures, collision-resistant hashing, and identity-based encryption.
Lecture 07
Wed · Sep 30
Public-key cryptography I
Key exchange and the number-theoretic ideas behind it.
Additional readings:
- A Method for Obtaining Digital Signatures and Public-Key Cryptosystems by Ron Rivest, Adi Shamir, and Leonard Adleman
Lecture 08
Mon · Oct 5
Public-key cryptography II
Key exchange, continued, and the hardness assumptions that support it.
Additional readings:
- Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information by Shafi Goldwasser and Silvio Micali
Lecture 09
Wed · Oct 7
Public-key cryptography III
From key exchange to probabilistic public-key encryption.
Additional readings:
- RSA and Rabin Functions: Certain Parts Are as Hard as the Whole by Werner Alexi, Benny Chor, Oded Goldreich, and Claus P. Schnorr
Mon · Oct 12
No lecture · Indigenous Peoples’ DayMonday schedule held Tue · Oct 13
Lecture 10
Tue · Oct 13
Public-key cryptography IV
Learning with Errors, Lattice-based Cryptography, Post-Quantum Security. Monday schedule of classes held Tuesday.
Additional readings:
Lecture 11
Wed · Oct 14
Digital signatures I
Signature syntax, security, and the leftover hash lemma.
Mon · Oct 19
Midterm examRegular time and location: 1:00–2:30 PM, Room 2-190
Lecture 12
Wed · Oct 21
Digital signatures II
Signature constructions and collision-resistant hash functions.
Lecture 13
Mon · Oct 26
Guest Lecture (Yael Kalai)
Commitment Schemes.
Lecture 14
Wed · Oct 28
Guest Lecture (Neekon Vafa)
Secure Storage: Memory Checking and Oblivious RAM
Pset 3 due · Pset 4 out
Module 03
Homomorphic encryption
Fully homomorphic encryption.
Lecture 15
Mon · Nov 02
Fully homomorphic encryption I
—
Lecture 16
Wed · Nov 04
Fully homomorphic encryption II
—
Module 04
Zero knowledge
Proofs that reveal nothing beyond validity.
Lecture 17
Mon · Nov 09
Zero knowledge I
Definitions, examples, simulation, and the knowledge-complexity viewpoint.
—
Wed · Nov 11
No lecture
Veterans Day · Institute holiday
Lecture 18
Mon · Nov 16
Zero knowledge II
Placing NP in zero knowledge and the GMW paradigm.
—
Lecture 19
Wed · Nov 18
Zero knowledge III
Non-interactive zero knowledge, non-malleability, and applications.
Pset 4 due · Pset 5 out—
Module 05
Secure computation
How mutually distrustful parties compute together: from secret sharing to secure multiparty computation.
Lecture 20
Mon · Nov 23
Secure computation: the toolkit
Secret sharing and oblivious transfer.
—
Lecture 21
Wed · Nov 25
The GMW protocol
Secure two-party and multi-party computation in the semi-honest setting.
—
Lecture 22
Mon · Nov 30
Yao’s garbled circuits
—
Lecture 23
Wed · Dec 02
Private Information Retrieval
Pset 5 due—
Lecture 24
Mon · Dec 07
The BGW protocol
Information-theoretic multi-party computation.
—
Module 06
Advanced topics
A view toward the frontiers of modern cryptography.
Lecture 25
Wed · Dec 09
The Frontiers of Cryptography
—
Date · TBA
Final examDate, time, and location to be announced
05
Resources
Previous courses
Textbooks