ECCC-Report TR09-027https://eccc.weizmann.ac.il/report/2009/027Comments and Revisions published for TR09-027en-usWed, 18 May 2022 11:09:08 +0300
Revision 2
| A Parallel Repetition Theorem for Any Interactive Argument |
Iftach Haitner
https://eccc.weizmann.ac.il/report/2009/027#revision2The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97], and constant-round public-coin protocols - Pass and Venkitasubramaniam [STOC '07]), Bellare et. al gave example of interactive arguments for which parallel repetition does not reduce the soundness error at all.
We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - \frac1{4m}, \frac1{4m}) biased coin (i.e., 1 is tossed with probability 1/4m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.
Wed, 18 May 2022 11:09:08 +0300https://eccc.weizmann.ac.il/report/2009/027#revision2
Revision 1
| A Parallel Repetition Theorem for Any Interactive Argument |
Iftach Haitner
https://eccc.weizmann.ac.il/report/2009/027#revision1The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97], and constant-round public-coin protocols - Pass and Venkitasubramaniam [STOC '07]), Bellare et. al gave example of interactive arguments for which parallel repetition does not reduce the soundness error at all.
We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - \frac1{4m}, \frac1{4m}) biased coin (i.e., 1 is tossed with probability 1/4m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.
Fri, 03 Apr 2009 00:00:00 +0300https://eccc.weizmann.ac.il/report/2009/027#revision1
Paper TR09-027
| A Parallel Repetition Theorem for Any Interactive Argument |
Iftach Haitner
https://eccc.weizmann.ac.il/report/2009/027The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97], and constant-round public-coin protocols - Pass and Venkitasubramaniam [STOC '07]), Bellare et. al gave example of interactive arguments for which parallel repetition does not reduce the soundness error at all.
We show that by slightly modifying any interactive argument, in a way that preserves its completeness and only slightly deteriorates its soundness, we get a protocol for which parallel repetition does reduce the error at a weak exponential rate. In this modified version, the verifier flips at the beginning of each round an (1 - \frac1{4m}, \frac1{4m}) biased coin (i.e., 1 is tossed with probability 1/4m), where m is the round complexity of the (original) protocol. If the coin is one, the verifier halts the interaction and accepts, otherwise it sends the same message that the original verifier would. At the end of the protocol (if reached), the verifier accepts if and only if the original verifier would.
Thu, 02 Apr 2009 23:17:06 +0300https://eccc.weizmann.ac.il/report/2009/027