Zamazane Obwody: Yao’s Bezpieczne Obliczenia Dwóch Stron

Od tabel prawd do zagubionych tabel

Każysta bramki logicznej, niezależnie od tego, czy jest to AND, OR, czy XOR, może być w pełni opisana przez tabelę prawdy, która wymienia jej wyjście dla każdej kombinacji bitów wejściowych. W protokole Yao'a zagłębacz (garbler) rozpoczyna się od przypisania każdej przewodowej w obwodzie dwóch losowych etykiet kryptograficznych, jednej reprezentującej 0 i drugiej 1, więc etykieta sama w sobie nie ma znaczenia dla obserwatora zewnętrznego. Dla każdej bramki zagłębacz szyfruje wyjście etykiety odpowiadającej każdej linii tabeli prawdy za pomocą dwóch etykiet wejściowych tej linii jako klucza symetrycznego, zwykle poprzez kluczowy hash lub zaszyfrowane szyfr. Cztery uzyskane teksty szyfrujące są losowo przemieszane tak, aby ich pozycja nie zdradzała, skąd pochodzi każda z nich, tworząc to, co nazywa się zagubioną tabelą. Proces powtarza się bramka po bramce w całym obwodzie i może to zrobić offline zagłębacz przed jakimkolwiek interakcją z oceniającym. W rezultacie osoba trzymająca tylko zagubione tabele i bez etykiet uczy się absolutnie niczego o strukturze funkcji ani o pośrednich wartościach, ponieważ każdy tekst szyfrujący wygląda jak losowy szum bez dopasowanej pary etykiet wejściowych do odszyfrowania go.

Niezauważne przesyłanie: bezwzględne przekazywanie danych wejściowych

Oceniający potrzebuje zakodowanych etykiet, które odpowiadają jego własnym prywatnym bitom wejściowym, ale ich uzyskanie stanowi delikatny problem: kodujący nie powinien się uczyć, które etykiety zostały zażądane, ponieważ to ujawniłoby wejście oceniającego, a jednocześnie oceniający nie powinien otrzymać żadnej etykiety dla żadnego przewodu, ponieważ to pozwoliłoby mu ocenić obwód na danych innych niż jego własne. Niezauważny transfer rozwiązuje dokładnie ten problem. W 1-z-dwóch niezauważnym transporcie kodujący trzyma dwie etykiety dla przewodnika, a oceniający utrzymuje pojedynczy bit wyboru; po uruchomieniu protokołu oceniający uczy się tylko etykietę pasującą do jego bitu, a kodujący niczego nie dowie się, która została wybrana. Współczesne implementacje niezauważonego transferu budują go z technik wykorzystujących klucze publiczne, takich jak elipsoidalny krzyż Diffie-Hellmana, oraz sprytnych technik rozszerzania, które pozwalają na wyciągnięcie garstki drogich podstawowych OT na miliony tanich, używając jedynie operacji symetrycznego szyfrowania. Kodujący nie potrzebuje żadnego OT dla własnych wejść; kodujący po prostu wysyła dopasowane etykiety bezpośrednio, ponieważ tylko kodujący w pierwszej kolejności znał mapowanie między etykietami a wartościami bitów.

Ocena zakrzywionej obwódki

Po tym jak evaluator przypisuje jedno etykietę do każdego przewodu wejściowego, ocena przebiega krok po kroku w kolejności topologicznej bez potrzeby interakcji z zagłuszaczem. W każdym kroku evaluator posiada dokładnie jedną etykietę dla każdego przewodu wejściowego i próbuje odszyfrować wszystkie cztery szyfrotek z zakrzywionej tabeli przy użyciu tych dwóch etykie na klucz; zgodnie z konstrukcją tylko jedna szyfrotka odszyfrowuje się pomyślnie, dając pojedynczą prawidłową etykietę wyjściową dla przewodu wyjściowego danego kroku, a pozostałe trzy odszyfrowują się na śmieci, którą dobrze zaprojektowany schemat pozwala evaluatorowi wykryć i odrzucić. Ta etykieta wyjściowa następnie przekazuje się jako etykieta wejściowa do dowolnego kroku, który konsumuje ten przewód, a proces rozgałęzia się aż do oceny każdego kroku. Ponieważ evaluator widzi tylko jedną etykietę na przewodzie, losowo przypisaną i wyglądającą jak losowe bity, może obliczyć całą funkcję bez uczenia się niczego o pośrednich wartościach, nawet czy wewnętrzny przewód przenosił 0 lub 1. Ostatnie przewody wyjściowe są obsługiwane specjalnym tabelą dekodującą każdy z dwóch możliwych końcowych etykiet do odpowiadającego bitu tekstu; ujawnia to jedynie odpowiedź.

