Dowód z wiedzą zerową – procedura kryptograficzna, w której jedna ze stron potrafi udowodnić drugiej, że dysponuje pewną informacją, bez jej ujawniania.
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 i 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 i V żąda dowodu P wysyła graf V wysyła liczbę 1 lub 2 P wysyła izomorfizm między a lub zależnie od wybranej przez V liczby Jeśli P zna izomorfizm między i generuje 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 i to nie potrafi znaleźć takiego żeby mógł zbudować izomorfizm zarówno do jak i – gdyby znał taki mógłby zbudować izomorfizm między a
Znajomość izomorfizmu między a lub jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między a
Przypisy
Bibliografia Radosław Juszczuk, Dowody o wiedzy zerowej
Linki zewnętrzne Wojciech Guzicki, Jak Ali-Baba może nas przekonać, że umie otworzyć Sezam ?, rocznik „Matematyka Poglądowa”, Ośrodek Kultury Matematycznej – Uniwersytet w Siedlcach (OKM UwS), 2019 [dostęp 2026-02-06].
Kategoria:Uwierzytelnienie Kategoria:Anonimowość