Seberapa sulit untuk dipecahkan

Dari grafik isomorfisme, kita tahu bahwa dua grafik A dan B adalah isomorfik jika ada matriks permutasi P sehingga $A = P \times B \times P^{-1}$

Jadi, untuk menyelesaikan masalah, jika dua grafik isomorfis, kita perlu menemukan matriks permutasi P. Masalahnya diyakini NP (dan NP lengkap untuk kasus isomorfisma subgraph). Namun, saya menemukan contoh untuk menyelesaikan untuk P yang tampaknya menjanjikan bagi saya dan dapat ditemukan di http://en.wikipedia.org/wiki/Permutation_matrix di bagian: memecahkan untuk P.

Kebingungan yang saya miliki sekarang adalah, apakah itu bekerja untuk matriks yang lebih besar? sangat besar? Apakah saya benar persamaan di atas sulit untuk dipecahkan dan dapat menjadi kandidat untuk sistem kriptografi?

Grafik isomorfisme telah dipelajari dengan baik. Ringkasan singkat: masalah grafik isomorfisme tidak diketahui berada di P (tidak ada algoritma waktu polinomial yang diketahui), tetapi tidak diyakini sebagai NP-lengkap. Ada algoritma heuristik untuk grafik isomorfisme yang bekerja sangat baik pada sebagian besar contoh yang muncul dalam praktik. Baca halaman Wikipedia pada grafik isomorfisma untuk informasi lebih lanjut.

Adapun pendekatan khusus yang Anda usulkan: halaman Wikipedia yang Anda tautkan sudah menjelaskan mengapa metode itu tidak berfungsi secara umum. Metode itu hanya bekerja jika tidak ada nilai eigen berulang dalam matriks yang sesuai dengan grafik adjacency. Oleh karena itu, grafik tersebut akan gagal untuk grafik di mana ada nilai eigen berulang. Grafik seperti itu tidak dapat diabaikan. Akibatnya, metode itu dapat bekerja untuk beberapa grafik tetapi akan gagal (atau bekerja dengan buruk) untuk grafik lain, jadi itu bukan solusi umum.

Grafik isomorfisma bukan kandidat yang baik untuk dasar sistem kriptografi, karena dua alasan. Pertama, algoritma heuristik yang ada sangat baik dalam memecahkan masalah dalam praktek, dan tidak jelas bagaimana menghasilkan contoh hard dari isomorfisme grafik. Kedua, dan lebih serius, agar bermanfaat untuk kriptografi, kita tidak hanya perlu memiliki masalah yang sulit; kita perlu memiliki "pintu jebakan tersembunyi" yang dapat ditanamkan oleh pembuat kunci publik, yang membuat masalah menjadi mudah bagi pembuatnya, tetapi yang sulit dideteksi oleh orang lain. Tidak ada yang tahu bagaimana menanamkan "pintu jebakan tersembunyi" ke dalam masalah grafik isomorfisme.

Sebagaimana dicatat DW dengan benar, grafik isomorfisme tidak diketahui berada dalam P, dan diyakini tidak NP-keras. Selain itu, banyak yang percaya hal itu ada dalam BQP, tetapi ini belum terbukti. Itu menempatkannya dalam kategori yang sama dengan masalah lain di mana cryptosystem biasanya mengandalkan keamanan mereka, seperti anjak piutang utama dan masalah log diskrit, keduanya diketahui berada dalam BQP. (Saya tidak tahu di mana kurva eliptik terbalik dengan masalah perkalian atau apa pun namanya duduk sehubungan dengan BQP, tapi itu tidak akan mengejutkan saya sedikit pun jika semua masalah yang bermanfaat secara kriptografis ini ternyata setara dalam beberapa hal.)

Memang benar bahwa kita tidak tahu masalah grafik isomorfisme yang solusinya "sulit". Namun, mari kita asumsikan sejenak yang kita lakukan. Maka ya, Anda bisa menggunakannya untuk kriptografi.

Sebagai contoh, mari kita lihat sistem kunci bukti-nol yang didasarkan pada isomorfisme grafik.

Kunci pribadi Alice adalah grafik berlabel (label hanya bisa bilangan bulat) yang telah dibuat sedemikian rupa sehingga sulit untuk memeriksa isomorfisma grafik, dan itu berisi siklus Hamilton yang sulit ditemukan. Kunci publiknya hanyalah grafik berlabel, tanpa informasi tentang siklus Hamilton. Perhatikan bahwa memperoleh kunci privat dari kunci publik memerlukan penyelesaian masalah siklus Hamilton, yang merupakan NP-hard dan, kami berasumsi, sulit untuk grafik ini pada khususnya.

Alice ingin meyakinkan Bob bahwa dia tahu siklus Hamilton dalam grafik, tanpa benar-benar memberinya siklus Hamilton. Begini cara dia melakukannya.

Alice mengirimkan grafik tanpa label kepada Bob. Dia menawarkan kepadanya pilihan: Entah dia akan mengungkapkan label, atau dia akan mengungkapkan siklus Hamiltonian dalam grafik. Bob membalik koin (atau membuat keputusan dengan cara lain) untuk memilih yang diinginkannya, dan Alice melakukan salah satu dari dua yang diminta Bob.

Jika Bob meminta label untuk diungkapkan, ia dapat dengan mudah memverifikasi (dalam waktu linier) bahwa grafik berlabel yang berkuasa sama dengan kunci publik Alice, tetapi tidak dapat menemukan siklus Hamilton karena itu akan menjadi NP-hard. Sebaliknya, jika Bob meminta siklus Hamilton, ia dapat dengan mudah memverifikasi (lagi, dalam waktu linier) bahwa grafik yang tidak berlabel yang dihasilkan memang mengandung siklus Hamilton, tetapi ia tidak dapat memverifikasi bahwa itu adalah grafik kunci publik Alice, karena grafik isomorfisma (mungkin) sulit.

Dari sudut pandang Bob, Alice bisa saja mencoba menipu Bob dengan memberikan grafik yang memang memiliki siklus Hamilton yang dikenal tetapi bukan isomorfis untuk kunci publiknya, atau dengan memberinya grafik kunci publik dengan label dihapus tetapi tidak mengetahui Siklus Hamilton. Dia akan bertaruh pada Bob membuat pilihan yang salah. Dengan asumsi bahwa Bob benar-benar membuat pilihannya secara acak, maka trik ini akan memiliki peluang keberhasilan 50%.

Jadi pertukaran di atas diulangi dengan grafik unlabelled yang berbeda. Setelah$n$ Pada putaran protokol, probabilitas Alice berhasil menipu Bob di semua putaran adalah $2^{-n}$, yang konvergen sangat cepat untuk "yakin seperti yang Anda butuhkan".

Ini, tentu saja, jauh dari sistem praktis yang ada. Selain itu, ada beberapa hal jelas yang dapat Anda lakukan untuk membuatnya lebih aman. Misalnya, alih-alih Alice mengirimkan grafik yang tidak diberi label kepada Bob, ia hanya bisa mengirim hash-nya. Ketika Bob membalas, ia kemudian dapat mengirim grafik, dan Bob dapat memeriksa apakah grafiknya cocok.

Meskipun demikian, pada prinsipnya Anda dapat membuat cryptosystem, bahkan jika itu tidak terlalu berguna.