Are PCPs Inherent in Efficient Arguments?

by Guy Rothblum and Salil Vadhan

Oded's comments

Known results of low communication argument systems utilize PCP systems. My feeling was that this is a coincidence (or rather a consequence of the use of a specific construction paradigm), but the current work essentially proves me wrong. Specifically, any argument system of low communication complexity that is proved sound by reducing (via relatively few queries) the breaking of a cryptographic primitive to the cheating strategy yields a good PCP. Interestingly, the soundness of the candidate PCP is absolute whereas its completeness condition relies on the existence of an implementation of the underlying cryptographic primitive. Indeed, the work present a general definition of a cryptographic primitive, which is of independent interest.
The proof oracle of the constructed PCP system is used to describe a strategy for the prover in the argument system. The PCP verifier first emulates an execution of the argument system and then invokes the reduction in an attempt to break the underlying cryptographic primitive. The PCP verifier accepts iff the original system accepts and the reduction fails to break the primitive. Thus, computational soundness follows by noting that if the prover manages to cheat then the reduction will break the primitive. Interestingly, establishing the completeness condition is the challenging part and it requires the use of a cryptographic primitive that cannot be broken. The query complexity of the constructed PCP equals the sum of (1) the communication complexity of the argument system, and (2) the query complexity of the reduction. I wonder whether the latter term can be eliminated.
[To appear in CCC'09.]

The original abstract

Starting with Kilian (STOC92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC07) raised the question of whether PCPs are inherent in efficient arguments, and to what extent. We give evidence that they are, by showing how to convert any argument system whose soundness is reducible to the security of some cryptographic primitive into a PCP system whose efficiency is related to that of the argument system and the reduction (under certain complexity assumptions).


Back to list of Oded's choices.