Begriff
Multi-Party Computation (MPC)
Warum wichtig?
Dieser Begriff ist ein Knoten im SengakujiWorks-Wissensnetz. Nutze Level 0 für die erste Einordnung, Level 1 für Praxis, Level 2 für technische Struktur und Level 3 für Grenzen, Fallstricke und Expertenkontext.
Das Millionärs-Problem:
Zwei Millionäre (Alice und Bob) wollen wissen: "Wer ist reicher?"
Aber keiner will sagen, wie viel er genau hat.
Wie berechnet man x > y, ohne x und y zu verraten?
Das ist MPC.
Mehrere Parteien berechnen gemeinsam eine Funktion auf ihren geheimen Inputs.
Niemand sieht die Inputs der anderen. Alle sehen nur das Ergebnis.
Es ist wie ein Tresor mit mehreren Schlüsseln, der innen rechnen kann.
Merksatz: Ein kryptografisches Teilgebiet, das Protokolle entwickelt, mit denen mehrere Parteien gemeinsam eine Berechnung über ihre geheimen Eingaben durchführen können, ohne diese Eingaben gegenseitig offenzulegen.
- Crypto Wallets (Threshold Sig): Der Private Key wird in 3 Teile zerlegt (Split). Einer auf dem Handy, einer auf dem Server, einer im Backup. Um zu signieren, müssen 2 von 3 Teile "MPC machen". Der ganze Key existiert nie an einem Ort (Schutz gegen Hacks).
- Werbe-Analyse: Google und Mastercard wollen wissen: "Haben Leute, die Werbung X sahen, das Produkt gekauft?" Ohne Daten zu teilen.
1. Shamir's Secret Sharing
Die Basis. Man zerlegt eine Zahl (Geheimnis) in Punkte auf einer Polynom-Kurve. $f(x) = S + a_1 x + \dots$. Man braucht $k$ Punkte, um die Kurve zu rekonstruieren (Interpolation). MPC rechnet mit diesen "Shares" (Anteilen), ohne sie zusammenzusetzen.
2. Garbled Circuits
Für Boolean Gates (AND, OR, XOR). Alice verschlüsselt eine Wahrheitstabelle (Garbled Table) und schickt sie Bob. Bob nutzt "Oblivious Transfer", um die Schlüssel für seine Inputs zu kriegen, ohne dass Alice weiß, was Bob wählt. Bob wertet den Circuit aus.
1. BGW & GMW Protokolle
In der Forschung unterscheidet man zwischen verschiedenen Sicherheitsgarantien:
- BGW (Ben-Or, Goldwasser, Wigderson): Basiert auf Shamir's Secret Sharing und bietet Sicherheit gegen "Passive Angreifer" (Leute, die nur gucken, aber das Protokoll korrekt befolgen). Es braucht eine ehrliche Mehrheit ($n > 2t$).
- GMW (Goldreich, Micali, Wigderson): Nutzt "Oblivious Transfer" und "Zero-Knowledge Proofs", um sogar gegen aktive Angreifer (Bösewichte, die falsche Daten senden, um das System zu manipulieren) sicher zu sein. GMW ist die theoretische Basis für fast alle modernen MPC-Frameworks.
2. Beaver Triples & Pre-Processing
MPC ist langsam, weil Multiplikationen interaktiv sind. Die Lösung in der Produktion: Beaver Triples ($a, b, c$ mit $c = a \cdot b$). Diese Tripel werden in einer "Offline-Phase" vorbereitet (bevor man die echten Daten kennt). Wenn dann die "Online-Phase" startet, nutzt man die Tripel, um die echte Multiplikation mit nur einer einzigen Nachricht pro Runde zu erledigen. Frameworks wie SPDZ (Speedz) nutzen diesen Trick, um MPC-Anwendungen fast so schnell wie CPU-Berechnungen zu machen (wenn man die Vorbereitungszeit ignoriert).
3. TEE vs. MPC (Software vs. Hardware)
Gibt es Konkurrenz? Ja: Trusted Execution Environments (TEE) wie Intel SGX.
- TEE: Das Geheimnis liegt in einem gesicherten CPU-Bereich. Schnell, aber man muss dem Hardware-Hersteller vertrauen.
- MPC: Das Geheimnis ist mathematisch im Netzwerk verteilt. Langsamer, aber man muss nur der Mathematik vertrauen (und einer Mehrheit der Teilnehmer). Hochsicherheitssysteme nutzen heute oft beides: MPC-Protokolle, die innerhalb von TEEs laufen. Sollte dann ein Hersteller korrumpiert sein, schützt die Mathematik den Rest des Systems.
Quick-Check
Unterschied zu FHE?
FHE = Eine Partei rechnet auf verschlüsselten Daten. MPC = Mehrere Parteien rechnen interaktiv auf verteilten Daten. MPC ist heute viel schneller und praxistauglicher als FHE.Fireblocks?
Ein Unicorn-Startup, das MPC für Custody (Verwahrung) von Krypto-Assets bei Banken nutzt.Langsam?
Der Kommunikations-Overhead ist riesig. Die Parteien müssen ständig Nachrichten austauschen. Funktioniert am besten bei wenigen Parteien (2-3) und schnellem Netz.