Apakah ada penelitian saat ini tentang penerapan Randomness Extractors?

Apakah sudah ada penelitian dalam mengimplementasikan konstruksi pengacakan acak?

Tampaknya bukti ekstraktor menggunakan Big-Oh, meninggalkan kemungkinan untuk konstanta tersembunyi yang besar, membuat implementasi terprogram berpotensi tidak realistis.

Beberapa konteks: Saya tertarik menggunakan ekstraktor acak sebagai sumber cepat (terbukti?) Bilangan acak untuk digunakan dalam simulasi Monte Carlo. Kami (grup Fisika Komputasi ETHZ) telah membiasakan sumber entropi tinggi dari generator bilangan acak kuantum yang ingin kami ekstrak dari keacakan. Seorang siswa sebelumnya berusaha untuk mengimplementasikan konstruksi Trevisan dan mengalami masalah kompleksitas spasial. Selain dari siswa itu, saya belum menemukan referensi kepada orang yang mencoba menerapkan ekstraktor.

Catatan: Saya mahasiswa CS yang sangat baru di bidang CS Teoretis dan Pengekstraksi Keacakan.

Banyak literatur extractor adalah tentang meminimalkan panjang benih, yang penting untuk aplikasi derandomisasi. Namun, itu mungkin tidak penting untuk Anda. Juga, seringkali literatur berfokus pada kesalahan yang relatif besar (misalnya, 1/100), yang baik untuk derandomisasi tetapi mungkin bermasalah dalam pengaturan lain, yang membutuhkan kesalahan kecil secara eksponensial.

Dalam pengaturan Anda, mungkin OK untuk menghasilkan sekali dan untuk semua benih acak panjang (katakanlah dengan melemparkan koin), dan kemudian menggunakannya untuk mengekstrak. Dalam hal ini Anda bisa menggunakan fungsi hash independen berpasangan yang memiliki implementasi yang agak efisien. Saya menulis makalah dengan Shaltiel dan Tromer tentang masalah ini. Anda juga dapat menggunakan fungsi hash yang hampir independen, yang dapat lebih efisien dan memiliki seed yang lebih kecil. (Tidak tahu begitu saja referensi yang baik untuk implementasi yang efisien, meskipun ada beberapa pekerjaan dalam hal ini.)

Jika Anda memiliki banyak sumber yang independen , maka Anda dapat melakukan hal-hal yang lebih baik. Extractor Hadamard klasik berfungsi jika tingkat entropi lebih besar dari 50% (ini harus disebutkan dalam survei di atas). Jika entropi lebih kecil dari 50%, maka kami memiliki satu konstruksi sederhana dengan Impagliazzo dan Wigderson . Ketergantungan antara jumlah sumber dan kesalahan yang dicapai pada tingkat entropi tidak ideal, meskipun untuk benar-benar memahaminya, Anda perlu melihat batas yang diberikan oleh teorema produk sum seni terkini. (Dan jika Anda mau mengasumsikan dugaan teoritik angka tertentu, Anda bisa mendapatkan ekstraktor yang lebih efisien.) Konstruksi ini telah sangat ditingkatkan dengan berbagai cara, beberapa di antaranya mungkin relevan dengan aplikasi Anda.Tesis Anup Rao .

Pertama-tama, lihat topik yang relevan di Wikipedia. Kedua, Anda dapat melihat makalah berikut:

Perkembangan terkini dalam konstruksi eksplisit ekstraktor oleh Ronen Shaltiel.

Makalah ini ditulis dalam bentuk survei, dan dapat membantu Anda menemukan "perkembangan terkini."

Akhirnya, jika semua yang Anda inginkan adalah urutan bit yang "terlihat" acak (tetapi belum tentu aman secara kriptografi), Anda dapat menerapkan fungsi hash (seperti MD5 atau SHA-1) ke sumber entropi tinggi Anda, dan dapatkan hasil yang sangat baik (untuk eksperimen fisik) dalam waktu hampir tidak ada.

Ada juga karya bagus karya Dodis, Gennaro, dkk. yang mempertimbangkan primitif kriptografi praktis yang dapat digunakan untuk ekstraksi. Mereka menunjukkan bahwa fungsi hash tidak dikenal sebagai ekstraktor yang baik, namun cipher blok dalam mode CBC-MAC dapat (dengan beberapa cetak-baik). Mereka juga mempertimbangkan konstruksi HMAC. Pendekatan ini menarik untuk diterapkan karena Anda dapat menggunakan pustaka kriptografi standar.

Untuk CBC-MAC, "fine-print" kira-kira:

• Mengasumsikan blockcipher adalah permutasi psuedo-acak
• Harus dikunci dengan kunci yang benar-benar acak (tetapi tidak harus rahasia) yang dapat digunakan kembali
• Jika outputnya adalah m bit, input harus memiliki minimal 2m bit min-entropi
• Panjang blok dan panjang kunci harus sama (jadi jika Anda menggunakan AES, itu berarti hanya AES-128 yang berfungsi)
• Panjang input dibatasi tetapi terikat tinggi

Untuk case generator pseudo-random kriptografis, Anda mungkin juga mencari di HKDF . Dalam makalah mereka membahas ekstraktor acak secara konseptual dan praktis, dan memberikan referensi yang bagus.

Sebagai catatan tambahan untuk menghasilkan keacakan untuk Monte Carlo, tentu saja ada HAVEGE . Jika kecepatan bit dan "provabilitas" sudah mencukupi, Anda mungkin menghindari keharusan bercampur dengan generator kuantum.