MIT 6.5620/6.875/18.425 (Fall 2022)
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 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 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 Vinod Vaikuntanathan
Email: vinodv at csail dot mit dot edu
LOCATION AND TIME Monday and Wednesday 1:00-2:30pm in 1-190
TAs Matthew Hong
Email: matthong at mit dot edu
Office hours: Thursday 10:30-11:30am in 5-233.

Surya Mathialagan
Email: smathi at mit dot edu
Office hours: Monday 3-4pm in 34-302, Tuesday 10-11am in 24-323.

Tina Zhang
Email: tinaz at mit dot edu
Office hours: Tuesday 5-6pm in 34-304, Thursday 4:15-5:15pm in 36-112.
RECITATIONS Probability review: Friday September 9 12-1pm in 32-575 (Probability theory handout)
Complexity and reductions review: Friday September 16 1-2pm in 32-G431.
(Complexity theory and reductions handout)
Number theory review: Friday September 30 12-1pm on Zoom (see Piazza for the link). (Number theory handout; see also Dana Angluin's high-quality 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
  1. Fall 2021 course website
  2. Pass-Shelat
Textbooks
  1. Katz-Lindell
  2. Boneh-Shoup
  3. Goldreich
  4. Rosulek
  5. Lindell's advanced tutorial on the foundations of crypto.
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:
  • You should typeset your pset answers in LaTeX.
  • 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.
  • Here is a LaTeX template you can use.
  • Solutions will be posted on piazza.

Released problem sets:
  • PSET 1 (PDF) | Released: 7 Sep, 2:30pm | Due: 21 Sep, 11:59:59pm ET
  • PSET 2 (PDF) | Released: 21 Sep, 2:30pm | Due: 5 Oct, 11:59:59pm ET
  • PSET 3 (PDF) | Released: 5 Oct, 3:30pm | Due: 19 Oct, 11:59:59pm ET
  • PSET 4 (PDF) | Released: 19 Oct, 11:30pm | Due: 2 Nov, 11:59:59pm ET
  • PSET 5 (PDF) | Released: 2 Nov, 9:30pm | Due: 16 Nov, 11:59:59pm ET
  • PSET 6 (PDF) | Released: 16 Nov, 11:30pm | Due: 7 Dec, 11:59:59pm ET
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:
  • Introduction to cryptography.
  • Secure Communication and Shannon’s definitions of perfect secrecy.
  • The One-time pad construction.
  • Shannon’s lower bound.

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

Topics covered:
  • How to circumvent Shannon’s lower bound: the computational adversary.
  • Definition of computational security.
  • The definition of pseudorandom generators (PRG).
  • Pseudorandom generators imply (stateful) secret-key encryption.

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

Topics covered:
  • The Hybrid Argument.
  • An application: PRG length extension.
  • The notion of pseudorandom functions: Definition, motivation, discussion and comparison with PRGs.
  • PRFs imply secret-key encryption.

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

Topics covered:
  • Formal definition of PRF security.
  • The Goldreich-Goldwasser-Micali (GGM) PRF construction.
  • Definition of IND-CPA secure encryption.

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

Topics covered:
  • Identification protocols.
  • Authentication and message-authentication codes (MAC).
  • Chosen ciphertext secure symmetric key encryption.
Recommended reading:
Lecture 6 (Mon Sep 26) Resources:
Slides, Slides (PDF) and lecture video.

Topics covered:
  • One-way functions and its properties.
  • Hard core bits and PRG.
  • Goldreich-Levin theorem.
Recommended reading:
Lecture 7 (Wed Sep 28) Resources:
Slides, Slides (PDF) and lecture video.

Topics covered:
  • Goldreich-Levin Theorem (contd.)
  • A TCS perspective on GL theorem: local list decoding (if time permits).
Advanced reading
Module 2.
Lecture 8 (Mon Oct 3) Resources:
Slides, Slides (PDF) and video.

Topics covered:
  • Merkle's key exchange protocol
  • Public-key encryption.
  • Definition of security: IND-CPA.
  • Overview of group theory and number theory.
Recommended reading Talk on history of public key cryptography mentioned in lecture:
Lecture 9 (Wed Oct 5)
HW #2 due, HW #3 out 		Resources:
Slides, Slides (PDF) and video.

Topics covered:
  • Discrete Log Asssumption.
  • Diffie-Hellman key exchange.
  • Diffie-Hellman/El Gamal encryption.
Recommended reading (same as last lecture).

Advanced reading:
No lecture (Mon Oct 10)
Indigenous Peoples' Day
Lecture 10 (Wed Oct 12) Resources:
Slides, Slides (PDF), video.

Topics covered:
  • Trapdoor functions.
  • RSA, trapdoor permutations and another public-key cryptosystem.
  • QRA, Goldwasser-Micali and Homomorphism.
Recommended reading: Advanced reading:
Lecture 11 (Mon Oct 17) Resources:
Slides, Slides (PDF), Video.

Topics covered:
  • Digital Signatures: Definition.
  • Lamport's One-time Signature Scheme.
Advanced reading:
Lecture 12 (Wed Oct 19)
HW #3 due, HW #4 out 		Resources:
Slides, Slides (PDF), Video.

Topics covered:
  • Collision-resistant hash functions.
  • Many-time, stateful, signature schemes.
  • Naor-Yung construction: stateless EUF-CMA-secure signature schemes.
Advanced reading:
Lecture 13 (Mon Oct 24) Resources:
Video and slides, slides (PDF).

Topics covered:
  • Instantiation of collision-resistant hash functions from discrete log.
  • Direct construction of digital signatures from RSA.
  • The hash-and-sign paradigm and the random oracle heuristic.
  • Variants of digital signatures.
Advanced reading:
Module 3.
Lecture 14 (Wed Oct 26)
Resources:
Video, slides, slides (PDF).

Topics covered:
  • Zero knowledge I, definitions and examples.
Recommended reading:
Lecture 15 (Mon Oct 31) Resources:
Video, slides, slides (PDF).

Topics covered:
  • Zero knowledge II: Zero Knowledge Proofs for all of NP.
Recommended reading:
  • ZK for NP by Oded Goldreich, Silvio Micali, and Avi Wigderson.
Lecture 16 (Wed Nov 2)
HW #4 due, HW #5 out 		Resources:
Video, slides, slides (PDF).

Recommended reading: Advanced reading:
Lecture 17 (Mon Nov 7) Resources:
Video, slides, slides (PDF).

Topics covered:
  • Succinct (Zero Knowledge) Argument Systems.
  • Tools: Merkle Trees, Probabilistically Checkable Proofs .
  • Kilian's Protocol.
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:
  • Lattices, Learning with Errors (LWE).
  • LWE-based Cryptography: Secret-key and Public-key Encryption, Collision-Resistant Hashing.
  • Fully Homomorphic Encryption.
  • A Construction of FHE from the LWE assumption.
Advanced reading:
Lecture 20 (Wed Nov 16)
HW #5 due, HW #6 out 		Resources:
Video, slides, slides (PDF).

Topics covered:
  • Fully Homomorphic Encryption continued: The Bootstrapping Theorem, and Circular Security.
  • Open Problems in FHE Research.
Module 6.
Lecture 21 (Mon Nov 21)
Resources:
Video, Slides, slides (PDF).

Topics covered:
  • Oblivious Transfer.
  • Private Information Retrieval.

Recommended reading:
No Lecture (Wed Nov 23)
Thanksgiving Break
Lecture 22 (Mon Nov 28)
Resources:
Video, Slides, slides (PDF).

Topics covered:
  • Secure Two-Party Computation.
  • The Goldreich-Micali-Wigderson Protocol.

Recommended reading:
Advanced reading:
Lecture 23 (Wed Nov 30) Resources:
Video, Slides, slides (PDF).

Topics covered:
  • Secret-Sharing.
  • Secure Multiparty Computation.

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

Topics covered:
  • Program Obfuscation and Applications.

Advanced reading:
Lecture 25 (Wed Dec 7)
HW #6 due 		Resources:
Video, slides, slides (PDF).

Topics covered:
  • Yao's Garbled Circuits.
Advanced reading:
Lecture 26 (Mon Dec 12) Resources:
Video.

Topics covered:
  • Quantum Cryptography.

Lecture 27 (Wed Dec 14) Topics covered:
  • Grand Challenges in Cryptography.
  • Crypto AMA with Vinod and the TAs.