TY - GEN

T1 - Probabilistically checkable arguments

AU - Kalai, Yael Tauman

AU - Raz, Ran

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2009

Y1 - 2009

N2 - 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. [1], 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 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). 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. The soundness property, in all our results, relies on exponential hardness assumptions for PIR schemes.

AB - 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. [1], 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 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). 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. The soundness property, in all our results, relies on exponential hardness assumptions for PIR schemes.

UR - http://www.scopus.com/inward/record.url?scp=70350343384&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350343384&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03356-8_9

DO - 10.1007/978-3-642-03356-8_9

M3 - Conference contribution

AN - SCOPUS:70350343384

SN - 3642033555

SN - 9783642033551

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 143

EP - 159

BT - Advances in Cryptology - CRYPTO 2009 - 29th Annual International Cryptology Conference, Proceedings

T2 - 29th Annual International Cryptology Conference, CRYPTO 2009

Y2 - 16 August 2009 through 20 August 2009

ER -