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 recent applications of probabilistic proof systems to cloud computing and cryptocurrencies.
There are no formal prerequisites for this course. However, mathematical maturity will be expected, as will some 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).
There is no required course textbook---as the course will be covering topics at the cutting edge of research and practice, no appropriate text exists. The instructor will, however, release relevant lecture notes in advance of most lectures (and immediately after the others). The schedule and lecture notes that we will be using are posted below (they will evolve over the course of the semester).
Grades in the course will be based on three problem sets and a final project. The problem sets will count for 60% of the grade, while the final project will count for 40%.
This course focuses on the design and analysis of probabilistic proof systems, mostly from a theoretical perspective. While I will frequently discuss implementation issues and practical efficiency in lectures, the problem sets will not require programming.
The final project can be either theory or implementation-based. Example course projects are: (1) Explore existing open-source implementations of probabilistic proof systems and compare their performances in the context of a chosen problem or application (or better yet, improve over the off-the-shelf implementations that are available); (2) Read a recent research paper related to a topic covered in the class and write a comprehensive, readable summary and your opinion of it; (3) Work on a research problem related to the course material and your own research, and write a paper following a conference-paper-like format that describes your findings; (4) Implement one or more algorithms covered in the course or from the research literature, and do a comprehensive performance evaluation of your implementation.
The course project can be done collaboratively in groups of up to 3 people. In fact, collaboration is encouraged. However, the more people in a group, the more substantial the project is expected to be.
After class or by appointment. My office is SMH 354.
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 |
| Part 1. Introduction and The Power of Randomness | |||
| 1 | 8/31 | Course overview; introduction to probabilistic proof systems (what are interactive proofs, arguments, zero-knowledge proofs, MIPs, and PCPs?); Quiz 0. | Lecture 1 notes. |
| 2 | 9/5 | The power of randomness (Part 1): Fingerprinting | Section 1 of these notes. |
| 3 | 9/7 | The power of randomness (Part 2): Freivalds' Algorithm for verifying matrix multiplication. Formal introduction to interactive proofs. | Section 2 of these notes. |
| Part 2. Interactive Proofs | |||
| 4 | 9/12 | Low-degree and multilinear extensions. | Lecture 4 notes |
| 5 | 9/14 | LFKN's sum-check protocol. | Lecture 5 notes |
| 6 | 9/19 | A first application of sum-check: arithmetization and LFKN's interactive proof for #SAT. | Lecture 6 notes |
| 7 | 9/21 | A second application of sum-check: An optimal interactive proof for matrix multiplication. | Lecture 7 notes |
| 8 | 9/26 | The GKR Protocol: Part 1. | Lecture 8 notes |
| 9 | 9/28 | Finishing the GKR protocol. | The rest of the notes from Lecture 8. |
| 10 | 10/3 | Part 1 of transformations from computer programs to circuits. | Lecture 10 notes |
| Part 3: Turning Interactive Proofs into Succinct Arguments | |||
| 11 | 10/5 | Part 2 of transformations from computer programs to circuit: circuit satisfiability and the importance of succinctness. | Lecture 11 notes |
| 12 | 10/10 | Succinct arguments by combining interactive proofs and polynomial commitment schemes. | Lecture 12 notes |
| Part 4. MIPs, PCPs, Linear PCPs, and How To Turn Them Into Arguments | |||
| 13 | 10/12 | MIPs (Part 1). | Lecture 13 notes |
| 14 | 10/17 | MIPs (Part 2). | Lecture 14 notes |
| 15 | 10/19 | Probabilistically Checkable Proofs (PCPs). A first PCP from an MIP. Interactive Arguments from PCPs via Merkle Trees (Kilian). | Lecture 15 notes |
| 16 | 10/24 | Interactive Arguments from "structured" PCPs (IKO). | Lecture 16 notes |
| 17 | 10/26 | A first structured PCP from the Hadamard Code. | Lecture 17 notes |
| 18 | 10/31 | A second structured PCP (QAPs). | Lecture 18 notes |
| Part 4. Zero-Knowledge | |||
| 19 | 11/2 | Zero-Knowledge Part 1 | Vadhan's survey (everything except the section on Zero-Knowledge for NP) |
| 20 | 11/7 | Zero-Knowledge Part 2 | Vadhan's survey (the section on Zero-Knowledge for NP) |
| 21 | 11/9 | Pedersen commitments, Schnorr's Zero-Knowledge Proof of Knowledge of the opening of a Pedersen commitment. | Lipmaa's Slides (slides 36-46, and slides 63-66). |
| 22 | 11/14 | Anything provable is provable in Zero-Knowledge. | Reading TBD |
| 23 | 11/16 | Polynomial Commitment Schemes Revisited | Reading TBD |
| Part 5. Miscellaneous | |||
| 24 | 11/21 | Short PCPs (Part 1) | Lecture 24 notes |
| 25 | 11/28 | Short PCPs (Part 2) | The rest of the notes from Lecture 24 |
| 26 | 11/30 | Streaming Interactive Proofs (Part 1) | See these slides |
| 27 | 12/5 | Streaming Interactive Proofs (Part 2) | Reading TBD |