Bisakah komputasi kuantum pada akhirnya digunakan untuk membuat istirahat hashing hari modern menjadi sepele?

Sederhananya, jika seseorang membangun perangkat komputasi kuantum dengan kekuatan, katakanlah, 20 qubit, dapatkah komputer seperti itu digunakan untuk membuat segala jenis algoritma hashing modern tidak berguna?

Apakah mungkin untuk memanfaatkan kekuatan komputasi kuantum dalam aplikasi komputasi tradisional?

Komputer kuantum mungkin memiliki beberapa keunggulan dibandingkan komputer klasik untuk beberapa kasus. Contoh yang paling luar biasa adalah Algoritma Shor yang dapat memfaktorkan sejumlah besar waktu polinomial (sementara secara klasik, algoritma yang paling terkenal membutuhkan waktu yang eksponensial). Ini benar-benar merusak skema seperti RSA, berdasarkan kekerasan faktorisasi.

Ini belum tentu kasus untuk fungsi hash. Pertama, kita perlu mendefinisikan apa artinya memecah fungsi hash. Salah satu cara untuk memecahnya disebut serangan pra-gambar : Anda memberi saya nilai hash , dan saya perlu menemukan pesan sedemikian sehingga . Serangan lain adalah serangan tabrakan , di mana Anda tidak memberi saya apa-apa, dan saya perlu membuat dua pesan berbeda yang memiliki hash . Ini lebih mudah daripada menemukan preimage, karena saya tidak terikat pada tertentu .$v$$m$$\operatorname{hash}(m)=v$$m_1, m_2$$\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$$v$

Apa yang dapat dilakukan komputer Quantum? Hasil utama adalah algoritma pencarian Grover : metode untuk komputer kuantum untuk mencari dalam database berukuran tidak disortir dengan waktu (sementara secara klasik akan membutuhkan waktu yang diharapkan dari ).$N$$O(\sqrt{N})$$N/2$

Dengan algoritma Grover, menemukan preimage dari fungsi hash yang outputnya bit membutuhkan waktu , daripada .$k$$O(2^{k/2})$$O(2^k)$

Apakah ini masalah ? Belum tentu. Fungsi hash dirancang sedemikian rupa sehingga waktu dianggap "aman" (dengan kata lain, desainer hash selalu menggandakan ). Ini disebabkan oleh paradoks Ulang Tahun yang dengannya menemukan tabrakan dimungkinkan dengan waktu oleh komputer klasik.$2^{k/2}$$k$$O(2^{k/2})$

Hal yang menyenangkan tentang algoritma Grover yang optimal - setiap algoritma kuantum lainnya untuk menemukan elemen dalam basis data yang tidak disortir akan berjalan dalam waktu .$\Omega(\sqrt{N})$

Dapatkah komputer kuantum melakukan serangan tabrakan yang lebih baik ? Sebenarnya saya tidak yakin tentang itu. Algoritma Grover dapat diperpanjang, sehingga jika ada item (yaitu, preimage), waktu untuk menemukannya dikurangi menjadi . Tapi ini tidak memberikan benturan - menjalankan algoritma lagi mungkin mengembalikan preimage yang sama. Di sisi lain, jika kita memilih secara acak, dan kemudian menggunakan Algoritma Grover, besar kemungkinan akan mengembalikan pesan yang berbeda. Saya tidak yakin apakah ini memberikan serangan yang lebih baik.$t$$O(\sqrt{N/t})$$m_1$

_{(ini menjawab pertanyaan yang lebih umum, tanpa membatasi komputer hingga 20 qubit, yang tidak akan cukup untuk memecahkan hash 1024-bit saat ini).}

Dari apa yang saya pahami, komputasi kuantum memang memiliki kekuatan untuk dengan mudah mematahkan algoritma hashing saat ini. Namun, dalam jangka panjang kita juga akan dapat menggunakan algoritma hashing yang lebih kompleks, dan umumnya lebih mudah untuk mengenkripsi daripada mendekripsi sesuatu. Saya pikir masalah terbesar untuk dipertimbangkan adalah ketika komputasi kuantum hanya tersedia untuk beberapa orang tertentu, memberi mereka akses mudah ke hal-hal yang dilindungi oleh algoritma saat ini jauh sebelum algoritma yang lebih maju atau bahkan kesadaran ancaman itu tersebar luas.

Lihat di sini untuk jawaban yang sebenarnya teknis untuk pertanyaan tentang Stack Overflow.