Sichere Mehrparteienberechnung

Die sichere Mehrparteienberechnung (MPC) ermöglicht es sich gegenseitig misstrauenden Parteien, gemeinsam eine Funktion ihrer privaten Eingaben zu berechnen, ohne dabei mehr als das vereinbarte Ergebnis preiszugeben.

Definition

Die sichere Mehrparteienberechnung ist ein Protokoll, das es einer Gruppe von Parteien, von denen jede eine private Eingabe besitzt, ermöglicht, eine vereinbarte Funktion so zu berechnen, dass jede Partei das korrekte Ergebnis und nichts Weiteres über die Eingaben der anderen erfährt.

Scope

Dieses Thema behandelt Protokolle für die sichere Berechnung: die Ideal-/Real-Simulations-Sicherheitsdefinition, Yaos Garbled Circuits für zwei Parteien, Secret-Sharing-basierte Protokolle (GMW, BGW) für viele Parteien, die Unterscheidung zwischen semi-ehrlicher und bösartiger Sicherheit sowie die Schwellenwertkryptographie. Es befasst sich mit praktischen Anwendungen wie der privaten Mengenintersection und der sicheren Aggregation. Ausgenommen sind Zero-Knowledge-Proofs, die oft als Subprotokoll verwendet werden, und die vollständig homomorphe Verschlüsselung, die einen alternativen Weg zur Berechnung verschlüsselter Daten bietet.

Core questions

• Wie können Parteien Daten gemeinsam verarbeiten, ohne dass eine Partei die Eingaben der anderen sieht?
• Was verlangt das Ideal-/Real-Simulationsparadigma von einem sicheren Protokoll?
• Wie ermöglichen Garbled Circuits eine sichere Zweiparteienberechnung?
• Wie skalieren Secret-Sharing-basierte Protokolle auf viele Parteien und tolerieren Korruptionen?
• Was ist der Unterschied zwischen semi-ehrlichen und bösartigen Sicherheitsgarantien?

Key concepts

• private Eingaben und gemeinsames Ergebnis
• Ideal-/Real-Simulation
• Garbled Circuits
• Oblivious Transfer
• Secret Sharing
• semi-ehrlicher vs. bösartiger Angreifer
• Schwellenwertkryptographie
• private Mengenintersection
• ehrliche Mehrheit vs. unehrliche Mehrheit

Key theories

Ideal-/Real-Simulationssicherheit

Ein MPC-Protokoll ist sicher, wenn alles, was ein Angreifer im realen Protokoll erreichen kann, auch in einer idealen Welt erreicht werden könnte, in der eine vertrauenswürdige Partei die Funktion berechnet – dies gewährleistet Datenschutz und Korrektheit gegenüber den modellierten Korruptionen.

Garbled Circuits und Secret Sharing

Yaos Garbled Circuits ermöglichen es zwei Parteien, jeden Booleschen Schaltkreis auszuwerten, indem eine Partei Wahrheitstabellen verschlüsselt und die andere diese unbewusst entschlüsselt; Secret-Sharing-Schemata teilen Eingaben unter Parteien auf, sodass Teilmengen Gatter gemeinsam berechnen können, ohne die Geheimnisse zu rekonstruieren.

Mechanisms

In Yaos Zweiparteienprotokoll verschlüsselt eine Partei einen Booleschen Schaltkreis, indem sie die Wahrheitstabelle jedes Gatters verschlüsselt, und die andere Partei wertet ihn unter Verwendung von Schlüsseln aus, die sie durch Oblivious Transfer erhalten hat, wobei sie nur das Ergebnis erfährt. Bei Secret-Sharing-Ansätzen (GMW, BGW, SPDZ) wird jede Eingabe in Anteile aufgeteilt, die unter den Parteien verteilt werden; Additionsgatter werden lokal auf den Anteilen berechnet, und Multiplikationsgatter verwenden Interaktion, wonach die Ergebnisanteile rekonstruiert werden. Bösartige Sicherheit fügt Zero-Knowledge-Proofs oder authentifizierte Anteile hinzu, um Betrug zu erkennen.

Clinical relevance

MPC entwickelt sich von der Theorie zur Anwendung für den datenschutzfreundlichen Austausch: Institutionen berechnen aggregierte Statistiken über kombinierte Datensätze, ohne Rohdaten zu poolen (die Bostoner Studie zur geschlechtsspezifischen Lohnlücke), Unternehmen führen private Mengenintersection für die Kontaktermittlung und Anzeigenmessung durch, Schwellenwertsignaturen schützen die Verwahrung von Kryptowährungen und Zertifizierungsstellenschlüsseln, und sichere Aggregation unterstützt datenschutzfreundliches maschinelles Lernen.

Evidence & guidelines

MPC wird durch ausgereifte offene Frameworks (z. B. MP-SPDZ) und zunehmend durch Standardisierungsbemühungen in der Schwellenwertkryptographie (NISTs Multi-Party Threshold Cryptography Projekt) unterstützt. Sicherheitsgarantien hängen entscheidend vom angenommenen Korruptionsmodell (semi-ehrlich vs. bösartig) und der Korruptionsschwelle (ehrliche Mehrheit vs. unehrliche Mehrheit) ab, die den Vertrauensannahmen der Bereitstellung entsprechen müssen.

History

Andrew Yao führte 1982-1986 die sichere Zweiparteienberechnung und die Idee der Garbled Circuits ein (das Millionärsproblem). Goldreich, Micali und Wigderson (1987) erweiterten die sichere Berechnung auf eine beliebige Anzahl von Parteien, und die BGW- und CCD-Protokolle (1988) lieferten informationstheoretische Sicherheit mit einer ehrlichen Mehrheit. Jahrzehntelange Effizienzverbesserungen (Oblivious-Transfer-Erweiterung, SPDZ) machten MPC in den 2010er Jahren praktisch genug für reale Anwendungen.

Key figures

• Andrew Yao
• Oded Goldreich
• Silvio Micali
• Avi Wigderson
• Adi Shamir

Seminal works

• yao1982
• goldreich2004
• katz2020

Frequently asked questions

Wie unterscheidet sich MPC von homomorpher Verschlüsselung?

Beide berechnen auf privaten Daten, aber homomorphe Verschlüsselung ermöglicht es einer einzelnen Partei, auf Chiffretexten zu rechnen, die sie nicht lesen kann, während MPC die Berechnung auf mehrere Parteien verteilt, die interagieren, wobei keine einzelne Partei die Eingaben sehen kann. Sie werden manchmal kombiniert.

Was bedeutet 'semi-ehrliche' versus 'bösartige' Sicherheit?

Semi-ehrliche (honest-but-curious) Sicherheit geht davon aus, dass Parteien dem Protokoll folgen, aber versuchen, zusätzliche Informationen aus dem Gesehenen zu gewinnen. Bösartige Sicherheit schützt zusätzlich vor Parteien, die willkürlich vom Protokoll abweichen, was stärker, aber auch kostspieliger ist.