Kryptografia II stopień

W12. Obliczenia wielostronne i OT

OT

Oblivious Transfer. Transfer utajniony. Odbiorca poznaje wybraną wartość, a nadawca nie poznaje jego wyboru.

Interfejs jest teraz interaktywny. Dla funkcji $f$ dwie strony wykonują algorytmy $\mathsf P_1(pp,x)$ i $\mathsf P_2(pp,y)$, a nie jedno wspólne wywołanie z jawnymi $x,y$ w tym samym urządzeniu. Schemat określa przygotowanie parametrów, lokalne stany, komunikaty i to, która strona otrzymuje wynik. Nie dopisujemy tu Sign lub Dec, jeśli nie należą do konkretnej realizacji. Dopiero wewnątrz protokołu mogą zostać użyte podpisy, szyfrowanie lub OT.

Alicja ma $x$, Bob $y$, a wyznaczony odbiorca poznaje $f(x,y)$. Prywatność porównuje widok rzeczywisty z możliwym do zasymulowania na podstawie własnego wejścia i dozwolonego wyniku. Wynik sam może dużo ujawniać. Dla jednoelementowego zbioru liczność przecięcia ujawnia bit przynależności.

OT: jedno z dwóch

Najpierw model. Strona półuczciwa wykonuje polecenia protokołu, ale analizuje cały zapamiętany widok. Strona złośliwa może też zmienić komunikaty lub przerwać wykonanie. Poniższy rachunek wyjaśnia poprawność i intuicję prywatności przy uczciwym wykonaniu. Nie stanowi samodzielnego dowodu dla złośliwych stron. OT (oblivious transfer) ogranicza informację uzyskaną przez odbiorcę, a jednocześnie ukrywa jego wybór przed nadawcą.

Nadawca ma $m_0,m_1$, odbiorca wybiera $b$. Odbiorca poznaje $m_b$, nie drugą wiadomość. Nadawca nie poznaje $b$.

Nadawca losuje swój tajny wykładnik $a$ i wysyła $A=g^a$. Odbiorca losuje własny tajny wykładnik $x$ i odsyła element $B$ zależny od wyboru $b$. Nadawca wyznacza dwa elementy $Z_0,Z_1$, a odbiorca tylko $Z$ odpowiadający wybranemu indeksowi. Dydaktyczny przepływ DH zapisujemy następująco:

Dla $b=0$ odbiorca uzyskuje $Z_0$, dla $b=1$ otrzymuje $Z_1$. KDF wiąże sesję i indeks, po czym wyznacza klucze szyfrowania. Jednostajne $x$ daje ten sam rozkład $B$ dla obu wyborów. Ochrona nieotrzymanej wiadomości wymaga argumentu obliczeniowego. Model złośliwy i walidacja punktów nie wynikają z samej równości.

Rozpiszmy role. Nadawca losuje sekret $a$ i wysyła $A$. Odbiorca losuje sekret $x$, wybiera bit $b$ i odsyła $B$. Nadawca oblicza oba $Z_i$, choć nie zna $b$. Odbiorca oblicza $Z$ i zna tylko klucz odpowiadający swojemu wyborowi. Obie strony stosują tę samą funkcję wyprowadzania klucza do kodowania elementu grupy, identyfikatora sesji i indeksu $i$. Nadawca szyfruje osobno $m_0,m_1$ pod tak otrzymanymi kluczami i wysyła oba szyfrogramy. Odbiorca odszyfrowuje wybrany szyfrogram kluczem wyprowadzonym z $Z$ oraz $b$.

Widać zatem trzy etapy komunikacji: $A$ do odbiorcy, $B$ do nadawcy, dwa szyfrogramy do odbiorcy. Równość $Z=Z_b$ zapewnia poprawność. Analiza prywatności wymaga jeszcze odpowiednich założeń o grupie, KDF i szyfrowaniu. Konkretne reguły oraz dowód podaje cytowana praca Chou–Orlandiego.

W garbled circuit OT dostarcza jedną etykietę wejściowego przewodu. Bramki przekształcają etykiety w następne. Wydanie obu etykiet zmienia informację dostępną odbiorcy.

Od OT do obwodu

