“Abrakadabra, nie wiesz nic!” - dowody z wiedzą zerową w życiu codziennym

17.12.2010 - Agata Murawska
Trudność

A może coś o grafach?

Pozostawmy już za sobą bajkę o kupcu z Bagdadu i jego krewnym, archeologu. W zamian zajmiemy się ciekawszym problemem. Jak być może wiesz, problem znajdowania izomorfizmu grafów (czyli przyporządkowania wierzchołkom jednego grafu wierzchołków drugiego w taki sposób, żeby krawędzie w obu grafach łączyły te same wierzchołki) to zadanie trudne - nie jest znany szybki algorytm rozwiązujący ten problem. Jak bardzo trudne? Przekonasz się o tym na przykład przy okazji czytania artykułu Damiana Rusaka Czy dostrzegasz podobieństwo. Znajdziesz w nim także więcej informacji o samym problemie.

Grafy











Wyobraź sobie zatem, że znasz izomorfizm między dwoma zadanymi grafami, $ G_1 $ i $ G_2 $. Chcesz przekonać kogoś, że znalazłeś ten izomorfizm, ale tak, żeby ta osoba nie poznała go. Osobę, którą chcesz przekonać nazwijmy po prostu “On”. Jak przeprowadzić taki dowód?









Grafy 2






Możesz wygenerować graf $ H $, który powstanie przez zamianę etykiet wierzchołków w którymś z grafów, a następnie pokazać ten graf Jemu.






On wybierze sobie wtedy, czy chce poznać izomorfizm między $ H $ a $ G_1 $, czy między $ H $ a $ G_2 $. Powie nam to, odpowiadając odpowiednio $ 1 $ lub $ 2 $.
Jak stworzyć odpowiedni izomorfizm? Jeśli $ H $ powstał z $ G_1 $, jak w naszym przykładzie, to gdy On prosi o izomorfizm między $ H $ a $ G_1 $, możemy mu go podać od razu - wystarczy, że pamiętamy, jak powstał graf $ H $.
Grafy 3
Gdy natomiast chce poznać izomorfizm między $ H $ a grafem drugim, przyjdzie nam składać izomorfizmy. Brzmi być może skomplikowanie, ale jest bardzo proste - jeśli wiemy, że wierzchołkowi $ x $ w grafie $ H $ odpowiada $ v $ w $ G_1 $, a $ v $ w $ G_1 $ odpowiada $ w $ w $ G_2 $, to złożenie izomorfizmów mówi po prostu, że $ x $ w $ H $ to $ w $ w $ G_2 $.

I już! Proste, prawda? A jednak działa - zauważ, że wiedza o izomorfizmie między $ H $ i którymś z dwóch grafów nie zbliża Jego ani o krok do znalezienia Twojego cennego izomorfizmu między $ G_1 $ a $ G_2 $.

Koniec bajki!

Można zadać sobie pytanie - co to wszystko ma wspólnego z kryptografią? Otóż, wbrew pozorom, całkiem dużo. Umiemy teraz pokazać, że znamy jakąś informację, ale bez ujawniania jej!
To ważne na przykład w procesie uwierzytelniania, kiedy przekonujemy kogoś, że znamy swoje własne hasło, ale nie chcemy go przesłać przez sieć.
Innym, dużo ważniejszym przykładem jest upewnianie się (“dowodzenie”), że dane, które są przesyłane w komunikacji sieciowej, są zgodne z jakimś ustalonym protokołem. Ale to zupełnie inna historia, do której może kiedyś wrócimy...

Zadania sprawdzające

  1. Jak oszukiwać sprytniej?
    Reporter i aktor grający Micka Aliego musieli powtarzać sceny z rzutem monetą, kiedy nie udawało im się zgrać wyniku rzutu z korytarzem, do którego wchodził aktor.
    Jak w prosty sposób zmodyfikować procedurę weryfikacji tak, żeby uniknąć tych powtórzeń?
  2. Tajne miejsce spotkań
    Jako członek Tajnego Stowarzyszenia Kryptograficznego masz dostęp do Tajnej Kwatery Głównej, w której odbywają się Tajne Spotkania. W jaki sposób przekonasz swojego kolegę, że znasz położenie Kwatery Głównej, jeśli nie wolno Ci ujawniać dojścia do tego miejsca?

Artykuł jest inspirowany pracą “How to Explain Zero-Knowledge Protocols to Your Children” autorstwa Jean-Jacquesa Quisquatera, Louisa C. Guilloua i Thomasa A. Bersona.

Obrazki Ali-Baby i Manuskryptu w artykule pochodzą z wikipedii.
Źródła oraz informacja o licencji, na jakiej zostały opublikowane:

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com