Sprawdzanie bezpieczeństwa generatora liczb pseudolosowych Nisan-Wigderson

Niech częściowe -design i być funkcją logiczną. Generator Nisan- jest zdefiniowany w następujący sposób:$\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$

Aby obliczyć ty bit , bierzemy bity z indeksami w a następnie stosujemy do nich .$i$$G_f$$x$$S_i$$f$

Załóżmy, że jest twarde dla obwodów o rozmiarze gdzie jest stałą. Jak możemy udowodnić, że jest bezpiecznym generatorem liczb pseudolosowych?$f$$\frac{1}{n^c}$$n^c$$c$$G_f$$(\frac{n^c}{2}, \frac{2}{n^c})$

Definicje:

Częściowa -design to zbiór podzbiorów tak, że$(m,k)$$S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

• dla wszystkich : oraz$i$$|S_i|=m$
• dla wszystkich : .$i \neq j$$|S_i \cap S_j| \leq k$

Funkcja jest twarda dla obwodów o rozmiarze iff żaden obwód o rozmiarze może przewidzieć z prawdopodobieństwem lepiej niż rzut monetą.$f$$\epsilon$$s$$s$$f$$\epsilon$

Funkcja jest -bezpiecznym generatorem liczb pseudolosowych, jeśli żaden obwód wielkości potrafi rozróżnić liczby losowej oraz liczba wygenerowana przez z prawdopodobieństwem lepszym niż .$G:\{0,1\}^l \to \{0,1\}^n$$(s, \epsilon)$$s$$G_f$$\epsilon$

Używamy na łańcuch składający się bitów „S z indeksami w .$x|_A$$x$$A$

Oto odpowiedź Ran G. wspomniana w komentarzach: Google daje całkiem niezłe wyniki: 1 , 2 .