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

Description

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.

Prerequisites

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

Grading

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

Schedule

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
Part 3: Turning Interactive Proofs into Argument Systems and Zero-Knowledge Proofs
99/28Finishing the GKR protocol. Transformations from computer programs to circuits. The importance of succinctness. Reading TBD
1010/3 Succinct arguments by combining GKR with polynomial commitment schemes. Examples of polynomial commitment schemes. Reading TBD
1110/5 Zero-Knowledge Proofs Part 1. Reading TBD
1210/10 Zero-Knowledge Proofs Part 2. Reading TBD
1310/12 Zero-Knowledge Proofs Part 3. Reading TBD
Part 4. MIPs, PCPs, Linear PCPs, and How To Turn Them Into Arguments
1410/17 Multi-Prover Interactive Proofs Part 1 Reading TBD
1510/19 Multi-Prover Interactive Proofs Part 2. 2-message arguments for P from standard crypto assumptions. Reading TBD
1610/24 Probabilistically Checkable Proofs (PCPs). A first PCP from an MIP. Reading TBD
1710/26 Interactive Arguments from PCPs using CRHFs (Kilian). Reading TBD
1810/31 Interactive Arguments from "structured" PCPs (IKO). Reading TBD
1911/2 A first structured PCP from the Hadamard Code. Reading TBD
2011/7 A second structured PCP (QAPs). Reading TBD
2111/9 Interactive Oracle Proofs Part 1 (?) Reading TBD
2211/14 Interactive Oracle Proofs Part 2 (?) Reading TBD
2311/16 Block Chains Part 1 (?) Reading TBD
2411/21 Block Chains Part 2 (?) Reading TBD
2511/28 TBD Reading TBD
2611/30 TBD Reading TBD
2712/5 TBD Reading TBD