13
$\begingroup$

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

$\endgroup$
  • $\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 '12 at 4:10
  • 3
    $\begingroup$ and let the CS.SE vs crypto.SE battle begin! (: $\endgroup$ – Ran G. Mar 13 '12 at 4:25
  • 1
    $\begingroup$ google gives quite a nice results: 1, 2 $\endgroup$ – Ran G. Mar 13 '12 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 '12 at 21:09
  • $\begingroup$ @RanG., good point. $\endgroup$ – Kaveh Apr 10 '12 at 21:14
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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