An Efficient Concurrent Repetition Theorem.

Abstract

H˚astad et al. (2008) prove, using Raz’s lemma (STOC ’95) the first efficient parallel repetition theorem for protocols with a non-constant number of rounds, for a natural generalization of public-coin protocols. They show that a parallel prover that convinces a fraction 1 − γ of the embedded verifiers of a k-wise repeated m-message verifier can be turned into a prover with error probability 1 − γ − O(m √ − log (ɛ) /k). This improves previous results of Impagliazzo et al. (Crypto 2007) and Pass and Venkitasubramaniam (STOC 2007) that studies the constant round case. We prove a generalization of Raz’s Lemma to random processes that allows us to improve the analysis of the reduction of H˚astad et al. in the public-coin case to 1 − γ − O ( √ − log (ɛ) /k), i.e., we remove the dependence on the number rounds completely, and thus the restriction to settings where k> m2. An important implication of the strengthened parallel repetition theorem is the first efficient concurrent repetition theorem for protocols with a non-constant number of rounds. In concurrent repetition, the verifiers execute completely independently and only report their final decision, i.e., the prover chooses arbitrarily in which order it interacts with the individual verifiers. This should be contrasted with parallel repetition where the verifiers are synchronized in each round. 1