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.
Joint work with Itay Berman and Eliad Tsfadia.