TR03-043 Authors: Elchanan Mossel, Amir Shpilka, Luca Trevisan

Publication: 6th June 2003 19:40

Downloads: 1665

Keywords:

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.

For large values of k, we construct generators that map n

bits to n^{Omega(sqrt k})} bits and such that every XOR of

outputs has bias exponentially small in n^{1/(2 sqrt k)}.

We also present a polynomial-time distinguisher for the

case k=4, assuming the number of output bits is at least

24n. Our distinguisher has constant distinguishing probability.

For large values of k we show that a linear distinguisher with

a constant distinguishing probability exists once

the number of output bits is bigger than 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 pseudo random generator for which the XOR

of every subset of the outputs has exponentially small bias in

n, and which maps n bits to Omega(n^2) bits.