Probabilistic Proof Systems

Expositions by Oded Goldreich

Several alternative formulations of the concept of an efficient proof system are nowadays coexisting in Theoretical Computer Science. These systems include the classical formulation of NP, interactive proof systems (giving rise to the class IP), computationally-sound proof systems, and probabilistically checkable proofs (PCP) which are closely related to multi-prover interactive proofs (MIP). Although these notions are sometimes introduced using the same generic phrases, they are actually very different in motivation, applications and expressive power.

Except for NP, all proof systems reviewed are probabilistic and furthermore have a non-zero error probability. However, the error probability is explicitly bounded and can be reduced by successive applications of the proof system. In all cases, non-zero error probability is essential to the interesting properties and consequences which these probabilistic proof systems have.

Four expositions of mine are available on-line are:

• Probabilistic Proof Systems - A Primer, June 2008.
  This is the latest and most recommended exposition. It provides a comprehensive treatment of the basic notions and results, and contains proof outlines and/or sketches for the main results.
  (This text is an abbreviated and self-contained version of Chapter 9 in Computational Complexity: A Conceptual Perspective.)
• Probabilistic Proof Systems (survey), May 1995. (revised, Dec. 1996).
  This survey was intended for a general audience and has appeared in the proceedings of ICM94, the International Congress of Mathematicians 1994. It focuses on the very basics and presents some well-known constructions.
• A Taxonomy of Proof Systems, Dec. 1995 (revised Sept. 1996).
  This survey was intended for readers with some background in computational complexity and appeared in the Complexity Theory Retrospective II. It provides a wider coverage than the first, but presents no constructions.
• Probabilistic Proof Systems (Lecture Notes), Sept. 1996.
  These are lecture notes in the strict sense of the word. They were prepared for a series of lectures given in the Theory Student Seminar of the CS Department of UC-Berkeley.

Additional related material available on-line

• S. Vadhan, Lecture notes on Probabilistic Proof Systems - Part I (interactive and zero-knowledge proofs).
• M. Sudan, Lecture notes on Probabilistic Proof Systems - Part II (probabilistically checkable proofs).
• O. Goldreich, webpage on zero-knowledge (including a tutorial).
• O. Goldreich, papers on Probabilistic Proof Systems.

• Chapter 2 in Modern Cryptography, Probabilistic Proofs and Pseudorandomness surveys various types of probabilistic proof systems.
• Chapter 9 in Computational Complexity: A Conceptual Perspective (2008) provides a revised and extended version of the above.
• Chapter 4 in Foundations of Cryptography provides an extensive treatment of zero-knowledge.