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?


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$.

  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Mar 13, 2012 at 4:10
  • 3
    $\begingroup$ and let the CS.SE vs crypto.SE battle begin! (: $\endgroup$
    – Ran G.
    Mar 13, 2012 at 4:25
  • 1
    $\begingroup$ google gives quite a nice results: 1, 2 $\endgroup$
    – Ran G.
    Mar 13, 2012 at 4:29
  • $\begingroup$ That's not a good answer - it's only a google search. Maybe you wish to make an answer out of it? $\endgroup$
    – Ran G.
    Apr 10, 2012 at 21:09
  • $\begingroup$ @RanG., good point. $\endgroup$
    – Kaveh
    Apr 10, 2012 at 21:14

1 Answer 1


Here is Ran G.'s answer mentioned in the comments: Google gives quite nice results: 1, 2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.