A jednak się da!

O obliczeniach wielopodmiotowych (AJSD IX)

Niniejszy odcinek jest ostatni z serii. Przez niemal rok, wraz z Łukaszem Rajkowskim, próbowaliśmy pokazać Czytelnikowi, co ciekawego, a przede wszystkim - co zaskakującego, wiąże się z kryptologią. Naszą wielką nagrodą będzie, gdy - po przeczytaniu tych 9 odcinków - choć niewielka część Czytelników chociaż przez chwilę zawaha się, gdy w życiu codziennym będzie stwierdzać, że czegoś się nie da...

Punktem wyjścia naszych rozważań będzie podział sekretu pomiędzy $|n$ osób (o którym pisaliśmy więcej w $|∆211$ ). To znaczy: załóżmy, że chcemy pewną tajną liczbę

x∈ {0,1,...,p − 1}

$(p$ to pewna ustalona duża liczba pierwsza, np. $|p = 19134702400093278081449423917)$ rozproszyć pomiędzy zbiór osób $|A$ w taki sposób, aby:

każda z nich dostała pewien udział w postaci liczby $x ∈{0,...,p − 1}, i$ oraz
dowolna ich $t$ -osobowa podgrupa nie była w stanie odtworzyć $x$ (analizując swoje udziały), ale już (każda) podgrupa $(t +1)$ -osobowa zawsze mogła to zrobić.

Powyższy problem da się rozwiązać dla dowolnego $0 ⩽ t⩽ (n −1),$ szczegóły znajdują się w artykule cytowanym wyżej. Ogólna idea (pochodząca od Adiego Shamira) polega na tym, że losujemy dowolny wielomian $w$ stopnia $t |$ (o współczynnikach $wi$ ) o wyrazie wolnym równym $|x.$ Następnie ustalamy dowolne niezerowe (i parami różne) elementy $|yi$ i określamy

