Menghasilkan Grafik dengan Automorfisme Trivial

14

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 .G1G2G1G2

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

  1. Pada input , buat grafik n -vertex G 1 , sehingga hanya memiliki automorfisme sepele.1nnG1
  2. Pilih permutasi acak lebih dari [ n ] = { 1 , 2 , ... , n } , dan terapkan pada G 1 untuk mendapatkan G 2 .π[n]={1,2,...,n}G1G2
  3. Output .G1,G2,π

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 .)G1G1,G2

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

MS Dousti
sumber
1
Hanya beberapa terminologi alternatif: Grafik yang automorfisme satu-satunya adalah identitas sering disebut grafik kaku . Mungkin bisa membantu dalam mencari ...
Joseph O'Rourke
@ Joseph: Terima kasih. Itu pasti akan membantu!
MS Dousti

Jawaban:

9

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.G1nnG1

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 .

Joshua Grochow
sumber
1
Terima kasih Joshua. Saya mempunyai satu pertanyaan. QUOTE: "isomorfisme graf biasa kasus terburuk setara dengan isomorfisme grafik terburuk (umum)." Apakah itu berarti bahwa, mengingat nubuat yang menentukan isomorfisme grafik biasa, orang dapat memutuskan graf isomorfisme kasus terburuk (umum) dalam waktu polinomial? Bisakah Anda memberi saya beberapa petunjuk?
MS Dousti
Itulah tepatnya artinya. Pembangunannya tidak terlalu sulit. Berikut ini adalah referensi; Saya tidak tahu apakah ini yang pertama: dx.doi.org/10.1016/0022-0000(79)90043-6 juga tersedia di cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
Joshua Grochow