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