Parallel Repetition Theorems for Interactive Arguments
Parallel Repetition Theorems for Interactive Arguments
复制标题
交互式论证的并行重复定理
DOI：
10.1007/978-3-642-11799-2_2
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Feng
中科院分区：
文献类型：
--
作者：
Kai;Feng
我们研究了几类交互论证的有效并行重复定理，并获得了以下结果：
我们通过对 Hastad 等人的归约算法进行严格分析，展示了公共币交互论证的紧密并行重复定理。 [HPPW08]。也就是说，n 次并行重复将健全性误差从 δ 降低到 δn。我们改进的关键是避免使用 Raz 采样引理的新分析，这是之前结果的关键要素。
我们给出了一种新的安全分析来加强 Hastad 等人的并行重复定理。对于更一般的论点。我们表明，n 次并行重复将健全性误差从 δ 降低到几乎紧密的 δn/2。特别是，我们消除了对边界中轮数的依赖，因此将 Wikstrom [Wik09] 的“并发”重复定理扩展到该模型。
我们获得了一种使用完全同态加密方案将任何交互式参数转换为上述类中的参数的方法。这提供了一种在不增加回合复杂性的情况下放大任何交互式论证的合理性的方法。
我们给出了一个简单而通用的变换，它表明紧直积定理意味着几乎紧的切尔诺夫型定理。这将我们的结果扩展到 Chernoff 型定理，并为 Impagliazzo 等人的 Chernoff 型定理提供了替代证明。 [IJK09] 用于弱可验证的谜题。
We study efficient parallel repetition theorems for several classes of interactive arguments and obtain the following results:
We show a tight parallel repetition theorem for public-coin interactive arguments by giving a tight analysis for a reduction algorithm of Hastad et al. [HPPW08]. That is, n-fold parallel repetition decreases 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 ingredient to the previous results.
We give a new security analysis to strengthen a parallel repetition theorem of Hastad et al. for a more general class of arguments. We show that n-fold parallel repetition decreases the soundness error from δ to δ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 [Wik09] to this model.
We obtain a way to turn any interactive argument to one in the class above using fully homomorphic encryption schemes. This gives a way to amplify the soundness of any interactive argument without increasing the round complexity.
We give a simple and generic transformation which shows that tight direct product theorems imply almost-tight Chernoff-type theorems. This extends our results to Chernoff-type theorems, and gives an alternative proof to the Chernoff-type theorem of Impagliazzo et al. [IJK09] for weakly-verifiable puzzles.