Доказательство безопасности генератора псевдослучайных чисел Нисана-Вигдерсона

Пусть $\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$ определяется следующим образом:

Чтобы вычислить $i$ й бит $G_f$ мы берем биты $x$ с индексами в $S_i$ и затем применяем $f$ к ним.

Предположим, что является -твердым для цепей размером где - константа. Как мы можем доказать, что является безопасным генератором псевдослучайных чисел?$f$$\frac{1}{n^c}$$n^c$$c$$G_f$$(\frac{n^c}{2}, \frac{2}{n^c})$

Определения:

Частичный -дизайн представляет собой набор подмножеств таких, что$(m,k)$$S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

• для всех : и$i$$|S_i|=m$
• для всех : .$i \neq j$$|S_i \cap S_j| \leq k$

Функция является -hard для цепей размером если никакая схема размера может предсказать с вероятностью лучше, чем бросок монеты.s s s f $f$$\epsilon$$s$$s$$f$$\epsilon$

Функция является ( s , ϵ ) -безопасным генератором псевдослучайных чисел, если только схема с размером s не может различить случайное число и число, сгенерированное G f с помощью вероятность лучше, чем ϵ .$G:\{0,1\}^l \to \{0,1\}^n$$(s, \epsilon)$$s$$G_f$$\epsilon$

Мы используем Для строки , состоящей из й бит «ы с индексами в A .$x|_A$$x$$A$

Вот ответ Ран Г., упомянутый в комментариях: Google дает довольно хорошие результаты: 1 , 2 .