Jak czytać obwód: reprezentujemy funkcję jako bramki logiczne. Każdy przewód ma dwie niezależne etykiety, oznaczające 0 i 1, lecz ich znaczenie jest ukryte przed wykonawcą. Dla bramki o dwóch wejściach twórca przygotowuje zaszyfrowaną tabelę wynikowych etykiet. Wykonawca posiada po jednej etykiecie wejściowej i może przejść do odpowiedniej etykiety wyjściowej. Dopiero na końcu poznaje uzgodnione znaczenie wyniku. To opis idei. Poprawne szyfrowanie tabel, kolejność wierszy i zabezpieczenia złośliwego twórcy wymagają konkretnego protokołu.

Model półuczciwy zakłada wykonywanie poleceń protokołu przy analizie całego zapamiętanego widoku. Model złośliwy pozwala wybierać inne komunikaty i przerywać wykonanie. Prywatność, poprawność wyniku, odporność na przerwanie i sprawiedliwe otrzymanie wyniku są osobnymi celami. Nie każdy protokół MPC zapewnia je wszystkie.

MPC

Multi-Party Computation. Obliczenia wielostronne.

Rachunek na udziałach

Udział nie jest osobnym szyfrogramem. Aby podzielić $x\in\mathbb Z_q$ między dwie osoby, losujemy jednostajnie $x_1$, a potem wyznaczamy $x_2=x-x_1\pmod q$. Pierwsza osoba dostaje tylko $x_1$, druga tylko $x_2$. Każdy udział osobno ma rozkład niezależny od $x$. Razem pozwalają obliczyć $x=x_1+x_2$. Zapis $[x]$ oznacza ten rozdzielony stan, nie wartość znaną każdemu uczestnikowi.

Na przykład dla $q=23$ i $x=7$ można dostać udziały 19 i 11, bo $19+11\equiv7\pmod{23}$. Otwarcie oznacza przekazanie udziałów i odtworzenie wartości. Otwarcie $[x]$ ujawniłoby sekret. Dlatego poniżej otwieramy tylko zamaskowane różnice. Dodawanie $[x]+[y]$ oznacza lokalne dodawanie odpowiednich udziałów. Mnożenie przez jawną liczbę $d$ oznacza mnożenie każdego udziału przez $d$.

Publiczną stałą $t$ reprezentujemy umownie przez $[t]=(t,0)$. Dodanie jej do obu udziałów byłoby błędem, ponieważ odtworzona suma wzrosłaby o $2\cdot t$. Rozdział W13 wprowadzi inny podział, Shamira, pozwalający ustalić próg odtwarzania. Nie jest potrzebny do poniższego rachunku dwóch udziałów.

Dla udziałów $x=x_1+x_2$ dodawanie wykonujemy lokalnie. Iloczyn nie jest sumą lokalnych iloczynów, bo brakuje wyrazów mieszanych. Jednorazowa trójka Beavera $(a,b,c)$ ma $c=a\cdot b$ i również jest podzielona na udziały. Otwieramy $d=x-a,e=y-b$:

Publiczny składnik $d\cdot e$ włączamy raz do sumy udziałów. Losowe niezależne maski ukrywają wejścia. Powtórne użycie trójki ujawnia różnice wejść. Złośliwy model wymaga dodatkowego sprawdzania.

W PSI opartym na DH haszujemy elementy zbioru do grupy i porównujemy podwójnie przekształcone punkty. W PSI-cardinality odbiorca ma poznać tylko liczbę. Tasowanie musi usuwać konkretne powiązanie wyniku z wejściem. Nie jest samodzielnym dowodem prywatności.

PSI

Private Set Intersection. Prywatne wyznaczanie przecięcia zbiorów.

Źródła: Chou–Orlandi, garbled circuits, kurs rozproszony.

W12a. Garbled circuits: obliczenie bez odczytywania wejść

Funkcjonalność. Alicja zna bity $a,c$, Bob zna bit $b$. Bob ma poznać tylko uzgodniony wynik $d=(a\land b)\oplus c$, oprócz informacji wynikającej z jego własnego wejścia. Obwód i liczba bramek są jawne. Nie próbujemy ukrywać samej funkcji. Wykonanie przenosi po przewodach losowe etykiety, zamiast jawnych bitów.

