Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there is always a
distinguisher; in fact, they show that it is always
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>3, and conjecture that every NC0 generator can be
broken by a statistical test that simply XORs some bits
of the input. Equivalently, they conjecture that no
NC0 generator can sample an epsilon-biased space with
negligible epsilon.

We refute the conjecture for k>4, and we give a generator
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 exponentially
small in n/c^4.

We also present a polynomial-time distinguisher for the
case k=4, having constant distinguishing probability.
We observe that constant distinguishing probability is
not achievable in general via linear tests.

It remains open whether noticeable distinguishing
probability can be achieved with linear tests for the
case k=4, and whether there is a polynomial time test
that breaks every generator (or even just our proposal)
for k>4.

This paper is superseded by the ECCC Technical
Report TR03-043.