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:

Moni Naor, Verification of a human in the loop or Identification via the Turing Test, Abstract , Postscript , gzipped Postscript

Back to On-Line Publications

Back Home