Paper 2019/393
A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence
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: three-message protocols (Bellare, Impagliazzo, and Naor [FOCS '97]) and public-coin 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 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
Note: In this version we extended the result to partially simulatable interactive arguments, and rewrote most parts of previous version.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- parallel repetitioninteractive argumentpartially simulatablesmooth KL-divergence
- Contact author(s)
-
eliadtsfadia @ gmail com
iftachh @ gmail com - History
- 2020-06-02: revised
- 2019-04-18: 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 {KL}-Divergence}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/393}, year = {2019}, url = {https://eprint.iacr.org/2019/393} }