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

Instructors

Vinod Vaikuntanathan

vinodv at csail dot mit dot edu

Office hours: Wed · 2:30–3:30 PM · 32-G696

Website

Shafi Goldwasser

shafi at csail dot mit dot edu

Office hours: Time TBD · Location TBD

Website

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
Slides -->
Lecture 02

Mon · Sep 14

Computational security & PRGs

Computational adversaries, pseudorandom generators, and stateful secret-key encryption.

Slides -->
Lecture 03

Wed · Sep 16

Hybrids, PRGs & PRFs

The hybrid argument, PRG length extension, pseudorandom functions, and encryption from PRFs.

Slides -->
Lecture 04

Mon · Sep 21

Pseudorandom functions

Formal PRF security, the GGM construction, and the definition of IND-CPA security.

Slides -->
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
Slides -->
Lecture 06

Mon · Sep 28

One-way functions

Hard-core bits, pseudorandom generators, and the Goldreich–Levin theorem.

Slides -->
Lecture 07

Wed · Sep 30

Goldreich–Levin, continued

A complexity-theoretic view of Goldreich–Levin through local list decoding.

Slides -->

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.

Slides -->
Lecture 09

Wed · Oct 07

Public-key cryptography II

Key exchange, continued, and the hardness assumptions that support it.

Pset 2 due · Pset 3 out
Slides -->

Mon · 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.

Slides -->
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.

Slides -->
Lecture 13

Mon · Oct 26

Digital signatures II

Signature constructions and collision-resistant hash functions.

Slides -->
Lecture 14

Wed · Oct 28

Digital signatures III

Hash-and-sign, random oracles, and compact signature schemes.

Pset 3 due · Pset 4 out
Slides -->
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