COSC 544 - Probabilistic Proof Systems

Fall 2017

Georgetown University

Prof. Justin Thaler

Tuesday and Thursday, 9:30 to 10:45

Intercultural Center 204B

Email: justin.thaler at georgetown dot edu

Course Overview


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).

Reference Material

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.

Academic Honesty

Academic honesty is taken very seriously, in accordance with Georgetown's Honor System. For problem sets, you are welcome to work with others or use other resources, but when you actually write your solutions you must do so by yourself as if you are taking an exam. You must also explicitly list all collaborators with whom you worked and any references or online material you used, separately for each problem. Most importantly, you must never turn in something that you do not understand. I reserve the right to ask you to explain to me something that you turned in; if you cannot do so in a way that demonstrates your understanding, then you will receive no credit and possibly be reported to the Honor Council.

Lateness Policy for Problem Sets

Problem sets should be handed in by the end of lecture on the day they are due. That is, bring a physical copy of the problem set to class to give to me at the end of lecture. Problem sets not handed in by the end of lecture will be considered late, and 10% of the points deducted. If a problem set is late, you may email it to me rather than hand in a physical copy. Problem sets not handed in until the day after the deadline will have an additional 10% deducted. Beyond this point, problem sets will not be accepted.

Course Logistics

Office Hours

After class or by appointment. My office is SMH 354.

Title IX: Sexual Misconduct and Sexual Harassment

Georgetown University and its faculty are committed to supporting survivors of sexual misconduct, including relationship violence and sexual assault. Please note that university policy requires faculty members to report any disclosures about sexual misconduct to the Title IX Coordinator, whose role is to coordinate the University’s response to sexual misconduct. For details of University resources, consult Georgetown University's Sexual Misconduct Reference Guide.


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 NumberDateDescription Readings
Part 1. Introduction and The Power of Randomness
18/31Course overview; introduction to probabilistic proof systems (what are interactive proofs, arguments, zero-knowledge proofs, MIPs, and PCPs?); Quiz 0. Lecture 1 notes.
29/5The power of randomness (Part 1): Fingerprinting Section 1 of these notes.
39/7The 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
49/12 Low-degree and multilinear extensions. Lecture 4 notes
59/14 LFKN's sum-check protocol. Lecture 5 notes
69/19A first application of sum-check: arithmetization and LFKN's interactive proof for #SAT. Lecture 6 notes
79/21A second application of sum-check: An optimal interactive proof for matrix multiplication. Lecture 7 notes
89/26The GKR Protocol: Part 1. Lecture 8 notes
99/28Finishing the GKR protocol. The rest of the notes from Lecture 8.
1010/3 Part 1 of transformations from computer programs to circuits. Lecture 10 notes
Part 3: Turning Interactive Proofs into Succinct Arguments
1110/5 Part 2 of transformations from computer programs to circuit: circuit satisfiability and the importance of succinctness. Lecture 11 notes
1210/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
1310/12 MIPs (Part 1). Lecture 13 notes
1410/17 MIPs (Part 2). Lecture 14 notes
1510/19 Probabilistically Checkable Proofs (PCPs). A first PCP from an MIP. Interactive Arguments from PCPs via Merkle Trees (Kilian). Lecture 15 notes
1610/24 Interactive Arguments from "structured" PCPs (IKO). Lecture 16 notes
1710/26 A first structured PCP from the Hadamard Code. Lecture 17 notes
1810/31 A second structured PCP (QAPs). Lecture 18 notes
Part 4. Zero-Knowledge
1911/2 Zero-Knowledge Part 1 Vadhan's survey (everything except the section on Zero-Knowledge for NP)
2011/7 Zero-Knowledge Part 2 Vadhan's survey (the section on Zero-Knowledge for NP)
2111/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).
2211/14 Anything provable is provable in Zero-Knowledge. Reading TBD
2311/16 Polynomial Commitment Schemes Revisited Reading TBD
Part 5. Miscellaneous
2411/21 Short PCPs (Part 1) Lecture 24 notes
2511/28 Short PCPs (Part 2) The rest of the notes from Lecture 24
2611/30 Streaming Interactive Proofs (Part 1) See these slides
2712/5 Streaming Interactive Proofs (Part 2) Reading TBD