Referendum w sprawie obliczeń wielopodmiotowych
26.12.2010 - Agata Murawska
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. 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.
Początkowy podział Zatem Alicja, chcąc podzielić się z Bobem -tym bitem liczby , wysyła do niego losowy bit , sama zapamiętując jako wartość. Jeśli teraz fragment znany Alicji oznaczymy jako , zaś fragment posiadany przez Boba jako , to .
Jak zanegować bit? Jak widać wystarczy, że to Alicja zaneguje przechowywany przez siebie fragment. Rzeczywiście,
A jak obliczyć koniunkcję dwóch bitów? To nieco bardziej skomplikowana procedura. Przyjrzyjmy się jej nieco uważniej: Chcemy obliczyć koniunkcję , 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! To, co chcemy uzyskać, wygląda zatem tak: Obliczenie oraz nie przedstawia większych trudności - w końcu wartości te są znane, odpowiednio, Alicji i Bobowi. Ale jak obliczyć oraz ? Załóżmy, że ustalimy następujący podział obliczeń: Trzeba wykazać się sprytem, pomysłowością i ...losowością! Chcemy policzyć . jest wartością znaną Alicji, podobnie jak ; zna tylko Bob. Przy pomocy transferu utajnionego (oznaczmy go jako ) Alicja przekazuje Bobowi parę jako swój argument . Bob wybiera tę z dwóch wartości, którą wskazuje mu wartość . Możemy tę komunikację opisać po prostu jako .
Ćwiczenie Oczywiście, transfer utajniony trzeba wykonać dwukrotnie - raz jako , zaś drugi raz jako . Podsumowanie całego protokołu obliczania koniunkcji ilustruje obrazek:
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łę:
Jak pamiętamy, zacząć trzeba od podzielenia się wiedzą o bitach wejściowych - oraz . 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ż!
(1 ocena) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com