Dowód z wiedzą zerową

Z Wikipedii

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

Znajomość izomorfizmu między H a G₁ lub G₂, jeśli nie zna on drugiego izomorfizmu, nie ułatwia mu w żaden sposób zadania znalezienia izomorfizmu między G₁ a G₂.