A Parallel Repetition Theorem for Any Interactive Argument
by Iftach Haitner
Oded's comments
It has been known for more than a decade that parallel repetition
may fail to reduce the error in computationally-sound proof
(a.k.a argument) systems. This work shows that any argument system
can be slightly modified such that parallel repetition does reduce
the error in the resulting argument system. The modification
of a generic argument amounts to having the verifier abort at random
with probability $1/4$ (i.e., after each round, the verifier aborts
with probability $1/4r$, where $r$ denotes the number of rounds).
In case of abort, the verifier always accepts, which means that
this modification increases the probability of error.
The benefit of this modification is that the probability
of cheating in the parallel execution is not sensitive to whether
the verifier aborts in any typical individual copy,
which establishes sufficient independence between the copies.
The above random-termination modification is applicable
to error-reduction (by parallel repetition) of any two-party game,
where the error here refers to the probability that a specific
party wins although we wish it to lose.
Note that the result is actually incomparable to a recent
Prallalel Repetition Theorem for any (unmodified) public-coin protocol
(by Hastad, Pass, Pietrzak, and Wikstrom).
The original abstract
The question whether or
not parallel repetition reduces the soundness error is a fundamental
question in the theory of protocols. While parallel repetition reduces
(at an exponential rate) the error in interactive proofs and (at a
weak exponential rate) in special cases of interactive arguments
(e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97],
and constant-round public-coin protocols - Pass and Venkitasubramaniam
[STOC '07]), Bellare et. al gave example of interactive arguments for
which parallel repetition does not reduce the soundness error at all.
We show that by slightly modifying any interactive argument, in a way
that preserves its completeness and only slightly deteriorates its
soundness, we get a protocol for which parallel repetition does reduce
the error at a weak exponential rate. In this modified version, the
verifier flips at the beginning of each round an (1 - frac1{4m},
frac1{4m}) biased coin (i.e., 1 is tossed with probability 1/4m),
where m is the round complexity of the (original) protocol. If the
coin is one, the verifier halts the interaction and accepts, otherwise
it sends the same message that the original verifier would. At the end
of the protocol (if reached), the verifier accepts if and only if the
original verifier would.
Back to
list of Oded's choices.