Probabilistic Proof Systems

CS6230: Topics in Information Security (AY2021/2022, Sem 1)

Information

Instructor:       Prashant Nalini Vasudevan
Times:            Tue 10am - 12am
Location:        Online, was never in COM1-VCRM (COM1-02-13)
Office Hours:  by appointment

Course Description

Starting in the 80's, a number of non-classical notions of proofs have been formalised by computer scientists. Whereas a classical proof in mathematics is a static sequence of claims that can be verified line-by-line, these systems inherently involve randomness and interactions between multiple parties. Understanding these proof systems has led to some of the greatest advances in theoretical computer science and cryptography over the past few decades.

This course will introduce students to such probabilistic proof systems and their connections to complexity theory and cryptography. Topics covered will include interactive proofs, probabilistically checkable proofs, zero-knowledge, argument systems, and their various applications. The objective will be to provide students with a foundation for research in these and related areas.

Pre-requisites: It is strongly recommended that prospective students have taken a class in computational complexity theory (CS5230 or equivalent). In particular, you will need to be comfortable with notions like reductions between computational problems, NP-hardness (and hardness for other complexity classes), and the abstraction of programs as Turing Machines. Basic familiarity with probability theory and algebra (specifically linear algebra, finite fields, and groups) will be assumed. Knowledge of statistics and the theory of cryptography will be helpful.

Schedule

The following is a tentative plan for the class. It will change over the course of the semester based on our preferences and the pace we set.

Week Date Topics Notes Slides
1 Aug 10 Introduction, Defining Interactive Proofs Lec 1 Lec 1
2 Aug 17 The Power of Interactive Proofs Lec 2 Lec 2
3 Aug 24 Resources in Interactive Proofs Lec 3 Lec 3
4 Aug 31 Computational Efficiency and Delegation Lec 4 Lec 4
5 Sep 7 Zero Knowledge (ZK) Lec 5 Lec 5
6 Sep 14 Statistical ZK (SZK) Lec 6 Lec 6
7 Sep 28 Polarisation of Statistical Distance, more SZK problems Lec 7 Lec 7
8 Oct 5 SZK Completeness, Probabilistically Checkable Proofs (PCPs) Lec 8 Lec 8
9 Oct 12 Hardness of Approximation, PCP for linear systems Lec 9 Lec 9
10 Oct 19 The Hadamard PCP, Interactive Arguments Lec 10 Lec 10
11 Oct 26 Arguments from PCPs, the Fiat-Shamir transformation Lec 11 Lec 11
12 Nov 2 Cryptographic Protocols - Identification and Signatures
See Chapter 11
of Justin Thaler's book
 Lec 12
13 Nov 9 Retrospective and uncovered topics Lec 13

Grading

Grading will be based on 3-4 problem sets (60%), and a final project (40%). The problem sets will be posted periodically throughout the semester. The final project will involve reading a few topically related papers and writing a survey of them; details will be posted later.

Problem Sets

References

There is no textbook for the course. The material will be based on research in this area over the past 30 years. Notes will be posted in the schedule above for most lectures, and they will contain several relevant references.

Final Project

The objective of the final project is to familiarise you with a topic related to probabilistic proof systems that we did not cover in detail in class (because it was either too advanced or too specific for the scope of the course). A secondary objective is for rest of the class to have a glimpse of this topic so they can be aware of it. You will work either individually or in pairs, and your tasks will be the following:

Selecting papers: I can help you in picking the set of papers to read. Below, I will maintain a list of appropriate topics and papers related to them. You are welcome to pick papers that are not on the list. If you are interested in reading about a specific topic that is not below, write to me and I can help you find relevant papers. Any paper can be covered by at most one group.

Once you have formed a group (or decided to work alone) and picked the set of papers you want to read, email me your plan, and we will set up a short meeting to discuss whether it is sufficient, how feasible it is, what background you might need, etc.. I encourage you to talk to me sooner rather than later, in case we need to make changes to your plan.

Presentation: For the presentation, you will have 20 minutes if you are working on your own, and 30 minutes if in a group (to be split equally between partners). Be sure to leave some time for questions at the end. These durations may change depending on how many groups are formed.

Report: The report is to be a self-contained exposition of the papers you read. Your intended readers should be your classmates, so anyone who has taken this class should be able to understand and appreciate your report. Only one report per group is needed, so you can collaborate with your partner on the writing (unlike in the case of problem sets).

Grading: You will be graded on the level of understanding apparent in your talk and report, your ability to place the results you read about in the larger context of research on probabilistic proofs, to clearly communicate the central ideas in the papers, and to identify interesting open questions. Grading of this sort is, unfortunately, necessarily subjective and I cannot list more specific rubrics ahead of time. If you put in the effort, though, you will probably do well.

Dates and deadlines:

Potential topics: The following are sets of papers that are intended to be read together for the final project. If you pick a set of papers outside this list, we will need to ensure they are as substantial as these. I will keep adding to this list, so check back once every few days. Also, if you are interested in one of the following topics but the papers listed under it seem too heavy, talk to me and we can find alternatives.