A jednak się da!

O dowodach z wiedzą zerową (AJSD III)

Bywa tak, że chcemy o czymś przekonać niedowiarków, jednak w taki sposób, aby uwierzyli, ale też aby za dużo się nie dowiedzieli. Fabularna, nieinformatyczna ilustracja, którą lubię przywoływać, gdy próbuję wyrazić, o co mi chodzi, jest następująca. Wyobraźmy sobie, że potrafię zliczyć liczbę liści na drzewie, jeśli tylko spojrzę na nie przez 5 sekund. Więcej: twierdzę, że umiem to publicznie udowodnić w przeciągu 5 minut, i to tak, że wszyscy mi uwierzą, ale nikt się nie zorientuje, jak ja to robię!

Jak mógłby wyglądać protokół, który realizuje powyższe założenia? Popatrzmy:

(1): Proszę publiczność o wskazanie dowolnego drzewa.
(2): Patrzę na to drzewo przez 5 sekund i mówię: "to drzewo ma $M$ liści".
(3): Proszę publiczność o zawiązanie mi oczu.
(4): Proszę publiczność o podejście do analizowanego drzewa i zerwanie z niego dowolnych $K$ liści (oczywiście $K |$ publiczność ustala samodzielnie, nie informując mnie o swoim wyborze).
(5): Proszę publiczność o rozwiązanie mi oczu.
(6): Ponownie patrzę na drzewo przez 5 sekund i mówię: "to drzewo ma $|X$ liści".

I teraz tak: jeśli $≠M−K, |X$ to z pewnością nikogo nie przekonałem. Jednak jeśli $=M−K, |X$ to eksperyment daje do myślenia. Oczywiście, aby zmniejszyć szansę zdarzenia, że po prostu miałem szczęście, protokół weryfikacyjny można kilka razy powtórzyć, dla różnych drzew i różnych wyborów zmiennej $|K.$ Jeśli więc pozytywnie przejdę na przykład 10 testów pod rząd, to sądzę, że już wszyscy mi uwierzą, że naprawdę umiem błyskawicznie zliczać liście na drzewie. Mimo to: nikt nie ma nawet cienia wskazówki, jak ja to robię!

Właśnie takie przekonywanie jak wyżej nazywamy fachowo dowodzeniem z wiedzą zerową (zero-knowledge proofs), a bardziej kolokwialnie: przekomarzaniem się w stylu "wiem, ale nie powiem". Okazuje się, że zaskakująco wiele stwierdzeń matematycznych da się udowodnić w taki właśnie sposób. W szczególności: gdybyśmy na przykład potrafili rozstrzygnąć pozytywnie hipotezę Riemanna, to możemy zaproponować światu pewną zabawę, w wyniku której wszyscy uwierzą, że faktycznie hipoteza Riemanna jest prawdziwa, ale nikt nawet powierzchownie nie liźnie smaku naszego dowodu. Jak to zrobić - obiecuję naszkicować na końcu, a na razie zajmijmy się prostszym przykładem.

Izomorfizm grafów

Opiszemy protokół dowodu z wiedzą zerową dla problemu izomorfizmu grafów (szerzej o tym problemie pisał Łukasz Kowalik w Delcie 12/2018). Przypomnijmy: problem polega na rozstrzygnięciu, czy dwa dane grafy $1G$ oraz $2 |G$ są izomorficzne, czy też nie. Załóżmy więc, że znamy pewien izomorfizm $π$ między $1 G$ a $2. |G$ Naszym celem jest przekonać publiczność (fachowo: weryfikatora), że faktycznie znamy $π ,$ ale bez ujawniania, jak to $π$ w rzeczywistości wygląda.

Do dzieła:

(1): Postulujemy publicznie, że grafy $1 G$ oraz $2 |G$ są izomorficzne.
(2): Publikujemy dowolny graf $H,$ który jest izomorficzny z $G | 1$ (czyli również z $2 G$ ).
(3): Weryfikator wybiera liczbę $k ∈ {1,2}.$
(4): Publikujemy izomorfizm $′ |π$ między $H$ a $k. G |$
(5): Weryfikator sprawdza, czy $π ′$ jest rzeczywiście poprawnym izomorfizmem między $|H$ a $. G | k$
(6): Kroki 2-5 powtarzamy $|N$ razy.

