MIT 6.5620/6.875/18.425 (Fall 2022)
Foundations of Cryptography
Foundations of Cryptography
Course Description
The field of cryptography gives us a technical language to define important realworld problems such as security, privacy and integrity, a mathematical toolkit to construct mechanisms such as encryption, digital signatures, zeroknowledge proofs, homomorphic encryption and secure multiparty computation, and a complexitytheoretic framework to prove security using reductions that together 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 realworld privacy and security problems. For example, cryptography is abuzz with solutions to longstanding 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 fastpaced, 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 
Vinod Vaikuntanathan Email: vinodv at csail dot mit dot edu 
LOCATION AND TIME  Monday and Wednesday 1:002:30pm in 1190 
TAs 
Matthew Hong Email: matthong at mit dot edu Office hours: Thursday 10:3011:30am in 5233. Surya Mathialagan Email: smathi at mit dot edu Office hours: Monday 34pm in 34302, Tuesday 1011am in 24323. Tina Zhang Email: tinaz at mit dot edu Office hours: Tuesday 56pm in 34304, Thursday 4:155:15pm in 36112. 
RECITATIONS 
Probability review: Friday September 9 121pm in 32575
(Probability theory handout) Complexity and reductions review: Friday September 16 12pm in 32G431. (Complexity theory and reductions handout) Number theory review: Friday September 30 121pm on Zoom (see Piazza for the link). (Number theory handout; see also Dana Angluin's highquality and comprehensive notes.) 
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. 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 (95%) and class participation (5%).
There will be 6 problem sets and your top 5 scores will count towards your grade.
You have a total of 10 late days to use across the 6 psets (max of 5 late days for any single pset). You can use these late days however you like; we will use the timestamp of your Gradescope submission to calculate the number of late days.
Submitting psets:
Released problem sets:

COLLABORATION POLICY  Collaboration is permitted and encouraged in smallgroups of at most three. You are free to collaborate in discussing answers, but you must write up solutions on your own, and specify in your submission the names of any collaborators. Do not copy any text from your collaborators; the writeup must be entirely your work. Additionally, you may make use of published material, provided that you acknowledge all sources used. Of course, scavenging for solutions from prior years is forbidden. 
Schedule (tentative and subject to change)
Lecture  Topic 
Module 1.  
Lecture 1 (Wed Sep 7) HW #1 out 
Resources: Slides, Slides (PDF) and lecture video. Topics covered:
Recommended reading:

Lecture 2 (Mon Sep 12) 
Resources: Slides, Slides (PDF) and lecture video. Topics covered:
Recommended reading:

Lecture 3 (Wed Sep 14) 
Resources: Slides, Slides (PDF) and lecture video. Topics covered:
Recommended reading:

Lecture 4 (Mon Sep 19) 
Resources: Slides (PDF) and lecture video. Topics covered:
Recommended reading:
Advanced reading:

Lecture 5 (Wed Sep 21) HW #1 due, HW #2 out 
Resources: Slides (PDF) and lecture video. Topics covered:

Lecture 6 (Mon Sep 26) 
Resources: Slides, Slides (PDF) and lecture video. Topics covered:

Lecture 7 (Wed Sep 28) 
Resources: Slides, Slides (PDF) and lecture video. Topics covered:

Module 2.  
Lecture 8 (Mon Oct 3) 
Resources: Slides, Slides (PDF) and video. Topics covered:

Lecture 9 (Wed Oct 5) HW #2 due, HW #3 out 
Resources: Slides, Slides (PDF) and video. Topics covered:
Advanced reading:

No lecture (Mon Oct 10) Indigenous Peoples' Day 

Lecture 10 (Wed Oct 12) 
Resources: Slides, Slides (PDF), video. Topics covered:

Lecture 11 (Mon Oct 17) 
Resources: Slides, Slides (PDF), Video. Topics covered:

Lecture 12 (Wed Oct 19) HW #3 due, HW #4 out 
Resources: Slides, Slides (PDF), Video. Topics covered:

Lecture 13 (Mon Oct 24) 
Resources: Video and slides, slides (PDF). Topics covered:

Module 3.  
Lecture 14 (Wed Oct 26) 
Resources: Video, slides, slides (PDF). Topics covered:

Lecture 15 (Mon Oct 31) 
Resources: Video, slides, slides (PDF). Topics covered:

Lecture 16 (Wed Nov 2) HW #4 due, HW #5 out 
Resources: Video, slides, slides (PDF). Recommended reading:

Lecture 17 (Mon Nov 7) 
Resources: Video, slides, slides (PDF). Topics covered:

Module 5.  
Lecture 18 (Wed Nov 9) 
Lecture Cancelled You can watch the Lecture 18 video from Fall 2022 here. The slides are here (PDF). 
Lecture 19 (Mon Nov 14) 
Resources: Video, slides, slides (PDF). Topics covered:

Lecture 20 (Wed Nov 16) HW #5 due, HW #6 out 
Resources: Video, slides, slides (PDF). Topics covered:

Module 6.  
Lecture 21 (Mon Nov 21) 
Resources: Video, Slides, slides (PDF). Topics covered:
Recommended reading:

No Lecture (Wed Nov 23) Thanksgiving Break 

Lecture 22 (Mon Nov 28) 
Resources: Video, Slides, slides (PDF). Topics covered:
Recommended reading:
Advanced reading: 
Lecture 23 (Wed Nov 30) 
Resources: Video, Slides, slides (PDF). Topics covered:
Recommended reading:

Lecture 24 (Mon Dec 5) 
Resources: Video, slides (keynote), slides (PDF). Topics covered:
Advanced reading:

Lecture 25 (Wed Dec 7) HW #6 due 
Resources: Video, slides, slides (PDF). Topics covered:
A full proof (and description) of Yao's protocol's security: 
Lecture 26 (Mon Dec 12) 
Resources: Video. Topics covered:

Lecture 27 (Wed Dec 14) 
Topics covered:
