Apakah generator pseudorandom suara secara teori digunakan dalam praktik?

Sejauh yang saya ketahui, sebagian besar implementasi pembuatan nomor pseudorandom dalam praktik menggunakan metode seperti register umpan balik pergeseran linier (LSFR), atau algoritma "Mersenne Twister" ini. Sementara mereka lulus banyak tes statistik (heuristik), tidak ada jaminan teoritis bahwa mereka terlihat acak, misalnya, semua tes statistik yang dapat dihitung secara efisien. Namun metode ini digunakan tanpa pandang bulu dalam semua jenis aplikasi, mulai dari protokol kriptografi hingga komputasi ilmiah hingga perbankan (mungkin). Saya merasa agak mengkhawatirkan bahwa kita memiliki sedikit atau tidak ada jaminan tentang apakah aplikasi ini berfungsi sebagaimana mestinya (karena segala jenis analisis kemungkinan akan menganggap keacakan benar sebagai input).

Di sisi lain, teori kompleksitas dan kriptografi menyediakan teori pseudorandomness yang sangat kaya, dan kami bahkan memiliki konstruksi kandidat generator pseudorandom yang akan membodohi SETIAP tes statistik efisien apa pun yang dapat Anda lakukan, dengan menggunakan kandidat fungsi satu arah.

Pertanyaan saya adalah: sudahkah teori ini diterapkan? Saya berharap bahwa untuk kegunaan penting dari keacakan, seperti kriptografi atau komputasi ilmiah, secara teori PRG digunakan.

Sebagai tambahan, saya dapat menemukan beberapa analisis terbatas tentang seberapa baik algoritma populer seperti quicksort bekerja ketika menggunakan LSFR sebagai sumber keacakan, dan ternyata mereka bekerja dengan baik. Lihat "Algoritma acak dan nomor pseudorandom" Karloff dan Raghavan .

cr.crypto-security randomized-algorithms pseudorandomness pseudorandom-generators Henry Yuen
sumber

Bahkan ada PRG Universal - aman jika PRG aman ada.

$\:$

Apakah maksud Anda PRGs kriptografis? Jika demikian, bukankah kita tahu bahwa PRG (kriptografis) setara dengan OWF?

Henry Yuen

Iya. Bagi bit seed menjadi kira-kira blok kira-kira masing-masing bit, jalankan [jumlah blok] pertama Mesin turing pada blok yang sesuai hingga langkah, pad output ke bits, dan output xor dari output TM itu. (Sama seperti pencarian universal Levin, ini tidak dapat digunakan dalam praktik.)

$\;\;$

k

$k$

\sqrt{k}

$\sqrt{k}$

\sqrt{k}

$\sqrt{k}$

$\hspace{.2 in}$

k^{2}

$k^2$

$\hspace{.15 in}$

k + 1

$\:k+1\:$

$\;\;$

$\;\;\;\;$

mungkin lebih relevan dengan praktik adalah hasil yang berkaitan dengan keacakan yang diperlukan untuk hashing: dari keluarga kemerdekaan terbatas klasik ke hasil yang lebih baru seperti Mitzenmacher-Vadhan (kemandirian berpasangan + beberapa entropi dalam input memberikan pseudorandomness yang cukup untuk probing linier dan filter bloom) atau Patrascu Hasil -Hasil pada hashing tabulasi.

Sasho Nikolov

"Namun metode ini digunakan tanpa pandang bulu dalam semua jenis aplikasi, mulai dari protokol kriptografi ...". Saya harap tidak. Mersenne Twisters tidak boleh digunakan untuk kriptografi karena mereka tidak kuat secara kriptografi meskipun ada varian yang mungkin.

Mike Samuel

Jawaban:

Gagasan generator pseudorandom "suara teoretis" tidak benar-benar didefinisikan dengan baik. Lagi pula, tidak ada generator pseudorandom yang memiliki bukti keamanan. Saya tidak tahu bahwa kita dapat mengatakan bahwa generator pseudorandom berdasarkan kekerasan anjak bilangan bulat besar adalah "lebih aman" daripada, katakanlah, menggunakan AES sebagai generator pseudorandom. (Pada kenyataannya, ada perasaan bahwa itu kurang aman, karena kita tahu algoritma anjak kuantum tetapi bukan algoritma kuantum untuk memecahkan AES.)

Apa yang kami punya bukti matematis untuk berbagai hasil komposisi, mengatakan bahwa jika Anda menulis blok-cipher atau fungsi hash dengan cara tertentu Anda bisa mendapatkan generator pseudorandom atau fungsi pseudorandom. Beberapa hasil seperti itu banyak digunakan dalam praktik, misalnya, HMAC . Tetapi memang benar bahwa hasil yang mencapai PRG dan mulai dengan hanya mengasumsikan bahwa komponen dasar adalah fungsi satu arah yang polos tidak cukup efisien untuk digunakan untuk aplikasi (dan ini setidaknya sebagian inheren). Jadi, biasanya kita perlu menganggap fungsi PRG / stream cipher / block-cipher / hash sebagai primitif dasar, dan mulai membangun hal-hal lain darinya. Masalahnya bukan tentang analisis asimptotik karena pada dasarnya semua pengurangan kriptografis (kecuali mungkin untuk PRG universal Levin) dapat dibuat konkret dan memberikan jaminan konkret berdasarkan asumsi konkret.