Dla przewodu $w$ twórca losuje dwie etykiety $K_w^0,K_w^1$. Indeks górny oznacza tutaj wartość logiczną, nie potęgę. Wykonawca dostaje tylko jedną z nich. Twórca pamięta obie i ich znaczenie. Nie wysyłamy tabeli znaczeń przewodów wewnętrznych.

Publiczny obwód oznaczamy przez $F$. Każda jego bramka $j$ otrzymuje zaszyfrowaną tabelę $T_j$. Zbiór tych tabel tworzy zakodowany obwód $\widetilde F$. Mapa $e_{\mathrm{in}}$ przypisuje bitom wejściowym etykiety. Osobna mapa $d_{\mathrm{out}}$ pozwala odczytać jedynie bity wyjściowe. Ciągi etykiet na wejściu i wyjściu obliczenia oznaczamy odpowiednio $X$ i $Y$.

Jedna etykieta nie mówi, czy oznacza zero

W wariancie point-and-permute etykieta zawiera bit wyboru $p_w(v)=v\oplus\pi_w$, gdzie $\pi_w$ jest tajnym, losowym bitem danego przewodu. Bit wyboru wskazuje wiersz, lecz sam nie ujawnia $v$. Dwie etykiety tego samego przewodu mają przeciwne bity wyboru. Ich pozostałe części są losowe.

$\mathcal K$ oznacza wyprowadzenie klucza szyfrowania z numeru bramki i obu etykiet. To nie jest używana wcześniej skalarna $\mathcal H$. $\mathsf{Seal}$ oznacza szyfrowanie etykiety z kontrolą integralności w poniższym demonstratorze. Numer obwodu, numer bramki i indeks wiersza wiążemy z kontekstem. Dwie znane etykiety wystarczają do otwarcia jednego wiersza, a otrzymana etykieta staje się wejściem następnej bramki.

Dla bramki $j$ o funkcji $g_j$, wejściach $u,v$ i wyjściu $w$ tworzymy cztery zaszyfrowane etykiety. W tabeli $T_j$ indeksujemy wiersze bitami wyboru z etykiet wejściowych:

Od bramki logicznej do czterech szyfrogramów

Bramka o dwóch wejściach ma cztery pary możliwych bitów: $(0,0)$, $(0,1)$, $(1,0)$ i $(1,1)$. Dla każdej pary twórca najpierw oblicza bit wyjściowy. Następnie wybiera odpowiadającą mu etykietę przewodu wyjściowego i szyfruje ją kluczem wyprowadzonym z dwóch etykiet wejściowych. Nie szyfrujemy tutaj samego bitu wyniku. Szyfrujemy etykietę, która może później posłużyć jako wejście kolejnej bramki.

AND

and. I, czyli koniunkcja logiczna. To angielskie słowo, nie akronim. Bramka AND zwraca 1 tylko wtedy, gdy oba wejścia mają wartość 1.

Na przykład dla AND i wejść $(1,1)$ para $(K_u^1,K_v^1)$ pozwala uzyskać $K_w^1$. Pozostałe trzy pary prowadzą do $K_w^0$, ale ich szyfrogramy nie muszą wyglądać podobnie. W demonstratorze każdy wiersz używa własnego klucza oraz losowego IV. Nie wolno traktować kolejności $(0,0),(0,1),(1,0),(1,1)$ w tabeli prawdy jako jawnego porządku wysyłanych szyfrogramów. Bity wyboru zmieniają adresy wierszy, a ich związek z bitami logicznymi pozostaje ukryty.

Podstawową ideę zastąpienia tabeli prawdy zaszyfrowanymi etykietami opisują Lindell i Pinkas, §1 i tabela 1. Ich opis używa zagnieżdżonego szyfrowania. Powyższy zapis $\mathsf{Seal}$ odpowiada lokalnemu wariantowi demonstracyjnemu z kluczem wyprowadzanym z obu etykiet, a nie dosłownemu przepisaniu tamtej konstrukcji. Poniższy obwód oblicza rzeczywiste szyfrogramy w WebCrypto.

Przepływ od dwóch osób do jednego wyniku

