Paper 2019/393
A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KLDivergence
Itay Berman, Iftach Haitner, and Eliad Tsfadia
Abstract
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: threemessage protocols (Bellare, Impagliazzo, and Naor [FOCS '97]) and publiccoin protocols (Hastad, Pass, Wikstrom, and Pietrzak [TCC '10], Chung and Lu [TCC '10] and Chung and Pass [TCC '15]), it fails to do so in the general case (the above Bellare et al.; also Pietrzak and Wikstrom [TCC '07]). The only known roundpreserving approach that applies to all interactive arguments is Haitner's randomterminating 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\varepsilon$, then the $n$parallel repetition of its randomterminating variant has soundness error $(1\varepsilon)^{\varepsilon n / m^4}$ (omitting constant factors). Hastad et al. have generalized this result to partially simulatable interactive arguments, showing that the $n$fold repetition of an $m$round $\delta$simulatable argument of soundness error $1\varepsilon$ has soundness error $(1\varepsilon)^{\varepsilon \delta^2 n / m^2}$. When applied to randomterminating arguments, the Hastad et al. bound matches that of Haitner. In this work we prove that parallel repetition of randomterminating arguments reduces the soundness error at a much stronger exponential rate: the soundness error of the $n$ parallel repetition is $(1\varepsilon)^{n / m}$, only an $m$ factor from the optimal rate of $(1\varepsilon)^n$ achievable in publiccoin and threemessage arguments. The result generalizes to $\delta$simulatable arguments, for which we prove a bound of $(1\varepsilon)^{\delta n / m}$. This is achieved by presenting a tight bound on a relaxed variant of the KLdivergence 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 randomterminating arguments, by presenting a matching protocol.
Note: In this version we extended the result to partially simulatable interactive arguments, and rewrote most parts of previous version.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 parallel repetitioninteractive argumentpartially simulatablesmooth KLdivergence
 Contact author(s)

eliadtsfadia @ gmail com
iftachh @ gmail com  History
 20200602: revised
 20190418: received
 See all versions
 Short URL
 https://ia.cr/2019/393
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/393, author = {Itay Berman and Iftach Haitner and Eliad Tsfadia}, title = {A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KLDivergence}, howpublished = {Cryptology ePrint Archive, Paper 2019/393}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/393}}, url = {https://eprint.iacr.org/2019/393} }