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 342-C.
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.
|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|
|Part 3: Turning Interactive Proofs into Argument Systems and Zero-Knowledge Proofs|
|9||9/28||Finishing the GKR protocol. Transformations from computer programs to circuits. The importance of succinctness.||Reading TBD|
|10||10/3||Succinct arguments by combining GKR with polynomial commitment schemes. Examples of polynomial commitment schemes.||Reading TBD|
|11||10/5||Zero-Knowledge Proofs Part 1.||Reading TBD|
|12||10/10||Zero-Knowledge Proofs Part 2.||Reading TBD|
|13||10/12||Zero-Knowledge Proofs Part 3.||Reading TBD|
|Part 4. MIPs, PCPs, Linear PCPs, and How To Turn Them Into Arguments|
|14||10/17||Multi-Prover Interactive Proofs Part 1||Reading TBD|
|15||10/19||Multi-Prover Interactive Proofs Part 2. 2-message arguments for P from standard crypto assumptions.||Reading TBD|
|16||10/24||Probabilistically Checkable Proofs (PCPs). A first PCP from an MIP.||Reading TBD|
|17||10/26||Interactive Arguments from PCPs using CRHFs (Kilian).||Reading TBD|
|18||10/31||Interactive Arguments from "structured" PCPs (IKO).||Reading TBD|
|19||11/2||A first structured PCP from the Hadamard Code.||Reading TBD|
|20||11/7||A second structured PCP (QAPs).||Reading TBD|
|21||11/9||Interactive Oracle Proofs Part 1 (?)||Reading TBD|
|22||11/14||Interactive Oracle Proofs Part 2 (?)||Reading TBD|
|23||11/16||Block Chains Part 1 (?)||Reading TBD|
|24||11/21||Block Chains Part 2 (?)||Reading TBD|