1. Przygotowanie. Alicja tworzy etykiety i zaszyfrowane tabele obu bramek. Publikuje tabele, ale nie znaczenia etykiet wewnętrznych.
2. Wejścia Alicji. Przekazuje Bobowi $K_a^a$ i $K_c^c$. Nie przekazuje pozostałych etykiet tych przewodów.
3. Wejście Boba. OT z pary $(K_b^0,K_b^1)$ dostarcza tylko $K_b^b$. Alicja nie poznaje wyboru. Bob nie otrzymuje drugiej etykiety.
4. Obliczenie. Bob otwiera właściwy wiersz AND, następnie właściwy wiersz XOR. Nie musi znać wartości pośredniego bitu.
5. Odczyt. Uzgodnione dekodowanie końcowego przewodu pozwala odczytać $d$. Wynik nie powinien ujawniać dodatkowych etykiet.

W demonstratorze tabele rzeczywiście powstają przez SHA-256 i AES-GCM w WebCrypto. Etykiety mają 128 bitów, w tym bit wyboru. Jest to dydaktyczne kodowanie czterech wierszy, a nie implementacja zoptymalizowanego protokołu Yao z dowodem bezpieczeństwa. OT jest lokalnie symulowaną usługą wydającą jedną etykietę. Jedna przeglądarka zna oba wejścia, więc nie zapewnia między nimi izolacji. Test uszkodzonego szyfrogramu sprawdza odrzucenie przez AEAD, nie odporność na złośliwego twórcę całego obwodu.

Co dokładnie ma wykazać dowód

Nie wystarczy, że Bob nie widzi napisu „0” ani „1”. Dla półuczciwego Boba symulator ma odtworzyć jego widok, znając tylko $b$ i dozwolony wynik $d$. Dla półuczciwej Alicji symulujemy widok na podstawie jej wejścia i jej dozwolonego wyjścia. Bezpieczeństwo OT ukrywa wybór Boba. Bezpieczeństwo garblingu ukrywa nieaktywne etykiety i wartości wewnętrzne. Argument hybrydowy zastępuje odpowiednie zaszyfrowane etykiety, z zachowaniem zgodności aktywnej ścieżki. To nie jest teza, że wszystkie wiersze można niezależnie zastąpić zerami.

Złośliwy twórca może przygotować inną funkcję. Szyfrowanie tabel samo temu nie zapobiega. Potrzebna jest konkretna metoda sprawdzania obwodów, zgodności wejść i poprawności OT. Przykładem jest rodzina technik cut-and-choose: otwieramy losowo wybrane obwody kontrolne, pozostałe służą obliczeniu. Parametry, sposób agregowania wyników i kontrola wejść decydują o błędzie bezpieczeństwa. Samo pokazanie jednego poprawnego obwodu nie certyfikuje pozostałych.

Precyzyjny opis i dowód dla modelu półuczciwego podają Lindell i Pinkas, A Proof of Security of Yao's Protocol for Two-Party Computation. Historyczny punkt odniesienia to Yao, How to Generate and Exchange Secrets, FOCS 1986. Konstrukcji demonstracyjnej nie przypisujemy automatycznie twierdzenia z tych prac.

FOCS

Foundations of Computer Science. Podstawy informatyki. Skrót w nazwie sympozjum teoretycznego.

Free-XOR i half-gates: gdzie znika komunikacja

W Free-XOR etykiety mają wspólną, tajną różnicę $\Delta$: $K_w^1=K_w^0\oplus\Delta$. Dla XOR można ustalić $K_w^0=K_u^0\oplus K_v^0$. Wtedy

Nie wysyłamy tabeli XOR. Cena to skorelowane etykiety i właściwe założenia dla całego garblingu. Nie wolno bez analizy wkleić tej korelacji do dowolnego szyfrowania tabel. Technika half-gates łączy darmowe XOR z dwoma blokami na AND. To dwa uzupełniające się usprawnienia, nie dwa różne cele bezpieczeństwa.

Blok ma długość parametru etykiety $\kappa$. Tabela nie obejmuje OT, wejść, dekodowania ani zabezpieczeń złośliwego modelu. Dla $n_\land$ bramek AND koszt tabel half-gates to $2\cdot\kappa\cdot n_\land$ bitów. To koszt komunikacji, nie całego obliczenia. Demonstrator powyżej pozostaje czterowierszowy i ma dodatkowy narzut IV oraz znaczników AES-GCM. Nie należy przypisywać mu podanych rozmiarów zoptymalizowanych tabel. Źródło optymalizacji: Zahur–Rosulek–Evans, Two Halves Make a Whole.

Powiązania: C12, L6.