Paper 2019/393

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

Itay Berman and Iftach Haitner and Eliad Tsfadia

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.