Powyższy protokół ma trzy kluczowe cechy:

(a): Jeśli naprawdę znamy postulowany izomorfizm, to jesteśmy zawsze w stanie wykonać poprawnie cały protokół;
(b): Szansa, że oszukamy weryfikatora (to znaczy: przekonamy go, że znamy izomorfizm między $1 G$ a $2, |G$ mimo że wcale go nie znamy) wynosi co najwyżej $1 |2N$ ;
(c): Przekonany weryfikator nie ma bladego pojęcia, jak może wyglądać izomorfizm między $1 |G$ a $2. G$

Naszkicujmy więc uzasadnienia stwierdzeń b oraz c (pozwolimy sobie napisać, że a jest trywialne):

Ad (b) Zauważmy, że jeśli odnosimy sukces z prawdopodobieństwem powyżej $-1N, 2$ to przynajmniej w jednej z $N$ iteracji protokołu, w kroku 4. byliśmy przygotowani na opublikowanie izomorfizmu zarówno między $|H$ a $1 G |$ (ozn. $π 1$ ), jak i między $H$ a $2 G |$ (ozn. $π 2$ ). Istotnie - gdyby tak nie było, to w każdej iteracji mielibyśmy szansę co najwyżej $12$ na akceptację przez weryfikatora, a więc ogólnie - co najwyżej tylko $-1N. 2$ Jednak znajomość zarówno $|π 1$ jak i $π 2$ oznacza również znajomość $−1 |π2○ π1 ,$ a to jest przecież izomorfizm między $1 G$ a $2. G$

