Kto jest najbogatszy i czy to naprawdę miłość?

25.02.2010 - Agata Murawska
TrudnośćTrudność

Orzeł czy reszka?

Naszej potencjalnie zakochanej parze udało się ustalić, że będą losować, kto będzie tworzyć parę liczb. Jeśli wypadnie reszka, czyli $ 0 $, parę tę tworzy Alicja, jeśli wynikiem jest orzeł ($ 1 $) - Bob.

XOR
Pamiętając już, jak działa operacja XOR($ \oplus $), można spodziewać się protokołu postaci:
1. Alicja losuje swój bit, $ b_A $.
2. Bob losuje swój bit, $ b_B $.
3. Przekazują sobie nawzajem wyniki i obliczają $ b_A \oplus b_B $.

Jest tylko jeden problem: jak przekazać wyniki w tym samym momencie, tak, żeby żadne z nich nie mogło oszukać? Nie da się tego niestety w żaden sposób zagwarantować.
Rozwiązaniem naszego problemu jest kolejny przykład MPC, tym razem korzystający z protokołu zobowiązania bitowego.
Zobowiązanie bitowe jest protokołem, umożliwiającym uczciwy wybór losowego bitu tak, że strona losująca nie może zmienić losu, a druga strona poznaje los tylko za zgodą losującego.
Zobowiązanie
1. Alicja wybiera bit $ b_A $ i losuje wiadomość $ m $ taką, że jej ostatnim (najmniej znaczącym) bitem jest $ b_A $.
2. Alicja szyfruje $ m $ za pomocą klucza publicznego $ e_A $ i wysyła Bobowi informację $ (e_A, m^{e_A}) $
XOR
Odtworzenie bitu
1. Alicja wysyła $ m $ do Boba.
2. Bob wybiera najmniej znaczący bit z $ m $. Oczywiście, Bob może sprawdzić, czy nie został oszukany - zna klucz $ e_A $, zatem może zaszyfrować $ m $ przy jego pomocy i sprawdzić, czy wynik zgadza się z nadesłanym wcześniej przez Alicję.

Skoro wiemy, jak zobowiązać się do bitu, to potrafimy już także bezpiecznie rzucać monetą. Jak?
1. Alicja losuje $ b_A $.
2. Bob losuje $ b_B $.
3. Alicja zobowiązuje się do $ b_A $.
4. Bob wysyła $ b_B $ do Alicji.
5. Alicja otwiera zobowiązanie dla $ b_A $, ujawniając go Bobowi.
6. Każde z nich oblicza $ b_A \oplus b_B $.

Dlaczego ten protokół jest dobry? Bob, wysyłając wylosowany bit $ b_B $ nie wie jeszcze, co wylosowała Alicja - zatem nie może wymusić żadnego wyniku wspólnego losowania. Z kolei Alicja zobowiązała się do $ b_A $ przed poznaniem $ b_B $, czyli także bez wiedzy, o wyniku drugiej strony.
Oczywiście, Alicja może odmówić otwarcia zobowiązania - ale jasne jest wtedy, że wynik $ b_A \oplus b_B $ był dla niej niekorzystny.

Najbogatszy człowiek świata

Najbogatszy człowiek świata nie znosi czekać. Na szczęście Anton i Bill nie wiedzą jeszcze, który z nich jest najbogatszy - inaczej moglibyśmy wpaść w poważne tarapaty.

Problem multimiliarderów to przykład podany w pracy, która zapoczątkowała badania nad obliczeniami dwu- i wielopodmiotowymi. Jej autorem jest Andrew Yao, laureat nagrody Turinga z 2000 roku. Przedstawione poniżej rozwiązanie pochodzi właśnie od Yao. Oczywiście, w oryginalnym problemie milionerami byli Alicja i Bob..

