MPC-Problem und Yao-Garbled-Circuits

MPC ermöglicht es n Parteien, die jeweils eine private Eingabe x_i besitzen, gemeinsam f(x_1,...,x_n) zu berechnen, ohne ihre Eingaben einander offenzulegen – so, als hätte eine vertrauenswürdige dritte Partei die Berechnung durchgeführt.

Yaos Millionärsproblem von 1982: Alice und Bob möchten herausfinden, wer reicher ist, ohne ihr Vermögen offenzulegen. Es gibt keine vertrauenswürdige dritte Partei. MPC löst dieses Problem mit kryptografischen Garantien.

1. Vertraulichkeit: Die Parteien erfahren nur die Ausgabe und Informationen, die sich daraus ableiten lassen. 2. Korrektheit: Die Ausgabe ist korrekt, selbst wenn einige Parteien kompromittiert sind. 3. Es gibt Varianten für semi-honest und böswillige Angreifer.

Jede Funktion lässt sich als boolesche Schaltung aus (AND-, XOR- und NOT-)Gattern darstellen. MPC-Protokolle arbeiten häufig auf Schaltungsebene und werten jedes Gatter sicher aus.

Alice (Garblerin) weist jeder Leitung zwei zufällige Labels zu: eines für 0 und eines für 1. Sie verschlüsselt die Wahrheitstabelle jedes Gatters mit den Labels der Eingangsleitungen. Bob (Evaluator) erhält die Labels für seine Eingaben über Oblivious Transfer.

Bob erhält verschleierte Tabellen (4 Verschlüsselungen pro AND-Gatter). Mit seinen Eingabe-Labels entschlüsselt er genau eine Zeile und erhält das Ausgabe-Label, ohne zu erfahren, ob es 0 oder 1 repräsentiert.

Fügen Sie jedem Label ein zufälliges „Auswahlbit“ hinzu. Bob verwendet die Auswahlbits, um die richtige Zeile der verschleierten Tabelle in O(1) zu finden, statt alle vier Entschlüsselungen auszuprobieren. Das reduziert den Berechnungsaufwand um den Faktor 4.

Kolesnikov und Schneider (2008): Wählen Sie einen globalen Offset Δ. Dann gilt für jede Leitung label_1 = label_0 ⊕ Δ. XOR-Gatter sind dadurch kostenlos (keine Verschlüsselung erforderlich), wodurch etwa 30 % Bandbreite eingespart werden.

Zahur et al. (2015): Jedes AND-Gatter benötigt nur 2 Chiffrate (statt 4). Zusammen mit Free-XOR halbiert dies die Bandbreite gegenüber standardmäßigen verschleierten Schaltungen.

Klassische verschleierte Schaltungen sind für zwei Parteien ausgelegt. Erweiterungen für mehrere Parteien (z. B. das BMR-Protokoll) parallelisieren die Verschleierung über alle Parteien, erfordern jedoch eine Kommunikation von O(n²). Für kleine n ist das praktikabel.

Wie erhält Bob im Protokoll der verschleierten Schaltung von Yao die Wire-Labels, die seinen privaten Eingabebits entsprechen?

MPC ermöglicht es Parteien, gemeinsam zu berechnen, ohne Eingaben offenzulegen. Verschleierte Schaltungen codieren boolesche Funktionen als verschlüsselte Wahrheitstabellen. Optimierungen (Free-XOR, Half-Gates, Point-and-Permute) machen sie praktikabel. OT übermittelt Bobs Eingabe-Labels vertraulich.