Apa motivasi di balik definisi pseudorandom dalam bahasa Nisan / Wigderson?

Saya membaca "Kekerasan vs Keacakan" klasik oleh Nisan dan Wigderson. Misalkan , dan memperbaiki fungsi l : N → N . Mereka mendefinisikan keluarga fungsi G = { G n : B l ( n ) → B n } menjadi pseudorandom jika setiap sirkuit ukuran n yang kita miliki$B=\{0,1\}$$l\colon \mathbb{N} \to \mathbb{N}$$G = \{G_n : B^{l(n)} \to B^n\}$$n$

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(di mana adalah variabel acak seragam).$x \in B^{n},y \in B^{l(n)}$

Saya mengerti bahwa saya menganggap dan y sebagai variabel acak, dan saya ingin membandingkan jarak antara x dan G ( y ) sebagai variabel acak. Saya mendapatkan intuisi bahwa sirkuit digunakan sebagai semacam "tes" untuk melihat apakah G dapat "diketahui". Yang benar-benar saya perjuangkan adalah mengapa kondisi ( ∗ ) yang benar. Adakah yang punya saran tentang bagaimana memikirkan definisi ini?$x$$y$$x$$G(y)$$G$$(*)$

Ada dua aspek yang perlu disebutkan.

Yang pertama adalah ide umum mendefinisikan PRG dengan memiliki output yang terlihat berbeda dari seragam ke sirkuit kecil . Gagasan ini kembali ke Yao dan benar-benar definisi terkuat yang dapat Anda tanyakan ketika bertujuan secara eksplisit pada keacakan acak untuk pengamat yang terikat komputasi .

Aspek kedua adalah pilihan parameter di mana kita membatasi ukuran rangkaian menjadi dan perbedaan probabilitas penerimaan menjadi 1 / n , di mana n juga merupakan ukuran keluaran PRG. Pilihan ini agak berbeda dari kripto biasa di mana ukuran sirkuit adalah p o l y ( n ) dan perbedaan probabilitas diperlukan untuk menjadi lebih kecil daripada p o l y ( n ) . Dalam parameter kasus khusus kami (bukan p o l y ( n $n$$1/n$$n$$poly(n)$$poly(n)$$poly(n)$) diperlukan untuk mendapatkan hasil yang paling ketat termasuk, dalam simulasi polinomial tertentu. Meskipun pada prinsipnya seseorang dapat memiliki 3 parameter yang berbeda, ternyata hasil kami memiliki ini bekerja pada dasarnya dengan cara yang sama sehingga kami melipatnya menjadi satu (di samping ukuran input yang dipandang sebagai fungsi dari n ).$l(n)$$n$

Saya sama sekali tidak ahli dalam hal ini, tetapi komponen kunci dari definisi pseudorandomness (sebagai lawan dari upaya untuk mendefinisikan keacakan) adalah bahwa tujuan dari sesuatu "pseudorandom" adalah untuk mengelabui sirkuit. Dengan kata lain, motivasinya adalah memikirkan string pseudorandom yang dipasok ke sirkuit alih-alih string yang benar-benar acak.

Dalam pengertian itu, sebenarnya Anda tidak mencoba berpura-pura bahwa dan G ( y ) "terlihat sama". Itu bahwa mereka "terlihat sama" ke sirkuit (tentu kompleksitas terikat).$x$$G(y)$

Jadi peran sirkuit sangat penting, bukan hanya menjadi "fungsi uji".

Mudah-mudahan, saya bisa sedikit memperluas tanggapan Suresh. Pertama, saya tidak berpikir bahwa ketatnya ketidaksamaan diperlukan dalam Anda , dan saya juga tidak yakin mengapa 1 / n diperlukan, dan tidak 1 / 2 n atau sesuatu yang lain. Namun, secara praktis, saya pikir 1 / n sudah cukup untuk mendapatkan beberapa hasil teoritis yang menarik.$(*)$$1/n$$1/2n$

Tetapi kemudian Anda hampir pasti ingin menegaskan bahwa setiap dapat dihitung dalam beberapa waktu, katakanlah eksponensial. Lebih jauh, saya pikir Anda harus menyatakan bahwa l ( n ) < n . Anda dapat menganggap l ( n ) sebagai panjang benih. Jadi G i adalah pseudorandom jika ia dapat meningkatkan jumlah bit dalam string acak panjang l ( n ) tanpa terdeteksi oleh rangkaian ukuran kurang dari n .$G_i$$l(n) < n$$l(n)$$G_i$$l(n)$$n$