提出可模拟任意随机布尔函数的超仿真器,能骗过更大规模的区分器。
Supersimulators
- 基于图正则化思想迭代构造,让仿真器适应目标函数复杂度
- 可区分者规模可达多项式增长,仍无法有效识破仿真结果
- 适用于复杂性理论、密码学等领域,解决此前理论缺口
我们证明每个随机布尔函数都存在一个超仿真器:即一个多项式大小的随机电路,其在随机输入下的输出无法被任何更大型的区分器以常数优势有效辨别,即使区分器比仿真器大得多。该结果建立在Trevisan、Tulsiani和Vadhan(2009)的标志性复杂性正则性引理基础上,但突破了传统限制。通过允许区分器大小上限随目标函数变化,同时保持绝对上界独立于目标函数,我们规避了仿真器规模的下限障碍。这一依赖关系自然源于源自图正则化文献的迭代技术。基于正则性引理及近年改进的多准确与多校准预测器(Hebert-Johnson等,2018),此前已广泛应用于复杂性理论、密码学与学习理论。本文首先证明,产品分布计算不可区分性的最新多校准刻画实际上仅需(校准的)多准确性;随后进一步展示,超仿真器能在此领域给出更紧致的结果,填补先前版本中的复杂性间隙。
原文摘要 · Abstract (English)
We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. Our result builds on the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani and Vadhan (2009), which, in contrast, provides a simulator that fools smaller distinguishers. We circumvent lower bounds for the simulator size by letting the distinguisher size bound vary with the target function, while remaining below an absolute upper bound independent of the target function. This dependence on the target function arises naturally from our use of an iteration technique originating in the graph regularity literature. The simulators provided by the regularity lemma and recent refinements thereof, known as multiaccurate and multicalibrated predictors, respectively, as per Hebert-Johnson et al. (2018), have previously been shown to have myriad applications in complexity theory, cryptography, learning theory, and beyond. We first show that a recent multicalibration-based characterization of the computational indistinguishability of product distributions actually requires only (calibrated) multiaccuracy. We then show that supersimulators yield an even tighter result in this application domain, closing a complexity gap present in prior versions of the characterization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。