Ancaman Kuantum: Kriptografi mana yang mati dan mana yang hidup? (Atau: Mengapa ZK-STARK aman PQ?) Sebelumnya, saya menjelaskan cara kerja komputer kuantum: Pikirkan pemecahan masalah seperti mencoba melarikan diri dari labirin. Ada banyak kemungkinan jalan dan Anda perlu memeriksa masing-masing sampai Anda menemukan jalan keluar. Begitulah cara kerja komputer klasik (non-kuantum). Tetapi hukum mekanika kuantum memungkinkan untuk melakukan yang lebih baik. Mereka memungkinkan sistem (sekelompok partikel) untuk menjelajahi secara paralel *semua* jalur yang berbeda di labirin. Jalur yang mencapai pintu keluar tetap layak sementara yang mengarah ke jalan buntu menghilang. Kemudian, alam semesta memilih secara acak salah satu jalur yang tersisa (ini adalah bagian yang tidak disukai Einstein, mengatakan "Tuhan tidak bermain dadu", hanya dia yang benar-benar melakukannya). Begitulah cara QC memecahkan masalah yang akan memakan waktu jutaan tahun untuk dipecahkan oleh komputer klasik. Tetapi ada jenis primitif kriptografi yang dapat dipecahkan oleh komputer kuantum, dan yang tetap aman. Bagaimana ini mungkin? Dalam penjelasan saya sebelumnya, saya menghilangkan bagian penting: Tidak semua labirin sama. Ada beberapa labirin di mana jalan buntu menghilang, meninggalkan alam semesta hanya dengan jalan yang baik yang mencapai pintu keluar. Saya menyebutnya "labirin kuantum mudah" karena ketika alam semesta mengambil sampel jalur untuk labirin seperti itu, itu akan selalu menjadi jalan yang mengarah ke jalan keluar. Mudah untuk mencapai ujung labirin berarti mudah untuk dipecahkan. Namun, dalam "labirin keras kuantum" semua jalan tetap "hidup", apakah mereka mencapai jalan buntu atau jalan keluar. Untuk labirin seperti itu, komputer kuantum tidak lebih baik dari komputer klasik. Ketika Tuhan melempar dadu dan memilih jalan, semua jalan – baik dan buruk – sama-sama mungkin muncul. Jadi komputer kuantum melakukan analog komputer klasik, secara acak memeriksa satu jalur di labirin. Sekarang Anda mungkin bertanya: Labirin mana yang mudah kuantum dan mana yang tidak? ...