Protokół GMW i transfer niejawny

Protokół Goldreich-Micali-Wigderson (GMW) oblicza obwody boolowskie za pomocą udziałów sekretu XOR. Wartość każdego przewodu jest dzielona między wszystkich uczestników, którzy wchodzą w interakcję dla każdej bramki.

Uczestnik i posiada udział s_i taki, że s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (prawdziwa wartość przewodu). Bramki XOR są bezpłatne: każdy uczestnik lokalnie wykonuje XOR na swoich udziałach.

Dla bramki AND na przewodach a,b wyrażenie (a_1⊕a_2)(b_1⊕b_2) rozwija się do składników mieszanych. Obliczenie składnika mieszanego a_i·b_j między uczestnikami i≠j wymaga Oblivious Transfer.

W OT 1-z-2 nadawca ma wiadomości (m_0, m_1), a odbiorca ma bit wyboru c. Odbiorca otrzymuje m_c, nadawca nie dowiaduje się niczego o c, a odbiorca nie dowiaduje się niczego o m_{1-c}.

Protokół oparty na Diffie-Hellman: odbiorca generuje dwa klucze publiczne, znając logarytm dyskretny tylko jednego z nich. Nadawca szyfruje każdą wiadomość za pomocą jednego klucza. Odbiorca odszyfrowuje tylko wybrany przez siebie szyfrogram.

Ishai i in. (2003): na podstawie k bazowych OT można wygenerować m >> k OT, używając wyłącznie operacji z kluczami symetrycznymi. Rozszerzenie IKNP zmniejsza koszt OT do około 3 wywołań AES na OT po jednorazowej konfiguracji.

Każda bramka AND wymaga jednego OT dla każdej pary uczestników. Dzięki rozszerzeniu OT wstępne obliczenie wszystkich OT w fazie offline pozwala ograniczyć fazę online do pojedynczej wymiany XOR dla każdej bramki.

Protokół GMW z założeniem półuczciwości można uodpornić na złośliwych uczestników za pomocą dowodów z wiedzą zerową lub OT typu cut-and-choose. Koszt wzrasta 3–8 razy, ale uzyskuje się gwarancję bezpieczeństwa wobec oszukujących uczestników.

MASCOT (Keller i in.) rozszerza OT tak, aby w modelu złośliwym tworzyć uwierzytelnione trójki AND, umożliwiając działanie protokołu SPDZ — omówionego w następnej lekcji.

EMP-toolkit i MOTION implementują GMW z rozszerzeniem OT. Osiągają miliony bramek AND na sekundę między dwiema stronami w sieci LAN, dzięki czemu rzeczywiste zastosowania są możliwe.

Dlaczego bramki XOR w protokole GMW nie wymagają komunikacji między uczestnikami?

GMW używa udziałów sekretu XOR w obwodach boolowskich. Bramki XOR są bezpłatne, a bramki AND wymagają OT. Rozszerzenie OT sprawia, że OT jest tanie. Bezpieczeństwo wobec złośliwych uczestników wymaga dowodów z wiedzą zerową lub cut-and-choose. Biblioteki takie jak EMP zapewniają praktyczną przepustowość dla rzeczywistych zastosowań.