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.