[Solved]: Proving the security of Nisan-Wigderson pseudo-random number generator

Problem Detail: Let $cal{S}={S_i}_{1leq ileq 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$.

Asked By : Kaveh

Answered By : Yuval Filmus

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/286  Ask a Question  Download Related Notes/Documents