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 G 1 {\displaystyle G_{1}} i G 2 {\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 G 1 {\displaystyle G_{1}} i G 2 {\displaystyle G_{2}}
  • V żąda dowodu
  • P wysyła graf H {\displaystyle H}
  • V wysyła liczbę 1 lub 2
  • P wysyła izomorfizm między H {\displaystyle H} a G 1 {\displaystyle G_{1}} lub G 2 , {\displaystyle G_{2},} zależnie od wybranej przez V liczby
    • Jeśli P zna izomorfizm między G 1 {\displaystyle G_{1}} i G 2 , {\displaystyle G_{2},} generuje H {\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 G 1 {\displaystyle G_{1}} i G 2 , {\displaystyle G_{2},} to nie potrafi znaleźć takiego H , {\displaystyle H,} żeby mógł zbudować izomorfizm zarówno do G 1 , {\displaystyle G_{1},} jak i G 2 {\displaystyle G_{2}} – gdyby znał taki H {\displaystyle H} mógłby zbudować izomorfizm między G 1 {\displaystyle G_{1}} a G 2 . {\displaystyle G_{2}.}

Znajomość izomorfizmu między H {\displaystyle H} a G 1 {\displaystyle G_{1}} lub G 2 , {\displaystyle G_{2},} jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między G 1 {\displaystyle G_{1}} a G 2 . {\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