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.