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.