SPDZ und arithmetische MPC mit Secret Shares

Boolesche MPC arbeitet mit Bits (XOR/AND). Arithmetische MPC arbeitet mit Ganzzahlen oder Körperelementen und unterstützt Addition und Multiplikation direkt. Das eignet sich besser für Anwendungen in den Bereichen maschinelles Lernen und Statistik.

Ein Wert x ∈ Z_p wird als x = x_1 + x_2 + ... + x_n mod p geteilt. Die Addition geteilter Werte ist kostenlos: Jede Partei addiert ihre Shares lokal. Es ist keine Kommunikation erforderlich.

Um die Shares [a] und [b] zu multiplizieren, verteilen die Parteien vorab ein Beaver-Tripel ([a_t], [b_t], [c_t]), für das c_t = a_t·b_t gilt. Die Multiplikation in der Online-Phase benötigt eine Kommunikationsrunde.

SPDZ (Damgård et al. 2012) = „Somewhat Homomorphic Encryption-based Distributed Zero-Knowledge“. In der Offline-Phase werden mithilfe von SHE authentifizierte Tripel erzeugt. Die Online-Phase ist eine schnelle Auswertung mit additiven Shares.

Jedes Share wird von einem MAC begleitet: MAC(x_i) = α·x mod p, wobei α ein globaler geheimer Schlüssel ist. Dadurch wird verhindert, dass böswillige Parteien ihre Shares unbemerkt verfälschen.

SPDZ verwendet in der Offline-Phase Somewhat Homomorphic Encryption (BGV/BFV). Die Parteien multiplizieren ihre Shares homomorph, um authentifizierte Beaver-Tripel zu erzeugen. Diese Phase ist rechenintensiv, lässt sich aber parallelisieren.

Gegeben seien das Tripel ([a],[b],[c]) und die Eingaben [x],[y]: Geben Sie d=x-a und e=y-b offen (maskiert, sodass keine Informationen durchsickern). Dann gilt [x·y] = [c] + d·[b] + e·[a] + d·e. Eine Kommunikationsrunde.

MASCOT ersetzt die SHE-Offline-Phase durch eine OT-Erweiterung und erzeugt Tripel für kleine Körper schneller. Für SPDZ mit zwei Parteien ist dies die bevorzugte Offline-Phase.

Mehrere Krankenhäuser berechnen das Durchschnittsalter von Patientinnen und Patienten, ohne ihre Datensätze zu teilen. Jedes Krankenhaus codiert seine Daten als arithmetische Shares. SPDZ wertet Summe und Anzahl aus; die Parteien erfahren nur das Verhältnis.

SPDZ-2k (Cramer et al. 2018) erweitert das Verfahren auf Z_{2^k} für festkommaarithmetische Berechnungen, die für maschinelles Lernen geeignet sind. Die MP-SPDZ-Bibliothek erreicht in Benchmarks über ein LAN bei 2 Parteien 1 Mio. Multiplikationen pro Sekunde.

Arithmetische MPC verwendet additive Shares über Z_p. Addition ist kostenlos, Multiplikation verwendet Beaver-Tripel in einer Runde. SPDZ ergänzt MACs für Sicherheit gegen böswillige Parteien. MASCOT verwendet OT zur schnellen Erzeugung von Tripeln. MP-SPDZ macht diese Verfahren praktisch nutzbar.