A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence
A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence
复制标题
通过平滑KL散度实现部分可模拟交互论证的紧并行重复定理
DOI：
10.1007/978-3-030-56877-1_19
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Eliad Tsfadia
中科院分区：
文献类型：
--
作者：
Itay Berman;Iftach Haitner;Eliad Tsfadia
硬度放大是交互式协议研究中的一个核心问题。而“自然”的平行重复变换被认为可以减少一些特殊情况下的交互式参数的可靠性错误：三消息协议（Bellare，Impagliazzo和Naor [FOCS '97]）和公共硬币协议（Hastad，Pass，Wikstrom和Pietrzak [TCC '10]，Chung和Liu [TCC '10]以及Chung和Pass [TCC '15]），它在一般情况下不能这样做（上述Bellare等人;还有Pietrzak和Wikstrom [TCC '07]）。
Hardness amplification is a central problem in the study of interactive protocols. While “natural” parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols (Bellare, Impagliazzo, and Naor [FOCS ’97]) and public-coin protocols (Hastad, Pass, Wikstrom, and Pietrzak [TCC ’10], Chung and Liu [TCC ’10] and Chung and Pass [TCC ’15]), it fails to do so in the general case (the above Bellare et al.; also Pietrzak and Wikstrom [TCC ’07]).