Probabilistically Checkable Arguments

We give a general reduction that converts any public-coin interactive proof into a one-round (two-message) argument. The reduction relies on a method proposed by Aiello et al. [ABOR00], of using a Private-Information-Retrieval (PIR) scheme to collapse rounds in interactive protocols. 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 2t . (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 2t is significantly larger than the running time of the honest prover). A probabilistically checkable argument (PCA) 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 the argument is of one round (two-message), where the verifier’s message depends only on his (private) randomness. We show that for membership in many NP languages, there are PCAs (with efficient honest provers) that are 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. These results are proved as follows: Similarly to the above mentioned reduction from interactive proofs to one-round arguments, we give a general reduction that converts any interactive-PCP, with certain properties, into a PCA. Roughly speaking, an interactive-PCP (recently defined in [KR08]) is a proof-string that can be verified by reading a small number of its bits, with the help of an interactive proof with very small communication complexity. Roughly speaking, we show that any interactive-PCP, with certain properties, can be converted into a PCA, where the size of the PCA is polynomial in the size of the interactive-PCP’s proof-string and in the communication complexity of the interactive-PCP’s interactive phase. The number of queries to the PCA is polynomial in the number of queries to the interactive-PCP’s proof-string and in the communication complexity of the interactive-PCP’s interactive phase. Combined with a recent interactive-PCP construction of Goldwasser, Kalai and Rothblum [GKR07]1 , the reduction implies the following result: Let t > log n be a security parameter. The satisfi- ability of a Boolean formula Φ(z1, . . . , zk) of size n can be proved by a PCA of size poly(k, t), which is sound for malicious provers of size 2t . The number of queries to the PCA is poly(t), and the running time of the honest-prover is poly(n, t). More generally, the satisfiability of a Boolean circuit Φ(z1, . . . , zk) of size n and depth d can be proved by a PCA of size poly(k, d, t), which is sound for malicious provers of size 2t . The number of queries to the PCA is poly(d, t), and the running time of the honest-prover is poly(n, t).