Prouver la sécurité du générateur de nombres pseudo-aléatoires Nisan-Wigderson

Soit $\cal{S}=\{S_i\}_{1\leq i\leq n}$ une conception partielle $(m,k)$ et $f: \{0,1\}^m \to \{0,1\}$ une fonction booléenne. Le générateur de Nisan-Wigderson $G_f: \{0,1\}^l \to \{0,1\}^n$ est défini comme suit:

Pour calculer le ème bit de G f, nous prenons les bits de x avec des index dans S i puis nous leur appliquons f .$i$$G_f$$x$$S_i$$f$

Supposons que est $f$ -hard pour les circuits de taillencoùcest une constante. Comment prouver queGfest(n$\frac{1}{n^c}$$n^c$$c$$G_f$générateur de nombres pseudo-aléatoires sûrs?$(\frac{n^c}{2}, \frac{2}{n^c})$

Définitions:

Une conception partielle est un ensemble de sous-ensembles S 1 , … , S n ⊆ [ l ] = { 1 , … , l } tels que$(m,k)$$S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

• pour tout : | S i | = m , et$i$$|S_i|=m$
• pour tout : | S i ∩ S j | ≤ k .$i \neq j$$|S_i \cap S_j| \leq k$

Une fonction est - ε -hard pour les circuits de taille s IFF pas de circuit de taille s peut prédire f avec une probabilité ε mieux qu'un tirage au sort pièce.$f$$\epsilon$$s$$s$$f$$\epsilon$

Une fonction est ( s , e ) -secure générateur de nombres pseudo-aléatoires ssi pas de circuit de taille s peut distinguer entre un nombre aléatoire et un nombre généré par G f avec probabilité meilleure que ϵ .$G:\{0,1\}^l \to \{0,1\}^n$$(s, \epsilon)$$s$$G_f$$\epsilon$

Nous utilisons pour la chaîne composée de x bits S » avec les index de A .$x|_A$$x$$A$

Voici la réponse de Ran G. mentionnée dans les commentaires: Google donne de très bons résultats: 1 , 2 .