Generowanie wykresów za pomocą trywialnych automorfizmów

14

Sprawdzam jakiś model kryptograficzny. Aby pokazać jego nieadekwatność, opracowałem wymyślony protokół oparty na izomorfizmie grafowym.

Zakładanie istnienia algorytmów BPP zdolnych do generowania „trudnych wystąpień problemu z izomorfizmem grafów” jest „powszechne” (a jednak kontrowersyjne!). (Wraz ze świadkiem izomorfizmu).

W moim skonstruowanym protokole założę istnienie takich algorytmów BPP, które spełniają jeden dodatkowy wymóg:

  • Niech wygenerowane wykresy będą i G 2 . Jest tylko jeden świadek (permutacja), który odwzorowuje G 1 na G 2 .G1G2G1G2

Oznacza to, że ma jedynie trywialne automorfizmy . Innymi słowy, zakładam istnienie jakiegoś algorytmu BPP, który działa w następujący sposób:G1

  1. Na wejściu wygenerować n wykres -Vertex G 1 , tak że ma tylko trywialne Automorfizmy.1nnG1
  2. π[n]={1,2,,n}G1G2
  3. G1,G2,π

G1G1,G2

Czy moje założenie jest uzasadnione? Czy ktoś mógłby wskazać mi jakieś odniesienia?

MS Dousti
źródło
1
Po prostu alternatywna terminologia: wykres, którego jedynym automorfizmem jest tożsamość, jest często nazywany grafem sztywnym . Może pomóc w poszukiwaniu ...
Joseph O'Rourke
@Joseph: Dzięki. Z pewnością pomoże!
MS Dousti,

Odpowiedzi:

9

G1nnG1

Ale drugie naiwne podejście ma szansę na zadziałanie: wygenerowanie losowego regularnego wykresu (o niestałym stopniu, ponieważ izomorfizm wykresu o stałym stopniu występuje w P). Nie ma też nietrywialnych automorfizmów o wysokim prawdopodobieństwie [KSV], ale wynik Babai-Kucera nie ma zastosowania (jak wskazano w artykule). Udowodnienie, że jest to niewrażliwy generator, oczywiście wymaga pewnych założeń, ale można sobie wyobrazić bezwarunkowe udowodnienie, że zwykły izomorfizm zwykłego wykresu jest tak trudny jak izomorfizm grafowy najgorszego przypadku, chociaż nie wiem, jak prawdopodobne jest to. (Należy zauważyć, że izomorfizm zwykły grafu najgorszego przypadku jest równoważny izomorfizmowi grafu najgorszego (ogólnego)).

[BK]. Laszlo Babai, Ludik Kucera, Kanoniczne oznaczanie wykresów w średnim czasie liniowym . FOCS 1979, s. 39–46.

[KSV] Jeong Han Kim, Benny Sudakov i Van H. Vu. O asymetrii losowych wykresów regularnych i losowych . Struktury losowe i algorytmy, 21 (3-4): 216–224, 2002. Dostępne również tutaj .

Joshua Grochow
źródło
1
Dzięki Joshua. Mam jedno pytanie. QUOTE: „Zwykły izomorfizm grafów najgorszego przypadku jest równoważny z izomorfizmem grafów najgorszego (ogólnego)”. Czy to oznacza, że ​​biorąc pod uwagę wyrocznię, która decyduje o regularnym graficznym izomorfizmie, można decydować o najgorszym (ogólnym) izomorfizmie grafowym w czasie wielomianowym? Czy możesz podać mi jakieś wskazówki?
MS Dousti
Dokładnie o to chodzi. Budowa nie jest zbyt trudna. Oto odniesienie; Nie wiem, czy jest to pierwsza: dx.doi.org/10.1016/0022-0000(79)90043-6 również dostępny na cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
Joshua Grochów