##
Does Parallel Repetition Lower the Error in Computationally Sound
Protocols?

** Authors: M. Bellare, R. Impagliazzo, and
M. 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.

** Ref:** Extended abstract was in Proceedings of 38th Annual Symposium
on Foundations of Computer Science, IEEE, 1997. Full paper available
below.

** Full paper: ** Available as compressed
postscript, postscript, or pdf. ( Help if
this doesn't work).