51496 Str076

148    4. Klucze publiczne

Przetłumaczymy najpierw len problem na język teorii grafów.

Definicja. Gra/jest to zbiór V, którego elementy nazywamy „wierzchołkami”, oraz podzbiór E zbioru wszystkich par (nie uporządkowanych) elementów zbioru V. Elementy zbioru E nazywamy „krawędziami”. Wyobrażamy sobie ..krawędź” e = («, i*}, gdzie u, v e V, jako odcinek łączący wierzchołki u i v.

Definicja. Mówimy, że graf jest kolorowalny kolorami c, n, z, gdy istnieje funk-cja/: ł’-* {r. n. r} laka, że żadne dwa wierzchołki połączone krawędzią nie są tego samego koloru, tzn. {u, v}eE=>f(u) ź/(»).

Problem 3-kolorowalności polega na ustaleniu, czy dany graf jest kolo-rowalny kolorami c, n, z, czy też nie jest kolorowalny tymi kolorami.

Aby przetłumaczyć problem kolorowania map na problem kolorowania grafów, po prostu jako V bierzemy zbiór państw (przedstawianych jako punkty) i „łączymy” dwa państwa krawędzią wtedy i tylko wtedy, gdy mają one wspólną granicę.

Problem 3-kolorowalności ma dwie przyjemne własności, dzięki którym nadaje się on dobrze do rozważania wielu zagadnień: (1) łatwo go sobie wyobrazić i (2) jest NP-zupcłny (por. omówienie problemu pakowania plecaka w podrozdziale 4.4). Własność NP-zupełności powoduje, że jeśli będziemy mieli dowód o zerowej wiedzy 3-kolorowalności, to będziemy również mieli dowód o zerowej wiedzy dla dowolnego problemu z klasy NP, przez „zredukowanie” tego problemu do problemu 3-kolorowalności.

Nie oznacza to jednakże, że jeśli skonstruujemy dowód o zerowej wiedzy dla pewnego problemu NP-zupełnego P_l (powiedzmy dla 3-kolorowalno-ści), to zbyteczne jest konstruowanie dowodu o zerowej wiedzy dla innego problemu NP-zupełnego P₂. Przeciwnie, w procesie redukcji P₂ do P_Y na ogól znacząco zwiększa się rozmiar danych. Zatem prawdopodobnie otrzymamy znacznie bardziej efektywny dowód o zerowej wiedzy bezpośrednio dla P₂, niż najpierw redukując P₂ do P_lt a następnie wykorzystując znany już dowód dla Pj. Na przykład podamy później bezpośredni dowód o zerowej wiedzy dla znajomości logarytmu dyskretnego. Wyjątkowo nieopłacalne byłoby konstruowanie takiego dowodu o zerowej wiedzy, redukując znajomość logarytmu dyskretnego do 3-kolorowalności pewnego grafu.

Dowód o zerowej wiedzy 3-kolorowalności. Przypuśćmy, że Urszula zna pewien graf. Wyobrażamy sobie wierzchołki jako małe kuleczki z małymi kolorowymi lampkami, połączone prętami tam, gdzie w grafie są krawędzie. Lampka w każdym wierzchołku może palić się na czerwono, niebiesko lub zielono. Urszula ma (1) urządzenie A, które zapala każdą lampkę na wybrany przez nią jeden z tych trzech kolorów, i (2) urządzenie B, które po naciśnięciu przycisku wybiera losową permutację trzech kolorów i zmienia kolor lampki w każdym wierzchołku zgodnie z tą pcrmutacją. Jeśli na przykład urządzenie B wybierze

transpozycję kolorów czerwonego i niebieskiego, to w każdym wierzchołku, ^ którym paliła się niebieska lampka, zapali teraz czerwoną lampkę, w kaź-jyni wierzchołku, w którym paliła się czerwona lampka, zapali teraz niebieską lampkę i pozostawi bez zmian wierzchołki, w których paliła się zielona lampka, Stefan nie ma żadnego wpływu na działanie urządzenia B i nie wie nawet, jakie permutacje ono generuje.

Założymy następnie, że lampki wewnątrz wierzchołków są niewidoczne, jednakże jeśli ktoś chwyci za pręt łączący dwa wierzchołki, to lampki na jego końcach (i żadne inne) staną się widoczne.

Teraz Urszula konstruuje 3-kolorowanie grafu i za pomocą urządzenia / zapala lampki odpowiednich kolorów w wierzchołkach. A oto procedura, która ma przekonać Stefana, że Urszuli udało się to zrobić:

1.    Stefanowi wolno chwycić za jeden pręt-krawędź, uwidoczniając kolory lampek w wierzchołkach na końcach tej krawędzi. Zobaczy on, że te dwa wierzchołki mają różne kolory, uzyskując w ten sposób odrobinę pewności, że Urszula zna prawidłowe kolorowanie grafu (przypomnijmy, że „prawidłowe” oznaczało, iż żadne dwa wierzchołki połączone krawędzią nie są tego samego koloru).

2.    Urszula naciska następnie przycisk urządzenia B, permutując kolory.

3.    Stefan może teraz chwycić następny pręt-krawędź.

4.    Urszula i Stefan powtarzają kroki 2 i 3 na zmianę dopóty, dopóki Stefan nie przetestuje wszystkich krawędzi (lub jeśli mu na tym zależy, dopóki me przetestuje on wszystkich krawędzi wielokrotnie - może on podejrzewać, że Urszula go oszukuje, zmieniając kolorowanie wierzchołków na końcach krawędzi przetestowanej wcześniej).

Po chwili zastanowienia dwie rzeczy powinny być oczywiste: (1) Jeśli Urszula nie umiała prawidłowo pokolorować grafu trzema kolorami, to nie będzie w stanie oszukać Stefana - w końcu okaże się w kroku 3, że dwa połączone wierzchołki mają ten sam kolor. (2) Ze względu na losowe permutacje kolorów Stefan nie dowiaduje się niczego o kolorowaniu, poza tym, że Urszuli się udało. Znaczy to, że jeśli teraz on też chce pokolorować ten graf, to po wykonaniu powyższych kroków 1 -4 stanie wobec takich samych trudności, jak przed wykonaniem ich.

Aby dowieść, że Stefan nie dowiedział się nic o kolorowaniu, rozumujemy następująco. Przypuśćmy, że trzecia osoba, Cezary, nie wie, w jaki sposób można pokolorować ten graf, ale umie przewidzieć, jakie pręty-krawędzie uchwyci Stefan. Wtedy Cezary mógłby osiągnąć ten sam rezultat, co Urszula, tzn. informacja, którą Stefan otrzyma od Cezarego, byłaby nieodróżnialna od informacji otrzymanej od Urszuli. Ale Cezary nie może oczywiście przekazać żadnej informacji, która mogłaby pomóc w kolorowaniu grafu, bo on sam nie umie tego grafu pokolorować. Mówimy, że Cezary „symuluje” zachowanie Urszuli. To rozumowanie, korzystające z symulacji, jest standardowym sposobem wykazywania, że pewien protokół rzeczywiście stanowi dowód o zerowej wiedzy.