**An Efficient Concurrent Repetition Theorem**

*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.

**Category / Keywords: **foundations / parallel repetition

**Date: **received 13 Jul 2009

**Contact author: **dog at csc kth se

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

**Note: **This is a preliminary version. All comments are most welcome!

The cited manuscript of Hastad et al. (2008) should be posted shortly.

**Version: **20090718:044300 (All versions of this report)

**Short URL: **ia.cr/2009/347

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

[ Cryptology ePrint archive ]