Generowanie wykresów za pomocą trywialnych automorfizmów

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 .$G_1$$G_2$$G_1$$G_2$

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:$G_1$

1. Na wejściu wygenerować n wykres -Vertex G 1 , tak że ma tylko trywialne Automorfizmy.$1^n$$n$$G_1$
2. $\pi$$[n]=\{1,2,\ldots,n\}$$G_1$$G_2$
3. $\langle G_1,G_2,\pi \rangle$

$G_1$$\langle G_1,G_2 \rangle$

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

$G_1$$n$$n \to \infty$$G_1$

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 .