Dowód z wiedzą zerową

Dowód z wiedzą zerową – procedura kryptograficzna, w której jedna ze stron potrafi udowodnić drugiej, że posiada pewną informację, bez jej ujawniania.

Właściwości takiej procedury są następujące:

• Jeśli dowodzący posiada daną informację, może zawsze przekonać o tym weryfikującego
• Jeśli dowodzący nie posiada danej informacji, może oszukać weryfikującego, że ją posiada, z prawdopodobieństwem dowolnie bliskim zera (chociaż nie równym 0)

Dowody takie znajdują zastosowanie w procesach uwierzytelniania, zwłaszcza gdy równocześnie konieczne jest zapewnienie określonego poziomu anonimowości.

Izomorfizm grafów

Nie znamy żadnego algorytmu wielomianowego, który dla danych dwóch grafów izomorficznych $G_1$ i $G_2$ znajduje izomorfizm (czyli przyporządkowania między wierzchołkami jednego a drugiego grafu, tak żeby wszystkie krawędzie łączyły takie same wierzchołki) między nimi. Można to wykorzystać w następujący sposób:

• P twierdzi, że zna izomorfizm między $G_1$ i $G_2$
• V żąda dowodu
• P wysyła graf $H$
• V wysyła liczbę 1 lub 2
• P wysyła izomorfizm między $H$ a $G_1$ lub $G_2$, zależnie od wybranej przez V liczby
  • Jeśli P zna izomorfizm między $G_1$ i $G_2$, generuje $H$ przez dowolną zamianę etykietek wierzchołków któregoś z grafów. Następnie z łatwością może wygenerować izomorfizm do jednego lub drugiego grafu.
  • Jeśli P nie zna izomorfizmu między $G_1$ i $G_2$, to nie potrafi znaleźć takiego $H$, żeby mógł zbudować izomorfizm zarówno do $G_1$ jak i $G_2$ – gdyby znał taki $H$ mógłby zbudować izomorfizm między $G_1$ a $G_2$.

Znajomość izomorfizmu między $H$ a $G_1$ lub $G_2$, jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między $G_1$ a $G_2$.

Źródła

Radosław Juszczuk, Dowody o wiedzy zerowej