Notions of Weak Pseudorandomness and GF (2 n )-Polynomials
Notions of Weak Pseudorandomness and GF (2 n )-Polynomials
复制标题
弱伪随机性和 GF (2 n )-多项式的概念
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Y. Tzur
中科院分区：
文献类型：
--
作者：
Y. Tzur
我们研究了有限场GF（2）在构建和攻击各种较弱的伪符号中的作用。 stoc'90]，愚人节构成了空间的不均匀区别，其标准的实例化可以看作是GF（2） - 多种形式图，我们表明其对（非均匀）空间的弹性是敏感的其输出位，排除发电机的一些天然概括。一个小偏置发生器（称为几何发生器），该发生器与[Alon等人，RS＆A'92]所呈现的动力结构相似（但不完全相同）。如果所需的偏差的倒数是输出长度的各种偏差，我们还使用几何发生器的变体来构建小偏见和愚弄小空间，从而提供良好的参数，从而提供指数 - 具有指数偏置的伸展生成器，即o（1）空间可区分（通过不均匀的机器），我们研究了GF（2） - 多项式如何用于区分各种分布和随机分布。 GF（2） - 线性区分的各种音符与标准线性（即GF（2） - 线性）测试有关，并得出了从小偏见到愚弄GF（2）的降低。这种还原用于证明上述几何发生器的小偏差。可以通过GF（2） - 双线性形式来精确计算或近似于各种速率。 d小偏见发生器的独立实例，最多是多项式的，我们在所需的实例数方面表明了这种结果的紧密度。
We study the role of polynomials over the finite field GF (2) in constructing and attacking various weak notions of pseudorandomness. First, we consider the construction of weak pseudorandom generators using GF (2)-polynomials. We study the generator of [Nisan, STOC’90], that fools space-bounded nonuniform distinguishers, whose standard instantiation can be seen as a GF (2)-polynomial map. Among other results, we show that its resilience to (nonuniform) space-bounded machines is sensitive to the order of its output bits, and rule out some natural generalizations of the generator. We also consider GF (2)-polynomial-based generators that have small bias, meaning that they fool all (bit-)linear tests. We present a simple construction of a small-bias generator (called the geometric generator), which is similar (but not identical) to the powering construction presented by [Alon et al., RS&A’92]. A variant of this generator has shorter seed than the classical constructions of Alon et al., if the reciprocal of the bias required is polylogarithmic in the output length. We also use a variant of the geometric generator to construct a separation between small-bias and fooling small space that has good parameters, giving an exponential-stretch generator with exponentially small bias that is O(1)-space distinguishable (by a nonuniform machine). Second, we study how GF (2)-polynomials can be used to distinguish various distributions from random ones. We provide a full picture of how various notions of GF (2)-linear distinguishers relate to standard linear (that is, GF (2)-linear) tests, and derive a reduction from having small-bias to fooling GF (2)-linear tests. In fact, this reduction is used to prove the small bias of the geometric generator mentioned above. We also conduct a study of GF (2)bilinear and GF (2)-quadratic forms, and in specific characterize the sets of GF (2)-bilinear forms that can be computed exactly, or approximated to various rates, by GF (2)-bilinear forms. Higher-degree polynomials are also studied, and specifically we consider a recent result of [Viola, CCC’08] that showed that the sum of d independent instances of a small-bias generator fools polynomials of degree at most d. We show the tightness of this result with respect to the number of instances required, showing an explicit degree-d+ 1 polynomial that distinguishes this construction from random with constant gap.