|
|
Dowód z wiedzą zerową
Dowód z wiedzą zerową to procedura kryptograficzna, w której udowadniamy, że posiadamy pewną informację, nie ujawniając tej informacji.
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 przydają się np. przy uwierzytelnianiu.
[edytuj] Izomorfizm grafów
Nie znamy żadnego algorytmu wielomianowego, który dla danych dwóch grafów izomorficznych G1 i G2 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 G1 i G2
- V żąda dowodu
- P wysyła graf H
- V wysyła liczbę 1 lub 2
- P wysyła izomorfizm między H a G1 lub G2, zależnie od wybranej przez V liczby
- Jeśli P zna izomorfizm między G1 i G2, 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 G1 i G2, to nie potrafi znaleźć takiego H, żeby mógł zbudować izomorfizm zarówno do G1 jak i G2 – gdyby znał taki H mógłby zbudować izomorfizm między G1 a G2.
Znajomość izomorfizmu między H a G1 lub G2, jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między G1 a G2.
|
