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.