Welcome to the resource topic for 2015/031
Title:
Tight Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence
Authors: Kai-Min Chung, 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.
ePrint: https://eprint.iacr.org/2015/031
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .