TR09-109 Authors: Kai-Min Chung, Feng-Hao Liu

Publication: 3rd November 2009 14:47

Downloads: 3666

Keywords:

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.