A jednak się da!

Nie wiem, ale powiem (AJSD VII)

Wyobraźmy sobie następującą wakacyjną historię miłosną, która miała prawo się zdarzyć przed nastaniem ery wszechobecnych mediów społecznościowych...

To, czego potrzeba Bogumiłowi do szczęścia, to protokół prywatnego uzyskiwania informacji (jest to próba tłumaczenia angielskiego terminu private information retrieval), czyli sposób na odpytywanie bazy danych (Dobromira) tak, aby baza danych nie wiedziała, o co ją pytamy, i mimo to dostarczyła odpowiedzi (tytułowe nie wiem, ale powiem). Oczywiście Bogumił mógłby poprosić o przesłanie całej bazy danych (czyli o przedyktowanie zawartości całego zeszytu), ale zależy mu na tym, by zminimalizować ilość przesyłanej informacji. Zaprawieni w lekturze kącika AJSD Czytelnicy nie powinni mieć trudności z przetłumaczeniem tego problemu na bardziej matematyczny język: Dobromir zna ciąg bitów $x = (x1,x2,...,xn).$ Bogumił chce poznać wartość $xi$ dla wybranego przez siebie $i ⩽n,$ jednak nie chce zdradzić Dobromirowi wartości $|i.$ Zakładamy, że każda informacja wysłana do i od Dobromira kosztuje, a Bogumił chce uczynić ten koszt jak najmniejszym. Wydaje się, że nie może on zrobić niczego istotnie lepszego od poproszenia Dobromira o cały ciąg $|x...$ Cóż, a jednak się da!

Kolegów dwóch (lub więcej)

Na początku uprośćmy sytuację i załóżmy, że Bogumił ma jeszcze jednego kolegę, Eustachego, który zna $x,$ ponadto nie zna się on z Dobromirem. Wówczas Bogumił mógłby zastosować następującą egzotyczną (i, jak się zaraz okaże, niezbyt mądrą) procedurę: losuje ciąg binarny $a = (a1,...,an)$ i prosi Dobromira o przesłanie $n xa = P k 1xkak,$ a Eustachego o $xa ,$ gdzie $|a′= (a′1,...,an′)$ to ciąg $|a,$ w którym wartość $i$ -tego bitu została zmieniona (tzn. $|a + a′= 1 i i$ oraz $|a = a′ k k$ dla $k ≠ i$ ). Okazuje się, że wówczas $xa + xa = xi,$ gdyż

n ′ ′ xa + xa = Q xk(ak + ak) = Q 2xkak + xi(ai + ai) = xi. k 1 kxi

W tej sytuacji, znając $xa$ oraz $xa ,$ Bogumił jest w stanie odtworzyć $|xi.$ Z drugiej strony, ciąg $|a$ jest losowy, więc nie dostarcza Dobromirowi żadnej informacji o $|i.$ Ponadto z punktu widzenia Eustachego ciąg $a ′$ jest losowy (co wymaga być może krótkiej chwili zastanowienia), więc on też nie uzyskuje żadnej informacji o $i.$ Zauważmy, że gdyby Dobromir i Eustachy połączyli siły, to mogliby łatwo odtworzyć $i$ - jest to jedyny indeks, na którym różnią się ciągi $a$ i $a ′.$ Zakładamy jednak, że nie komunikują się oni ze sobą, zatem Bogumił nie musi się przejmować taką ewentualnością.

Jak już wspomnieliśmy, powyższy sposób - choć wykorzystuje pewne chytre obserwacje - jest dla Bogumiła bezwartościowy. Przypomnijmy bowiem, że przesył informacji w obie strony jest kosztowny, a w zaprezentowanym protokole Bogumił wysyła dwa ciągi długości $|n,$ czyli aż $2n$ bitów. Już (dwa razy) lepiej byłoby poprosić Dobromira o przesłanie całego ciągu $|x$ !

Rzecz jasna, nie zaprezentowaliśmy powyższej idei tylko po to, by stwierdzić jej bezużyteczność. Okazuje się, że można ją tak zmodyfikować, żeby jednak coś na niej zyskać. W tym celu potrzebujemy kolejnych dwóch kolegów z dostępem do $x,$ którzy się ze sobą nie komunikują. Umieśćmy wartości $x$ w kwadratowej tablicy $-- X= [xk,l]k,lDm$ rozmiaru $m |$ gdzie $|m$ Powiedzmy, że $-- xi = xα,β.$ Tym razem Bogumił losuje dwa binarne ciągi $a$ i $|b$ długości $m$ i wysyła je Dobromirowi. Dobromir oblicza $xa,b = P xk,lakbl. k,lDm$ Podobnie jak poprzednio niech $′ a$ powstaje z $a$ przez zmianę $|α$ -tego bitu, a $′ b$ powstaje z $|b$ przez zmianę $β$ -tego bitu. Do kolejnych znajomych Bogumił wysyła pary ciągów bitów $(a,b), (a′,b), (a,b′)$ i $(a′,b′),$ otrzymując od nich $|xa,b,xa ,b,x- a,b$ oraz $|x- . a,b$ Wówczas w sumie $xa,b + xa ,b + x +x- a,b a,b$

dla $|k≠ α,l ≠ β$ składnik $xk,lakbl$ liczony jest cztery razy (występuje w każdej składowej sumie), więc nie jest liczony wcale,
dla $l≠ β$ składnik $-- x α,laαbl$ liczony jest dwa razy, tak samo jak $x-α,la′bl α$ ; obu nie musimy zatem liczyć,
dla $k ≠α$ składniki $-- xk,βakbβ$ i $-- ′ xk,βakbβ$ liczone są dwa razy, więc podobnie jak w poprzednim punkcie nie wpływają na wynik,
wśród liczb $′ ′ ′ ′ aαbβ,a αbβ,aαbβ,aαbβ$ są trzy zera i jedynka, a zatem suma składników $-- -- x α,β aαbβ,x α,βa′αbβ,$ $-- -- |xα,β aαb ′β,xα,β a′αb ′β$ daje $-- xα,β.$

