ECCC-Report TR09-109https://eccc.weizmann.ac.il/report/2009/109Comments and Revisions published for TR09-109en-usTue, 03 Nov 2009 14:47:20 +0200
Paper TR09-109
| Tight Parallel Repetition Theorems for Public-coin Arguments |
Kai-Min Chung,
Feng-Hao Liu
https://eccc.weizmann.ac.il/report/2009/109Following 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.
Tue, 03 Nov 2009 14:47:20 +0200https://eccc.weizmann.ac.il/report/2009/109