Pseudorandomness and the Minimum Circuit Size Problem
Pseudorandomness and the Minimum Circuit Size Problem
复制标题
伪随机性和最小电路尺寸问题
DOI：
10.4230/lipics.itcs.2020.68
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
R. Santhanam
我们探讨了基于基本最小电路尺寸问题（MCSP[s]）的平均情况难度的单向函数的可能性，该问题询问由其真值表指定的 n 位布尔函数是否具有大小为 s(n) 的电路。 1.（来自零误差平均情况硬度的伪随机性）我们证明，对于给定大小的函数 s，以下内容是等效的：存在由 s(O(n)) 大小的电路描述的字符串上支持的伪随机分布；存在由 s(O(n)) 大小电路描述的字符串支持的命中集； MCSP[s(O(n))] 是零误差平均情况困难的。使用类似的技术，我们表明 Feige 对随机 k-CNF 的假设意味着存在完全由可满足公式支持的伪随机分布（具有恒定误差）。我们的结果的基础是语义采样的一般概念，这可能是独立的兴趣。 2.（一个新猜想）与已知的针对任意多项式大小的对手的简洁命中集的通用构造类似，我们提出了普遍性猜想：存在针对任意多项式大小的对手的简洁伪随机分布的通用构造。我们证明，在普遍性猜想下，以下内容是等价的： 单向函数存在；不存在针对次指数尺寸电路有用的自然证明；通过均匀分布上的成员查询来学习多项式大小的电路是很困难的；对于某些 > 0 的情况，MCSP[2] 平均来说是零错误困难的；存在密码学简洁命中集生成器。 3.（非黑盒结果）我们表明，对于有自然证明的弱电路类别 C [RR97]，针对 C 中的多尺寸电路安全的伪随机函数意味着 P 中针对 C 中的多尺寸电路的超多项式下界。我们还表明，对于 MCSP 的某种自然变体，从在最坏情况下很好地逼近问题到平均解决问题存在多项式时间减少。这些结果是使用非黑盒技术显示的，在第一种情况下，我们表明在标准加密假设下没有结果的黑盒证明。 *电子邮件：rahul.santhanam@cs.ox.ac.uk
We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n). 1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for a given size function s, the following are equivalent: Pseudorandom distributions supported on strings describable by s(O(n))-size circuits exist; Hitting sets supported on strings describable by s(O(n))-size circuits exist; MCSP[s(O(n))] is zero-error average-case hard. Using similar techniques, we show that Feige’s hypothesis for random k-CNFs implies that there is a pseudorandom distribution (with constant error) supported entirely on satisfiable formulas. Underlying our results is a general notion of semantic sampling, which might be of independent interest. 2. (A New Conjecture) In analogy to a known universal construction of succinct hitting sets against arbitrary polynomial-size adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomial-size adversaries. We show that under the Universality Conjecture, the following are equivalent: One-way functions exist; Natural proofs useful against sub-exponential size circuits do not exist; Learning polynomial-size circuits with membership queries over the uniform distribution is hard; MCSP[2 ] is zero-error hard on average for some > 0; Cryptographic succinct hitting set generators exist. 3. (Non-Black-Box Results) We show that for weak circuit classes C against which there are natural proofs [RR97], pseudorandom functions secure against poly-size circuits in C imply superpolynomial lower bounds in P against poly-size circuits in C. We also show that for a certain natural variant of MCSP, there is a polynomial-time reduction from approximating the problem well in the worst case to solving it on average. These results are shown using non-black-box techniques, and in the first case we show that there is no black-box proof of the result under standard crypto assumptions. ∗E-mail: rahul.santhanam@cs.ox.ac.uk
影响因子：
1.4
作者：
Eric Allender;D. Holden;Valentine Kabanets
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets