Does parallel repetition lower the error in computationally sound protocols?
Does parallel repetition lower the error in computationally sound protocols?
复制标题
并行重复是否会降低计算合理协议中的错误？
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Naor
中科院分区：
文献类型：
--
作者：
M. Bellare;R. Impagliazzo;M. Naor
是否平行重复降低了错误是协议理论中的一个基本问题，在许多不同领域的应用。众所周知，在交互式证明和Arthur-Merlin游戏中，并行重复以指数率减少了错误。似乎是理所当然的，在参数中也是如此，或者其他仅在计算方面存在的证据。我们表明事实并非如此。令人惊讶的是，在这种情况下，并行重复实际上可能会失败。我们提出四轮协议，其在并行重复下的错误不会减小。这适用于任何（多项式）的重复数。这些协议利用了不可损坏的加密，可以基于任何陷阱置换。另一方面，我们表明，对于三轮协议，错误确实会迅速下降。当协议在标识之类的加密设置中使用时，并行误差降低的问题尤为重要，而误差表示入侵者成功的概率。
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 represents the probability that an intruder succeeds.