Course Schedule

Topics:

• Logistics & Course Overview
• Relationship between symmetric primitives: from OWFs to PRGs, using Hardcore bits.

Readings:

• Probability cheat-sheet
• Goldreich & Levin’s paper

Topics:

• Blum-Micali (PRG extension)
• Goldreich-Goldwasser-Micali (PRF from PRG)
• Luby-Rackoff (PRP from PRF)

Readings:

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

Topics:

• Commitment schemes

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
  • Coppersmith’s Theorem

Readings:

• “Mining Your Ps and Qs” [Heninger, Durumeric, Wustrow, Halderman, USENIX'12]
• “The Return of Coppersmith’s Attack” [Nemec, Sys, Svenda, Klinec, Matyas, CCS'17]
• Linux removes insecure randomness and rolls back.

Topics:

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

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:

• Polynomial Commitment + PolyIOP = SNARG
  • Polynomial IOPs
  • Plonkish Arithmetization
  • Plonk-Light: SNARG for Arithmetic Circuit-SAT

Readings:

• Proofs, Arguments, and Zero Knowledge by Justin Thaler (esp. Section 9)
• PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru
• 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:

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

• 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
• A survey covering constructions up to 2008.
• The state of the art for information-theoretic 2-server PIR.
• A recent breakthrough result giving a computationally efficient single-server PIR (best paper award in STOC 2023).

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)

Readings:

• Boaz Barak, An Intensive Introduction to Cryptography (Chapter 17)
• Shai Halevi, Homomorphic Encryption
• A Decade of Lattice Cryptography (Section 6.1), by Chris Peikert

Topics:

• To be decided
• Course wrap-up

Readings: