MIT 6.5620/6.875/18.425 (Fall 2025)
Foundations of Cryptography
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: TBD. Andrew Huang Email: ahuang at mit dot edu Office hours: Tuesdays 4:00-5:30pm. Location: TBD. |
COURSE STAFF EMAIL | 6.5620staff at gmail dot com |
REVIEW MATERIALS |
Probability review: Probability theory handout | Video Complexity and reductions review: Complexity theory and reductions handout, updated | Video |
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 Textbooks
|
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.5620staff at gmail dot com 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:
Submitting psets:
|
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:
|
Fri Sep 5: HW #1 out | |
Lecture 2 (Mon Sep 8) | Computational Security |
Lecture 3 (Wed Sep 10) | Constructing PRGs |
Lecture 4 (Mon Sep 15) | Goldreich-Levin Theorem (cont.) |
Lecture 5 (Wed Sep 17) |
Pseudorandom Functions (PRFs) |
Fri Sep 19: HW #1 due | |
Lecture 6 (Mon Sep 22) | Message Authentication Codes (MACs) |
Lecture 7 (Wed Sep 24) | Construction of CCA-secure Encryption |
Fri Sep 26: HW #2 out | |
Module 2: Public-Key Cryptography | |
Lecture 8 (Mon Sep 29) | Key Exchange |
Lecture 9 (Wed Oct 1) |
Public-Key Encryption |
Lecture 10 (Mon Oct 6) | Construction of Public-Key Encryption from Trapdoor Permutations |
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 |