Demostrando la seguridad del generador de números pseudoaleatorios Nisan-Wigderson

Deje que ser un parcial ( m , k ) -Diseño y f : { 0 , 1 } m → { 0 , 1 } sea una función booleana. El generador de Nisan-Wigderson G f : { 0 , 1 } l → { 0 , 1 } n se define de la siguiente manera:$\cal{S}=\{S_i\}_{1\leq i\leq n}$$(m,k)$$f: \{0,1\}^m \to \{0,1\}$$G_f: \{0,1\}^l \to \{0,1\}^n$

Para calcular el ésimo bit de G f tomamos los bits de x con índices en S i y luego les aplicamos f .$i$$G_f$$x$$S_i$$f$

Suponga que es $f$ -duro para circuitos de tamañon$\frac{1}{n^c}$$n^c$ donde es una constante. ¿Cómo podemos demostrar que G f es ( n $c$$G_f$-seguro seguro generador de números pseudoaleatorios?$(\frac{n^c}{2}, \frac{2}{n^c})$

Definiciones:

Un diseño parcial es una colección de subconjuntos S 1 , ... , S n ⊆ [ l ] = { 1 , ... , l } tal que$(m,k)$$S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

• para toda : | S i | = m , y$i$$|S_i|=m$
• para todo : | S i ∩ S j | ≤ k .$i \neq j$$|S_i \cap S_j| \leq k$

Una función es ε -Hard para circuitos de tamaño s FIB ningún circuito de tamaño s puede predecir f con probabilidad ε mejor que un sorteo.$f$$\epsilon$$s$$s$$f$$\epsilon$

Una función es un generador de números pseudoaleatorios seguro ( s , ϵ ) si ningún circuito de tamaño s puede distinguir entre un número aleatorio y un número generado por G f con probabilidad mejor que ϵ .$G:\{0,1\}^l \to \{0,1\}^n$$(s, \epsilon)$$s$$G_f$$\epsilon$

Usamos para la cadena compuesta de x bits de 's con índices en A .$x|_A$$x$$A$

Aquí está la respuesta de Ran G. mencionada en los comentarios: Google da resultados bastante buenos: 1 , 2 .