This monograph is about various proof systems that are central to the study of computational complexity theory, cryptography, and the hardness of approximation. A proof system consists of two parties, called the prover and the verifier, whose combined objective is to validate a mathematical assertion through a sequence of message interactions and computations. Proof systems typically require the verifier to follow a computationally efficient verification procedure, whereas they allow the prover to be computationally unbounded. If the verification procedure of the verifier can be performed in deterministic polynomial time and the prover initiates the only message interaction between the two parties, then the resulting proof system is known to be equivalent to the NP-proof system. In this monograph, the author surveys three kinds of probabilistic proof systems, namely, interactive proofs, zero-knowledge proofs, and Probabilistically Checkable Proofs (PCPs), that differ from NP-proof systems in essentially two regards. First, these proof systems utilize probabilistic verification procedures in the computation of the verifier and, as a result, also permit a small probability of error in the final decision by the verifier on the validity of the assertion. Second, these proof systems allow for multiple interactions between the two parties, making proofs a dynamic process of validating an assertion. The monograph begins with an abstract and is then followed by Preface, Conventions and Organization, Contents, three chapters, Bibliographic Notes, Acknowledgements, and References in this order. The three chapters are: Chapter 1 ‒ Interactive proof systems, Chapter 2 ‒ Zero-knowledge proof systems, and Chapter 3 ‒ Probabilistically checkable proof systems. A chapter-wise summary of the monograph is presented next. Chapter 1: Interactive proof systems. The chapter opens with a discussion on the motivation behind the notion of interactive proof systems. The discussion makes clear that having bounded uncertainty and interaction in proofs is quite natural, as is the case in various real-life scenarios, such as debates. A formal definition of interactive proof systems is then presented in which two technical conditions, completeness and soundness, are emphasized. The chapter notes that if the verifier in an interactive proof system is not permitted to use randomness (or more generally, the soundness error of the interactive proof system is zero), then the resulting proof system is provably no more powerful than an NP-proof system. The chapter presents a nice story from Greek mythology to illustrate the main idea underlying the interactive proof system for the Graph Non-Isomorphism problem, a problem in coNP for which no deterministic polynomial-time algorithm is known yet. The very first example on interactive proof systems for Graph Non-Isomorphism, presented in the chapter, illustrates the power of these systems over NP-proof systems. While this problem has a 2-round interactive proof system, it is currently unknown whether it also has an NP-proof system. The chapter shows that the full computational power of interactive proof systems coincides with that of algorithms that use polynomial amount of work-space (i.e., IP = PSPACE). Finally, the chapter concludes with a discussion on several variants of the basic definition of interactive proofs (e.g., Arthur-Merlin proof systems that are interactive proof systems in which randomness is not private, and interactive proof systems in which error is permitted in both soundness and completeness conditions) and on the possibility of restricting the computational power of the prover. Chapter 2: Zero-knowledge proof systems. This chapter defines zero-knowledge interactive proof systems in which the scenario is that a malicious verifier tries to learn information from proofs provided by an honest prover. A zero-knowledge proof system is essentially an interactive proof system with an additional constraint: The honest prover has a strategy (proof) by which he can convince any efficient (but adversarial) verifier of the validity of a given assertion without revealing anything except its validity. A formal definition of zero-knowledge proofs, presented in the chapter, considers a probabilistic polynomial-time algorithm called {\it simulator} that has the ability to efficiently simulate the view of any efficient verifier without needing interaction. Based on how well enough this simulation is performed, the proof system is referred to as perfect, almost-perfect/statistical, or computational zero-knowledge. The chapter presents a perfect zero-knowledge proof system for Graph Isomorphism and gives a nice explanation of its analysis. This example makes clear that zero-knowledge proofs, although counter-intuitive, can indeed be realized. The chapter presents a more involved (computational) zero-knowledge proof system for an NP-complete problem, $3$-Colorability, under the assumption that a certain kind of one-way functions exist. The analysis and the implementation of this proof system is briefly sketched in the chapter; a curious reader will perhaps need to consult outside references for complete details. The chapter points out that under the assumption of the existence of these one-way functions, any problem solvable by an interactive proof system can also be solved by a (computational) zero-knowledge one (i.e., IP = CZK). The power of statistical zero-knowledge proofs is summarized in one paragraph. The chapter concludes with discussions on a related concept called proofs of knowledge. The author has done a very nice job of explaining the abstract notion of zero-knowledge proofs and surveying some important results known on this topic. There is one place in the chapter where I find myself puzzled while going over it; it’s the fact mentioned on page 29 that only sets in Bounded-error Probabilistic Polynomial-Time class (BPP) have zero-knowledge proofs in which the verifier is deterministic. The perplexing aspect for me is that BPP, by definition, allows randomness in its model, and so it is unclear how problems solvable by BPP-algorithms can indeed be solved by zero-knowledge proofs in which the verifier is deterministic. Perhaps, more explanation is needed to illustrate this point. Chapter 3: Probabilistically checkable proof systems. The chapter on Probabilistically Checkable Proofs (PCPs), the longest one in the monograph, defines this proof system in terms of an efficient verifier that has oracle access to an alleged proof. The main complexity class corresponding to PCPs, denoted PCP$(r,q)$, is characterized by the randomness complexity $r$ and the query complexity $q$ of the proof system. The issues of adaptive versus non-adaptive verifiers and randomness versus proof length are dealt with in the chapter. It is shown that PCP$(r,q)$ can be simulated in deterministic time $O(2^{2^rq+1} \cdot \text{poly})$ and that PCP$(\log, \text{poly})$ is a subclass of NP. The celebrated PCP theorem states the surprising fact that NP $\subseteq$ PCP$(\log, O(1))$, and so the two classes NP and PCP$(\log, O(1))$ are equivalent in computational power. The chapter presents overviews of two different proofs of the PCP theorem: the original proof of the PCP theorem that involves three main conceptual steps as explained in the chapter, and the more recent proof in which step-wise amplification of the PCPs are done starting with a trivial PCP system. The chapter explains how the PCP theorem plays a role in proving hardness of approximation results for various NP-optimization problems, by noting that PCP constructions essentially yield “gap amplifying" reductions for these problems. The chapter surveys various studies done on analyzing the parameters of PCP systems for NP (e.g., the length of proofs in PCPs, the number of queries in PCPs, non-binary queries, etc.). Finally, the chapter briefly discusses some variants of PCPs, such as PCPs of proximity and a stronger form of PCPs for NP. The proof in Section~3.2.1 of the statement NP $\subseteq$ PCP$(\text{poly}, O(1))$ is well explained. The proof of the fact that every problem in NP has a PCP system with logarithmic randomness and polylogarithmic query complexity is succinctly presented, and so one may need to look at additional references for complete details. (For instance, more discussions are needed to explain small-bias probability spaces used in this proof.) The caption of the figure on page 68, Fig.~3.3, does not give much information about the underlying graph. Reviewer’s conclusion: This monograph is aimed for researchers in computational complexity theory and cryptography. It can also be included as a reference or supplemental resource for graduate courses in these disciplines. Although most of the topics are very theoretical in content, the emphasis of the monograph is more on clarity and intuition than on precise mathematical details. Because of this feature, this monograph seems to be easily readable and understood by any starting graduate student in theoretical computer science. Throughout the text, the references are linked to the main results and so it is very convenient for readers to check the original sources of these results for details. The bibliographical notes at the end give an interesting history of the discovery of these proof systems. The monograph deserves full credit for presenting a nice overview of the exciting developments over the period of two decades on these proof systems in a concise, clear, and engaging language. It would certainly be a valuable resource and a guiding pathway for anyone interested in learning about probabilistic proof systems. The only negative aspect of this monograph is its cost in relation to the number of pages. The monograph is less than 100 pages long, but costs as much as \$75. For many readers, this might be too much to pay for such a thin text.
Reviewer: Rahul Tripathi (Tampa)