Course Schedule

Date	Topic and Readings
Foundations of Cryptography
Tuesday, April 7 (Florian)	Topics (Lecture Notes) Logistics and administration Basic cryptogrpahic primitives and the relation between them: OWFs, PRGs Readings Boneh-Shoup (§4.4, §4.6) Probability-Theory Cheat Sheet
Thursday, April 9 (Dima)	Topics (Lecture Notes) The Blum-Micali PRG and hybrid arguments Constructing PRGs from one-way permutations (the Goldreich-Levin Theorem) Readings Boneh-Shoup (§3.4) Luca Trevisan's lecture notes Katz-Lindell §7.3
Tuesday, April 14 (Saba)	Topics (Lecture Notes) Commitment schemes The random oracle model Readings Boneh-Shoup (§8.10.2) Katz-Lindell (§5.5 in second edition, §13.1 in first edition) David Wu's Notes (Theorem 5.1)
Cryptanalysis
Thursday, April 16 (Florian)	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 20	Problem Set 1 Due at 11:59pm via Gradescope.
Tuesday, April 21 (Dima)	Topics (Lecture Notes) Discrete-log algorithms: Baby-Step Giant-Step, Pollard Rho 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
Elliptic-curve cryptography
Thursday, April 23 (Saba)	Topics (Lecture Notes) Introduction to elliptic curves Readings Boneh-Shoup (Chapter 15) Elliptic Curve Cryptosystems, by Neal Koblitz
Tuesday, April 28 (Florian)	Topics (Lecture Notes) Pairings-based cryptography: 3-party key-exchange, short signatures, identity-based encryption 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 30 (Saba)	Topics (Lecture Notes) Interactive proofs Zero knowledge Readings Boaz Barak's notes on Zero Knowledge (Read until section on quadratic residues) Sanjam Garg's lecture notes Just for fun: Knuth on Hamiltonian paths and cycles
Monday, May 4	Problem Set 2 Due at 11:59pm via Gradescope
Tuesday, May 5 (Dima)	Topics (Lecture Notes) Sigma protocols Readings Boneh-Shoup, Chapter 19 Benny Pinkas, Sigma Protocols (slides, video) Hazay and Lindell, Efficient Secure Two-Party Protocols, Chapter 6
Thursday, May 7 (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 12 (Florian)	Topics (Lecture Notes) Succinct Non-interactive Arguments (SNARGs) PCPs, Linear PCPs Readings Succinct Non-Interactive Arguments via Linear Interactive Proofs, by Bitansky, Chiesa, Ishai, Ostrovsky, and Paneth (TCC 2013) Alessandro Chiesa's class on proof systems at Berkeley Several blog posts give an accessible explanation of zkSNARKs
Multi-party computation
Thursday, May 14 (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
Monday, May 18	Problem Set 3 Due at 11:59pm via Gradescope
Tuesday, May 19 (Dima)	Topics (Lecture Notes) Secret sharing Readings How to Share a Secret, by Adi Shamir (CACM 1979) Boneh-Shoup, Section 11.6.1
Thursday, May 21 (Florian)	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
Tuesday, May 26 (Florian)	Topics (Lecture Notes) 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
Thursday, May 28 (Dima)	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
Monday, June 1	Problem Set 4 Due at 11:59pm via Gradescope
Lattice-based cryptography
Tuesday, June 2 (Florian)	Topics (Lecture Notes) Lattice signatures The learning with errors (LWE) problem Regev encryption Readings A Decade of Lattice Cryptography (Sections 4.2 and 5.2.1), by Chris Peikert
Thursday, June 4 (Dima)	Topics (Lecture Notes) Fully homomorphic encryption (FHE), part 1 Readings Boaz Barak, An Intensive Introduction to Cryptography (Chapter 17) Shai Halevi, Homomorphic Encryption
Topics
Tuesday, June 9 (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
Wednesday, June 10	Problem Set 5 Due at 11:59pm via Gradescope