Wyjaśnienie dowodów braku wiedzy Część 2: Nieinteraktywne dowody braku wiedzy

Przykład nieinteraktywnych dowodów zerowej wiedzy: Sudoku i karty do gry

W części 1 naszej serii dowodów zerowej wiedzy wyjaśniliśmy, w jaki sposób może działać dowód zerowej wiedzy, gdy weryfikator i łowca współdziałają ze sobą.

Interaktywny dowód zerowej wiedzy ma tę zaletę, że tylko weryfikator może być absolutnie przekonany, że wiedza posiada wiedzę. Ale może to być również wadą.

Jeśli osoby postronne i obserwatorzy nie mogą zweryfikować roszczenia, wówczas przysłowiowiec musi wejść w interakcję z każdym weryfikatorem niezależnie – co zajmuje dużo czasu i wymaga dużych zasobów.

W tej części 2 przyjrzymy się nieinteraktywnym dowodom zerowej wiedzy.

Nieinteraktywne dowody zerowej wiedzy

Powodem nieinteraktywnych dowodów zerowej wiedzy jest umożliwienie dużej liczbie obserwatorów skutecznego zweryfikowania dowodu.

Nie zawsze musimy robić nieinteraktywne dowody zerowej wiedzy. Często można znaleźć zaufanego weryfikatora, który gwarantuje integralność dowodu.

Przykład nieinteraktywnych dowodów zerowej wiedzy: Sudoku i karty do gry

Sudoku to gra o różnym stopniu trudności, ale stosunkowo prostych zasadach. Każdy z 9 wierszy, 9 kolumn i 9 sektorów (zgodnie z grubą czarną linią) musi zawierać każdą liczbę od 1 do 9 dokładnie raz.

Wyobraź sobie, że rozwiązanie zagadki sudoku jest szczególnie trudne do uzyskania, a nawet superkomputer zajmuje kilka dni.

Ale ktoś (prover) twierdzi, że ma rozwiązanie zagadki i chce ją sprzedać za pewną cenę. Jak mogą udowodnić, że mają rozwiązanie – bez ujawnienia go – aby weryfikator był przygotowany do dokonania płatności?

Dowód:

Potwór potrzebuje 27 kart do gry (dowolnego koloru) o numerach od 1 do 9–243.

Teraz prover umieszcza trzy karty z liczbą odpowiadającą prawidłowemu rozwiązaniu Sudoku w każdym pudełku. Np. Jeśli prawidłowa odpowiedź na pole to 7, to przysłowie umieści w nim 3 karty do gry o wartości 7.

Na stole Sudoku niektóre odpowiedzi będą widoczne. Na tych polach odpowiedzi znajdują się karty do gry stawić czoła. Na pustych polach Sudoku karty są umieszczane głową w dół.

Aby udowodnić, że zakryte karty znajdują się we właściwej pozycji (bez ujawnienia rozwiązania), przysłowia musi:

  • Weź najlepszą kartę z każdego rząd i zrób 9 stosów
  • Weź najlepszą kartę z każdego kolumna i zrób 9 stosów
  • Weź pozostałe karty z każdego sektor i zrób 9 stosów

Wnioski o dowód zerowej wiedzy

Każdy stos jest następnie tasowany i odwracany.

Każda liczba od 1 do 9 musi pojawić się w każdym wierszu, kolumnie i sektorze Sudoku. Więc jeśli każdy stos kart provera (z stosów rzędu, kolumny i sektora) zawiera każdą kartę do gry o wartości 1-9, wiemy, że muszą mieć rozwiązanie.

Wnioski o dowód zerowej wiedzy

Trzeba przyznać, że stosunkowo młoda dziedzina dowodów zerowej wiedzy nie znalazła jeszcze akceptacji, na którą może zasłużyć. Mogą się jednak okazać bardzo cenne.

Wiele problemów matematycznych jest podobnych do zagadek sudoku (na przykład problem kolorowania graficznego). Jeśli potrafimy zastosować powyższą zasadę i z powodzeniem zastosować ją do różnych problemów, możemy być w stanie efektywniej wykorzystywać zasoby handlowe i problemy matematyczne oraz handlować nimi. A może szybciej rozwiążą matematyczne problemy.

Uznanie dla Ronena Gradwohla, Moni Naor, Benny’ego Pinkasa i Guya Rothbluma

Kim Martin
Kim Martin Administrator
Sorry! The Author has not filled his profile.
follow me