Powyższe rozważania dowodzą, że $xa,b + xa ,b + xa,b + xa ,b = xα,β .$ Bogumił uzyskuje zatem szukaną wartość $x- = x , α,β i$ a jego koledzy nie dowiadują się niczego o $α ,β$ (co uzasadniamy tak jak poprzednio). Tym razem wykorzystujemy cztery bazy danych, ale za to rozmiar naszej komunikacji to $√ -- |4(2 n+ 1).$ W analogiczny sposób, poprzez zapisanie $|x$ w $d$ -wymiarowej tablicy i wykorzystanie $|2d$ baz danych, możemy dokonać prywatnego uzyskania informacji przy komunikacji rozmiaru $d d√ -- 2 (d n+ 1).$ Widzimy zatem, że możemy w ten sposób uzyskać dowolnie mały wykładnik przy $|n,$ jednak kosztem wykładniczo rosnącej liczby potrzebnych, nieskomunikowanych baz danych.

...a może jednak wystarczy jeden?

Co, jeśli nie jesteśmy w tak wygodnej sytuacji i Bogumił jest skazany wyłącznie na Dobromira? Czy możemy istotnie zmniejszyć koszt transmisji, mając do czynienia tylko z jedną bazą danych? Cóż, gdyby było inaczej, temat niekoniecznie zasługiwałby na prezentację w naszym kąciku. Okazuje się, że nawet mając do dyspozycji jeden egzemplarz bazy danych, możemy dokonać "prywatnego zapytania" kosztem rzędu rozmiaru bazy danych podniesionego do dowolnie małej potęgi. Po raz pierwszy taki magiczny sposób zaproponowali Eyal Kuszilewić i Rafail Ostrowski w 1997 roku. Aby dokonać jego prezentacji, musimy przedstawić małe przypomnienie z teorii liczb (patrz również artykuł o commicie w Delcie 11/2018).

Wykorzystując przedstawioną teorię, możemy zaproponować następujący protokół prywatnego uzyskiwania informacji dla jednej bazy danych (Dobromira):

(a): Bogumił i Dobromir umawiają się na reprezentację ciągu $x$ w postaci tablicy $|X= [xk,l]kDs,lDt.$ Załóżmy, że $xi = xα,β$ ;
(b): Bogumił wybiera duże liczby pierwsze $p,q$ (których reprezentacja dwójkowa ma $K$ bitów) i oblicza $n | = pq,$ po czym wybiera losowo $y1,...,ys⩽ n$ w taki sposób, że $|y ∈ ℛ α n$ oraz $y ∈ 𝒬 k n$ dla $|k ≠α .$ Następnie przekazuje $n$ oraz wszystkie liczby $y1,...,ys$ Dobromirowi. Zauważmy, że zgodnie z naszą uwagą Dobromir (nieznający $p,q$ ) dla żadnego $k ⩽ s$ nie jest w stanie stwierdzić, czy $|yk∈ 𝒬n,$ nie dowie się zatem niczego o $α$ ;
(c): Dla każdego $r ⩽t$ Dobromir oblicza $- |zr = Lsk 1y1+xk;r k$ modulo $n.$ Jest to iloczyn wszystkich wysłanych liczb $|y , k$ przy czym niektóre - te, którym w $|r$ -tej kolumnie odpowiada jedynka - mnożone są "w kwadracie". Ponieważ tylko $|yα$ nie jest kwadratem modulo $n,$ więc $zr$ jest kwadratem tylko wtedy, gdy $yα$ jest mnożone "w kwadracie", czyli gdy $x = 1 α,r$ ;
(d): Bogumił sprawdza, czy $|zβ$ jest kwadratem (może to uczynić, gdyż zna $p,q$ ). Jeśli tak, to $x α,β$ wynosi 1, w przeciwnym przypadku 0.

Przedstawiona komunikacja zajmuje $Ks + Kt$ bitów, czyli w ten sposób, biorąc $√ -- s = t≈ n,$ możemy już osiągnąć komunikację rozmiaru $√ -- |2K n.$ A można jeszcze lepiej! Zauważmy, że spośród skonstruowanych przez Dobromira liczb $|z1,...,zt$ Bogumiła interesuje tylko $zβ,$ przy czym nie chce on, by Dobromir poznał $β.$ Toż to brzmi dokładnie jak wyjściowy problem, więc rzecz pachnie rekurencją na kilometr! Bogumił może zastosować ten sam protokół dla ciągu $z1,...,zt,$ aby poznać $zβ.$ Wówczas rozmiar komunikacji jest rzędu $√ - Ks + K ⋅2K t$ ; optymalizując ze względu na $s,t,$ pod warunkiem $st = n,$ dostajemy koszt $5~3√ 3- |3K n.$ W ten rekurencyjny sposób możemy dowolnie zbijać wykładnik przy $n$ (odwrotnie proporcjonalnie do głębokości rekurencji); niestety, kosztem puchnącego (z grubsza liniowo wraz z głębokością rekurencji) wykładnika przy $K.$ Cóż, odwołując się do klasyka, nie udało nam się przyrządzić zupełnie darmowego obiadu, mamy jednak nadzieję, że Czytelnicy i tak docenią (podobnie jak Bogumił) chytrość i elegancję przedstawionych protokołów.