Suppose we have a length-increasing function , which we think of as a pseudorandom generator mapping a shorter seed into a longer output.

Then the distribution of for a random seed is not uniform (in particular, it is concentrated on at most of the elements of ). We say that a statistical test has *advantage* in distinguishing the output of from the uniform distribution if

If the left-hand side of (1) is at most for every computable by a circuit of size , then we say that is -pseudorandom against circuits of size , or that it is an -secure pseudorandom generator.

How secure can a pseudorandom generator possibly be? This question (if we make no assumption on the efficiency of ) is related to the question in the previous post on approximating a boolean function via small circuits. Both questions, in fact, are special cases of the question of how much an arbitrary real-valued function must correlate with functions computed by small circuits, which is answered in a new paper with Anindya De and Madhur Tulsiani.

Suppose that we are given an arbitrary and we want to construct a circuit of size such that (1) holds for the largest possible value of .

A simple strategy is to hard-wire images of into the circuit. If receives in input one of the strings from such set, it outputs 1, otherwise it output 0. We see that outputs 1 with probability at least given an output of the generator (because each possible output of the generator is produced with probability at least ), but accepts with probability given a random string from . This simple construction shows that size is sufficient to achieve in (1), so that -secure generators cannot exist.

What kind of lower bounds can we prove? If we fix a test , we call , and we pick a function uniformly at random among all functions , then by Chernoff bounds we have

Since there are circuits of size , a union bound tells us that there are -secure pseudorandom generator .

It turns out that this bound is tight, that is, for every , we can always construct a circuit of size whose advantage is about .

The following more general result (whose proof I will discuss in later posts) subsumes both the question of constructing distinguishers for pseudorandom generators and the question of approximating boolean functions.

Theorem 1Let be any real-valued function. Then for every there is a a function computable by a circuit of size at most such that

To see why it subsumes both questions, let us start from the boolean function approximation problem. If is a boolean function, we can define , and the theorem gives us a function computable by a circuit of size such that

Dividing both sides by we have

and the left-hand side is , so

Regarding the problem of distinguishing the output of a generator from the uniform distribution, set

get a function , computable by a circuit of size such that

and note that is the distance of the distribution of outputs of the generator from the uniform distribution, that is, at least 1, while the left-hand side is twice the distinguishing probability of , so

In (1), should $x$ and $y$ be the same variable? Also, what is $T$ (just below (1))?

Thanks

Pingback: Distinguishers from linear functions « in theory