# Proving the security of Nisan-Wigderson pseudo-random number generator

Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as follows:

$$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$$

To compute the $i$th bit of $G_f$ we take the bits of $x$ with indexes in $S_i$ and then apply $f$ to them.

Assume that $f$ is $\frac{1}{n^c}$-hard for circuits of size $n^c$ where $c$ is a constant. How can we prove that $G_f$ is $(\frac{n^c}{2}, \frac{2}{n^c})$-secure pseudo-random number generator?

### Definitions:

A partial $(m,k)$-design is a collection of subsets $S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$ such that

• for all $i$: $|S_i|=m$, and
• for all $i \neq j$: $|S_i \cap S_j| \leq k$.

A function $f$ is $\epsilon$-hard for circuits of size $s$ iff no circuit of size $s$ can predict $f$ with probability $\epsilon$ better than a coin toss.

A function $G:\{0,1\}^l \to \{0,1\}^n$ is $(s, \epsilon)$-secure pseudo-random number generator iff no circuit of size $s$ can distinguish between a random number and a number generated by $G_f$ with probability better than $\epsilon$.

We use $x|_A$ for the string composed of $x$'s bits with indexes in $A$.

• ps: this is not really my homework but please treat it as you would treat a homework question, it is sometimes given to students taking an introduction to crypto course. – Kaveh Mar 13 '12 at 4:10
• and let the CS.SE vs crypto.SE battle begin! (: – Ran G. Mar 13 '12 at 4:25
• google gives quite a nice results: 1, 2 – Ran G. Mar 13 '12 at 4:29
• That's not a good answer - it's only a google search. Maybe you wish to make an answer out of it? – Ran G. Apr 10 '12 at 21:09
• @RanG., good point. – Kaveh Apr 10 '12 at 21:14