Dowód z wiedzą zerową

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

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

• Jeśli dowodzący dysponuje daną informacją, może zawsze przekonać o tym weryfikującego
• Jeśli dowodzący nie dysponuje daną informacją, może oszukać weryfikującego, że nią dysponuje, 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 ${\displaystyle G_{1}}$ i ${\displaystyle 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 ${\displaystyle G_{1}}$ i ${\displaystyle G_{2}}$
• V żąda dowodu
• P wysyła graf ${\displaystyle H}$
• V wysyła liczbę 1 lub 2
• P wysyła izomorfizm między ${\displaystyle H}$ a ${\displaystyle G_{1}}$ lub ${\displaystyle G_{2},}$ zależnie od wybranej przez V liczby
  • Jeśli P zna izomorfizm między ${\displaystyle G_{1}}$ i ${\displaystyle G_{2},}$ generuje ${\displaystyle 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 ${\displaystyle G_{1}}$ i ${\displaystyle G_{2},}$ to nie potrafi znaleźć takiego ${\displaystyle H,}$ żeby mógł zbudować izomorfizm zarówno do ${\displaystyle G_{1},}$ jak i ${\displaystyle G_{2}}$ – gdyby znał taki ${\displaystyle H}$ mógłby zbudować izomorfizm między ${\displaystyle G_{1}}$ a ${\displaystyle G_{2}.}$

Znajomość izomorfizmu między ${\displaystyle H}$ a ${\displaystyle G_{1}}$ lub ${\displaystyle G_{2},}$ jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między ${\displaystyle G_{1}}$ a ${\displaystyle G_{2}.}$

Przypisy

1. Bruce Schneier: Kryptografia dla praktyków. Protokoły, algorytmy i programy źródłowe w języku C. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 149–161. ISBN 83-204-2678-2.

Bibliografia

• Radosław Juszczuk, Dowody o wiedzy zerowej