Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
复制标题
是否有可能使用利用预言机效率的归约来改进 Yao 的 XOR 引理？
DOI：
10.1007/s00037-023-00238-9
复制
发表时间：
2023
影响因子：
1.4
通讯作者：
Ronen Shaltiel
中科院分区：
文献类型：
--
作者：
Ronen Shaltiel
Yao 的 XOR 引理指出，对于每个函数 $$f:\{0,1\}^k \rightarrow \{0,1\}$$ f : { 0 , 1 } k → { 0 , 1 } ，如果 f 对于 P / poly 的硬度为 2/3 （这意味着对于 P / poly 中的每个电路 C， $$\Pr[C(X)=f(X)] \le 2/3$$ Pr [ C ( X ) = f ( X ) ] ≤ 2 / 3 在统一输入 X ) 上，则计算 $$f(X_1) \oplus \ldots \oplus f(X_t)$$ f ( X 1 ) ⊕ … ⊕ f ( X t ) 对于足够大的 t 的任务具有硬度 $$\frac{1}{2} + \epsilon$$ 1 2 + ϵ 对于 P / poly 。该引理的已知证明无法实现 $$\epsilon=\frac{1}{k^{\omega(1)}}$$ ϵ = 1 k ω ( 1 ) ，甚至对于 $$\epsilon=\frac{1}{k}$$ ϵ = 1 k ，我们也不知道如何用 AC^0[ parity ] 替换 P / poly （具有门 { and, or, not, 的恒定深度电路类，无限制扇入的奇偶校验}）。 Grinberg、Shaltiel 和 Viola (FOCS 2018)（基于一系列早期作品）表明，这些限制不能通过黑盒缩减来规避。也就是说，通过约简 $${\rm Red}^{(\cdot)}$$ Red ( · ) 使预言机能够访问违反 Yao 异或引理结论的函数 D，实现违反 Yao 异或引理假设的电路。相关文献中有一些已知的关于从最坏情况到平均情况的非黑盒减少的减少。具体来说，Gutfreund、Shaltiel 和 Ta-Shma（Computational Complexity 2007）以及 Hirahara（FOCS 2018））的缩减是“类缩减”，只有当预言机从某些高效算法类别访问预言机 D 时，才能保证成功。这些作品似乎规避了一些黑箱不可能的结果。在本文中，我们将 Grinberg、Shaltiel 和 Viola 的先前限制扩展到几种类型的类别归约，证明类别归约不能产生 Yao 的 XOR 引理所需的改进。据我们所知，这是适用于等级降低的硬度放大降低的第一个限制。我们的技术模仿了以前的黑盒缩减下限，用基于有限独立性的高效预言机取代了该证明中使用的低效预言机，并开发了工具来处理这种替代后出现的技术困难。
Yao’s XOR lemma states that for every function $$f:\{0,1\}^k \rightarrow \{0,1\}$$ f : { 0 , 1 } k → { 0 , 1 } , if f has hardness 2/3 for P / poly (meaning that for every circuit C in P / poly , $$\Pr[C(X)=f(X)] \le 2/3$$ Pr [ C ( X ) = f ( X ) ] ≤ 2 / 3 on a uniform input X ), then the task of computing $$f(X_1) \oplus \ldots \oplus f(X_t)$$ f ( X 1 ) ⊕ … ⊕ f ( X t ) for sufficiently large t has hardness $$\frac{1}{2} + \epsilon$$ 1 2 + ϵ for P / poly . Known proofs of this lemma cannot achieve $$\epsilon=\frac{1}{k^{\omega(1)}}$$ ϵ = 1 k ω ( 1 ) , and even for $$\epsilon=\frac{1}{k}$$ ϵ = 1 k , we do not know how to replace P / poly by AC^0[ parity ] (the class of constant depth circuits with the gates { and, or, not, parity } of unbounded fan-in). Grinberg, Shaltiel and Viola (FOCS 2018) (building on a sequence of earlier works) showed that these limitations cannot be circumvented by black-box reductions . Namely, by reductions $${\rm Red}^{(\cdot)}$$ Red ( · ) that given oracle access to a function D that violates the conclusion of Yao’s XOR lemma, implement a circuit that violates the assumption of Yao’s XOR lemma. There are a few known reductions in the related literature on worst-case to average-case reductions that are non-black-box . Specifically, the reductions of Gutfreund, Shaltiel and Ta-Shma (Computational Complexity 2007) and Hirahara (FOCS 2018)) are “class reductions” that are only guaranteed to succeed when given oracle access to an oracle D from some efficient class of algorithms. These works seem to circumvent some black-box impossibility results. In this paper, we extend the previous limitations of Grinberg, Shaltiel and Viola to several types of class reductions, giving evidence that class reductions cannot yield the desired improvements in Yao’s XOR lemma. To the best of our knowledge, this is the first limitation on reductions for hardness amplification that applies to class reductions. Our technique imitates the previous lower bounds for black-box reductions, replacing the inefficient oracle used in that proof, with an efficient one that is based on limited independence, and developing tools to deal with the technical difficulties that arise following this replacement.
具有建议的自适应程序的不可区分性以及硬度放大证明的下限
DOI：
10.1109/focs.2018.00094
发表时间：
2018
期刊：
FOCS
影响因子：
--
作者：
Grinberg, Aryeh;Shaltiel, Ronen;Viola, Emanuele
通讯作者：
Viola, Emanuele