“Abrakadabra, nie wiesz nic!” - dowody z wiedzą zerową w życiu codziennym
17.12.2010 - Agata Murawska
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.
Wyobraź sobie zatem, że znasz izomorfizm między dwoma zadanymi grafami, i . 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?
Możesz wygenerować graf , 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 a , czy między a . Powie nam to, odpowiadając odpowiednio lub . Jak stworzyć odpowiedni izomorfizm? Jeśli powstał z , jak w naszym przykładzie, to gdy On prosi o izomorfizm między a , możemy mu go podać od razu - wystarczy, że pamiętamy, jak powstał graf . Gdy natomiast chce poznać izomorfizm między a grafem drugim, przyjdzie nam składać izomorfizmy. Brzmi być może skomplikowanie, ale jest bardzo proste - jeśli wiemy, że wierzchołkowi w grafie odpowiada w , a w odpowiada w , to złożenie izomorfizmów mówi po prostu, że w to w . I już! Proste, prawda? A jednak działa - zauważ, że wiedza o izomorfizmie między i którymś z dwóch grafów nie zbliża Jego ani o krok do znalezienia Twojego cennego izomorfizmu między a . 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! Zadania sprawdzające
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. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com