Course Schedule

Warning: This is the spring 2021 course website.
The latest CS355 website is online here.

Specific topics and suggested readings are subject to change as the quarter progresses.

Date	Topic and Readings
Foundations of Cryptography
Tuesday, March 30 (Saba)	Topics (Lecture Notes) Logistics and administration Basic cryptographic primitives and the relation between them: OWFs, PRGs Readings Luca Trevisan's lecture notes Probability-Theory Cheat Sheet
Thursday, April 1 (Saba)	Topics (Lecture Notes) The Blum-Micali PRG and hybrid arguments The GGM PRF Readings Boneh-Shoup (§3.4,§4.4,§4.6)
Tuesday, April 6 (Alex)	Topics (Lecture Notes) Commitment schemes The random oracle model Readings Boneh-Shoup (§8.10.2: RO model, §8.8: sponge construction) "Random Oracles are Practical" [Bellare, Rogoway CCS'93] "Coin Flipping By Telephone" [Blum, CRYPTO'81]
Cryptanalysis
Thursday, April 8 (Riad)	Topics (Lecture Notes) Real-world cryptanalysis: Infineon attack GCD attack on RSA keys Readings The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli, by Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, and Vashek Matyas (CCS 2017) Mining Your Ps and Qs - Widespread Weak Keys in Network Devices, by Nadia Heninger, Zakir Durumeric, Eric Wustrow, and J. Alex Halderman (USENIX Security 2012)
Monday, April 12	Problem Set 1 Due at 11:59pm via Gradescope.
Tuesday, April 13 (Alex)	Topics (Lecture Notes) Discrete-log algorithms: Baby-Step Giant-Step, Pollard Rho, Shoup's lower bound Index calculus Readings Chapters 13, 14, and 15 in Galbraith's book The Past, evolving Present and Future of Discrete Logarithm by Joux, Odlyzko and Pierrot Notes for Lectures 10 and 11 of Sutherland's class at MIT "Lower Bounds for Discrete Logarithms and Related Problems," Victor Shoup "The Discrete Logarithm Problem with Preprocessing"
Elliptic-curve cryptography
Thursday, April 15 (Saba)	Topics (Lecture Notes) Introduction to elliptic curves Readings Boneh-Shoup (Chapter 15) Elliptic Curve Cryptosystems, by Neal Koblitz
Tuesday, April 20 (Riad)	Topics (Lecture Notes) Pairings-based cryptography: 3-party key-exchange, short signatures, hashing to elliptic curves Readings Short Signatures from the Weil Pairing, by Dan Boneh, Ben Lynn, and Hovav Shacham (Asiacrypt 2001) Identity-Based Encryption from the Weil Pairing, By Dan Boneh and Matthew Franklin (Crypto 2001). This paper is quite approachable and enjoyable to read
Zero knowledge
Thursday, April 22 (Alex)	Topics (Lecture Notes) Interactive proofs Zero knowledge Readings Boaz Barak's notes on Zero Knowledge Sanjam Garg's lecture notes Just for fun: Knuth on Hamiltonian paths and cycles
Monday, April 26	Problem Set 2 Due at 11:59pm via Gradescope
Tuesday, April 27 (Riad)	Topics (Lecture Notes courtesy of Dima Kogan) Sigma protocols Readings Boneh-Shoup, Chapter 19 Benny Pinkas, Sigma Protocols (slides, video) Hazay and Lindell, Efficient Secure Two-Party Protocols, Chapter 6
Thursday, April 29 (Saba)	Topics (Lecture Notes) Non-interactive zero-knowledge Fiat-Shamir heuristic Readings Susan Hohenberger's lecture notes on Fiat-Shamir Boneh-Shoup (Section 19.1, 20.3)
Tuesday, May 4 (Alex)	Topics (Lecture Notes) Succinct Non-interactive Arguments (SNARGs) from PCPs Polynomial commitments Readings Polynomial Commitments, by Kate, Zaverucha, and Goldberg (Asiacrypt 2010) Alessandro Chiesa's class on proof systems at Berkeley Justin Thaler's book Several blog posts give an accessible explanation of zkSNARKs
Thursday, May 6 (Riad)	Topics (Lecture Notes) Arithmetic circuits and rank-1 constraint systems (R1CS) Polynomial Commitment + IOP = SNARG mini-protocols: polynomial equality, vanishing polynomials, and univariate sum-check Marlin-Lite: a SNARG for R1CS-SAT Readings Proofs, Arguments, and Zero Knowledge by Justin Thaler (esp. Section 9) Aurora: Transparent succinct arguments for R1CS by Ben-Sasson, Chiesa, Riabzev, Spooner, Virza, and Ward (EUROCRYPT 2019) Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS by Chiesa, Hu, Maller, Mishra, Vesely, Ward (EUROCRYPT 2020)
Monday, May 10	Problem Set 3 Due at 11:59pm via Gradescope
Multi-party computation
Tuesday, May 11 (Saba)	Topics (Lecture Notes) Oblivious transfer Two-party computation: Yao's garbled circuits Readings A Proof of Security of Yao's Protocol for Two-Party Computation (§1 and §4 p. 12-15), by Lindell and Pinkas
Thursday, May 13 (Alex)	Topics (Lecture Notes) Secret sharing Readings How to Share a Secret, by Adi Shamir (CACM 1979) Boneh-Shoup, Section 11.6.1
Tuesday, May 18 (Saba)	Topics (Lecture Notes) Multi-party computation Readings A Pragmatic Introduction to Secure Multi-Party Computation, by Evans et al. (Chapters 2 and 3) Nigel Smart's slides on MPC and Secret Sharing
Thursday, May 20 (Riad)	Topics (Lecture Notes courtesy of Florian Tramèr) Differential privacy Readings Two great surveys: The Algorithmic Foundations of Differential Privacy, by Cynthia Dwork and Aaron Roth Differential Privacy: A Survey of Results, by Cynthia Dwork
Monday, May 24	Problem Set 4 Due at 11:59pm via Gradescope
Tuesday, May 25 (Alex)	Topics (Lecture Notes) Private Information Retrieval Readings Ryan Henry, Tutorial on PIR Ostrovsky and Skeith, A Survey of Single-Database PIR This sequence of papers gives a beautiful and very efficient computational two-server PIR
Lattice-based cryptography
Thursday, May 27 (Riad)	Topics (Lecture Notes courtesy of Florian Tramèr) The learning with errors (LWE) problem Regev encryption Readings A Decade of Lattice Cryptography (Sections 4.2 and 5.2.1), by Chris Peikert
Tuesday, June 1 (Saba)	Topics (Lecture Notes) Fully homomorphic encryption (FHE), part 1 Readings Boaz Barak, An Intensive Introduction to Cryptography (Chapter 17) Shai Halevi, Homomorphic Encryption
Thursday, June 3 (Saba)	Topics (Lecture Notes) Fully homomorphic encryption (FHE), part 2 Course wrap-up Readings A Decade of Lattice Cryptography (Section 6.1), by Chris Peikert
Friday, June 4	Problem Set 5 Due at 11:59pm via Gradescope