Secure Multiparty Computation

Bei der Mehrparteienberechnung (engl. multiparty computation, MPC) geht es um Prozesse, die es mehreren Parteien ermöglichen, gemeinsam ein Ergebnis auf der Grundlage ihrer eigenen privaten Eingaben zu berechnen. Aus Sicherheitsgründen möchte jede Partei, dass ihre privaten Eingaben während des gesamten Rechenvorgangs geheim bleiben.

Stellen Sie sich zum Beispiel eine Blindauktion für einen Gegenstand vor, bei der jede Partei ein privates Gebot als Eingabe hat, welche sie geheim halten möchte. Das gewünschte Ergebnis ist der Höchstbietende. In der Realität fungiert oft eine zentrale dritte Partei als Auktionator und nimmt alle Gebote entgegen, um den Gewinner zu ermitteln. Dieser Auktionator kann alle Gebote verraten und stellt damit eine Bedrohung für jeden Teilnehmer dar. Die zentrale Frage lautet: Wie können die Parteien den Gewinner ermitteln, ohne dass die Gebote an Dritte weitergegeben werden?

Hier kommen die Kryptographie und der Begriff der sicheren MPC ins Spiel. Sichere MPC-Protokolle ermöglichen solche gemeinsamen Berechnungen, ohne sich auf eine vertrauenswürdige Partei zu verlassen, und geben nur die gewünschten Ergebnisse preis. Beispielsweise würden alle Bieter über ein zugrunde liegendes P2P-Netzwerk interagieren, die Auktion mit entsprechend "maskierten" Geboten durchführen und schließlich nur den Index i des siegreichen Bieters und sein Gebot B "demaskieren". Durch geeignetes Verbergen der Zwischenergebnisse wird sichergestellt, dass die Parteien nicht mehr als die Ausgabe erfahren.

In der Kryptographie formalisieren wir solche Sicherheitsanforderungen wie "Partei A erfährt nicht mehr als die Information x" durch das sogenannte Simulationsparadigma. Wenn die Nachrichten, die A während der Ausführung eines Protokolls erhält, nur mit Hilfe von x generiert werden können, dann enthalten diese Nachrichten keine über x hinausgehenden Informationen. Formal verlangen wir, dass es für die Partei A einen effizienten Simulator gibt, der mit der idealen Information x die Nachrichten so generiert, dass sie von den realen Protokollausführungen von A nicht zu unterscheiden sind.

Aufgrund ihrer sehr allgemeinen Formulierung und Formalisierung kann die sichere MPC in einer Vielzahl von Situationen eingesetzt werden, und die folgenden zusätzlichen Beispiele sollen Ihnen davon ein besseres Verständnis vermitteln:

  • Aggregieren von Statistiken aus verschiedenen Datenquellen (z.B. Krankenhäuser und Versicherungen): Als Eingabe hat jede Partei i eine private Datenbank mit Tupeln (ID, Wert-i). Als Ausgabe aggregieren die Parteien die Werte z.B. zu ihrer Summe. Dies geschieht, ohne eine zentrale Datenbank zu erzeugen, in der alle Werte durch ihre ID verbunden sind. Kontextabhängig ist die Generierung eines solchen zentralen Datensatzes sogar gesetzlich verboten.
  • Trainieren von Modellen des maschinellen Lernens (ML) auf der Grundlage privater Daten (z. B. Trainieren von Wortvorhersagen aus Tastaturdaten): Jede Partei i erzeugt ständig vertrauliche Eingabedaten, z. B. durch Tippen auf ihrem Smartphone. Die MPC-Ausgabe soll ein prädiktives ML-Modell sein, bei dem die vertraulichen Eingabedaten niemandem offengelegt wurden.
  • Auswertung von ML-Modellen: Eine Partei hat ein trainiertes ML-Modell als Eingabe, während eine andere Partei es auf ihre privaten Eingaben anwenden, zum Beispiel zur Kategorisierung eines privaten Bildes. Weder das Modell noch die Daten, auf die es angewendet wurde, sollten offengelegt werden.
  • Gemeinsames Einrichten eines kryptografischen Systems: Die Parteien haben keine Eingabe, wollen aber Parameter eines kryptografischen Systems als Ausgabe erzeugen. Dies ist z. B. sinnvoll, um zu verhindern, dass einzelne Parteien Systemparameter erstellen und mit Backdoors versehen.
  • ...

Einer unserer Forschungsschwerpunkte ist effiziente MPC. Es gibt zwar Protokolle zur sicheren Berechnung beliebiger effizienter Funktionen, aber diese sind oft zu langsam für praktische Anwendungen wie das Training von ML-Modellen oder die Berechnung stabiler Matchings. Die Herausforderung besteht darin, schnelle, aber sichere MPC-Protokolle zu entwerfen, die auf die jeweilige Anwendung zugeschnitten sind. Außerdem berücksichtigen wir rationale Anreize der Teilnehmer bei der Ausführung von MPC-Protokollen. Für eine sichere Berechnung einer (Zweitpreis-)Auktion haben rationale Teilnehmer zum Beispiel einen Anreiz, ihre wahren Gebote einzugeben. Dies kann beim Entwurf von Protokollen nützlich sein und wird in der rationalen Kryptographie genauer beschrieben.