On ε‐biased generators in NC0
Elchanan Mossel, Amir Shpilka, Luca Trevisan · Random Structures and Algorithms · 2005
Abstract Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC0, that is, a pseudorandom generator that mapsn‐bit strings tom‐bit strings such that every bit of the output depends on a constant numberkof bits of the seed. They show that fork= 3, ifm≥ 4n+ 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with alinear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open fork≥ 4. In fact, they ask whether every NC0generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC0generator can sample an ε‐biased space with negligible ε? We give a generator fork= 5 that mapsnbits intocnbits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2 . For large values ofk, we construct generators that mapnbits to$n^{\Omega(\sqrt{k})}$ bits such that every XOR of outputs has bias$2^{-{n^{{1 \over 2\sqrt k}}}}$ . We also present a polynomial‐time distinguisher fork= 4,m≥ 24nhaving constant distinguishing probability. For large values ofkwe show that a linear distinguisher with a constant distinguishing probability exists oncem≥ Ω(2kn⌈k/2⌉). Finally, we consider a variant of the problem where each of the output bits is a degreekpolynomial in the inputs. We show there exists a degreek= 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2−Ω(n)and which mapsnbits to Ω(n2) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006