Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-049 | 15th April 2019 13:39

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

RSS-Feed




Revision #1
Authors: Itay Berman, Iftach Haitner, Eliad Tsfadia
Accepted on: 15th April 2019 13:39
Downloads: 8
Keywords: 


Abstract:

Soundness amplification is a central problem in the study of interactive protocols. While ``natural'' parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols, it fails to do so in the general case.

The only known round-preserving approach that applies to the general case of interactive arguments is Haitner's "random-terminating" transform [FOCS '09, SiCOMP '13]. Roughly speaking, a protocol $\pi$ is first transformed into a new slightly modified protocol $\widetilde{\pi}$, referred as the random terminating variant of $\pi$, and then parallel repetition is applied. Haitner's analysis shows that the parallel repetition of $\widetilde{\pi}$ does reduce the soundness error at a weak exponential rate. More precisely, if $\pi$ has $m$ rounds and soundness error $1-\epsilon$, then $\widetilde{\pi}^k$, the $k$-parallel repetition of $\widetilde{\pi}$, has soundness error $(1-\epsilon)^{\epsilon k / m^4}$. Since the security of many cryptographic protocols (e.g., binding) depends on the soundness of a related interactive argument, improving the above analysis is a key challenge in the study of cryptographic protocols.

In this work we introduce a different analysis for Haitner's method, proving that parallel repetition of random terminating protocols reduces the soundness error at a much stronger exponential rate: the soundness error of $\widetilde{\pi}^k$ is $(1-\epsilon)^{k / m}$, only an $m$ factor from the optimal rate of $(1-\epsilon)^k$, achievable in public-coin and three-message protocols. We prove the tightness of our analysis by presenting a matching protocol.


Paper:

TR19-049 | 2nd April 2019 15:33

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





TR19-049
Authors: Itay Berman, Iftach Haitner, Eliad Tsfadia
Publication: 2nd April 2019 15:39
Downloads: 76
Keywords: 


Abstract:

Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case.

Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument $\pi$ into a slightly modified protocol $\widetilde{\pi}$, which he named the random terminating variant of $\pi$, such that the parallel repetition of $\widetilde{\pi}$ does reduce the soundness error at a weak exponential rate. More precisely, if $\pi$ has $m$ rounds and soundness error $(1-\epsilon)$, then Haitner proved that $\widetilde{\pi}^k$, the $k$-parallel repetition of $\widetilde{\pi}$, has soundness error $(1-\epsilon)^{\epsilon k / m^4}$.

We emphasize that parallel repetition of the random-terminating variant of a protocol is the only unconditional round-preserving hardness amplification technique we have for arbitrary interactive arguments. Since the security of many cryptographic protocols (e.g., binding) depends on the soundness of a related interactive argument, improving the analysis of Haitner is a key challenge in the study of cryptographic protocols.

In this work we introduce a different analysis for Haitner's method, proving that parallel repetition of random terminating protocols reduces the soundness error at a much stronger exponential rate: the soundness error of $\widetilde{\pi}^k$ is $(1-\epsilon)^{k / m}$, only an $m$ factor from the optimal rate of $(1-\epsilon)^k$, achievable in public-coin and three-message protocols. We prove the tightness of our analysis by presenting a matching protocol.



ISSN 1433-8092 | Imprint