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

25.02.2010 - Agata Murawska
TrudnośćTrudność

Czy zdarzyło Wam się kiedyś zakochać? Strasznie głupia sprawa, ale Alicja i Bob nie są pewni, co do siebie czują. Żadne z nich nie zdecyduje się powiedzieć drugiemu, że go (nie) kocha, póki nie usłyszy podobnej deklaracji od drugiej strony. Sytuacja wydaje się bez wyjścia - póki któreś z nich nie "pęknie", będą trwali w zawieszeniu. Zawieszona Alicja nie jest w stanie programować, a Bob projektować protokołów kryptograficznych - trzeba więc coś zrobić, żeby pomóc nieszczęsnej parze. Wystarczy, że będą wiedzieli, czy to miłość - i znów będą w stanie normalnie funkcjonować.

Zapiszmy to formalnie: Niech $ A $ oznacza odpowiedź na pytanie, czy Alicja kocha Boba, zaś $ B $ pozwala stwierdzić, czy Bob kocha Alicję. Wówczas $ \mathrm{miłość}(A,B) = A \land B $ - czyli miłość jest wtedy, kiedy Alicja kocha Boba i Bob kocha Alicję.





Wracając na ziemię, podajmy jeszcze jeden, nieco bardziej przyziemny przykład tego, czym się za chwilę zajmiemy.

Klucz

Anton i Bill są multimiliarderami. Nie chwalą się swoimi majątkami publicznie, bo jeszcze okazałoby się, że muszą zapłacić jakiś podatek - są jednak ciekawi, który z nich jest bogatszy. Żaden nie zamierza podawać drugiemu swojego stanu konta, a mimo to są zdeterminowani rozstrzygnąć ten spór o wielką kasę.








Dwa powyższe problemy mają podobną strukturę. Mamy dwóch uczestników, którzy chcą coś wspólnie policzyć. Każdy z nich ma fragment danych wejściowych, ale żaden nie ma dostępu do całości. Tego typu zadania to przykłady obliczeń dwupodmiotowych, czyli szczególnego przypadku obliczeń wielopodmiotowych (ang. multi-party computations, MPC).

Jak sugeruje nazwa, problem obliczeń wielopodmiotowych ma następującą postać:
Mamy danych $ k $ osób: $ P_1, P_2, \dots, P_k $, z których każda ma dostęp do jednego fragmentu informacji, odpowiednio $ x_1, x_2, \dots, x_k $. Osoby te stają wspólnie przed zadaniem obliczenia funkcji $ \mathrm{f}(x_1, x_2, \dots , x_k) = (y_1, y_2, \dots, y_k) $. Założenia przyjmowane w tym modelu są następujące:

  • tylko osoba $ P_i $ ma dostęp do informacji $ x_i $
  • osoba $ P_i $ wie o fragmentach wejściowych (różnych od swojego własnego wejścia $ x_i $) tylko tyle, ile da się wywnioskować z wyniku $ y_i $ funkcji $ \mathrm{f} $
Czy to nie brzmi jakoś znajomo? Skojarzenia z problemem dzielenia sekretu są jak najbardziej zasadne. Mówiąc o tym zagadnieniu wspominaliśmy pod koniec, że istnieją wersje protokołu, umożliwiające sprawdzanie potencjalnych oszustw. Nazywa się je weryfikowalnym dzieleniem sekretu (ang. verifiable secret sharing, VSS) i są podstawową "cegiełką" do skonstruowania bezpiecznych obliczeń wielopodmiotowych.

Klucz

Oczywiście, obliczenia te będą bezpieczne także, jeśli znajdziemy bezstronną, zaufaną osobę trzecią, której możemy powierzyć najskrytsze sekrety. Wtedy po prostu obaj uczestnicy przesyłają swoje dane wejściowe zaufanej stronie, która dokonuje obliczeń i rozdziela wyniki. Nie ma w tym żadnej magii, poza tą jedynie, że niestety, o aż tak zaufane osoby jest dziś ciężko. Zwłaszcza, jeśli jest się multimiliarderem. Porzućmy zatem marzenia o innym, piękniejszym świecie (Po co nam w takim świecie kryptografia? Przecież tam każdemu możemy ufać!) i wróćmy na ziemię.

Jak zatem rozwiązać problem Alicji i Boba nie mając nikogo zaufanego na podorędziu, a jedynie parę być-może-zakochanych? Załóżmy na początek, że Alicja i Bob są wobec siebie uczciwi i nie będą próbowali się okłamywać.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com