Jika P = NP, apakah ada cryptosystems yang akan membutuhkan n ^ 2 waktu untuk istirahat?

Jika P tidak sama dengan NP, apakah masih mungkin melakukan desain cryptosystem di mana algoritma cryptanalysis optimal membutuhkan, katakanlah, kuadrat waktu yang dihabiskan oleh algoritma enkripsi dan dekripsi yang sah? Apakah sudah ada algoritma seperti itu?

Ya - pada kenyataannya, algoritma kunci publik pertama yang ditemukan di luar badan intelijen bekerja seperti itu! Publikasi pertama yang mengusulkan kriptografi kunci publik adalah "Secure Communications over Insecure Channels" oleh Ralph Merkle , di mana ia mengusulkan untuk menggunakan "puzzle" . Ini adalah protokol perjanjian kunci.

1. Alice mengirim pesan terenkripsi (disebut teka-teki), masing-masing berisi pengidentifikasi unik I i dan kunci sesi K i , dengan tombol untuk setiap pesan yang dipilih di antara serangkaian tombol n . Ini membutuhkan O ( n ) waktu ( O ( 1 ) per pesan).$n$$I_i$$K_i$$n$$O(n)$$O(1)$
2. Bob mendekripsi salah satu pesan dengan brute force dan mengirimkan kembali terenkripsi dengan K i . Ini membutuhkan O ( n ) waktu ( O ( 1 ) per tombol, kali n kunci yang mungkin).$I_i$$K_i$$O(n)$$O(1)$$n$
3. Alice mencoba semua kunci untuk mendekripsi pesan. Ini membutuhkan waktu lagi.$O(n)$

Masing-masing pihak hanya membutuhkan perhitungan , tetapi penguping yang ingin menemukan K saya perlu mencoba setengah dari rata-rata teka-teki untuk menghitung kunci yang tepat (eavesdropper tidak tahu pesan mana yang dipilih Bob untuk didekripsi), jadi eavesdropper membutuhkan Θ ( n 2 ) perhitungan rata-rata.$O(n)$$K_i$$\Theta(n^2)$

Setelah Merkle menemukan puzzle-nya, Diffie dan Hellman menerbitkan protokol perjanjian kunci berdasarkan masalah logaritma diskrit . Protokol ini masih digunakan sampai sekarang.

Masalah dengan teka-teki Merkle, atau apa pun di mana jumlah pekerjaan yang harus dilakukan oleh penyerang hanya meningkat seiring kuadrat dari pihak yang sah, adalah bahwa dibutuhkan ukuran kunci yang sangat besar dan jumlah perhitungan untuk mencapai margin keamanan yang layak.

Bagaimanapun, tidak jelas bahwa hanya membuktikan bahwa P = NP akan membatalkan algoritma kriptografi yang ada. Jika peningkatan polinomial adalah daya yang cukup tinggi, dalam praktiknya mungkin tidak terlalu penting. Lihat Bagaimana keamanan perlu diubah jika P = NP? , Dapatkah kita mengatakan bahwa jika P = NPP = NP tidak ada enkripsi kunci publik aman BPA? , P = NP dan sistem kriptografi saat ini , ...

https://en.m.wikipedia.org/wiki/One-time_pad

One Time Pad aman terlepas dari kerumitannya, asalkan nomor Anda benar-benar acak.

Bahkan jika Anda dapat mencoba setiap kunci dengan cepat, itu tidak berguna karena ini akan mengungkapkan setiap pesan yang mungkin, dan tidak ada cara untuk mengetahui mana yang diinginkan.

Untuk apa yang Anda gambarkan, jika analisis hanya membutuhkan kuadrat waktu enkripsi, itu akan dianggap tidak aman oleh standar modern. Enkripsi perlu terjadi dalam hitungan detik atau bahkan kurang, sehingga peningkatan kuadrat akan memungkinkan pesan untuk diterjemahkan dalam beberapa jam.