Mengapa belum ada algoritma enkripsi yang didasarkan pada masalah NP-Hard yang diketahui?

109

Sebagian besar enkripsi saat ini, seperti RSA, bergantung pada faktorisasi bilangan bulat, yang tidak diyakini sebagai masalah NP-keras, tetapi milik BQP, yang membuatnya rentan terhadap komputer kuantum. Saya bertanya-tanya, mengapa belum ada algoritma enkripsi yang didasarkan pada masalah NP-hard yang dikenal. Kedengarannya (setidaknya dalam teori) seperti itu akan membuat algoritma enkripsi yang lebih baik daripada yang tidak terbukti sebagai NP-hard.

Ken Li
sumber

Jawaban:

76

Kekerasan terburuk. Masalah lengkap NP tidak cukup untuk kriptografi. Bahkan jika masalah NP-lengkap sulit dalam kasus terburuk ( ), mereka masih bisa dipecahkan secara efisien dalam kasus rata-rata. Kriptografi mengasumsikan adanya masalah rata-rata yang sulit diatasi dalam NP. Juga, membuktikan adanya masalah sulit rata-rata di NP menggunakan asumsi adalah masalah terbuka utama.P N PPNPPNP

Bacaan yang sangat baik adalah karya klasik oleh Russell Impagliazzo, A Personal View of Average-Case Complexity , 1995.

Sebuah survei yang sangat baik adalah Kompleksitas Kasus Rata-rata oleh Bogdanov dan Trevisan, Yayasan dan Tren dalam Theoretical Computer Science Vol. 2, No. 1 (2006) 1–106

Mohammad Al-Turkistany
sumber
1
Bukankah kita juga membutuhkan kekerasan dalam kasus terbaik? Bagaimanapun, semua kunci kami harus aman. Atau bisakah kita secara efektif (dan efisien) mencegah kasus terbaik terjadi?
Raphael
7
Selain itu, kita harus dapat menghasilkan instance yang sulit dalam waktu yang wajar. Singkatnya, kita membutuhkan lebih dari sekadar ness. NP-hard
Kaveh
@ Raphael, itu harus cukup jika probabilitas untuk mendapatkan kasus "baik" yang tidak diinginkan cukup kecil. Jika dikatakan lebih kecil dari probabilitas untuk menebak kunci yang benar dari kasus "buruk" yang diinginkan, risiko ini harus dianggap sebagai IMHO yang dapat diterima.
quazgar
49

Telah ada.

Salah satu contohnya adalah cryptosystem McEliece yang didasarkan pada kekerasan dari decoding kode linier.

Contoh kedua adalah NTRUEncrypt yang didasarkan pada masalah vektor terpendek yang saya yakini dikenal sebagai NP-Hard.

Lainnya adalah cryptosystem knapsack Merkle-Hellman yang telah rusak.

Catatan: Saya tidak tahu apakah dua yang pertama rusak / seberapa baik mereka. Yang saya tahu adalah bahwa mereka ada, dan saya mendapatkannya dari melakukan pencarian web.

Aryabhata
sumber
6
Untuk keperluan cryptanalysis, McEliece mungkin tidak boleh dianggap hanya sebagai satu crytosystem; untuk setiap kelas kode linier yang dapat didekode secara efisien yang Anda pasang, Anda harus membuat strategi yang berbeda untuk memecahkannya. Sudah rusak untuk beberapa kelas kode, tetapi (seperti yang dikatakan artikel Wikipedia) bukan untuk kode Goppa, yang merupakan saran asli McEliece.
Peter Shor
Dari daftar itu saya akan mengatakan NTRU terlihat paling menjanjikan, itu belum diuji secara ekstensif cara RSA diuji berdasarkan apa yang telah saya baca sejauh ini.
Ken Li
Cryptosystem Merkle-Hellman bukan contoh yang tepat. Vektor knapsack Merkle-Hellman hanya merupakan subset dari semua vektor knapsack sehingga masalah knapsack Merkle-Hellman mungkin bukan NP yang sulit. Saya tidak berpikir itu NP-hard, setidaknya saya tidak mengetahui ada kertas yang menunjukkan ini.
miracle173
25

