# Parallel Repetition of Computationally Sound Protocols Revisited

## Krzysztof Pietrzak and Douglas Wikström

```
```Parallel repetition is well known to reduce the error probability at
an exponential rate for single- and multi-prover interactive
*proofs*.

Bellare, Impagliazzo and Naor (1997) show that this is also true for
protocols where the soundness only holds against computationally
bounded provers (e.g. interactive arguments) if the protocol has at
most three rounds.

On the other hand, for four rounds they give a protocol where this is
no longer the case: the error probability does not decrease below some
constant even if the protocol is repeated a polynomial number of
times. Unfortunately, this protocol is not very convincing as the
communication complexity of each instance of the protocol grows
linearly with the number of repetitions, and for such protocols the
error does not even decrease for some types of interactive
*proofs*. Noticing this, Bellare et al. construct (a quite
artificial) oracle relative to which a four round protocol exists
whose communication complexity does not depend on the number of
parallel repetitions. This shows that there is no ``black-box'' error
reduction theorem for four round protocols.

In this paper we give the first computationally sound protocol where
$\rep$-fold parallel repetition does not decrease the error
probability below some constant for any polynomial $\rep$ (and where
the communication complexity does not depend on $\rep$). The protocol
has eight rounds and uses the universal arguments of Barak and
Goldreich (2001). We also give another *four* round protocol
relative to an oracle, unlike the artificial oracle of Bellare et al.,
we just need a generic group. This group can then potentially be
instantiated with some real group satisfying some well defined
hardness assumptions (we do not know of any candidate for such a group
at the moment).