Paper 2015/031
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in TCC 2015
- Keywords
- parallel repetitionpublic coininteractive argumentscomputationally sound proofsKL divergence
- Contact author(s)
- kmchung @ iis sinica edu tw
- History
- 2015-01-14: received
- Short URL
- https://ia.cr/2015/031
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/031,
author = {Kai-Min Chung and Rafael Pass},
title = {Tight Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence},
howpublished = {Cryptology ePrint Archive, Paper 2015/031},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/031}},
url = {https://eprint.iacr.org/2015/031}
}
