Paper 2009/347

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.

Note: This is a preliminary version. All comments are most welcome! The cited manuscript of Hastad et al. (2008) should be posted shortly.