GMW-Protokoll und Oblivious Transfer

Das Goldreich-Micali-Wigderson (GMW)-Protokoll wertet boolesche Schaltungen mithilfe von XOR-Secret-Shares aus. Jeder Leitungswert wird auf alle Parteien aufgeteilt; diese interagieren Gatter für Gatter.

Partei i besitzt ein Share s_i mit s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (dem tatsächlichen Leitungswert). XOR-Gatter sind kostenlos: Jede Partei verknüpft ihre Shares lokal per XOR.

Für ein AND-Gatter auf den Leitungen a und b wird (a_1⊕a_2)(b_1⊕b_2) in Kreuzterme entwickelt. Die Auswertung des Kreuzterms a_i·b_j zwischen Parteien i≠j erfordert Oblivious Transfer.

Bei einem 1-aus-2-OT besitzt der Sender die Nachrichten (m_0, m_1), während der Empfänger das Auswahlbit c besitzt. Der Empfänger erhält m_c, der Sender erfährt nichts über c, und der Empfänger erfährt nichts über m_{1-c}.

Es basiert auf Diffie-Hellman: Die Empfängerin erzeugt zwei öffentliche Schlüssel, wobei sie den diskreten Logarithmus nur eines Schlüssels kennt. Der Sender verschlüsselt jede Nachricht mit einem der Schlüssel. Die Empfängerin entschlüsselt nur das von ihr ausgewählte Chiffrat.

Ishai et al. (2003): Aus k Basis-OTs werden m >> k OTs erzeugt, wobei nur Operationen mit symmetrischen Schlüsseln verwendet werden. Die IKNP-Erweiterung reduziert die OT-Kosten nach einer einmaligen Einrichtung auf etwa 3 AES-Aufrufe pro OT.

Jedes AND-Gatter benötigt ein OT pro Parteienpaar. Mit der OT-Erweiterung können alle OTs in einer Offline-Phase vorberechnet werden, sodass die Online-Phase pro Gatter nur aus einem einzigen XOR-Austausch besteht.

Semi-honest GMW kann mithilfe von Nullwissensbeweisen oder Cut-and-Choose-OT gegen böswillige Parteien abgesichert werden. Der Aufwand steigt um das 3- bis 8-Fache, dafür ist die Sicherheit auch gegenüber betrügerischen Parteien gewährleistet.

MASCOT (Keller et al.) erweitert OT, um authentifizierte AND-Tripel im böswilligen Modell zu erzeugen, und ermöglicht dadurch das SPDZ-Protokoll, das in der nächsten Lektion behandelt wird.

EMP-toolkit und MOTION implementieren GMW mit OT-Erweiterung. Sie erreichen zwischen zwei Parteien über ein LAN mehrere Millionen AND-Gatter pro Sekunde und machen dadurch reale Anwendungen praktikabel.

Warum erfordern XOR-Gatter im GMW-Protokoll keine Kommunikation zwischen den Parteien?

GMW verwendet XOR-Secret-Shares für boolesche Schaltungen. XOR-Gatter sind kostenlos, AND-Gatter benötigen OT. Die OT-Erweiterung macht OT kostengünstig. Sicherheit gegen böswillige Parteien ergänzt ZKPs oder Cut-and-Choose. Bibliotheken wie EMP erreichen einen für reale Anwendungen praktikablen Durchsatz.