Classically, a mathematical proof of a theorem is something that can be written down and efficiently checked line by line. However, over the last 30 years, computer scientists have introduced a variety of nonclassical notions of proofs. These can be broadly described as "probabilistic proof systems", because they fundamentally involve randomness. The study of probabilistic proof systems has led to many exciting developments in cryptography and theoretical computer science over the last three decades.
This course will describe a variety of probabilistic proof systems and their applications to cryptography and complexity theory. Topics include interactive proofs, multi-prover interactive proofs, probabilistically checkable proofs, zero-knowledge proofs, and proofs secure against computationally bounded provers (i.e., argument systems). Particular attention will be devoted to practical zero-knowledge argument systems, which have recently seen deployment in anonymous cryptocurrencies and other privacy-preserving blockchain technologies.
There are no formal prerequisites for this course. However, substantial mathematical maturity will be expected, as will knowledge of basic probability theory, induction, asymptotic notation, modular arithmetic, and the notion of NP-completeness (these topics will be reviewed in lecture, but quickly). If you have not previously taken an algorithms or theory of computation course, you will likely be unprepared.
The course reference is a draft monograph written by the instructor that is available here.
Lecture notes from the Fall 2017 iteration of the course have been cited in the research literature, e.g., for pointing out how to combine multi-prover interactive proofs with polynomial commitment schemes to obtain succinct arguments. The Fall 2017 course webpage is archived here.
Grades in the course will be based on participation (comments on the reading), problem sets, and a final project. Each component will count for 1/3 of the grade. Information about the final project will be provided later in the semester.
After class or by appointment.
Below is the highly tentative schedule for the course. I will modify it as the semester progresses. Topics and readings will not become "official" until the date of lecture.
| Class Number | Date | Description | Readings | Slides |
| Part 1. Introduction and The Power of Randomness | ||||
| 1 | 8/26 | Course overview; introduction to probabilistic proof systems (what are interactive proofs, arguments, zero-knowledge proofs, MIPs, and PCPs?); Quiz 0. | No reading. | Lecture 1 slides |
| 2 | 8/31 | The power of randomness: Fingerprinting and Freivalds' Algorithm for verifying matrix multiplication. Low-degree and multilinear extensions. | Chapter 1 of the course reference. | Lecture 2 slides |
| Part 2. Interactive Proofs | ||||
| 3 | 9/2 | LFKN's sum-check protocol. | Chapter 2 of the course reference. | Lecture 3 slides |
| 4 | 9/7 | Arithmetization and LFKN's interactive proof for #SAT. | Chapter 3 of the course reference. | Lecture 4 slides |
| 5 | 9/9 | More applications of the sum-check protocol: counting triangles, matrix multiplication, IP=PSPACE. | Sections 4.1 and 4.2 of the course reference. | Lecture 5 slides |
| 6 | 9/14 | The GKR Protocol. | Sections 4.3-4.5 of the course reference. | Lecture 6 slides |
| 7 | 9/16 | The GKR protocol continued. | Section 4.6 of the course reference. | |
| 8 | 9/21 | Wrap up the GKR protocol. | Section 4.7 of the course reference. | |
| Part 3: Succinct Arguments for NP-complete problems. | ||||
| 9 | 9/23 | The Fiat-Shamir Transformation. Part 1 of transformations from computer programs to circuits. | Sections 5.1-5.4 of the course reference. | Lecture 9 slides |
| 10 | 9/28 | Part 2 of transforamtions from computer programs to circuits. Succinct arguments by combining interactive proofs and polynomial commitment schemes. A first polynomial commitment scheme. | Section 5.5 of the course reference. | |
| 11 | 9/30 | MIPs (Part 1). | Chapter 6 of the course reference. | |
| 12 | 10/5 | MIPs (Part 2). | Sections 7.1-7.2 of the course reference. | |
| 13 | 10/7 | Probabilistically Checkable Proofs (PCPs). A first PCP from an MIP. Interactive Arguments from PCPs via Merkle Trees (Kilian). | Sections 7.3-7.6 of the course reference. | |
| 14 | 10/12 | A first quasi-linear length PCP for RAM execution. | Section 8.1-8.3 of the course reference. | |
| 15 | 10/14 | IOPs: Part 1 | Section 8.4 of the course reference. | |
| 16 | 10/19 | IOPs: Part 2 | Sections 9.1 and 9.2 of the course reference. | |
| Part 4: Zero-Knowledge, Polynomial Commitments, and more | ||||
| 17 | 10/21 | Zero-Knowledge | Sections 9.3 and 9.4 of the course reference. | |
| 18 | 10/26 | Discrete Logarithm Problem. Sigma Protocols. | Chapter 10 of the course reference. | |
| 19 | 10/28 | Pedersen Commitments | Sections 11.1-11.2.2 of the course reference. | |
| 20 | 11/2 | Zero-Knowledge arguments for circuit satisfiability from Pedersen commitments (Cramer-Damgard transformation). | Sections 11.2.3-11.2.5 of the course reference. | |
| 21 | 11/4 | Polynomial commitment schemes based on hardness of discrete log. | Section 11.3 of the course reference. | |
| 22 | 11/7 | Polynomial commitment schemes from pairings. | Section 12.1 of the course reference. | |
| 23 | 11/9 | Wrap up polynomial commitment schemes | Section 12.2 of the course reference. | |
| 24 | 11/14 | Linear PCPs and derived arguments (Part 1) | Sections 12.3-12.5 of the course reference. | |
| 25 | 11/16 | Linear PCPs and derived arguments (Part 2) | Sections 13.1 and 13.2 of the course reference. | |
| XX | 11/21 | No class (Thanksgiving holiday) | ||
| XX | 11/23 | No class (Thanksgiving holiday) | ||
| 26 | 11/28 | Wrap up linear PCPs and derived arguments | Sections 13.3 and 13.4 of the course reference. | |
| 27 | 11/30 | Bird's eye view of argument systems and practical considerations | Section 13.5 of the course reference. | |
| 28 | 12/2 | Applications of zero-knowledge arguments. | Chapter 14 of the course reference. | |
| 29 | 12/7 | TBD | TBD |