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

Instructor: Prashant Nalini Vasudevan

Times: Tue 10am - 12am

Location: Online, was never in COM1-VCRM (COM1-02-13)

Office Hours: by appointment

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.

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 | of Justin Thaler's book | Lec 12 |

13 | Nov 9 | Retrospective and uncovered topics | Lec 13 |

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.

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.

Other courses on probabilistic proof systems

Justin Thaler's lecture notes from his course at Georgetown

Alessandro Chiesa's course at UC Berkeley

Eli Ben-Sasson's lecture notes from his course on PCPs at the Technion

Other resources

Computational Complexity: A Modern Approach, by Arora and Barak (Chapters 1-7 are pre-requisites for the course)

A history of the PCP Theorem, by Ryan O'Donnell

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:

Read a set of 1-3 research papers on a topic of your choice

Present them in class

Write an expository report on them

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

It should start with an introduction that sets up the background, introduces the problems being solved in the papers, and explains what their significance is.

This should be followed by a technical overview of the approach taken to solve these problems. Give a high-level sketch of the constructions/proofs, identify the primary technical challenges, and how they are overcome. The level of detail should be about that of the lecture notes – the details do not have to be present, but the main ideas should come through.

Finally, identify the primary questions left open by the papers, and discuss some approaches that you think might answer them.

**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:**

Form a group, pick your papers, and discuss it with me by: Oct 15

Presentations will be on: Nov 16 and 18 (10am to noon)

Final report due by: Nov 23

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

Proofs for lattice problems (any two of these)

On the Limits of Nonapproximability of Lattice Problems, by Goldreich and Goldwasser

Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems, by Peikert and Vaikuntanathan

Lattice Problems in NP ∩ coNP, by Aharonov and Regev

Better delegation of computation

Constant-Round Interactive Proofs for Delegating Computation, by Reingold, Rothblum, and Rothblum

Batch verification of SZK proofs

Batch Verification for Statistical Zero Knowledge Proofs, by Kaslasi, Rothblum, Rothblum, Sealfon, and myself

Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers, by Kaslasi, Rothblum, and myself

IP and PSPACE

IP = PSPACE using Error Correcting Codes, by Or Meir

Needs knowledge of error correcting codes

Interactive Oracle Proofs

Interactive Oracle Proofs, by Ben-Sasson, Chiesa, and Spooner

Delegating quantum computation

Classical Verification of Quantum Computations, by Urmila Mahadev

Needs knowledge of quantum computation and some cryptography

The PCP Theorem

The PCP Theorem by Gap Amplification, by Irit Dinur

Not for the fainthearted

Communication Complexity of Interactive Proofs

On the Complexity of Interactive Proofs with Bounded Communication, by Goldreich and Hastad

On Interactive Proofs with a Laconic Prover, by Goldreich, Vadhan, and Wigderson

Private vs. public randomness in Interactive Proofs

Private Coins versus Public Coins in Interactive Proof Systems, by Goldwasser and Sipser

On Emulating Interactive Proofs with Public Coins, by Goldreich and Leshkowitz

Randomness Complexity of Interactive Proofs

On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs, by Applebaum and Golombek