Probabilistically Checkable Arguments by Yael Kalai, Microsoft

Abstract: We give two results. The first is a general reduction converting any public-coin interactive proof into a one-round (two-message) argument. It is based on a method of Aiello et al, using a Private-Information-Retrieval (PIR) scheme to collapse rounds in interactive proofs. For example, the reduction implies that for any security parameter t, the membership in any language in PSPACE can be proved by a one-round (two-message) argument of size poly(n,t), which is sound for malicious provers of size 2^t. (Note that the honest prover in this construction runs in exponential time, since she has to prove membership in PSPACE, but we can choose t such that 2^t is significantly larger than the running time of the honest prover). We then define the notion of a *probabilistically checkable argument* (PCA). This is a relaxation of the notion of probabilistically checkable proof (PCP). It is defined analogously to PCP, except that the soundness property is required to hold only computationally. We consider the model where each verifier is associated with a public key, and each PCA is verifier-dependent, i.e., it depends on the verifier's public key. (The key does not need to be certified, and we can assume that the verifier simply publishes it on his web-page). We show that every NP language, verifiable by a poly-size formula, has a PCA (with efficient honest prover) of size polynomial in the size of the *witness*. This compares to the best PCPs that are of size polynomial in the size of the *instance* (that may be significantly larger). The number of queries to these PCAs is poly-logarithmic. The soundness property, in all our results, relies on exponential hardness assumptions. This is joint work with Ran Raz.

Joanne Talbot Hanley

Last modified: Mon Aug 16 11:10:58 EDT 2010