Wyobraź sobie, że masz przydatną wiedzę — może tajny przepis lub klucz do szyfru. Czy możesz udowodnić przyjacielowi, że posiadasz tę wiedzę, nie ujawniając niczego na jej temat? Informatycy udowodnili ponad 30 lat temu, że można, jeśli użyje się tak zwanego dowodu wiedzy zerowej.
Aby w prosty sposób zrozumieć tę ideę, załóżmy, że chcesz pokazać przyjacielowi, że wiesz, jak przejść przez labirynt, nie ujawniając żadnych szczegółów na temat ścieżki. Możesz po prostu przemierzyć labirynt w określonym czasie, podczas gdy twój przyjaciel miał zakaz oglądania. (Ograniczenie czasowe jest konieczne, ponieważ mając wystarczająco dużo czasu, każdy może w końcu znaleźć wyjście za pomocą prób i błędów.) Twój przyjaciel wiedziałby, że możesz to zrobić, ale nie wiedziałby, jak.
Dowody z wiedzą zerową są pomocne dla kryptografów, którzy pracują z tajnymi informacjami, ale także dla badaczy złożoności obliczeniowej, którzy zajmują się klasyfikacją trudności różnych problemów. „Wiele współczesnej kryptografii opiera się na założeniach złożoności – przy założeniu, że pewne problemy są trudne do rozwiązania, więc zawsze istniały pewne połączenia między tymi dwoma światami” – powiedział. Claude Crepeau, informatyk na Uniwersytecie McGill. „Ale [te] dowody stworzyły cały świat połączeń”.
Dowody z wiedzą zerową należą do kategorii zwanej dowodami interaktywnymi, więc aby dowiedzieć się, jak działają te pierwsze, warto zrozumieć te drugie. Pierwszy opisane w artykule z 1985 roku autorstwa informatyków Shafiego Goldwassera, Silvio Micali i Charles Rackoff, interaktywne dowody działają jak przesłuchanie: w serii wiadomości jedna ze stron (dowodzący) próbuje przekonać drugą (weryfikatora), że dane stwierdzenie jest prawdziwe. Dowód interaktywny musi spełniać dwie właściwości. Po pierwsze, prawdziwe stwierdzenie zawsze w końcu przekona uczciwego weryfikatora. Po drugie, jeśli dane zdanie jest fałszywe, żaden dowodzący — nawet udający, że posiada pewną wiedzę — nie może przekonać weryfikatora, chyba że z prawdopodobieństwem znikomym.
Dowody interaktywne mają charakter probabilistyczny. Dowódca może odpowiedzieć poprawnie na jedno lub dwa pytania po prostu przez szczęście, więc potrzeba wystarczająco dużej liczby wyzwań, z których wszystkie musi wykonać poprawnie, aby weryfikator nabrał pewności, że faktycznie wie, że zdanie jest prawdziwe.
Pomysł interakcji pojawił się, gdy Micali i Goldwasser — ówcześni absolwenci Uniwersytetu Kalifornijskiego w Berkeley — zastanawiali się nad logistyką gry w pokera przez sieć. Jak wszyscy gracze mogą sprawdzić, czy gdy jeden z nich dostanie kartę z wirtualnej talii, wynik jest losowy? Interaktywne dowody mogą poprowadzić drogę. Ale w jaki sposób gracze mogą sprawdzić, czy cały protokół — pełny zestaw zasad — był przestrzegany prawidłowo, bez ujawniania po drodze rąk każdego gracza?
Aby osiągnąć ten cel, Micali i Goldwasser dodali trzecią właściwość do dwóch potrzebnych do interaktywnego dowodu: Dowód nie powinien ujawniać niczego o samej wiedzy, a jedynie prawdziwość twierdzenia. „Istnieje pomysł przejścia przez protokół, na końcu którego wierzysz, że [pokerzyści] nie wiedzą nic więcej niż to, co powinni wiedzieć”, powiedział Goldwasser.
Rozważmy klasyczny przykład. Alicja chce udowodnić Bobowi, że pewien wykres G — unikalny zbiór wierzchołków (kropek) połączonych krawędziami (liniami) — ma „cykl Hamiltona”. Oznacza to, że wykres ma ścieżkę, która odwiedza każdą kropkę dokładnie raz i kończy się tą samą kropką, od której zaczął. Alicja mogłaby to zrobić, po prostu pokazując Bobowi ścieżkę, która to robi, ale oczywiście on też znałby ścieżkę.
Oto jak Alicja może przekonać Boba, że wie, że taka ścieżka istnieje, nie pokazując mu jej. Najpierw rysuje nowy wykres, H, to nie wygląda na G ale jest podobny w zasadniczy sposób: ma taką samą liczbę wierzchołków, połączonych w ten sam sposób. (Jeśli G naprawdę ma cykl hamiltonowski, to podobieństwo oznacza H też.) Następnie, po zakryciu każdej krawędzi w H taśmą maskującą, ona blokuje H w pudełku i daje je Bobowi. To uniemożliwia mu zobaczenie go bezpośrednio, ale także uniemożliwia jej zmianę. Wtedy Bob dokonuje wyboru: albo może poprosić Alicję, żeby to pokazała H naprawdę jest podobny do Glub może poprosić ją o pokazanie mu cyklu Hamiltona w H. Obie prośby powinny być łatwe dla Alice, zakładając, że H naprawdę jest wystarczająco podobny do Gi że naprawdę zna ścieżkę.
Oczywiście, nawet jeśli Alicja nie zna cyklu Hamiltona w G, może spróbować oszukać Boba, rysując wykresy, które nie są podobne do Glub przesyłając wykresy, do których nie zna ścieżki. Ale po rozegraniu wielu rund szansa, że Alice oszuka Boba za każdym razem, staje się znikoma. Jeśli wszystko zrobi dobrze, w końcu Bob będzie przekonany, że Alicja zna na wykresie cykl Hamiltona G, a Bob nigdy tego nie widział.
Po pierwszym artykule, który jako pierwszy opisał takie dowody, Micali i dwaj matematycy — Oded Goldreich i Avi Wigderson — odkryli nieoczekiwaną konsekwencję o dalekosiężnych skutkach. Ma to związek z główną kategorią problemów o mniej więcej równym stopniu trudności, znaną jako NP. Problemy te są trudne do rozwiązania, ale ich rozwiązania są łatwe do zweryfikowania. Trzej badacze znalazłem to, jeśli naprawdę bezpieczne szyfrowanie jest możliwe, to rozwiązanie każdego problemu w NP można również udowodnić za pomocą dowodu z wiedzą zerową. To badanie pomogło naukowcom wyobrazić warianty dowodów z wiedzą zerową, które nie wymagają nawet bezpiecznego szyfrowania; są one znane jako interaktywne dowody z wieloma dowodzeniami.
A w 1988 roku Micali i inni pokazał że jeśli dowodzący i weryfikator dzielą krótki ciąg losowych bitów, interakcja nie jest konieczna. Teoretycznie oznaczało to, że dowody z wiedzą zerową nie muszą być interaktywne, co oznaczałoby, że ciągła komunikacja między dwiema stronami nie jest konieczna. Dzięki temu byłyby znacznie bardziej przydatne dla badaczy, ale dowody takie pojawiły się dopiero na przełomie XIX i XX wieku.
„Pod koniec 2000 roku zaczęliśmy dostrzegać ewolucję wydajnych technik budowania dowodów z wiedzą zerową”, powiedział Mateusz D. Green, kryptograf z Uniwersytetu Johna Hopkinsa. „Dotarliśmy do punktu, w którym zdaliśmy sobie sprawę:„ Chwileczkę, może rzeczywiście istnieje sposób na wykorzystanie tego w praktyce”.
Teraz dowodzący może wysłać pojedynczą wiadomość do weryfikatora bez konieczności połączenia obu z sieci, a badacze mogą stworzyć bardzo krótki dowód, który można szybko zweryfikować, nawet w przypadku bardzo skomplikowanych problemów. Doprowadziło to do kilku praktycznych zastosowań, takich jak możliwość szybkiej weryfikacji blockchain po transakcji kryptowalutowej przy jednoczesnym ukryciu szczegółów transakcji. A w 2016 roku grupa fizyków pokazał jak dowody z wiedzą zerową mogą pomóc w rozbrojeniu nuklearnym: bez ujawniania żadnej tajemnicy dotyczącej konstrukcji swojej głowicy nuklearnej, kraj może teraz udowodnić inspektorom nuklearnym, czy głowica jest aktywna, czy nieaktywna.
Niedawno postępy w obliczeniach kwantowych zmusiły Crépeau do przetestowania wcześniejszych badań, aby upewnić się, że protokoły z wiedzą zerową są nadal wykonalne. W 2021 pomagał wykazać że interaktywne dowody na wielu dowodach zachowują swoją tajemnicę, nawet gdy w grę wchodzą komputery kwantowe, ale osiągnięcie tego samego poziomu bezpieczeństwa powoduje, że protokół jest znacznie wolniejszy. Powiedział, że odkrycie to dobra wiadomość, ale wraz z postępem technologicznym pojawią się nowe obawy.
„Każdy rodzaj obliczeń, które możemy wykonać w przyszłości, będzie obejmował komputery kwantowe” – powiedział Crépeau. „Jako dobrzy paranoiczni kryptografowie, za każdym razem, gdy oceniamy bezpieczeństwo systemu, chcemy mieć pewność, że nasz system jest bezpieczny”.
Od redakcji: Shafi Goldwasser otrzymał dofinansowanie z Fundacji Simonsa, która również to finansuje niezależna od wydawnictwa publikacja. Decyzje o finansowaniu Fundacji Simonsa nie mają wpływu na nasz zasięg.
