Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Tight Parallel Repetition Theorems for Public-Coin Arguments Using KL-Divergence
verfasst von : Kai-Min Chung, Rafael Pass
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a new and conceptually simpler proof of a tight parallel-repetition theorem for public-coin arguments [Pass-Venkitasubramaniam, STOC’07], [Håstad et al, TCC’10], [Chung-Liu, TCC’10]. We follow the same proof framework as the previous non-tight parallel-repetition theorem of Håstad et al—which relied on
statistical distance
to measure the distance between experiments—and show that it can be made tight (and further simplified) if instead relying on
KL-divergence
as the distance between the experiments.
We then use this new proof to present the first tight “Chernoff-type” parallel repetition theorem for arbitrary public-coin arguments, demonstrating that parallel-repetition can be used to simultaneously decrease both the soundness and completeness error of
any
public-coin argument at a rate matching the standard Chernoff bound.