Saya dapat memikirkan empat rintangan utama yang tidak sepenuhnya independen:

  • Kekerasan NP hanya memberi Anda informasi tentang kompleksitas dalam batas . Untuk banyak masalah NP-complete, ada algoritma yang memecahkan semua contoh yang menarik (dalam skenario tertentu) cukup cepat. Dengan kata lain, untuk setiap ukuran masalah yang diperbaiki (mis. "Kunci" yang diberikan), masalahnya tidak selalu sulit hanya karena NP-hard.
  • Kekerasan NP hanya mempertimbangkan waktu kasus terburuk. Banyak, bahkan sebagian besar dari semua contoh mungkin mudah diselesaikan dengan algoritma yang ada. Bahkan jika kita tahu bagaimana mengkarakterisasi contoh sulit (afaik, kita tidak), kita masih harus menemukannya.
  • 2n(n1)nn
  • Anda perlu semacam keterbalikan. Misalnya, bilangan bulat apa pun secara unik dijelaskan oleh faktorisasi utamanya. Gambar kami ingin menggunakan TSP sebagai metode enkripsi; diberikan semua tur terpendek, bisakah Anda (kembali) membuat grafik dari mana mereka berasal secara unik?

Perhatikan bahwa saya tidak memiliki keahlian dalam kriptografi; ini hanyalah respons algoritmik. keberatan kompleksitas-teoretis.

Raphael
sumber
Ringkasan yang luar biasa. Tetapi perhatikan bahwa kekerasan BQP memiliki peringatan yang sama dengan dua poin pertama Anda.
Mitch
14

Kriptografi kunci publik seperti yang kita kenal sekarang ini dibangun di atas permutasi pintu trap satu arah , dan pintu trap sangat penting.

Agar protokol aman untuk umum, Anda memerlukan kunci yang tersedia untuk siapa saja, dan cara untuk mengenkripsi pesan menggunakan kunci ini. Jelas, setelah dienkripsi, akan sulit untuk memulihkan pesan asli hanya mengetahui sandi dan kunci publik: sandi hanya dapat diuraikan dengan beberapa informasi tambahan, yaitu kunci pribadi Anda.

Dengan pemikiran itu, mudah untuk membangun sistem crypto primitif berdasarkan permutasi pintu jebol satu arah.

  1. Alice memberikan permutasi satu arah kepada publik, dan menjaga pintu jebakan untuk dirinya sendiri.
  2. Bob memasukkan inputnya ke permutasi, dan mengirimkan output ke Alice.
  3. Alice menggunakan pintu jebakan untuk membalikkan permutasi dengan output Bob.

PNP

PNPNPINPNPNPINP

NPNPNP

Heinz Fiedler
sumber
RSA, ya itu fungsi pintu jebakan. Saya tidak yakin bahwa dlog adalah TDF (satu arah)
111
Jika masalah NP-menengah adalah NP-keras, mereka akan NP-lengkap, sebuah kontradiksi.
Myria
0

Sekedar memberi argumen heuristik, berdasarkan pengalaman praktis.

Hampir semua contoh, dari hampir semua masalah NP-complete, mudah diselesaikan. Ada masalah di mana ini tidak benar, tetapi mereka sulit ditemukan, dan sulit untuk menjadi positif Anda memiliki kelas seperti itu.

Ini telah muncul dalam praktik beberapa kali ketika orang mencoba untuk menulis generator masalah acak untuk beberapa kelas NP-lengkap terkenal, seperti Constraint Programming, SAT atau Travelling Salesman. Pada beberapa tanggal kemudian seseorang menemukan metode untuk menyelesaikan hampir semua contoh yang dihasilkan generator acak sepele. Tentu saja, jika itu terjadi pada sistem enkripsi kita akan berada dalam masalah serius!

Chris Jefferson
sumber
-1

Cryptosystems Merkle-Hellman didasarkan pada masalah ransel biner (jumlah subset).

pengguna13675
sumber
Bisakah Anda memberikan referensi?
Raphael
" en.wikipedia.org/wiki/Merkle-Hellman_knapsack_cryptosystem " dan juga monografinya: Postquantum Cryptography (Springer).
user13675