Kriptografi tanpa asumsi - mencari gambaran umum

Misalkan dan algoritma linear-waktu yang cepat untuk SAT muncul besok. Tiba-tiba RSA tidak aman, sebagian besar sistem komunikasi modern kita rusak, dan kita perlu mempertimbangkan kembali cara menjaga rahasia satu sama lain.$P = NP$

Pertanyaan: Apakah ada referensi tunggal yang baik (atau daftar pendek) untuk mendapatkan gambaran besar tentang apa yang mungkin dilakukan di crypto (dan dalam bidang sekutu "keamanan") tanpa asumsi yang tidak dapat dipraktikkan? Ini bisa menyelamatkan peradaban suatu hari, dan juga menyenangkan untuk membaca sementara.

Diskusi: Sebagian besar tugas kriptografi yang sekarang kita pelajari (OWFs, PRGs, PKE) terbukti mustahil di dunia (dunia yang dijuluki "Algorithmica" dalam esai berpengaruh oleh Impagliazzo), tetapi beberapa hal tetap mungkin: komunikasi dengan a satu kali pad ; pembagian rahasia yang didistribusikan ; pengambilan info pribadi ; dan beberapa hal bagus lainnya. (Jenis mekanisme fisik tertentu seperti kotak yang dikunci , perangkat yang menerapkan transfer yang tidak sadar , dan keadaan kuantum juga bisa berguna. Tentu saja selalu ada semacam asumsi fisik tentang siapa yang dapat melihat informasi apa.)$P = NP$

Seseorang dapat membedakan antara keamanan informasi-teoretis (yang bekerja melawan musuh yang tidak terikat secara komputasi) dan keamanan "tanpa syarat" (yang mungkin memerlukan musuh yang terikat, tetapi masih menunjukkan keamanan tanpa asumsi yang tidak terbukti). Saya paling tertarik pada kasus info-theoretic.

Sebagai permulaan, berikut ini adalah satu bibliografi keamanan informasi-teoretis (yang, untuk tujuan saya, panjang dan tidak terkendali).

Frasa kunci yang mungkin Anda cari adalah "informasi-teoritik kriptografi" dan "kriptografi kuantum". Mencari literatur tentang topik-topik ini akan menghasilkan banyak pekerjaan yang Anda cari. Beberapa contoh sorotan di bawah ini:

• Untuk kerahasiaan: papan sekali pakai, saluran penyadapan Wyner, berbagi rahasia, pertukaran kunci kuantum, dll.

• Untuk integritas dan otentikasi: fungsi hash universal.

• Untuk anonimitas: komunikasi anonim (mis., Jaring DC, skema berbasis bawang merah, jaringan p2p berdasarkan percampuran acak jalan cepat), protokol pembatas jarak.

• Untuk keamanan yang didasarkan pada asumsi fisik: PUF (fungsi yang tidak dapat diklasifikasi secara fisik), kode integritas (Capkun et al.), Kriptografi kuantum, keamanan menggunakan TPM atau perangkat keras yang mengutak-atik.

Ada banyak makalah tentang topik-topik itu; terlalu banyak untuk merangkum semua hasil dalam literatur.

Ini adalah pertanyaan yang cukup rumit, karena kami benar-benar tidak memiliki tinjauan yang baik tentang area tersebut. Sebagian ini disebabkan oleh fakta-teori informasi dan komunitas kripto telah bekerja pada topik yang sama tanpa benar-benar cukup berinteraksi satu sama lain. Banyak poin bagus telah diberikan di atas. Saya hanya ingin menambahkan beberapa pengamatan tambahan:

• Kami telah memiliki sejumlah besar pekerjaan yang berurusan dengan masalah perjanjian kunci-rahasia (dan komunikasi aman) dengan pengaturan yang diberikan. Di sini, pengaturan berarti misalnya bahwa pihak-pihak dalam sistem (katakanlah Alice, Bob, dan Hawa musuh) berbagi beberapa informasi berkorelasi yang berasal dari distribusi probabilitas tripartit. Pengaturan alternatif dapat terdiri dari saluran bising (mis., Alice dapat mengirim informasi ke Bob dan Hawa melalui saluran bising). Selain itu, Alice dan Bob terhubung melalui saluran komunikasi (yang mungkin atau mungkin tidak diautentikasi). Lini kerja ini dimulai dengan Aaron Wyner di tahun 70-an, yang memperkenalkan model saluran Wiretap, dan selanjutnya dibersihkan oleh Maurer dan yang lainnya di tahun 90-an. Juga, banyak teknik di bidang ini (amplifikasi privasi, rekonsiliasi informasi) akhirnya digunakan dalam pengaturan Quantum Key-Distribution (QKD). Sejumlah pekerjaan sedang dilakukan di sini bahkan sampai saat ini, misalnya di bidang terkait seperti ekstraktor yang tidak dapat ditempa, dll. Model penyimpanan terikat juga merupakan pengaturan yang berbeda dari yang di atas, tetapi menggunakan teknik yang serupa dan memiliki kesamaan tujuan.

• Di luar sekadar berbagi rahasia, Anda akan menemukan banyak karya tentang komputasi multi-partai yang aman secara informasi (MPC). Secara khusus, garis pekerjaan yang diprakarsai oleh protokol BGW sepenuhnya informasi teoritis.

• Juga, saya tidak yakin sejauh mana ruang lingkup pertanyaan: Jika misalnya P = NP memang berlaku, tetapi kita entah bagaimana dapat membenarkan keberadaan oracle acak di langit, maka kriptografi simetris masih dimungkinkan. Kadang-kadang, model semacam itu memang digunakan untuk membuktikan keamanan konstruksi kriptografi tertentu (seperti fungsi hash atau blok cipher), dan tekniknya sepenuhnya informasi-teoretis.

• Teknik informasi-teori dalam kriptografi juga sering muncul sebagai alat perantara dalam kompleksitas-teori hasil, tapi saya pikir ini di luar ruang lingkup pertanyaan. (Lihat karya Maurer pada sistem acak dan pada amplifikasi indistinguishability sebagai contoh dari jenis pekerjaan ini.)

Beberapa kelompok penelitian di Eropa telah mengejar jalur penelitian ini; lebih khusus, karena minat saya pada teori informasi saya telah berlari ke dalam karya Ueli Maurer dan sekolahnya, yang keduanya signifikan dari sudut pandang teori informasi murni (yang saya lebih akrab dengan) dan juga menawarkan beberapa pendekatan praktis untuk informasi keamanan teoretis.

Terkait dengan pekerjaan di atas, beberapa tempat yang mungkin ingin Anda pertimbangkan adalah tesis PhD Christian Cachin dan juga Renato Renner (lebih banyak kuantum).

Tentu saja, ada pendekatan yang berbeda dengan kata kunci termasuk BB84, Preskill-Shor, Artur Ekert, dll.

Hal di atas tentu saja hanya mencerminkan pengalaman saya yang terbatas, dan tentu saja ada lebih banyak pendekatan dan garis pekerjaan yang menarik.