We study the role of polynomials over the finite field $GF(2^n)$ in constructing and attacking various weak notions of pseudorandomness.
First, we consider the construction of weak pseudorandom generators using $GF(2^n)$-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^n)$-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^n)$-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^n)$-polynomials can be used to distinguish various distributions from random ones. We provide a full picture of how various notions of $GF(2^n)$-linear distinguishers relate to standard linear (that is, $GF(2)$-linear) tests, and derive a reduction from having small-bias to fooling $GF(2^n)$-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^n)$-bilinear and $GF(2^n)$-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^n)$-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.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, October 2009.
Available: the thesis (in PDF format).
Yoav's board, filled with polynomials etc.
Back to Oded Goldreich's homepage.