aqora

A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments.

Itay Berman, Iftach Haitner, Eliad Tsfadia

Electronic colloquium on computational complexityJan 1, 20191 citation

On Parallel Repetition of Interactive Proof Systems

Oded Goldreich

Lecture notes in computer scienceJan 1, 20251 citation

Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems

Richard Cleve, William Slofstra, Falk Unger +1 more

Computational ComplexityApr 29, 200893 citations

A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal +2 more

Electronic colloquium on computational complexityJan 1, 20210 citations

The Randomness Complexity of Parallel Repetition

Kai-Min Chung, Rafael Pass

Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i.e., o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.Consider a m-round interactive protocol with soundness error 1/2. How much extra randomness is required to decrease the soundness error to δ through parallel repetition? Previous work, initiated by Bell are, Goldreich and Goldwasser, shows that for public-coin interactive protocols with statistical soundness, m · O(log (1/δ)) bits of extra randomness suffices. In this work, we initiate a more general study of the above question. We establish the first derandomized parallel repetition theorem for public-coin interactive protocols with computational soundness (a.k.a. arguments). The parameters of our result essentially matches the earlier works in the information-theoretic setting. We show that obtaining even a sub-linear dependency on the number of rounds m (i.e., o(m)·log(1/δ)) is impossible in the information-theoretic, and requires the existence of one-way functions in the computational setting. We show that non-trivial derandomized parallel repetition for private-coin protocols is impossible in the information-theoretic setting and requires the existence of one-way functions in the computational setting. These results are tight in the sense that parallel repetition theorems in the computational setting can trivially be derandomized using pseudorandom generators, which are implied by the existence of one-way functions.

Annual Symposium on Foundations of Computer ScienceOct 1, 20114 citations

Does parallel repetition lower the error in computationally sound protocols?

Mihir Bellare Y, Russell Impagliazzo, Moni Naor

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.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.

Annual Symposium on Foundations of Computer ScienceNov 22, 2002114 citations

Guest column

Abstract

Related papers

Guest column

Abstract

Related papers