Menghasilkan Grafik dengan Automorfisme Trivial

Saya merevisi beberapa model kriptografi. Untuk menunjukkan kekurangannya, saya telah menyusun protokol yang dibuat berdasarkan isomorfisme grafik.

Adalah "lumrah" (namun kontroversial!) Untuk mengasumsikan keberadaan algoritma BPP yang mampu menghasilkan "contoh sulit dari masalah Grafik Isomorfisme." (Bersamaan dengan saksi isomorfisme.)

Dalam protokol yang saya buat, saya akan menganggap keberadaan algoritma BPP tersebut, yang memenuhi satu persyaratan tambahan:

• Biarkan grafik yang dihasilkan menjadi dan G 2 . Hanya ada satu saksi (permutasi) yang memetakan G 1 hingga G 2 .$G_1$$G_2$$G_1$$G_2$

Ini berarti bahwa hanya memiliki automorphisms sepele . Dengan kata lain, saya mengasumsikan adanya beberapa algoritma BPP, yang berfungsi sebagai berikut:$G_1$

1. Pada input , buat grafik n -vertex G 1 , sehingga hanya memiliki automorfisme sepele.$1^n$$n$$G_1$
2. Pilih permutasi acak lebih dari [ n ] = { 1 , 2 , ... , n } , dan terapkan pada G 1 untuk mendapatkan G 2 .$\pi$$[n]=\{1,2,\ldots,n\}$$G_1$$G_2$
3. Output .$\langle G_1,G_2,\pi \rangle$

Aku akan menganggap bahwa, pada Langkah 1, dapat dihasilkan sesuai kebutuhan, dan ⟨ G 1 , G 2 ⟩ adalah keras contoh dari masalah Grafik isomorfisma. (Tolong tafsirkan kata "keras" secara alami; definisi formal diberikan oleh Abadi et al. Lihat juga makalah oleh Impaliazzo & Levin .)$G_1$$\langle G_1,G_2 \rangle$

Apakah asumsi saya masuk akal? Adakah yang bisa mengarahkan saya ke beberapa referensi?

Setidaknya pendekatan naif pertama yang mungkin dipikirkan orang tidak berhasil. Pendekatan yang ada dalam pikiran saya adalah dengan hanya menghasilkan murni secara acak. Karena hampir semua grafik tidak memiliki simetri (yaitu, proporsi grafik pada n simpul tanpa automorfisme nontrivial mendekati 1 sebagai n → ∞ ), G 1 tidak akan memiliki automorfisma nontrivial dengan probabilitas tinggi, yang kami inginkan. Namun, versi rata-rata kasus isomorfisma grafik, di mana grafik dipilih secara acak, dapat diselesaikan dalam waktu linier [BK], jadi ini tidak menghasilkan distribusi contoh yang sulit.$G_1$$n$$n \to \infty$$G_1$

Tetapi pendekatan naif kedua memiliki peluang untuk bekerja: hasilkan grafik reguler acak (tingkat tidak konstan, karena grafik derajat konstan isomorfisma ada di P). Ini juga tidak memiliki automorfisme nontrivial dengan probabilitas tinggi [KSV], tetapi hasil Babai-Kucera tidak berlaku (sebagaimana ditunjukkan dalam makalah). Membuktikan bahwa ini adalah generator yang kebal jelas memerlukan beberapa asumsi, tetapi orang dapat membayangkan membuktikan tanpa syarat bahwa isomorfisme grafik biasa kasus-rata sama sulitnya dengan isomorfisme grafik kasus terburuk, meskipun saya tidak tahu seberapa besar kemungkinannya. (Perhatikan bahwa isomorfisma grafik kasus terburuk terburuk sama dengan isomorfisme grafik kasus terburuk.)

[BK]. Laszlo Babai, Ludik Kucera, label label Canon pada grafik dalam waktu rata-rata linier . FOCS 1979, hlm.39-46.

[KSV] Jeong Han Kim, Benny Sudakov, dan Van H. Vu. Pada asimetri grafik reguler acak dan grafik acak . Random Structures & Algorithms, 21 (3-4): 216-224, 2002. Juga tersedia di sini .