Tetapi meskipun mereka tidak didasarkan pada fungsi satu arah, ada perasaan di mana konstruksi seperti AES "secara teoritis sehat" karena: (1) Ada dugaan formal tentang keamanan mereka. (2) Ada pekerjaan untuk mencoba menyangkal dugaan ini, dan juga mendapatkan implikasi dari dugaan tersebut.

Dan memang, orang sadar bahwa untuk banyak aplikasi, tidak akan pintar menggunakan PRG seperti LSFR yang tidak memuaskan (1) dan (2) di atas.

Boaz Barak
sumber

Saya kira Anda ingin menautkan ke salah satu makalah Jonathan Katz yang ada di laman webnya. Btw, apakah Anda ingin kami menggabungkan ini dengan akun Anda yang lain ?

Kaveh

Anda tampaknya membingungkan teori dengan praktik. Generator pseudorandom yang secara teoretis kedengarannya tidak sesuai untuk penggunaan praktis karena beberapa alasan:

Mungkin sangat tidak efisien.
Bukti keamanan hanya asimptotik, dan untuk parameter keamanan tertentu yang digunakan, generator pseudorandom mungkin mudah rusak.
Semua bukti keamanan bersyarat, jadi dalam beberapa hal bahkan tidak memuaskan gagasan keamanan teoritis.

Berbeda dengan ini, generator pseudorandom yang sebenarnya cepat, dan tersedia dalam berbagai rasa tergantung pada penggunaannya. Untuk penggunaan non-kriptografi, hampir apa pun selain LFSR biasa akan melakukan pekerjaan - tidak terbukti, tetapi dalam praktiknya (yang lebih penting bagi orang yang menggunakan barang pada kenyataannya).

Untuk penggunaan kriptografi, orang mencoba menjadi lebih pintar. Pada titik ini kritik Anda masuk akal: kita tidak bisa tahu bahwa generator pseudorandom tertentu yang digunakan adalah "aman", dan memang beberapa yang lama telah rusak, misalnya RC4 seperti yang digunakan dalam WEP. Namun, untuk alasan yang disebutkan di atas, menggunakan generator pseudorandom suara yang secara teoritis (kondisional) sayangnya bukan solusi yang realistis. Sebagai gantinya, komunitas kriptologis bergantung pada "peer review" - peneliti lain yang mencoba untuk "merusak" sistem (definisi mereka tentang kapan sebuah cipher rusak sangat luas).

Akhirnya, dalam aplikasi ketika uang dapat diinvestasikan dan keamanan cukup penting - katakanlah kode nuklir - orang menggunakan kebisingan yang dihasilkan secara fisik (melewati ekstraktor acak), meskipun itu tidak di luar kritik teoritis.

Ketika peneliti menulis proposal hibah atau pengantar untuk makalah, mereka sering mengklaim bahwa penelitian mereka berkaitan dan menginformasikan praktik. Apakah mereka mempercayainya atau hanya omong kosong, saya tidak tahu (dan itu mungkin tergantung pada peneliti), tetapi Anda harus sadar bahwa hubungannya sangat dilebih-lebihkan di kalangan akademis, karena alasan yang jelas.

Satu hal yang membatasi kita sebagai peneliti matematika adalah ikatan dogmatis kita pada bukti formal. Anda menyebutkan analisis algoritma acak yang diberikan oleh generator pseudorandom sederhana. Jenis analisis ini tidak dapat diperluas ke masalah dunia nyata, karena mereka terlalu rumit. Namun, dalam praktiknya orang bahkan memecahkan masalah NP-hard sepanjang waktu, dengan metode informasi.

Masalah dunia nyata lebih baik dipahami dengan mata yang lebih ilmiah dan eksperimental. Mereka lebih baik diselesaikan dari perspektif teknik. Mereka menginspirasi penelitian teoritis, dan kadang-kadang diinformasikan olehnya. Seperti yang dikatakan Dijsktra, ilmu komputer (secara teoritis) tidak benar-benar tentang komputer, tidak lagi.

Yuval Filmus
sumber

Terima kasih atas jawaban Anda, Yuval. Namun, saya tidak sepenuhnya percaya bahwa konstruksi generator pseudorandom dari kriptografi sangat tidak efisien. Sejauh yang saya bisa lihat, tidak ada yang melakukan penelitian tentang ini.

Henry Yuen

Saya juga tidak setuju dengan pernyataan selimut bahwa generator pseudorandom standar cukup untuk "keperluan sehari-hari". Seperti yang ditunjukkan oleh kertas baru-baru ini "Ron salah, Whit benar", generasi pseudorandom yang rusak telah menyebabkan kerentanan yang memalukan bagi jumlah orang yang tidak dapat diabaikan. Analisis khusus itu cukup sederhana; berapa banyak aplikasi "dunia nyata" dapat mengalami kerentanan lebih halus karena LSFR tidak memadai? Jika overhead komputasi tambahan yang dibutuhkan untuk PRG yang secara teori bagus tidak banyak, mengapa tidak menggunakannya?

Henry Yuen

@HenryYuen LSFR tidak digunakan untuk aplikasi kriptografi dalam sistem modern yang layak. (Tentu saja, ada sistem yang dirancang dengan buruk di luar sana, seperti GSM yang diajarkan dalam kursus pengantar bagaimana tidak melakukannya.) Masalah yang ditemukan dalam kertas "Ron salah, Whit benar" kertas tidak berkualitas. PRNG sendiri, tetapi dengan kualitas pertemuan entropi.

Gilles 'SANGAT berhenti menjadi jahat'