MIT 6.5620/6.875/18.425 (Fall 2025)
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 Yael Kalai
Email: yaelism at gmail dot com
Office hours: By appointment (send an email). Location: 32-G682.
LOCATION AND TIME Monday and Wednesday 1:00-2:30pm in 2-190
TAs Aparna Gupte
Email: agupte at mit dot edu
Office hours: Thursdays 4:00-5:30pm. Location: 34-304

Andrew Huang
Email: ahuang at mit dot edu
Office hours: Tuesdays 4:00-5:30pm. Location: 34-304

COURSE STAFF EMAIL 6.5620_staff at mit dot edu
REVIEW MATERIALS AND HANDOUTS Probability review: Probability theory handout | Video
Complexity and reductions review: Complexity theory and reductions handout, updated | Video
Handout on non-uniform adversaries: Non-Uniform Computation
RECITATION Number theory review: TBD (sometime in October).
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
  1. Fall 2023 course website
  2. Noah Stephens-Davidowitz's lecture notes
Textbooks
  1. Katz-Lindell
  2. Boneh-Shoup
  3. Pass-Shelat book
  4. Lindell's advanced tutorial on the foundations of crypto.
  5. Mike Rosulek's book "The Joy of Cryptography"
  6. Goldreich's "Foundations of Cryptography" Volumes 1 and 2
PIAZZA We will use Piazza for class communication. Our class Piazza is here. The access code will be posted on the first day of lecture; if you miss lecture, you can watch the beginning of the recording. 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 and midterm exam. There will be 5 problem sets and your top 4 scores will count towards your grade. If you need a short extension on an assignment, we will automatically grant you a 72-hour extension; simply send an email to the course staff at 6.5620_staff at mit dot edu before the assignment is due (preferably earlier, if you can).
If you need more than a 72-hour extension on any assignment, please follow these steps:
  • If you are an undergraduate, please contact S^3 first.
  • If you are a graduate student, please contact your graduate advisor first.
If your S^3 dean or advisor supports the extension request, please have them email the course staff so that we can figure out a plan.

Submitting psets:
  • Psets will be posted on Piazza and on this website. Both a source file and PDF version will be made available for use.
  • All pset writeups should be typeset in LaTeX and compiled into a PDF file for submission.
  • 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.

Released problem sets:
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; again, the writeup must be entirely your own words and your own work and should demonstrate clear understanding of the solution. Solutions should be typeset in LaTeX. You may make use of published material, provided that you clearly acknowledge all sources/tools used. Of course, scavenging for solutions from prior years is forbidden.
USE OF LLMS You may use AI however you wish to deepen your understanding of the lecture material. Upload the notes, talk to your AI about them, ask for more explanation or examples; it's all fine. You may not use LLMs in any way to work on your homework. You may not upload assignments, ask for hints, ask how certain concepts from the lectures might be applied to specific homework problems, or upload your assignments to check for correctness or clarity or anything else. You may not include any AI generated content whatsoever in your homework submissions. If it becomes clear that you have used an AI tool when working on your homework (either directly by making edits or to ask for hints/solutions), we may mark your grade down to reflect that.

Schedule (tentative and subject to change)



Lecture Topic
Module 1: Private-Key Cryptography
Lecture 1 (Wed Sep 3)
Perfectly Secure Encryption

Resources:
Lecture Notes (PDF) and Lecture Recording

Topics covered:
  • Introduction to cryptography.
  • Definition of perfectly secure encryption.
  • The one-time pad construction.
  • Impossibility for many-time security.
Recommended reading:
Fri Sep 5: HW #1 out
Lecture 2 (Mon Sep 8) Computational Security

Resources:
Lecture Notes (PDF) and Lecture Recording

Topics covered:
  • How to circumvent Shannon’s lower bound: the computational adversary.
  • Definition of computational security and negligible functions.
  • Definition of CPA-secure encryption.
  • Definition of one-way functions.
  • Introduction to pseudorandom generators.
Recommended reading:
Lecture 3 (Wed Sep 10) Pseudorandom Generators (PRGs)

Resources:
Lecture Notes (PDF) and Lecture Recording

Topics covered:
  • Definition of PRG.
  • Stateful encryption from PRGs.
  • PRG length extension.
Recommended reading:
Lecture 4 (Mon Sep 15) Constructing PRGs

Resources:
Lecture Notes (PDF) and Lecture Recording

Topics covered:
  • Increasing PRG stretch.
  • Constructing PRGs from one-way permutations.
  • Definition of hardcore predicates.
  • The Goldreich-Levin hardcore predicate.
Lecture 5 (Wed Sep 17) Goldreich-Levin, cont.

Resources:
Lecture Notes (PDF)

Topics covered:
  • Proof of Goldreich-Levin.
Recommended reading:
Fri Sep 19: HW #1 due
Lecture 6 (Mon Sep 22)
Pseudorandom Functions (PRFs)
Lecture 7 (Wed Sep 24) Message Authentication Codes (MACs)
Fri Sep 26: HW #2 out
Lecture 8 (Mon Sep 29) Construction of CCA-secure Encryption
Module 2: Public-Key Cryptography
Lecture 9 (Wed Oct 1) Key Exchange
Lecture 10 (Mon Oct 6)
Public-Key Encryption
Lecture 11 (Wed Oct 8) Construction of Public-Key Encryption from LWE
Fri Oct 10: HW #2 due, HW #3 out
No lecture (Mon Oct 13)
Indigenous Peoples' Day
Lecture 12 (Wed Oct 15)
Fully Homomorphic Encryption I
Lecture 13 (Mon Oct 20)
Fully Homomorphic Encryption II
Lecture 14 (Wed Oct 22)
Digital Signatures I
Fri Oct 24: HW #3 due
Lecture 15 (Mon Oct 27)
Digital Signatures II
Lecture 16 (Wed Oct 29)
Digital Signatures III
Midterm (Mon Nov 3)
Module 3: Proofs
Lecture 17 (Wed Nov 5) Zero-Knowledge Proofs I
No lecture (Mon Nov 10)
Student holiday, HW #4 out
Lecture 18 (Wed Nov 12)
Zero-Knowledge Proofs II
Lecture 19 (Mon Nov 17) Non-Interactive ZK (NIZK)
Lecture 20 (Wed Nov 19)
Succinct Proofs I
Lecture 21 (Mon Nov 24)
HW #4 due, HW #5 out 		Succinct Proofs II
Module 4: Secure Computation
Lecture 22 (Wed Nov 26)
Secure Multi-Party Computation I
Lecture 23 (Mon Dec 1)
Secure Multi-Party Computation II
Lecture 24 (Wed Dec 3)
Yao's Garbled Circuits
Module 5: Special Topics
Lecture 25 (Mon Dec 8)
HW #5 due 		Quantum Cryptography
Lecture 26 (Wed Dec 10) TBD