Suppose we have a length-increasing function {G: \{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n}, which we think of as a pseudorandom generator mapping a shorter seed into a longer output.

Then the distribution of {G(z)} for a random seed {z} is not uniform (in particular, it is concentrated on at most {2^{n-1}} of the {2^n} elements of {\{ 0,1 \}^n}). We say that a statistical test {D: \{ 0,1 \}^n \rightarrow \{ 0,1 \}} has advantage {\epsilon} in distinguishing the output of {G} from the uniform distribution if

\displaystyle \left| \mathop{\mathbb P}_{z \in \{ 0,1 \}^{n-1}} [D(G(z)) =1 ] - \mathop{\mathbb P}_{x \in \{ 0,1 \}^{n}} [D(x) =1 ] \right| \geq \epsilon \ \ \ \ \ (1)

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

How secure can a pseudorandom generator possibly be? This question (if we make no assumption on the efficiency of {G}) 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 {G: \{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n} and we want to construct a circuit {D} of size {S} such that (1) holds for the largest possible value of {\epsilon}.

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

What kind of lower bounds can we prove? If we fix a test {D}, we call {p:= \mathop{\mathbb P}_{x\in \{ 0,1 \}^n} [ D(x)=1]}, and we pick a function {G: \{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n} uniformly at random among all functions {\{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n}, then by Chernoff bounds we have

\displaystyle \mathop{\mathbb P}_{G: \{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n} \left[ \left| \mathop{\mathbb P}_{z\in \{ 0,1 \}^{n-1} } [ D(G(z)) = 1] - p \right| \geq \epsilon \right] \leq e^{-2\epsilon^2 2^{n-1}}

Since there are {2^{O(S\log S)}} circuits of size {S}, a union bound tells us that there are {(S,O(\sqrt{S\log S/2^n }))}-secure pseudorandom generator {G:\{ 0,1 \}^{n-1} \rightarrow \{ 0,1 \}^n}.

It turns out that this bound is tight, that is, for every {G}, we can always construct a circuit of size {S} whose advantage is about {\sqrt{S/2^n}}.

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 1 Let {g: \{ 0,1 \}^n \rightarrow {\mathbb R}} be any real-valued function. Then for every {S} there is a a function {c: \{ 0,1 \}^n \rightarrow \{0,1\}} computable by a circuit of size at most {S} such that

\displaystyle \sum_x (-1)^{c(x)} \cdot g(x) \geq \Omega\left( \sqrt{\frac {S}{2^n}}\right) \cdot\sum_x \left| g(x) \right|

To see why it subsumes both questions, let us start from the boolean function approximation problem. If {f: \{ 0,1 \}^n \rightarrow \{ 0,1 \}} is a boolean function, we can define {g(x) := (-1)^{f(x)}}, and the theorem gives us a function {c} computable by a circuit of size {O(\epsilon^2 2^n)} such that

\displaystyle \sum_x (-1)^{c(x)} \cdot (-1)^{f(x)} \geq \epsilon \cdot \sum_x \left| (-1)^{f(x)} \right| = \epsilon 2^n

Dividing both sides by {2^n} we have

\displaystyle \mathop{\mathbb E}_{x\sim \{ 0,1 \}^n} (-1)^{c(x)} \cdot (-1)^{f(x)} \geq \epsilon

and the left-hand side is {\mathop{\mathbb P} [ c(x)=f(x)] - \mathop{\mathbb P} [ c(x)\neq f(x)] = 2\mathop{\mathbb P}[c(x)=f(x)]-1}, so

\displaystyle \mathop{\mathbb P} [ c(x) = f(x) ] \geq \frac 12 + \frac \epsilon 2

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

\displaystyle g(x) := \mathop{\mathbb P}_{z\in \{ 0,1 \}^{n-1}} [ G(z) = x] - \frac 1 {2^n}

get a function {c(x)}, computable by a circuit of size {O(\epsilon^2 2^n)} such that

\displaystyle \sum_x (-1)^{c(x)} \cdot g(x) \geq \epsilon \cdot \sum_x \left| g(x) \right|

and note that {\sum_x |g(x)|} is the {\ell_1} 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 {c}, so

\displaystyle \mathop{\mathbb P}_{z\in \{ 0,1 \}^{n-1}} [ c(G(z)) =1] - \mathop{\mathbb P}_{x\in \{ 0,1 \}^n} [c(x)=1] \geq \frac \epsilon 2

About these ads