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