Time: Wednesday 10:15 AM - 11:45 AM, Thursday 10:00
- 11:40 AM.
Location: Wednesday: 177 Huntington Ave, 6th floor 602.
Thursday: 177 Huntington Ave, 5th floor 503. Access to 177 Huntington is restricted. Send me an
email if you need access.
Pre-requisites: Basic knowledge of cryptography and
complexity theory. If you need to waive
pre-requisite courses, send me an email.
This seminar is centered around Succinct Non-interactive Arguments (SNARGs), a cryptographic proof system that allows a prover to convince a verifier that a statement is true through a very short message. SNARGs are used in blockchain and cryptocurrency infrastructure to enhance privacy and improve scalability. Their development incorporates a variety of techniques from algorithm and complexity theory.
The course will cover both foundational theory and modern practical approaches, including polynomial commitments, interactive oracle proofs and their variants, linear-time prover schemes, and recent progress in basing SNARGs on standard assumptions. If time permits, we will also explore proofs of proximity and their connection to property testing. This curriculum will equip students with the knowledge to understand and innovate cryptographic proofs for future research.
There will be no written exams in this course. Students will also be encouraged to present.
| Date | Topic | Reading |
|---|---|---|
| Sept. 11 | Introduction | |
| Sept. 12 | Linear PCPs, BLR linear testing | Linearity Testing in Characteristic Two and related lecture notes |
| Sept. 18 | Kilian | Kilian’92 Chiesa-Dall’Agnol-Guan-Spooner-Yogev’24 |
| Sept. 19 | Micali | Fiat-Shamir, Random Oracle Model, Micali’s CS Proofs |
| Sept. 25 | Sum-check & low-degree testing | Related lecture notes, book chapters, and Chiesa’s Course |
| Sept. 26 | GKR Protocol | GKR08, Understanding GKR, Viola’s Book, Thaler’s Note |
| Oct. 2 | SNARGs from Linear PCPs | Bitansky-Chiesa-Ishai-Ostrovsky-Paneth’13 |
| Oct. 3 | Interactive Oracle Proofs (IOPs) | Chiesa’s Course |
| Oct. 9 | Polynomial Commitments I (Mingqi) | KZG, Hyrax |
| Oct. 10 | Polynomial Commitments II (Kabir) | FRI: Fast Reed-Solomon IOP of Proximity |
| Oct. 16 | Polynomial Commitments III | Spielman’s Linear-time Codes, Brakedown, Orion, Yupeng’s lec |
| Oct. 17 | Incrementally Verifiable Computation I | Valiant08 |
| Oct. 23 | Incrementally Verifiable Computation II (Julia) | Folding Scheme Nova, HyperNova |
| Oct. 24 | Concretely Efficient Prover I | Libra, Linear-time IOPs Spartan |
| Oct. 30 | Concretely Efficient Prover II | Plonk, (HyperPlonk) |
| Oct. 31 | Lookup Arguments (LaKyah) | Lasso, Jolt |
| Nov. 6 | Standard Assumptions I | SSB, CI Hash Canetti et. al’19, Peikert-Shiehian’19 |
| Nov. 7 | Standard Assumptions II | SNARGs for Bounded-depth P |
| Nov. 13 | Standard Assumptions III | SNARGs for Batch-NP, from LWE |
| Nov. 14 | Standard Assumptions IV | SNARGs for P from LWE |
| Nov. 20 | Interactive Proofs and Learning Theory (Mingqi) | Interactive Proofs for Verifying Machine Learning |
| Nov. 21 | Interactive Proofs and Property Testing (Ethan) | Doubly Efficient Interactive Proofs for Distribution Properties |
| Dec. 4 | Interactive Proofs and LLM (Quan and Kashif) | Models that prove their own correctness |
| Dec. 5 | TBD |
Recent papers in the field and book chapters. Specific readings will be distributed before each topic discussion.
Textbooks: