Schedule

Topics:

• Logistics & Course Overview
• What is secure computation? Physical demonstrations.
• Computational indistinguishability
• PRGs

Readings:

• Boneh-Shoup (§3.1: PRGs, §3.11: computational and statistical indistinguishability)

Topics:

• Hybrid arguments
• Blum-Micali (PRG stretching)
• Goldreich-Goldwasser-Micali (PRF from PRG)

Readings:

• Luca Trevisan’s notes.
• Boneh-Shoup (§3.4: composing PRGs, §4.4: PRFs, §4.6: GGM)

Topics:

• Coin-flipping problem
• Commitments
• Groups, fields, the discrete logarithm problem
• Pedersen commitments

Readings:

• Boneh-Shoup (§3.12: coin flipping, §8.12: commitments, §10.5: discrete log and related assumptions)
• “Coin Flipping By Telephone” [Blum, CRYPTO'81]

Topics:

• graph (non)isomorphism (GI/GNI)
• IPs
• An IP for GNI
• Counting problems (#P) and the sum-check protocol

Readings:

• Boneh-Shoup (§18.1: IP)
• Justin Thaler’s book (§4.1-4.3: sum-check)
• IP = PSPACE (lecture)(original proof)(better proof)

Topics:

• ZK (simulation)
• non-interactive ZK is impossible
• Honest-verifier zero knowledge (HVZK)
• HVZK for GI, ZK for GI

Readings:

• Boneh-Shoup (§19.1.1: HVZK, §20.4: computational ZK)
• ZK 3-colorings, in detail (§7.2)

Topics:

• Hamiltonian cycle (NP-complete)
• HVZK for Hamiltonian cycle
• ZK for Hamiltonian cycle

Readings:

• Boneh-Shoup (§20.7: everything that can be proved, can be proved in zero knowledge)
• ZK for Hamiltonian cycles
• Just for fun: Knuth on Hamiltonian paths and cycles

Topics:

• identification protocols
• knowledge soundness/proofs of knowledge (PoK) (extraction)
• Schnorr’s protocol

Readings:

• Boneh-Shoup (§18.2: ID protocols, §19.1: Schnorr)

Topics:

• Sigma protocols
• Sigma protocol combinators
• Sigma protocols for circuits

Readings:

• Boneh-Shoup (§19.4: sigma protocols, §19.5: examples, §19.7: combinators)

Topics:

• Goal: NIZKs (recall: impossible in the standard model)
• The random oracle model
• Commitments from a random oracle
• The Fiat-Shamir transform

Readings:

• Boneh-Shoup (§8.10.2: random oracles, §19.6.1: Fiat-Shamir for signatures, §20.3: non-interactive proof systems)
• “Random Oracles are Practical” [Bellare, Rogaway, CCS'93]
• Susan Hohenberger’s lecture notes on Fiat-Shamir

Topics:

• Motivation: delegating computation
• Succinct proofs
• Probabilistically checkable proofs (PCPs)
• Kilian-Micali

Readings:

• Boneh-Shoup (§8.9: Merkle trees, §20.6: SNARKs)
• Justin Thaler’s book (§9.1: PCPs, §9.2: Merkle trees and Kilian-Micali)
• Alessandro Chiesa’s class on proof systems

Topics:

• Polynomial commitments
• Pairings (bilinear maps)
• KZG

Readings:

• Boneh-Shoup (§15.4: pairing based cryptography)
• KZG, by Kate, Zaverucha, and Goldberg (Asiacrypt 2010)

Topics:

• PIOPs
• Polynomial commitment + PIOP = SNARK
• Some PIOPs (zero-check, univariate sum-check, Fibonacci)

Readings:

• Justin Thaler’s book (§10.2: polynomial IOPs, §10.3: a polynomial IOP for R1CS)
• Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS

Topics:

• Arithmetic circuit satisfiability (AC)
• Plonk: a PIOP for AC

Readings:

• Justin Thaler’s book (§6: circuit arithmetization)
• PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge by Gabizon, Williamson, and Ciobotaru

Topics:

• Multivariate polynomials
• PST multivariate commitments
• Multilinear extensions and layered circuits

Readings:

• Justin Thaler’s book (§3.5: multilinear extensions, §15.3: multilinear KZG)
• Papamanthou, Shi, and Tamassia, “Signatures of Correct Computation” (TCC 2013)

Topics:

• GKR

Readings:

• Justin Thaler’s book (§4.6: the GKR protocol)
• Goldwasser, Kalai, and Rothblum, “Delegating Computation: Interactive Proofs for Muggles” (JACM 2015)

Topics:

• Uninstantiability results in the ROM
• GK uninstantiability for a ROM signature (contrived)
• KRS uninstantiability for GKR + Fiat-Shamir (somewhat contrived)

Readings:

• Goldwasser and Kalai, “On the (In)security of the Fiat-Shamir Paradigm” (FOCS 2003)
• Khovratovich, Rothblum, and Soukhanov, “How to Prove False Statements: Practical Attacks on Fiat-Shamir” (2025)

Topics:

• Oblivious transfer
• Diffie-Hellman assumptions
• Bellare-Micali OT, from Diffie-Hellman

Readings:

• Boneh-Shoup (§11.6: OT from Diffie-Hellman)

Topics:

• MPC (passive security)
• Garbled circuits
• Optimizations (Vlad!)

Readings:

• Boneh-Shoup (§23.1: MPC, §23.3: garbled circuits)
• A Proof of Security of Yao’s Protocol for Two-Party Computation, by Lindell and Pinkas
• A Pragmatic Introduction to Secure Multi-Party Computation, by Evans et al. (Chapters 2 and 3)

Topics:

• Secret sharing (additive and Shamir)
• Beaver’s protocol: arithmetic MPC
• active security for MPC

Readings:

• Boneh-Shoup (§22.1: Shamir’s secret sharing, §23.2: arithmetic MPC)
• How to Share a Secret, by Adi Shamir (CACM 1979)

Topics:

• Differential privacy
• The Gaussian mechanism
• Composition
• Concrete security: Apple’s QuickType, Microsoft’s US Broadband dataset

Readings:

• The Algorithmic Foundations of Differential Privacy, by Cynthia Dwork and Aaron Roth
• Differential Privacy: A Survey of Results, by Cynthia Dwork
• Tang, Korolova, Bai, Wang, and Wang, “Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12” (2017)

Topics:

• PIR
• Two-server, information-theoretic PIR (Chor-Goldreich-Kushilevitz-Sudan)
• Additively homomorphic encryption
• Single-server PIR from AHE (Kushilevitz-Ostrovsky)

Readings:

• Ryan Henry, Tutorial on PIR
• Ostrovsky and Skeith, A Survey of Single-Database PIR
• A recent breakthrough theory result on efficient single-server PIR

Topics:

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

Readings:

• Boneh-Shoup (§17.1: integer lattices, §17.2.2: LWE, §17.5: public-key encryption from lattices)
• A Decade of Lattice Cryptography (§4.2 and §5.2.1), by Chris Peikert

Topics:

• Fully homomorphic encryption
• GSW: FHE from LWE via noisy eigenvalues

Readings:

• Boneh-Shoup (§17.6: fully homomorphic encryption)
• Boaz Barak, An Intensive Introduction to Cryptography (Chapter 17)
• Shai Halevi, Homomorphic Encryption
• A Decade of Lattice Cryptography (§6.1), by Chris Peikert

Topics:

• digital signatures
• remote attestation
• deployments
• attacks (Daniel!)

Readings:

• Boneh-Shoup (§13: digital signatures)
• TBD: TEE reading