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 .
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:
- Na wejściu wygenerować n wykres -Vertex G 1 , tak że ma tylko trywialne Automorfizmy.
Czy moje założenie jest uzasadnione? Czy ktoś mógłby wskazać mi jakieś odniesienia?
graph-theory
cr.crypto-security
automorphism
graph-isomorphism
randomized-algorithms
MS Dousti
źródło
źródło
Odpowiedzi:
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 .
źródło