MIT 6.875
/
Berkeley CS 276
Graduate Cryptography
Graduate Cryptography
Course Description
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. On the one hand, security and privacy are of paramount importance in the age of big data and mass surveillance. On the other hand, cryptography is abuzz with solutions to long-standing open problems such as fully homomorphic encryption and software obfuscation that use the abundance of data for public good without compromising security. The course will explore both the rich theory of cryptography as well as its real-world applications.Prerequisites: This is an introductory graduate course, intended for beginning graduate students and upper level undergraduates in CS and Math. The required background is general ease with algorithms, elementary number theory and discrete probability equivalent to Berkeley's CS 170, and MIT's 6.042 and 6.046).
Lectures
Welcome to 6.875/CS 276! Lectures will start at 9:30am PT / 12:30pm ET going forward. The Zoom links for lectures will be available on the course Piazza for registered students (including listeners). If you are not already on the course Piazza, please email 6-875-fa20@lists.csail.mit.edu to be added.Course Information
| INSTRUCTORS |
Raluca Ada Popa
Email: raluca at eecs dot berkeley dot edu Shafi Goldwasser Email: shafi at csail dot mit dot edu OR shafi at berkeley dot edu Vinod Vaikuntanathan Email: vinodv at csail dot mit dot edu |
| TAs |
Ofer Grossman
Email: ogrossma at mit dot edu Saleet Mossel Email: saleet at mit dot edu Nick Ward Email: npward at berkeley dot edu Lisa Yang Email: lisayang at mit dot edu Rachel Zhang Email: rachelyz at mit dot edu |
| LOCATION | Zoom link available for registered students |
| TIME |
TuTh 12:30-2pm ET / 9:30-11am PT.
Office Hours by appointment |
| TEXTBOOKS |
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.
|
| 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.
Late day policy: You have a total of 10 late days to use across the 6 psets (max of 5 late days for a single pset). You can use these late days however you'd like - we will use the timestamp of your Gradescope submission to calculate the number of late days. Submitting psets: Typesetting your pset answers in LaTeX is strongly encouraged. PDFs are to be submitted via Gradescope. Here is a LaTeX template you can use. |
| COLLABORATION POLICY | You are free to collaborate with other students on the homework 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 |
| Lecture 0 (Tr Aug 27) Berkeley-only lecture |
Introduction |
| Lecture 1 (Tu Sep 1) |
Shannon, perfect security and the one-time pad
Lecture Slides A Communication Theory of Secrecy Systems (by Claude Shannon) New Directions in Cryptography (by Whitfield Diffie and Martin E. Hellman) |
| Lecture 2 (Th Sep 3) |
The computational adversary, definition of computational security,
definition of pseudo random generators (informally),
and pseudo random generators implies symmetric encryption Lecture Slides (PPTX version) |
| Lecture 3 (Tu Sep 8) |
The tool: One-way functions, hard core bits, GL theorem
Lecture Slides (PPTX version) Goldreich Chapter 2 - Computational Difficulty |
| Lecture 4 (Th Sep 10) |
Pseudorandom generators: definition, construction, properties Lecture Slides (PPTX version) Goldreich Chapter 3 - Pseudorandom Generators Pseudorandom Generators notes Pseudorandom Generators from OWF notes Blum-Micali paper on cryptographically strong PRG HILL paper showing OWF implies PSRG |
| Lecture 5 (Tu Sep 15) |
Pseudorandom functions: definition, construction, properties Lecture Slides (PPTX version) How to Construct Pseudorandom Functions (by Oded Goldreich, Shafi Goldwasser, and Silvio Micali) How to Construct Pseudorandom Permutations (by Michael Luby and Charles Rackoff) |
| Lecture 6 (Th Sep 17) |
Pseudorandom permutations and AES, symmetric key encryption via cipher chaining modes Lecture Slides Section 3.7 (on PRPs) of Goldreich Chapter 3 |
| Lecture 7 (Tu Sep 22) |
Number theory 1: discrete log and MSB (bit), QR, etc. Lecture Slides (PPTX version) Number Theory notes (by Dana Angluin) Generating Random Factored Numbers, Easily (by Adam Kalai) |
| Lecture 8 (Th Sep 24) |
Number theory 2: factoring, RSA Lecture Slides Blum-Micali paper on cryptographically strong PRG Shoup paper on finding elliptic curve order How discreet is the discrete log? (by Avi Widgerson) Probabilistic encryption (by Shafi Goldwasser and Silvio Micali) RSA paper Provable Security notes (by Dana Angluin) |
| Lecture 9 (Tu Sep 29) |
Public key encryption I: definition and construction from RSA and Quadratic Residuosity
Lecture Slides (PPTX version) RSA paper Diffie-Hellman paper Merkle paper Goldwasser-Micali paper |
| Lecture 10 (Th Oct 1) |
Public key encryption II: construction from Diffie-Hellman and Learning with Errors
Lecture Slides (PPTX version) The Learning With Errors Problem (by Oded Regev) |
| Lecture 11 (Tu Oct 6) |
Digital signatures and MACs I
Lecture Slides RSA paper |
| Lecture 12 (Th Oct 8) |
Digital signatures and MACs II
Lecture Slides Lamport's one-time signatures Naor-Yung signatures Rompel signatures from OWF Incremental signatures (by Bellare, Goldreich, and Goldwasser) Goldwasser-Micali-Rivest signature scheme Cramer-Shoup signature scheme |
| Lecture 12b (Tu Oct 13) Berkeley-only lecture |
Merkle Trees and Certificate Transparency
Lecture Slides Boneh-Shoup notes (Merkle Trees are discussed in Sec. 8.9) Google talk on Certificate Transparency (video) The RFC for Certificate Transparency |
| Lecture 13 (Th Oct 15) |
Proof of Work, consensus, cryptographic transactions, Bitcoin application
Lecture Slides The Bitcoin Whitepaper How the Bitcoin Protocol actually works (optional) |
| Lecture 14 (Tu Oct 20) |
Zero knowledge I: definitions and examples
Lecture Slides |
| Lecture 15 (Th Oct 22) |
Zero knowledge II: NP in ZK
Lecture Slides GMR paper GMW paper ZK arguments by Brassard et al ZK proof systems (from Oded Goldreich's book) Probabilistic Proof Systems by Oded Goldreich Incremental Cryptography paper |
| Lecture 16 (Tu Oct 27) |
NIZK
Lecture Slides (PPTX version) NIZK paper by Blum, Micali, et al Multiple NIZK from general assumptions (Feige, Lapidot, Shamir) New Techniques for NIZK (Groth, Ostrovsky, Sahai) Fiat-Shamir practice to theory (Canetti, Lombardi, Wichs) NIZK from LWE (Peikert and Shiehian) |
| Lecture 17 (Th Oct 29) |
CCA
Lecture Slides (PPTX version) CCA Attacks on RSA (Bleichenbacher) Non-Malleable Cryptography (Dolev, Dwork, Naor) |
| Lecture 18 (Tu Nov 3) |
Zcash: privacy-preserving cryptocurrency with zero-knowledge proofs
Lecture Slides Zerocash (Sections I, II, III-A, III-B, IV) |
| Lecture 19 (Th Nov 5) |
Specialized homomorphic encryption, and applications
Lecture Slides zkLedger (optional reading) |
| Lecture 20 (Tu Nov 10) |
Lattices and Learning with Errors
Lecture Slides (PPTX version) |
| Lecture 21 (Th Nov 12) |
Fully homomorphic encryption
Lecture Slides (PPTX version) Vinod's Lecture Notes on Lattices |
| Lecture 22 (Tu Nov 17) |
PIR (single-server PIR from FHE)
Lecture Slides (PPTX version) |
| Lecture 23 (Th Nov 19) |
Secret sharing
Lecture Slides Sections 13.3.1 and 13.3.2 (pp. 501-5) of Modern Cryptography by Katz and Lindell — available in Resources (General Resources section) on Piazza |
| Lecture 24 (Tu Dec 1) |
Garbled circuits and Yao's two-party computation protocol
Lecture Slides Proof of Yao's Protocol for Secure 2PC |
| Lecture 25 (Th Dec 3) |
GMW two-party computation
Lecture Slides A Pragmatic Introduction to Secure Multi-Party Computation (see sections 3.2 and 6.5.1) BGW88 MPC Paper |
| Lecture 26 (Tu Dec 8) optional for Berkeley |
Practical machine learning with MPC
Lecture Slides Helen: Maliciously Secure Coopetitive Learning for Linear Models |