Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-109 | 3rd November 2009 13:57

Tight Parallel Repetition Theorems for Public-coin Arguments


Authors: Kai-Min Chung, Feng-Hao Liu
Publication: 3rd November 2009 14:47
Downloads: 3666


Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition reduces the soundness error from $\delta$ to $\delta^n$. The crux of our improvement is a new analysis that avoid using Raz's sampling lemma, which is the key to the previous results.

2. We give a new reduction to strengthen the direct product theorem of Hastad et al. for arguments with extendable and simulatable verifiers. We show that $n$-fold parallel repetition reduces the soundness error from $\delta$ to $\delta^{n/2}$, which is almost tight. In particular, we remove the dependency on the number of rounds in the bound, and as a consequence, extend the ``concurrent'' repetition theorem of Wikstrom (ePrint 2009) to this model.

3. We give a simple and generic reduction which shows that tight direct product theorems implies almost tight Chernoff-type theorems. The reduction extends our results to Chernoff-type theorems, and gives an alternative proof to the Chernoff-type theorem of Impagliazzo et al. (Crypto 2007) for weakly-verifiable puzzles.

4. As an additional contribution, we observe that the reduction of Pass and Venkitasubramaniam (STOC 2007) for constant-round public-coin arguments gives tight parallel repetition theorems for any threshold verifiers, who accept when more than a certain number of repetition accepts.

ISSN 1433-8092 | Imprint