Welcome to the resource topic for 2009/347
Title:
An Efficient Concurrent Repetition Theorem
Authors: Douglas Wikström
Abstract:Håstad et al. (2008) prove, using Raz’s lemma (STOC '95) thefirst efficient parallel repetition theorem for protocols with anon-constant number of rounds, for a natural generalization ofpublic-coin protocols. They show that a parallel prover thatconvinces a fraction 1-\gamma of the embedded verifiers of a$\reps$-wise repeated \exchanges-message verifier can be turnedinto a prover with error probability$1-\gamma-O(\exchanges\sqrt{-\logg{\epsilon}/\reps})$. This improvesprevious results of Impagliazzo et al. (Crypto 2007) and Pass andVenkitasubramaniam (STOC 2007) that studies the constant round case. We prove a generalization of Raz’s Lemma to random processes thatallows us to improve the analysis of the reduction of Håstad etal. in the public-coin case to$1-\gamma-O(\sqrt{-\logg{\epsilon}/\reps}), i.e., we remove thedependence on the number rounds completely, and thus the restrictionto settings where \reps>\exchanges^2$. An important implication of the strengthened parallel repetitiontheorem is the first efficient \emph{concurrent} repetition theoremfor protocols with a non-constant number of rounds. In concurrentrepetition, the verifiers execute completely independently and onlyreport their final decision, i.e., the prover chooses arbitrarily inwhich order it interacts with the individual verifiers. This shouldbe contrasted with parallel repetition where the verifiers aresynchronized in each round.
ePrint: https://eprint.iacr.org/2009/347
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 .