Problem bogaczy wydaje się być nieco trudniejszy, niż dwa rozważane przed chwilą. Dla uproszczenia załóżmy, że majątki biznesmenów są z przedziału od $ 1 $ do $ 15 $ miliardów dolarów - $ 1< m_A, m_B < 15 $. Ustalmy, że wynikiem działania $ \mathrm{bogatszy}(m_A,m_B) $ będzie $ 0 $, jeśli Anton jest bogatszy od Billa ($ m_A \geq m_B $) i $ 1 $, w przeciwnym wypadku.
Uwaga: majątki obu bogaczy mogą być wyrażone liczbami $ 4 $-bitowymi.
Protokół zaproponowany przez Andrew Yao wygląda następująco:
1.
Bill wybiera $ N=4 $-bitową liczbę $ x $. (Dlaczego właśnie $ 4 $ bity? Wynika to z uwagi powyżej.)
Następnie oblicza $ k = x^{e_A} $ i wysyła do Antona $ m = k-m_B+1 $.
2.
Anton deszyfruje liczby $ m, m+1, \dots m+14 $, podnosząc je do potęgi $ d_A $ - otrzymując wartości $ y_i $:
$ m+i = k-m_B+(i+1) $, $ y_i = (m+i)^{d_A} $
Następnie generuje pewną $ \frac{N}{2}=2 $-bitową liczbę pierwszą $ r $ taką, że wszystkie wartości $ z_i = y_i \mod r $ różnią się przynajmniej o 2.
W kolejnym kroku Anton wysyła do Billa zestaw: $ r, z_1, z_2,\dots z_{m_A-1}, z_{m_A} + 1 \mod r, z_{m_A+1}+1\mod r,\dots z_{10}+1 \mod r $. - czyli zaznacza swój stan posiadania, zwiększając o $ 1 $ ($ \mod r $) duże odszyfrowane wartości.
3.
Bill patrzy na $ m_B-1 $-szą z ciągu liczb otrzymanych za $ r $.
Jeśli liczba ta jest równa $ x  \mod p $, to uznaje, że $ m_A\geq m_B $ i odpowiedzią jest $ 0 $.
W przeciwnym razie dochodzi do wniosku, że $ m_A < m_B $ i odpowiedzią jest $ 1 $.
Wysyła uznaną za poprawną odpowiedź do Antona.


Dlaczego protokół jest bezpieczny i skąd Bill wie, kto ma więcej?
Po pierwszym kroku Anton otrzymuje $ m_B $ zaciemnione losową informacją, nie jest więc w stanie powiedzieć nic na jego temat. Jest to jedyny moment, w którym Anton otrzymuje od Billa jakąkolwiek wiadomość zawierającą $ m_B $ - zatem nie ma on szans poznać stanu konta konkurenta.
Co z Billem? W przedstawionej wersji może oszukiwać w ostatnim kroku, ale żeby dowiedzieć się dzięki temu, kto jest bogatszy, musiałby powtarzać protokół kilkukrotnie - na to Anton się nie nabierze!
Czy gdzieś jeszcze uda się Billowi wywnioskować coś o nie swoim stanie konta? Anton wysyła do niego $ 15 $ różnych liczb (różnych, bo każde dwie różniły się o przynajmniej $ 2 $, a do niektórych przed wysłaniem dodaliśmy $ 1 $). Wystarczy, żeby miliarder potrafił ustalić, od której liczby zaczyna się ciąg zwiększony o $ 1 $. Dlaczego nie jest to proste? Przeliczmy to (jeśli nie pamiętasz oznaczeń, cofnij się do opisu prookołu):
$ z_i = y_i \mod r = (m+i)^{d_A} \mod r =  $
$  (k-m_B+(i+1))^{d_A} \mod r =  $
$ (x^{e_A}-m_B+(i+1))^{d_A} \mod r $.
Bill, nie znając klucza prywatnego $ d_A $, nie jest w stanie zrobić nic, poza znalezieniem swojej liczby, $ x $.
Tę ostatnią może odtworzyć, ponieważ $ z_{m_B-1} = (x^{e_A}-m_B+(m_B-1+1))^{d_A} \mod r = (x^{e_A})^{d_A} = x $. Jeśli zatem $ (m_B-1) $-sza liczba była równa $ x $ (a nie $ x+1 $), to $ m_B-1 $ < $ m_A $, czyli $ m_B \leq m_A $.

Zamiast zakończenia

Rozwiązaliśmy dwa całkiem życiowe problemy. Oczywiście, im więcej wiemy, tym więcej nasuwa się pytań - czy da się policzyć w podobny sposób każdą funkcję? Jak wydajne będą to obliczenia? Czy obliczenia w parach są dużo prostsze, niż w większych grupach? I właściwie - czy to ma jakieś praktyczne zastosowania? Wstrzymamy się na chwilę i nie odkryjemy jeszcze wszystkich kart, ale do tematu na pewno wrócimy. Powiedzmy na razie tylko, że odpowiedź na ostatnie pytanie jest pozytywna. Shafi Goldwasser, jedna z bardziej zasłużonych dla kryptografii osób na świecie, powiedziała kiedyś, że MPC jest w miejscu, gdzie 15-20 lat temu było szyfrowanie RSA; mechanizm ten faktycznie wydaje się być bardzo silny i dawać ogromne możliwości, trzeba tylko dokładnie go zbadać.

Zadanie sprawdzające

W problemie dwóch biznesmenów powiedzieliśmy, że Bill może ustalić, ile Anton ma na koncie, jeśli będzie powtarzać protokół. W jaki sposób mógłby to osiągnąć i jaka jest minimalna liczba powtórzeń, jeśli obaj panowie mają więcej niż $ 1 $, ale mniej niż $ n $ miliardów dolarów?

Niektóre obrazki w artykule pochodzą z wikipedii.
  • Źródło serca oraz informacja o licencji, na jakiej zostało opublikowane: link.
  • Źródło zdjęcia banknotów oraz informacje o licencji, na jakiej zostało opublikowane: link.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com