Course Schedule

Topics:

• Logistics & Course Overview
• Merkle Puzzles

Readings:

• Probability cheat-sheet
• Merkle’s project proposal

Topics:

• Relationship between symmetric primitives: OWFs, PRGs, PRFs, block ciphers
• Blum-Micali PRG construction
• Goldreich-Goldwasser-Micali (GGM) PRF construction

Readings:

• Luca Trevisan’s lecture notes
• Boneh-Shoup (§3.4,§4.4,§4.6)

Topics:

• 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]

Topics:

• GCD attack on RSA keys
• Infineon attack

Readings:

• 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)
• 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)
• Linux removes insecure randomness and rolls back.

Topics:

• Generic d-log attacks: Baby-Step Giant-Step, Pollard Rho, Shoup’s lower bound
• A non-generic attack: 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

Topics:

• Introduction to elliptic curves

Readings:

• Boneh-Shoup (Chapter 15)
• Elliptic Curve Cryptosystems, by Neal Koblitz

Topics:

• 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

Topics:

• Interactive proofs
• Zero knowledge

Readings:

• IP = PSPACE (lecture)(original proof)(better proof)
• ZK for Hamiltonian cycles
• ZK 3-colorings, in detail (§7.2)
• Just for fun: Knuth on Hamiltonian paths and cycles

Topics:

• Sigma protocols

Readings:

• Boneh-Shoup, Chapter 19
• Benny Pinkas, Sigma Protocols (slides, video)
• Hazay and Lindell, Efficient Secure Two-Party Protocols, Chapter 6

Topics:

• Non-interactive zero-knowledge
• Fiat-Shamir heuristic

Readings:

• Susan Hohenberger’s lecture notes on Fiat-Shamir
• Boneh-Shoup (Section 19.1, 20.3)

Topics:

• Succinct Non-interactive Arguments (SNARGs) from PCPs
• Polynomial commitments
• Arithmetic circuits and constraints

Readings:

• Polynomial Commitments, by Kate, Zaverucha, and Goldberg (Asiacrypt 2010)
• Alessandro Chiesa’s class on proof systems
• Justin Thaler’s book
• Several blog posts give an accessible explanation of zkSNARKs

Topics (Lecture Notes):

• 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)

Topics:

• 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

Topics:

• Secret-sharing
• Multi-Party Computation

Readings:

• How to Share a Secret, by Adi Shamir (CACM 1979)
• Boneh-Shoup, Section 11.6.1
• 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

Topics:

• 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

Topics:

• 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

Topics:

• The learning with errors (LWE) problem
• Regev encryption

Readings:

• A Decade of Lattice Cryptography (Sections 4.2 and 5.2.1), by Chris Peikert

Topics:

• Fully homomorphic encryption (FHE), part 1

Readings:

• Boaz Barak, An Intensive Introduction to Cryptography (Chapter 17)
• Shai Halevi, Homomorphic Encryption

Topics:

• Fully homomorphic encryption (FHE), part 2
• Course wrap-up

Readings:

• A Decade of Lattice Cryptography (Section 6.1), by Chris Peikert