**Tight Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence**

*Kai-Min Chung and Rafael Pass*

**Abstract: **We present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments (Pass-Venkitasubramaniam, STOC'07, Hastad et al, TCC'10, Chung-Liu, TCC'10). We follow the same proof framework as the previous non-tight parallel-repetition theorem of Hastad et al---which relied on *statistical distance* to measure the distance between experiments---and show that it can be made tight (and further simplied) if instead relying on *KL-divergence* as the distance between the experiments.

We then show that our proof technique directly yields tight ``Chernoff-type'' parallel-repetition theorems (where one considers a ``threshold'' verifier that accepts iff the prover manages to convince a certain fraction of the parallel verifiers, as opposed to all of them) for any public-coin interactive argument; previously, tight results were only known for either constant-round protocols, or when the gap between the threshold and the original error-probability is a constant.

**Category / Keywords: **foundations / parallel repetition, public coin, interactive arguments, computationally sound proofs, KL divergence

**Original Publication**** (in the same form): **IACR-TCC-2015

**Date: **received 13 Jan 2015

**Contact author: **kmchung at iis sinica edu tw

**Available format(s): **PDF | BibTeX Citation

**Version: **20150114:165217 (All versions of this report)

**Short URL: **ia.cr/2015/031

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]