Apa perbedaan antara crypto klasik dan crypto post-quantum?

Akankah ada kebutuhan untuk mengubah definisi keamanan jika kita memiliki komputer kuantum? Konstruksi kriptografi apa yang akan rusak? Apakah Anda tahu survei atau artikel yang menjelaskan apa yang perlu diubah?

Ringkasan makalah ini memberikan jawaban (sebagian).

Ada dua jenis metode kriptografi kunci publik tradisional: yang didasarkan pada faktorisasi bilangan bulat, dan yang didasarkan pada logaritma diskrit, termasuk metode berbasis kurva eliptik. Model-model ini diyakini sulit dalam model klasik, tetapi telah ditunjukkan bahwa tidak ada yang sulit dalam model kuantum.

Meskipun Grover mengembangkan algoritme kuantum yang menyediakan percepatan kuadrat untuk pencarian, Bennet, Bernstein, Brassard dan Vazirani menunjukkan bahwa model kuantum tidak dapat memungkinkan percepatan eksponensial untuk masalah pencarian. Ini menyarankan algoritma enkripsi simetris, fungsi satu arah dan hash kriptografi harus menahan serangan berbasis kuantum. Fokusnya, kemudian, harus pada pengembangan metode kunci publik yang aman.

Tanda tangan Lamport dapat memberikan mekanisme tanda tangan satu kali yang aman terhadap serangan kuantum. Masalah kisi dapat membentuk dasar untuk metode kunci publik yang tahan terhadap serangan kuantum; khususnya, masalah NP-Hard vektor-pendek dan vektor terdekat adalah menarik. Untuk model klasik dan kuantum, masalah ini diyakini sulit untuk kisi dimensi tinggi. The NTRU keluarga algoritma kriptografi, berdasarkan masalah kisi, dapat memberikan cara praktis untuk mencapai tahan terhadap serangan kuantum kriptografi kunci publik. Masalah lain yang mungkin berfungsi sebagai dasar untuk metode kunci publik yang aman adalah masalah decoding sindrom. Sistem enkripsi McEliece didasarkan pada masalah ini, dan varian mungkin menyediakan jalan ke depan.

Saya sama sekali tidak ahli (atau bahkan dekat dengan itu) pada topik, tetapi dari apa yang saya tahu:

Kriptografi klasik tergantung pada tingkat kepraktisan anjak (atau masalah log diskrit) yang tidak bisa dipraktikkan. Namun, anjak piutang tidak diyakini sebagai NP-lengkap, dan memang bisa dipecahkan dalam waktu polinomial oleh komputer kuantum. Jadi setiap kriptografi yang bergantung pada operasi itu akan rusak (yang mana setiap jenis kriptografi digunakan di luar sana yang saya tahu).

Kriptografi kuantum bergantung pada mekanika kuantum, dan secara teori tidak mungkin untuk memutusnya. Ini bukan masalah waktu sama sekali - itu hanya didasarkan pada keacakan, dan fakta bahwa sebuah negara runtuh saat diukur, jadi tanpa informasi yang tepat, pilihan terbaik Anda adalah dengan hanya 'menebak' pesan ... yang tidak berguna .