xi = (w(yi)

Okazuje się, że tak zdefiniowane udziały spełniają nasze pierwotne założenia. Dziś jednak będziemy chcieli osiągnąć znacznie więcej. To znaczy, zapragniemy na podzielonych sekretach rachować!

Przyjmijmy, że sekrety są dwa: $|a,b ∈{0,...,p − 1}$ oraz że osoba o numerze $|i$ ma udziały w obu (w postaci liczb $ai,bi∈ {0,...,p −1}$ ). Chcemy teraz opracować taki protokół, który umożliwi wszystkim $|n$ osobom dokonanie wspólnych obliczeń, po których osoba $i$ otrzyma pewną wartość $|ci.$ Oczekujemy, że tak obliczone elementy ${ci}1DiDn$ razem będą stanowić podział sekretu dla (rozważamy trzy przypadki):

1.: $|c = a + b (mod p)$ ;
2.: $|c = k ⋅a (mod p)$ $(k$ jest publicznie znaną stałą);
3.: $|c = a ⋅b (mod p).$

Banalne rozwiązanie polega na odtworzeniu $a$ i $|b,$ obliczeniu $c$ oraz dokonaniu nowego podziału, według oryginalnego protokołu. Nasz cel jest jednak ambitniejszy: chcemy rozproszyć $c,$ ale w taki sposób, aby bezpośrednia informacja o $a$ i $|b$ nie została na żadnym etapie przez nikogo (przez żadnego uczestnika bądź ich podgrupy o ograniczonej liczebności) jawnie odtworzona. Jak to zrobić?

Przypadek pierwszy i drugi jest łatwy (Zajmiemy się tylko pierwszym. Niech drugi pozostanie jako łatwe ćwiczenie.) i nie wymaga nawet żadnej komunikacji pomiędzy stronami. Wystarczy, że osoba $i$ przyjmie $|c = a + b mod p i i i$ i wszystko będzie w porządku. Dlaczego? Przypomnijmy sobie tylko, czym jest $ai$ oraz $bi.$ Wiemy przecież, że

ai = wa(yi)(

dla pewnych wielomianów $wa$ oraz $wb. |$ Wtedy oczywiście

ai +bi = (wa ,

co oznacza, że (z definicji) elementy $ai + bi$ stanowią podział sekretu dla wyrazu wolnego wielomianu $(wa$ modulo $p.$ Ten jednak wynosi $|(a+ b)$ modulo $p,$ gdyż wyrazem wolnym $wa$ musi być $a, |$ a wyrazem wolnym $w$ jest $b.$

Powyższe rozwiązanie rodzi pokusę, aby analogicznie rozwiązać przypadek trzeci. To znaczy, aby każda z osób przyjęła $c = a ⋅b mod p, i i i$ jako że $|a⋅b (mod p)$ jest wyrazem wolnym wielomianu $|wa$ modulo $|p.$ Niestety, jest to rozwiązanie błędne. Problem bierze się stąd, że mnożenie dwóch wielomianów stopnia $t$ daje wielomian stopnia $|2t.$ A my przecież chcemy koniecznie otrzymać stopień $t$ (w przypadku dodawania ten problem nie występował)! Rozwiązanie jest tutaj nieco bardziej skomplikowane.

Mnożenie podzielonych sekretów

Pierwszy krok jest taki sam, jak w naiwnym rozwiązaniu wyżej. To znaczy, faktycznie każdy z uczestników protokołu mnoży $ai$ przez $|bi,$ otrzymując pewne $gi.$ Zanim przejdziemy do szczegółów kolejnego kroku, potrzebujemy jeszcze kilku oznaczeń. Oznaczmy więc wielomian $|(wa$ modulo $p$ przez $|h.$ Wówczas wyraz wolny $h$ to $a ⋅b$ modulo $p$ (tak jak potrzeba), natomiast wartość $gi = ai ⋅bi = wa(yi)$ jest znana osobie $i.$ Problemem jest tylko stopień wielomianu

2t2t )=(a⋅bmodp)+h1⋅X+h2⋅X+...htX+...h2tX, h(X

który wynosi $|2t.$ Wprowadźmy więc (trochę na siłę) nowy wielomian:

2t )=(a⋅bmodp)+h1⋅X+h2⋅X+...htX, v(X

który powstał przez zwykłe wymazanie ostatnich $|t$ jednomianów wielomianu $h.$ Byłoby oczywiście świetnie, gdyby osoba $i$ potrafiła (za pomocą jakiegoś protokołu) po prostu bezpiecznie obliczyć wartość $|v(yi).$ Okazuje się, że jest to wykonalne! Co więcej, nie aż tak trudne obliczeniowo i nie wymaga dużej komunikacji między uczestnikami protokołu. Kluczowa jest tu (dość zaskakująca) obserwacja, że każde $v(yi)$ jest kombinacją liniową elementów $|{gi}i 1...n.$

Gdy już to wiemy, to dalej jest z górki. Dodawanie i mnożenie przez stałą sekretów potrafimy już wykonywać. Trzeba więc tylko rozproszyć każde $|gi$ i zastosować (być może wielokrotnie) dwa proste przypadki rozważane wyżej (oraz na koniec wysłać osobie $i$ odpowiednie udziały do odtworzenia $|v(yi)$ ). Dokładne wyjaśnienie, ze względu na techniczny charakter zagadnienia, musimy niestety pominąć. Wierzymy jednak, że dokładne odtworzenie wszystkich kroków tego przypadku może być bardzo pouczające. Szczegóły znajdują się w pracy "A Full Proof of the BGW Protocol for Perfectly-secure Multiparty Computation" autorstwa Gilada Asharova oraz Yehudy Lindella.

Po co to wszystko?!

Przyjmijmy, że każda z osób $|A$ wybrała swój własny argument $|si ∈{0,...,p − 1}$ i rozproszyła go wśród wszystkich pozostałych osób. Co umożliwiają nam protokoły naszkicowane wyżej? Otóż na pewno grupa może (wspólnie) obliczyć chociażby $s1 + 3⋅s7$ modulo $|p$ czy $|s + 23⋅s ⋅s ⋅s + s44 2 1 3 5 100$ modulo $p$ (w taki sposób, że żadne obliczenia pośrednie nie są nikomu znane - wszak wszystko odbywa się dla rozproszonych wartości), bo potrafi dodawać, skalować przez stałą i mnożyć sekrety. Jak wiele w taki sposób można policzyć? Okazuje się, że … wszystko!

Obliczenia w ciele modulo $|p$ mają taką cechę, że każdą funkcję (oczywiście o zbiorze wartości ${0, ...,p − 1}$ ) da się zapisać jako wielomian, a więc jako złożenie (być może bardzo wielu) dodawań, skalowań przez stałą i mnożeń (wszystko modulo $|p$ ). Innymi słowy: z faktu, że znamy protokoły dla trzech przypadków z pierwszej części artykułu, wynika, że potrafimy obliczyć zupełnie dowolną funkcję rozproszonych argumentów. Stąd już tylko krok do protokołów na np. granie w pokera przez Internet bez zaufanej strony czy bezpieczne aukcje internetowe bez serwera zbierającego i w zaufaniu porównującego oferty.

Science-fiction

Wyżej ledwie naszkicowaliśmy ideę obliczeń wielopodmiotowych (i to jeszcze w mniej ciekawym, bo pasywnym przypadku - szczegóły na jednym z marginesów). Póki co nie są one jeszcze bardzo praktyczne, ale powoli zbliżamy się do momentu, gdy (na razie) proste ich zastosowania będą możliwe do codziennego wykorzystania. Chcielibyśmy jednak mocno zaznaczyć, że drzemie w nich potencjał niemal rewolucyjny.

Rozpraszanie obliczeń i przechowywania danych czy ogólniej - pozbywanie się zaufanych stron z cyfrowego świata jest wszak (skromnym zdaniem autora tego tekstu) najważniejszym wyzwaniem rewolucji cyfrowej XXI wieku.