Optymalizacje, które uczyniły garbienie praktyczne

Niewykonalne garbione obwody są kosztowne: każdy element sterujący wymaga czterech zaszyfrowanych tekstów, każdy o długości zbliżonej do klucza symetrycznego, a każda bramka AND lub XOR wymaga własnego haszowania kryptograficznego. Przez dziesięciolecia badań udało się zredukować ten koszt. Technika 'punkt i permuta' dodaje losową permutację bitów do każdej etykiety, dzięki czemu evaluator może zidentyfikować, który z czterech zaszyfrowanych tekstów spróbować, bez ujawniania żadnych informacji, eliminując marnotrawne próby odszyfrowania. 'Darmowa sztuczka XOR', wprowadzona przez Kolesnikowa i Schneidera, wybiera etykiety tak, aby bramki XOR nie wymagały w ogóle szyfrowania ani komunikacji, co powoduje, że ich koszt spada prawie do zera, ponieważ XOR jest liniowy względem przesunięcia etykiet. Techniki redukcji rzędu i późniejsze połowiczne bramki opracowane przez Zahura, Rosuleka i Evansa zmniejszyły koszty bram AND z czterech zaszyfrowanych tekstów do dwóch, co w przybliżeniu dzieli komunikację dla dominującego typu bramki na pół. W połączeniu te optymalizacje przekształciły garbione obwody z ciekawostki akademickiej w fundament rzeczywistych systemów wdrażanych w celu realizacji prywatnego przecięcia zbiorów, bezpiecznych aukcji i wnioskowania z uczenia maszynowego chroniącego prywatność, gdzie dwie strony mogą wykonywać znaczące obliczenia, wymieniając jedynie niewielką ilość zaszyfrowanych danych.

Gwarancje bezpieczeństwa i ograniczenia

Protokoł Yaoa, zgodnie z opisem, zapewnia bezpieczeństwo przed półszczerywnymi wrogami, co oznacza, że obie strony przestrzegają protokołu wiernie, ale próbują pozyskać dodatkowe informacje z wiadomości, które widzą. W ramach tego modelu garbler niczego nie uczy poza tym, co wynika z ich własnego wejścia i końcowego wyjścia, a evaluator niczego nie uczy poza wyjściem samym – gwarancja ta została sformalizowana za pomocą dowodów opartych na symulacji, które pokazują, że symulator bez prywatnych danych może wygenerować transkrypt niezróżnicowany od rzeczywistego. Rozszerzając to na wrogie bezpieczeństwo, gdzie zepsuty podmiot może dowolnie odbiegać, wymagane są dodatkowe mechanizmy, takie jak garbling z wyborem cięcia dla wielu zbędnych obwodów, dowody niewiedzy zerowej lub uwierzytelniany garbling – wszystko to dodaje narzut, ale wypełnia lukę między teoretycznymi a praktycznymi wrogami. Warto również zauważyć, czego nie ukrywają garbowane obwody: rozmiar i topologia samego obwodu zwykle są publiczne, więc funkcja obliczana musi być ustalona i znana z góry, a wszelkie informacje, które można wywnioskować wyłącznie z wyniku, takie jak kto ma większe zarobki w problemie milionerów, jest celową i nieuniknioną wyciekiem inherentną do funkcji, a nie wadą protokołu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Garbled Circuits: Yao's Secure Two-Party Computation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.