Instructors
Vinod Vaikuntanathan
vinodv at csail dot mit dot edu
Office hours: Wed · 2:30–3:30 PM · 32-G696
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: Time TBD · Location TBD
Review Material
-
Sep 10
Probability review Time TBD · Location TBD
-
Sep 18
Complexity & reductions Time TBD · Location TBD
-
Oct 02
Number theory review Time TBD · Location TBD
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
PDF
TeX
Problem set
02- Released
- Sep 23
- Due
- Oct 07
PDF
TeX
Problem set
03- Released
- Oct 07
- Due
- Oct 28
PDF
TeX
Problem set
04- Released
- Oct 28
- Due
- Nov 18
PDF
TeX
Problem set
05- Released
- Nov 18
- Due
- Dec 02
PDF
TeX
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
Five 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.
Pset 1 out
Lecture 02
Mon · Sep 14
Computational security & PRGs
Computational adversaries, pseudorandom generators, and stateful secret-key encryption.
Lecture 03
Wed · Sep 16
Hybrids, PRGs & PRFs
The hybrid argument, PRG length extension, pseudorandom functions, and encryption from PRFs.
Lecture 04
Mon · Sep 21
Pseudorandom functions
Formal PRF security, the GGM construction, and the definition of IND-CPA security.
Lecture 05
Wed · Sep 23
Authentication & chosen-ciphertext security
Identification protocols, message-authentication codes, and CCA-secure symmetric encryption.
Pset 1 due · Pset 2 out
Lecture 06
Mon · Sep 28
One-way functions
Hard-core bits, pseudorandom generators, and the Goldreich–Levin theorem.
Lecture 07
Wed · Sep 30
Goldreich–Levin, continued
A complexity-theoretic view of Goldreich–Levin through local list decoding.
Module 02
Public-key cryptography
Key exchange, public-key encryption, signatures, and collision-resistant hashing.
Lecture 08
Mon · Oct 05
Public-key cryptography I
Key exchange and the number-theoretic ideas behind it.
Lecture 09
Wed · Oct 07
Public-key cryptography II
Key exchange, continued, and the hardness assumptions that support it.
Pset 2 due · Pset 3 outMon · Oct 12
No lecture · Indigenous Peoples’ DayMonday schedule held Tue · Oct 13
Lecture 10
Tue · Oct 13
Public-key cryptography III
From key exchange to probabilistic public-key encryption. Monday schedule of classes held Tuesday.
Lecture 11
Wed · Oct 14
Public-key encryption IV
Trapdoor permutations, RSA, and further constructions for public-key encryption.
—
Mon · Oct 19
Midterm examTime and location to be announced
Lecture 12
Wed · Oct 21
Digital signatures I
Signature syntax, security, and the leftover hash lemma.
Lecture 13
Mon · Oct 26
Digital signatures II
Signature constructions and collision-resistant hash functions.
Lecture 14
Wed · Oct 28
Digital signatures III
Hash-and-sign, random oracles, and compact signature schemes.
Pset 3 due · Pset 4 out
Lecture 15
Mon · Nov 02
Identity-based encryption
—
Module 03
Zero knowledge
Proofs that reveal nothing beyond validity, from interactive definitions to non-interactive systems.
Lecture 16
Wed · Nov 04
Zero knowledge I
Definitions, examples, simulation, and the knowledge-complexity viewpoint.
—
Lecture 17
Mon · Nov 09
Zero knowledge II
Placing NP in zero knowledge and the GMW paradigm.
—
Wed · Nov 11
No lecture
Veterans Day · Institute holiday
Lecture 18
Mon · Nov 16
Zero knowledge III
Non-interactive zero knowledge, non-malleability, and applications.
—
Module 04
Secure computation
How mutually distrustful parties compute together: from secret sharing to fully homomorphic encryption.
Lecture 19
Wed · Nov 18
Secure computation: the toolkit
Secret sharing and oblivious transfer.
Pset 4 due · Pset 5 out—
Lecture 20
Mon · Nov 23
The GMW protocol
Secure two-party and multi-party computation in the semi-honest setting.
—
Lecture 21
Wed · Nov 25
Yao’s garbled circuits
—
Lecture 22
Mon · Nov 30
Fully homomorphic encryption I
—
Lecture 23
Wed · Dec 02
Fully homomorphic encryption II
Pset 5 due—
Lecture 24
Mon · Dec 07
The BGW protocol
Information-theoretic multi-party computation.
—
Module 05
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
Lecture notes
Textbooks
