On ε‐biased generators in NC 0

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 NC 0 , that is, a pseudorandom generator that maps n ‐bit strings to m ‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4 n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test , that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC 0 generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC 0 generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, 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   −Ω( n / c   4 ) . For large values of k , we construct generators that map n bits 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 for k = 4, m ≥ 24 n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2 k n ⌈ k /2⌉ ). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2 −Ω( n ) and which maps n bits to Ω( n 2 ) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006