Ad (c) Zastanówmy się, czego - po wykonaniu całego protokołu - dowiedział się weryfikator. Jak widać, poznał $N$ różnych trójek postaci $|(Hi,$ takich, że $π ′i$ jest izomorfizmem między $|Hi$ a $ei. G |$ Czy taka wiedza jest w jakikolwiek sposób ekskluzywna? Otóż łatwo zauważyć, że absolutnie nie - przecież takie trójki można sobie samemu (w dowolnych ilościach) produkować, znając wyłącznie $1 G$ oraz $2, G$ a te są przecież publiczne od samego początku!

Cykl Hamiltona w grafie

Czas na nieco bardziej skomplikowany przykład - protokół dowodu z wiedzą zerową dla problemu istnienia cyklu Hamiltona w grafie.

W tym protokole będziemy używać idei zobowiązań $(Commit),$ opisanych przez Łukasza Rajkowskiego w poprzednim odcinku AJSD, w Delcie 11/2018.

Jak poprzednio, załóżmy, że znamy cykl Hamiltona $|c = (a1,...,an)$ pewnego grafu $. G$ Teraz:

(1)

Postulujemy publicznie, że w

G

istnieje cykl Hamiltona. Będziemy próbować to udowodnić, ale nie zdradzając, jak faktycznie wygląda

c.

(2)

Losujemy dowolną permutację

|π

oraz obliczamy graf

) |π(G

(czyli izomorficzny do

, G

ale z wierzchołkami spermutowanymi według

|π

(3)

Upubliczniamy następujące zobowiązania:

$|Commit( π )$
$|Commit(e ),Commit(e ),...,Commit(e ), 1 2 m$ gdzie $|{e1,...,em}$ stanowią opisy wszystkich krawędzi grafu $) π (G$ (to znaczy: każde $ei$ jest parą pewnych wierzchołków grafu $) |π(G$ ).

(4)

Weryfikator wybiera liczbę

k ∈ {1,2}.

(5)

Jeśli

k = 1,

to otwieramy wszystkie (zarówno permutacji, jak i krawędzi) zobowiązania z kroku 3.

(6)

Jeśli

k = 2,

to otwieramy zobowiązania tych (i tylko tych) krawędzi, które tworzą cykl Hamiltona w

) |π(G

(NIE otwieramy zobowiązania permutacji!).

(7)

Jeśli

k = 1,

to weryfikator sprawdza, czy otwarte krawędzie

{e1,...,em}

są faktycznie krawędziami grafu

). |π(G

(8)

Jeśli

k = 2,

to weryfikator sprawdza, czy faktycznie otwarte krawędzie tworzą jeden zamknięty cykl długości

|n.

(9)

Kroki 2-8 powtarzamy

|N

razy.

Twierdzimy, że ten protokół również ma trzy cechy, o których mówiliśmy w poprzednim przykładzie. To znaczy: jeśli rzeczywiście znamy cykl Hamiltona w $, |G$ to wykonamy protokół bez problemu (trywialna obserwacja). Dalej: szansa na oszukanie weryfikatora wynosi ponownie co najwyżej $|1-, 2N$ a schemat dowodu jest dokładnie taki sam jak poprzednio. Wystarczy tylko zauważyć, że jeśli w którejkolwiek iteracji jesteśmy pewni akceptacji weryfikatora (niezależnie od wyboru $|k$ ), to znaczy, że zobowiązaliśmy się do permutacji $π$ takiej, że znamy cykl Hamiltona w $). π (G$ To jednak oznacza, że znamy również cykl Hamiltona w $. G$ Pozostaje tylko upewnić się, że nabyta (w wyniku realizacji protokołu) przez weryfikatora wiedza nic mądrego mu nie mówi. I tak jest w istocie: jeśli $|k = 1,$ to weryfikator uczy się tylko pewnego izomorfizmu $,G$ a jeśli $k = 2,$ to weryfikator poznaje losową permutację liczb $|{1,...,n},$ zupełnie niezależną od $G$ (bo w tym przypadku nie zna $|π$ !).

Co jeszcze?

Pokazaliśmy dwa przykłady protokołów dowodów z wiedzą zerową. Nasuwa się pytanie: jakie inne (i jak bardzo skomplikowane) stwierdzenia możemy podobnie dowodzić? Okazuje się (być może zaskakująco), że... niemal wszystkie. Aby się o tym przekonać, potrzebna jest pewna wiedza z teorii złożoności obliczeniowej, a konkretnie: informacja, że problem istnienia cyklu Hamiltona w grafie jest problemem NP-zupełnym. Nie jest ambicją tego artykułu, aby dokładnie wytłumaczyć to pojęcie (patrz na przykład Delta 11/2013, Delta 1/2017 czy Delta 11/2017), więc siłą rzeczy musimy w tym momencie trochę rozluźnić rygor ścisłej precyzji na rzecz intuicji.

Otóż fakt, że problem cyklu Hamiltona (CH) jest NP-zupełny, oznacza, że dzięki temu, że pokazaliśmy protokół dowodu z wiedzą zerową dla CH, wiemy jak konstruować protokoły z wiedzą zerową dla dowolnego innego problemu z klasy NP! W jaki sposób? Wystarczy zastosować odpowiednią efektywną redukcję do problemu CH (która musi zawsze istnieć) i dalej stosować protokół opisany wyżej.

W szczególności: załóżmy, że udowodniliśmy hipotezę Riemanna. Rozważmy teraz język:

L = {zdanie prawdziwe ϕ ϕma dow ód dł ugo ści⩽ k}.

Niewątpliwie $|L∈ NP$ (dlaczego?), więc dla każdego $ϕ ′∈L$ istnieje dowód z wiedzą zerową, w szczególności: dla $ϕ ′= „Hipoteza Riemanna jest prawdziwa ”.$

A po ludzku: okazuje się, że istnieje graf $kRiemann G$ (rozmiaru wielomianowego od $k$ ) taki, że jeśli hipoteza Riemanna ma dowód długości $⩽ k,$ to w tym grafie jest cykl Hamiltona, a jeśli nie ma takiego dowodu - to i cyklu Hamiltona w $k Riemann |G$ nie znajdziemy. Więcej: znalezienie grafu $kRiemannG$ jest efektywnie obliczalną funkcją zdania $ϕ′$ (zapisanego w jakiejś formalnej logice). Jeśli więc rzeczywiście znajdziemy dowód dla hipotezy Riemanna długości $k$ i mamy nieodpartą pokusę pohandryczyć się ze światem, to możemy zawsze przedstawić wyłącznie dowód istnienia cyklu Hamiltona w grafie $kRiemann. |G$ Dowód z wiedzą zerową, rzecz jasna!