52749 Str078

152    4. Kłucie puhłłcnie

Zauważmy, żc zakłada się, iż Stefan nic zna logarytmu dyskretnego liczby p który oznaczamy przez v' gdyż w przeciwnym razie znałby również loJ^N rytm dyskretny iloczynu C *= co przeczy założeniu.

Przypuśćmy teraz, że Urszula ma jednostkę tekstu /zi| g F5 z pierwszy pakietu i jednostkę tekstu m₂ e FJ z drugiego pakietu. Wybiera ona dwie liczby losowe 0 <V|, >’₂ < q - 1 i wysyła Stefanowi następujące dwa elementy L i dwa elementy FJ:    ^q

&K *1 = m, + tKfflP). «₂ = m₂ + ♦(/??) .

(Dodawanie jest tu działaniem w przestrzeni liniowej FJ nad ciałem F₂; to działanie jest czasem nazywane „alternatywą wykluczającą” lub „dysjunkc-ją”^ł)). Urszula zachowuje y_t i y₂ w tajemnicy.

Ponieważ jjffj* = (b^yi)^x i Stefan zna zarówno b^y,t jak i x, może on łatwo wyznaczyć t//(/if')» a następnie znaleźć m, = a, + Jednakże, gdyby chciał znaleźć m₃__f, musiałby wcześniej znaleźć /ę-j = b^x'^yi~^l, znając tylko b^,i~ⁱ i b^x' i nie znając ani y₃__f, ani x\ Jest to niemożliwe, na mocy założenia DifTiego--Hcllmana.

Zauważmy, że Urszula może łatwo sprawdzić, że = C, a więc może być pewna, że Stefan nie zna logarytmów dyskretnych obu elementów swojego publicznego klucza (fi_lt Jł₂). Ponieważ w jego interesie leży posiadanie jak najwięcej informacji, więc Urszula może być pewna, że zna on logarytm dyskretny jednego z tych dwóch elementów. Ale niema sposobu, który pozwoliłby Urszuli rozróżnić i /ł₂, w tym sensie, by wiedzieć, który z nich Stefan uzyskał jako 6*, a który jako C/6*. Zatem oboje, Urszula i Stefan, mogą być pewni, że warunki 1 i 2 zostały spełnione.

Jeżeli wysłany ciąg par (m_A, m₂) będzie utworzony za pomocą tych samych (P_lt /ł₂) (tzn. za pomocą tych samych wartości x oraz i), to Urszula będzie wiedziała, że element pary (m₁, m₂), który Stefan umie rozszyfrować (mianowicie m,) będzie tym samym elementem™ dla wszystkich par jednostek tekstu w tym ciągu. Jeśli chce ona wysłać niezależnie inny ciąg jednostek tekstu, to Stefan musi wybrać losowo nowe wartości x oraz i i wysłać nowy klucz publiczny (fi_t, 0₂).

Zastosowanie przekazów nierozróżnialnych do nieinterakcyjnego dowodu faktoryzacji. Określenie „nieintcrakcyjny” może najlepiej być zilustrowane za pomocą wykresu

Centrum

Urszula —►    Stefan

^ł) Ostatnio to działanie coraz częidej oznacza się symbolem XOR (przyp. tłum.). ^1,1 To znaczy zawsze pierwszym lub zawsze drugim (przyp. tłum.).

Rolą obdarzanego pełnym zaufaniem „Centrum” jest tu dostarczanie losowych bitów, wysyłanych jednocześnie do Urszuli i Stefana (dopuszcza się, by Centrum najpierw wykonało pewne operacje arytmetyczne na tych bitach, zanim je wyśle). Połączenie tych bitów i reakcji Urszuli na nie - tego, co ona wyśle Stefanowi - musi wystarczyć, by przekonać Stefana (z wykładniczo malejącym prawdopodobieństwem tego, że został oszukany), że Urszula rzeczywiście zrobiła to, co twierdzi, że zrobiła.

„Nicinterakcyjność” oznacza, źe w czasie przeprowadzania dowodu Stefan nie kontaktuje się z Urszulą. Jednakże dopuszczamy to, że na samym początku Urszula otrzymuje długi ciąg publicznych kluczy (fi_v /ł₂) Stefana, służących do przekazów nierozróżnialnych, tak jak to opisaliśmy wyżej. Nic uważamy tego za kontaktowanie się Stefana z Urszulą. Przecież te same klucze publiczne, jak sugeruje słowo „publiczne”, są dostępne dla każdego, kto zechce odegrać rolę Urszuli. A Urszula może użyć tego samego ciągu kluczy publicznych w wielu różnych dowodach o zerowej wiedzy, które będzie przesyłać Stefanowi.

Opiszemy teraz procedurę, której Urszula używa do przekonania Stefana, że potrafi rozłożyć na czynniki liczbę całkowitą n = pq, nie dając mu jednocześnie żadnych informacji o tych czynnikach. Skorzystamy z tego, że umiejętność obliczania pierwiastków kwadratowych modulo n-pq z dowolnej liczby mającej taki pierwiastek kwadratowy jest równoważna znajomości p i q (por. ćwiczenie 5 poniżej). A oto sama procedura:

1.    Centrum generuje losowo liczbę całkowitą x i wysyła Urszuli i Stefanowi resztę z dzielenia x² przez n; oznaczmy tę resztę przez y y = x² (mod n).

2.    Urszula znajduje cztery pierwiastki kwadratowe z liczby y modulo n, mianowicie +*, ±x'. Jako x₀ wybiera wtedy arbitralnie jeden z tych czterech pierwiastków kwadratowych.

3.    Urszula wybiera losowo liczbę całkowitą r i wysyła Stefanowi liczbę s = r² mod n. Przyjmuje następnie m_l = r mod n oraz m₂ = x₀r mod n i wysyła te dwie liczby Stefanowi jako dwie różne wiadomości za pomocą przekazów nierozróżnialnych.

4.    Stefan może odczytać dokładnie jedną z tych dwóch wiadomości. Sprawdza, że kwadrat odczytanej liczby przystaje modulo n do liczby s (jeśli jego losową liczbą i jest 1) lub do ys (jeśli z = 2).

5.    Kroki 1-4 są powtarzane wielokrotnie (dla różnych kluczy publicznych (fiu fil))- J^eśli Urszula powtórzy ten test T razy, to Stefan jest przekonany (z prawdopodobieństwem 1 - 2"^r), że Urszula rzeczywiście zna rozkład liczby Ti na czynniki.

Ćwiczenia

1. Jakie jest prawdopodobieństwo tego, że Urszuli, która nie zna logarytmu dyskretnego, mimo wszystko uda się oszukać Stefana, powtarzając T razy