首页    期刊浏览 2025年02月17日 星期一
登录注册

文章基本信息

  • 标题:Tight Parallel Repetition Theorems for Public-coin Arguments
  • 本地全文:下载
  • 作者:Kai-Min Chung ; Feng-Hao Liu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 to 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 to n2 , 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

  • 关键词:Arthur-Merlin; direct product theorem; interactive arguments; Parallel Repetition; public coin
国家哲学社会科学文献中心版权所有