Referendum w sprawie obliczeń wielopodmiotowych

26.12.2010 - Agata Murawska
TrudnośćTrudnośćTrudnośćTrudność

A co z referendum?

Można stwierdzić, że skoro zliczanie sumy jedynek da się sprowadzić do stworzenia obwodu logicznego, to problem jest rozwiązany. Z drugiej strony wydaje się, że powyższa metoda, jakkolwiek dość ogólna, ma jedną poważną wadę - jest POTWORNIE wolna! Może da się zatem podejść do sprawy nieco mniej ogólnie i wymyślić prostą metodę, która zdąży obliczyć wynik przed następnymi wyborami?

Przypomnijmy dane do zadania:
Mamy $ n $ osób, wyrażających swoją opinię na dany temat. Zostaje im zadanie jedno pytanie, na które mogą odpowiedzieć “tak” (co odpowiada wartości $ 1 $) albo “nie” ($ 0 $). Naszym zadaniem jest obliczenie, ile było głosów “za” - a zatem sumy pewnej liczby jedynek.

Niech $ x_i $ oznacza głos $ i $-tego uczestnika protokołu. Chcemy zatem obliczyć $ \Sigma_{i=1}^{n} x_i $. Jak?

Wybiera się (w dowolny sposób) liczbę $ m > n $.

Każdy z uczestników dzieli swój głos $ x_i $ na $ n $ głosów $ x_{(i,1)} \dots x_{(i,n)} $ w taki sposób, że $ \Sigma_{j=1}^n x_{(i,j)} \mod m = x_i $, a następnie rozsyła fragmenty do wszystkich w taki sposób, że osoba $ j $ dostaje od osoby $ i $ fragment $ x_{(i,j)} $.

Każdy z użytkowników systemu zna swoją składową każdego z oddanych głosów. Liczy zatem sumę tych składowych, czyli $ s_i = \Sigma_{j=1}^n x_{(i,j)} \mod m $

Wszystkie wartości $ s_i $ zostają upublicznione - przesłane wspólnym kanałem rozgłoszeniowym. Aby poznać wynik referendum pozostaje obliczyć $ \Sigma_{i=1}^n s_i \mod m $

Proste, prawda? Dowód poprawności tego protokołu jest stosunkowo nieskomplikowany i może być wykonany jako proste ćwiczenie.
Wskazówka

Czy to aby bezpieczne?

Można zastanawiać się dalej - na ile wiarygodne są obliczone przez nas wartości? Jaki poziom bezpieczeństwa jesteśmy w stanie zapewnić, jeśli wiemy, że część użytkowników systemu jest w zmowie i udostępnia sobie na wzajem poznane informacje? Ilu z nich może współpracować bez zakłócenia pracy systemu, jeśli oszukują i działają niezgodnie z protokołem?

Nie wchodząc w matematyczne szczegóły powiemy tylko, że umiemy projektować protokoły, które pozostają bezpieczne nawet, jeśli połowa użytkowników jest w zmowie i przekazuje sobie wszystke dane (prywatne, jak i uzyskane za pośrednicwem protokołu).

Przy zapewnianiu bezpieczeństwa mając do czynienia z tak zwanymi przeciwnikami aktywnymi, czyli nie działającymi według zasad protokołu radzimy sobie, póki jest ich mniej, niż $ \frac{n}{3} $.

Dokąd to wszystko zmierza?

Jak łatwo się domyślić na podstawie powyższego protokołu, w tej chwili rozważania dotyczące obliczeń wielopodmiotowych koncentrują się raczej na szukaniu wydajnych i bezpiecznych rozwiązań znanych problemów, niż wynajdywaniu kolejnych metod uniwersalnych. W tym wypadku stwierdzenie “kiedy coś jest do wszystkiego, to jest do niczego” sprawdza się niemal bezbłędnie.

Zadania sprawdzające

  1. W protokole do obliczania wyników referendum, nieuczciwy uczestnik może łatwo oszukać system i zmienić wyniki. W jaki sposób?
  2. Jak zmieni się protokół do obliczania wyników referendum, jeśli zechcemy użyć go do obliczenia średniej pensji w grupie $ n $ pracowników, o których wiemy, że żaden nie zarabia więcej, niż 10 000 zł?

Artykuł powstał częściowo na podstawie notatek doktora Stefana Dziembowskiego do wykładów na Uniwersytecie Warszawskim oraz University of Rome - La Sapienza.

Obrazki bramek logicznych i sumatora dwubitowego pochodzą z wikipedii.
Źródła oraz informacja o licencji, na jakiej zostały opublikowane:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com