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 realworld 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 longstanding 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 realworld 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 6875fa20@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:302pm ET / 9:3011am 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) Berkeleyonly lecture 
Introduction 
Lecture 1 (Tu Sep 1) 
Shannon, perfect security and the onetime 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: Oneway 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 BlumMicali 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 BlumMicali 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 DiffieHellman paper Merkle paper GoldwasserMicali paper 
Lecture 10 (Th Oct 1) 
Public key encryption II: construction from DiffieHellman 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 onetime signatures NaorYung signatures Rompel signatures from OWF Incremental signatures (by Bellare, Goldreich, and Goldwasser) GoldwasserMicaliRivest signature scheme CramerShoup signature scheme 
Lecture 12b (Tu Oct 13) Berkeleyonly lecture 
Merkle Trees and Certificate Transparency
Lecture Slides BonehShoup 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) FiatShamir 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) NonMalleable Cryptography (Dolev, Dwork, Naor) 
Lecture 18 (Tu Nov 3) 
Zcash: privacypreserving cryptocurrency with zeroknowledge proofs
Lecture Slides Zerocash (Sections I, II, IIIA, IIIB, 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 (singleserver 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. 5015) 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 twoparty computation protocol
Lecture Slides Proof of Yao's Protocol for Secure 2PC 
Lecture 25 (Th Dec 3) 
GMW twoparty computation
Lecture Slides A Pragmatic Introduction to Secure MultiParty 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 