# Does parallel repetition reduce the error in computationally
sound protocols?

### Mihir Bellare Russell Impagliazzo Moni Naor

### Abstract:

Whether or not parallel repetition lowers the error has been a fundamental
question in the theory of protocols, with applications in many different
areas. It is well known that parallel repetition reduces the error at an
exponential rate in interactive proofs and Arthur-Merlin games. It seems
to have been taken for granted that the same is true in arguments, or other
proofs where the soundness only holds with respect to computationally bounded
parties.
We show that this is not the case. Surprisingly, parallel repetition can
actually fail in this setting. We present four-round protocols whose error
does not decrease under parallel repetition. This holds for any (polynomial)
number of repetitions. These protocols exploit non-malleable encryption and
can be based on any trapdoor permutation. On the other hand we show that
for three-round protocols the error does go down exponentially fast.

The question of parallel error reduction is particularly important when
the protocol is used in cryptographic settings like identification, and the
error represent the probability that an intruder succeeds.

Postscript
, gzipped Postscript
.

**Related On-Line Papers:**

Back to On-Line Publications

Back Home