Membuktikan keamanan generator nomor pseudo-acak Nisan-Wigderson

Misalkan $\cal{S}=\{S_i\}_{1\leq i\leq n}$ menjadi desain parsial $(m,k)$ dan $f: \{0,1\}^m \to \{0,1\}$ menjadi fungsi Boolean. Generator Nisan-Wigderson $G_f: \{0,1\}^l \to \{0,1\}^n$ didefinisikan sebagai berikut:

Untuk menghitung $i$ th sedikit $G_f$ kita mengambil bit $x$ dengan indeks di $S_i$ dan kemudian menerapkan $f$ kepada mereka.

Asumsikan $f$ adalah $\frac{1}{n^c}$ -Hard untuk sirkuit ukuran$n^c$di mana$c$adalah konstanta. Bagaimana kita dapat membuktikan bahwa$G_f$adalah-secure pseudo-random number generator?$(\frac{n^c}{2}, \frac{2}{n^c})$

Definisi:

Parsial -design adalah kumpulan himpunan bagian S 1 , ... , S n ⊆ [ l ] = { 1 , ... , l } sedemikian rupa sehingga$(m,k)$$S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$

• untuk semua : | S i | = $i$$|S_i|=m$ , dan
• untuk semua : | S i ∩ S j | ≤ $i \neq j$$|S_i \cap S_j| \leq k$ .

Suatu fungsi adalah ϵ -beras untuk rangkaian ukuran s jika jika tidak ada rangkaian ukuran s dapat memprediksi f dengan probabilitas ϵ lebih baik daripada lemparan koin.$f$$\epsilon$$s$$s$$f$$\epsilon$

Fungsi adalah ( s , ε ) Secure pseudo-random number generator IFF ada sirkuit ukuran s dapat membedakan antara nomor acak dan sejumlah dihasilkan oleh G f dengan probabilitas lebih baik dari $G:\{0,1\}^l \to \{0,1\}^n$$(s, \epsilon)$$s$$G_f$$\epsilon$ .

Kami menggunakan untuk string terdiri dari x 's bit dengan indeks di A .$x|_A$$x$$A$

Inilah jawaban Ran G. yang disebutkan dalam komentar: Google memberikan hasil yang cukup bagus: 1 , 2 .