COSC 544 - Probabilistic Proof Systems

Fall 2020

Georgetown University

Prof. Justin Thaler

Monday and Wednesday, 12:30pm to 1:45pm

Online via Zoom

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

Reference Material

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.

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 not submitted 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.

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 ReadingsSlides
Part 1. Introduction and The Power of Randomness
18/26Course overview; introduction to probabilistic proof systems (what are interactive proofs, arguments, zero-knowledge proofs, MIPs, and PCPs?); Quiz 0. No reading. Lecture 1 slides
28/31The 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
39/2 LFKN's sum-check protocol. Chapter 2 of the course reference. Lecture 3 slides
49/7 Arithmetization and LFKN's interactive proof for #SAT. Chapter 3 of the course reference. Lecture 4 slides
59/9More 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
69/14The GKR Protocol. Sections 4.3-4.5 of the course reference. Lecture 6 slides
79/16The GKR protocol continued.Section 4.6 of the course reference.
89/21 Wrap up the GKR protocol. Section 4.7 of the course reference.
Part 3: Succinct Arguments for NP-complete problems.
99/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
109/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.
119/30 MIPs (Part 1). Chapter 6 of the course reference.
1210/5 MIPs (Part 2). Sections 7.1-7.2 of the course reference.
1310/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.
1410/12A first quasi-linear length PCP for RAM execution. Section 8.1-8.3 of the course reference.
1510/14 IOPs: Part 1 Section 8.4 of the course reference.
1610/19 IOPs: Part 2 Sections 9.1 and 9.2 of the course reference.
Part 4: Zero-Knowledge, Polynomial Commitments, and more
1710/21 Zero-Knowledge Sections 9.3 and 9.4 of the course reference.
1810/26 Discrete Logarithm Problem. Sigma Protocols. Chapter 10 of the course reference.
1910/28 Pedersen Commitments Sections 11.1-11.2.2 of the course reference.
2011/2 Zero-Knowledge arguments for circuit satisfiability from Pedersen commitments (Cramer-Damgard transformation). Sections 11.2.3-11.2.5 of the course reference.
2111/4 Polynomial commitment schemes based on hardness of discrete log. Section 11.3 of the course reference.
2211/7 Polynomial commitment schemes from pairings. Section 12.1 of the course reference.
2311/9 Wrap up polynomial commitment schemes Section 12.2 of the course reference.
2411/14 Linear PCPs and derived arguments (Part 1) Sections 12.3-12.5 of the course reference.
2511/16 Linear PCPs and derived arguments (Part 2) Sections 13.1 and 13.2 of the course reference.
XX11/21 No class (Thanksgiving holiday)
XX11/23 No class (Thanksgiving holiday)
2611/28 Wrap up linear PCPs and derived arguments Sections 13.3 and 13.4 of the course reference.
2711/30 Bird's eye view of argument systems and practical considerations Section 13.5 of the course reference.
2812/2 Applications of zero-knowledge arguments. Chapter 14 of the course reference.
2912/7 TBD TBD