Referendum w sprawie obliczeń wielopodmiotowych

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

Do dzieła!

O funkcji transferu utajnionego mówiliśmy przy okazji poprzedniego artykułu. Omówiliśmy tam transfer jednej z dwóch możliwych wartości między dwoma użytkownikami.
A jak uogólnić transfer między parą użytkowników na większą grupę? Zakładamy, że w grupie $ n $-osobowej każda para osób jest połączona synchronicznym kanałem bezpiecznym. Umożliwiamy także wysłanie wiadomości do wszystkich osób, będących uczestnikami komunikacji - dopuszczamy zatem istnienie kanału rozgłoszeniowego (tak zwanego broadcastu).

Co dalej? Każdy z uczestników dzieli swoje własne wejście pomiędzy pozostałe osoby, uczestniczące w wykonaniu protokołu. Następnie tworzymy podprotokoły, które umożliwiają graczom ustalenie wartości koniunkcji i negacji.

Dzielenie bitu

Początkowy podział

Zatem Alicja, chcąc podzielić się z Bobem $ i $-tym bitem liczby $ a $, wysyła do niego losowy bit $ s_i $, sama zapamiętując $ a_i \oplus s_i $ jako wartość. Jeśli teraz fragment znany Alicji oznaczymy jako $ a_{i_A} $, zaś fragment posiadany przez Boba jako $ a_{i_B} $, to $ a_i = a_{i_A} \oplus a_{i_B} $.


Negacja bitu





Jak zanegować bit?
Jak widać wystarczy, że to Alicja zaneguje przechowywany przez siebie fragment. Rzeczywiście, $ \neg a = \neg (a_A \oplus a_B) = \neg{a_A} \oplus a_B} $




Koniunkcja 1





A jak obliczyć koniunkcję dwóch bitów?
To nieco bardziej skomplikowana procedura. Przyjrzyjmy się jej nieco uważniej: Chcemy obliczyć koniunkcję $ a \wedge b $, czyli, de facto, mnożenie dwóch bitów. Żaden problem! Ale zaraz zaraz, te bity są przecież rozdzielone między dwie osoby, co więcej wynik też ma zostać podzielony!



Koniunkcja 2




To, co chcemy uzyskać, wygląda zatem tak:
$ a b = (a_A \oplus a_B) (b_A \oplus b_B) =\\(a_A b_A) \oplus (a_A b_B) \oplus (a_B b_A) \oplus (a_B b_B) =\\ c_A \oplus c_B $
Obliczenie $ a_A b_A $ oraz $ a_B b_B $ nie przedstawia większych trudności - w końcu wartości te są znane, odpowiednio, Alicji i Bobowi. Ale jak obliczyć $ a_B b_A $ oraz $ a_A b_B $?


Załóżmy, że ustalimy następujący podział obliczeń:
Koniunkcja 3

Trzeba wykazać się sprytem, pomysłowością i ...losowością!
Niech Alicja wybierze dwa losowe bity, $ R_0 $ i $ R_1 $. Naszym celem będzie obliczenie $ c_A $ i $ c_B $ jako, odpowiednio:
$ c_A = a_A b_A \oplus R_0 \oplus R_1 $
$ c_B = (a_B b_B) \oplus ( (a_A b_B) \oplus R_0)\oplus ((a_B b_A) \oplus R_1) $
W ten sposób zachowamy własność $ c_A \oplus c_B = a b $. Czy umiemy skonstruować protokół, który umożliwia Bobowi obliczenie $ c_B $? Tak!
Użyjemy do tego protokołu transferu utajnionego:

OT


Chcemy policzyć $ a b \oplus R $. $ a $ jest wartością znaną Alicji, podobnie jak $ R $; $ b $ zna tylko Bob. Przy pomocy transferu utajnionego (oznaczmy go jako $ \mathrm{OT} $) Alicja przekazuje Bobowi parę $ (R,R \oplus a) $ jako swój argument $ \mathrm{OT} $. Bob wybiera tę z dwóch wartości, którą wskazuje mu wartość $ b $. Możemy tę komunikację opisać po prostu jako $ \mathrm{OT}( (R, R\oplus a), b) $.




Ćwiczenie
Przelicz, że rzeczywiście wynik, który uzyskuje Bob to $ a b \oplus R $

Oczywiście, transfer utajniony trzeba wykonać dwukrotnie - raz jako $ \mathrm{OT}((R_0, R_0 \oplus a_A), b_B) $, zaś drugi raz jako $ \mathrm{OT}((R_1, R_1 \oplus b_A), a_B) $.

Podsumowanie całego protokołu obliczania koniunkcji ilustruje obrazek:

obliczenia

Uff, było ciężko, ale już prawie koniec. Pozostaje nam pokrótce wyjaśnić, jak obliczyć wartość funkcji przepisanej do formuły logicznej, korzystając z MPC. Załóżmy, że mamy następującą formułę:

Obwod logiczny

 

Jak pamiętamy, zacząć trzeba od podzielenia się wiedzą o bitach wejściowych - $ a_i $ oraz $ b_j $. Następnie każdy poziom bramek logicznych obliczamy, korzystając z wcześniejszych wyników (podzielonych między uczestników protokołu podobnie, jak podzielone były dane wejściowe). Kiedy dojdziemy do końca, wysyłamy do siebie ostateczne wyniki. I już!

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com