Apakah batas bawah asimptotik relevan dengan kriptografi?

Batas bawah asimptotik seperti kekerasan eksponensial umumnya dianggap menyiratkan bahwa suatu masalah "secara inheren sulit". Enkripsi yang "secara inheren sulit" untuk dipecah dianggap aman.

Namun, batas bawah asimptotik tidak mengesampingkan kemungkinan bahwa kelas instance masalah yang besar namun terbatas itu mudah (mis. Semua instance dengan ukuran kurang dari ). $10^{1000}$

Apakah ada alasan untuk berpikir bahwa kriptografi yang didasarkan pada batas bawah asimptotik akan memberikan tingkat keamanan tertentu? Apakah pakar keamanan mempertimbangkan kemungkinan seperti itu, atau mereka hanya diabaikan?

Contohnya adalah penggunaan fungsi pintu jebakan berdasarkan dekomposisi sejumlah besar menjadi faktor utama mereka. Ini pada satu titik dianggap sulit secara inheren (saya pikir eksponensial adalah dugaan) tetapi sekarang banyak yang percaya bahwa mungkin ada algoritma polinomial (seperti ada untuk pengujian primality). Tidak seorang pun tampaknya sangat peduli tentang kurangnya batas bawah eksponensial.

Saya percaya bahwa fungsi pintu jebakan lainnya telah diusulkan yang dianggap sebagai NP-hard (lihat pertanyaan terkait ), dan beberapa bahkan mungkin memiliki batas bawah yang terbukti. Pertanyaan saya lebih mendasar: apakah masalah apakah batas bawah asimptotik itu? Jika tidak, apakah keamanan praktis dari kode kriptografi sama sekali terkait dengan hasil kompleksitas asimptotik?

complexity-theory cryptography asymptotics Micah Beck
sumber

Selamat datang! Tidak cukup duplikat, tapi sangat terkait: pertanyaan ini . Untuk meningkatkan pertanyaan, berikan contoh konkret di mana Anda pikir masalah ini diabaikan. Anda tidak ingin melawan pabrik angin!

Raphael

Jawaban:

Saya akan mencoba memberikan jawaban parsial, karena saya tidak sepenuhnya menyadari bagaimana masalah ini dipertimbangkan oleh seluruh komunitas crypto (mungkin memposting ulang di crypto.SE ?).

Saya akan mengatakan ada dua "jenis" kriptografi: Teoritis dan Praktis . Saya tidak akan mencoba membedakan mereka (setiap cryptographer praktis juga sedikit teoritikus ..) tetapi saya akan mengatakan bahwa untuk kriptografi teoretis - masalah ini tidak terlalu penting. Untuk parameter keamanan apa pun, akan ada ukuran instance yang akan memberikan tingkat keamanan itu, dan biasanya itulah yang kita pedulikan.

$2^{1024}$

$G$ $O(|G|)$ $\text{P}=\text{NP}$ $O(\log |G|)$ $G$

Ran G.
sumber

Jawaban ini tidak terlalu memuaskan bagi saya, mungkin karena saya tidak cukup ahli untuk mencari tahu bagaimana menjawab pertanyaan saya. Memang, saya belum mempelajari teori kompleksitas selama 25 tahun, tetapi saya mengerti banyak konsep yang mendasarinya. Setelah mencari beberapa referensi terkait, tampaknya penokohan kompleksitas yang digunakan adalah asimptotik , jadi saya masih tidak tahu bagaimana mereka dapat memberikan jaminan yang dapat digunakan atas kelas instance yang terbatas .

Micah Beck