A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence

Hardness 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 (Bellare, Impagliazzo, and Naor [FOCS '97]) and public-coin protocols (Håstad, Pass, Wikström, and Pietrzak [TCC '10], Chung and Liu [TCC '10] and Chung and Pass [TCC '15]), it fails to do so in the general case (the above Bellare, Impagliazzo, and Naor; also Pietrzak and Wikström [TCC '07]).

The only known round-preserving approach that applies to all interactive arguments is Haitner's random-terminating transformation [SICOMP '13], who showed that the parallel repetition of the transformed protocol reduces the soundness error at a weak exponential rate: if the original m-round protocol has soundness error 1-ε, then the n-parallel repetition of its randomterminating variant has soundness error (1ε) εn/m 4 (omitting constant factors). Håstad et al. have generalized this result to partially simulatable interactive arguments, showing that the nfold repetition of an m-round δ-simulatable argument of soundness error 1ε has soundness error (1ε) εδ 2 n/m 2 . When applied to random-terminating arguments, the Håstad et al. bound matches that of Haitner.

In this work we prove that parallel repetition of random-terminating arguments reduces the soundness error at a much stronger exponential rate: the soundness error of the n parallel repetition is (1ε) n/m , only an m factor from the optimal rate of (1ε) n achievable in publiccoin and three-message arguments. The result generalizes to δ-simulatable arguments, for which we prove a bound of (1ε) δn/m . This is achieved by presenting a tight bound on a relaxed variant of the KL-divergence between the distribution induced by our reduction and its ideal variant, a result whose scope extends beyond parallel repetition proofs. We prove the tightness of the above bound for random-terminating arguments, by presenting a matching protocol.