Multi-Party Computation

Wo Sicherheit Türen öffnet

von Lena Csomor

am 04. August 2022

Lesezeit: 16 Minuten

Keypoints

Darum ist Secure Multi-Party Computation wichtig

Erlaubt gemeinsame Berechnungen mit privatem Input
Kein Vertrauen in andere Parteien nötig
Ermöglicht genauere Forschung und bessere Zusammenarbeit
In der Digitalisierung von zunehmender Relevanz

Wenn wir über Sicherheit sprechen, geht es häufig um Funktionen, die existierende Anwendungen wie ein schützender Mantel umhüllen. Für viele sind diese zusätzlichen Ebenen vor allem mit zusätzlicher Mühsal verbunden, die zum Schutz der eigenen Firma und der Kundschaft in Kauf genommen wird . Was wir aber kaum je beachten ist das schöpferische Potenzial von Produkten aus der Sicherheitsforschung. Produkte, die uns Anwendungen erlauben, deren Existenz aufgrund von Datenschutzbedenken und astronomischen Kosten bisher beinahe unvorstellbar waren. Dieser Artikel möchte anhand von einem Beispiel eine neue Perspektive auf Cybersicherheit eröffnen, wo diese nicht ein Hindernis, sondern eine offene Tür für neue Anwendungen darstellt.

Um diese Vorstellung ein wenig greifbarer zu machen, beginnen wir mit einem konkreten Gedankenexperiment. Zwei Ärzte, Dr. Alice und Dr. Bob, aus verschiedenen Institutionen haben die Vermutung, dass Personen mit einer bestimmten Vorerkrankung X besonders anfällig für eine andere Krankheit, Y, sind. Sie möchten gerne ihre Hypothese überprüfen, haben jeweils alleine jedoch zu wenige Daten zur Verfügung, um statistisch signifikante Ergebnisse zu erhalten. Als Ärzte sind sie an strengste Daten- und Patientenschutzgesetze gebunden und gleichzeitig dazu angehalten, ihre Forschungskosten möglichst tief zu halten. Es wäre ihnen aber erlaubt, ihre Daten zu nutzen und auszutauschen, wenn sie diese anonymisieren. Dadurch würden jedoch mit hoher Wahrscheinlichkeit wichtige Details verloren gehen, und die Genauigkeit ihrer Forschungsergebnisse würde sinken.

Unsere beiden Ärzte sind überglücklich, als sie auf eine moderne Lösung für ihre Probleme stossen: Secure Multi-Party Computation. Darum soll es in diesem Artikel gehen.

Was ist Secure Multi-Party Computation?

Der Überbegriff Secure Computation umfasst sämtliche Berechnungsmethoden, bei denen die Daten, auf denen gerechnet wird, geheim bleiben. Secure Multi-Party Computation, im folgenden MPC genannt, ist nun nichts anderes als eine Berechnungsmethode, bei der mehrere Parteien gemeinsam eine Berechnung durchführen können, ohne ihre eigenen Eingabewerte jemals preiszugeben. Dazu gehört auch, dass eine Partei aus dem Ergebnis der Berechnung nicht auf die Eingabe anderer Parteien schliessen kann. Einer der grossen Vorteile von MPC ist, dass nicht nur die Parteien einander nicht ihre Daten anvertrauen müssen, sondern auch keine zusätzliche dritte Partei Daten erhält.

In den Anfängen von MPC in den 1980er-Jahren galten die existierenden Protokolle als rein theoretisches Konstrukt. Nach der Verbesserung bestehender Algorithmen und der günstigen, stark gestiegenen Rechenleistung der 2000er wurden die Protokolle praktisch anwendbar und heutzutage bieten bereits erste Firmen MPC-Softwarelösungen an.

Ganz grob kann man die heutigen Protokolle in zwei Gruppen einteilen. Garbled-Circuit Protokolle werden häufig in Systemen genutzt, in denen nur zwei Parteien agieren. Diese Protokolle basieren auf dem sogenannten Oblivious Transfer und Boolean Circuits. Sind mehr Parteien beteiligt, wird auf Secret-Sharing-basierte Protokolle zurückgegriffen. Während Boolean Circuits den meisten bekannt sein dürften, werden hier die zwei Bausteine Oblivious Transfer und Secret Sharing kurz vorgestellt, um eine Intuition zu vermitteln, weshalb etwas wie MPC überhaupt funktionieren kann. Ausserdem betrachten wir auch mögliche Angreifer und ihre Fähigkeiten.

Oblivious Transfer

Das Ziel von Oblivious Transfer (OT) ist, einem Empfänger eine Nachricht zuzustellen, ohne dass der Absender den finalen Inhalt der Nachricht kennt. Dies wird realisiert, indem der Absender dem Empfänger mehrere Geheimnisse schickt, und der Empfänger daraus auswählt. Dabei erfährt der Absender nicht, welches Geheimnis der Empfänger ausgewählt hat. Der Empfänger hingegen erfährt nur das Geheimnis, welches er selbst ausgewählt hat.

Damit kann eine Partei, z.B. Dr. Alice, ihren Teil der Berechnung durchführen unter Beachtung aller möglichen Eingabewerte von Dr. Bob. Zur Vereinfachung nehmen wir an, Bobs Eingabewerte sind entweder 0 oder 1. Sie schickt nur ihre Resultate m₀, m₁ verschlüsselt zu Dr. Bob, welcher nun ein Resultat m_b auswählen und entschlüsseln kann. Er wählt dabei das Resultat, welches auch seiner Eingabe in die Berechnung entspricht. Da Dr. Alice schon alle möglichen Eingabewerte von Dr. Bob mitgerechnet hat, ist die Berechnung damit abgeschlossen, ohne dass einer der beiden etwas über die Eingabewerte des anderen gelernt hätte.

Oblivious Transfer zwischen Dr. Alice und Dr. Bob

Secret Sharing

Secret Sharing ist eine Methode, ein Geheimnis unter n Parteien so aufzuteilen, dass nur wenn eine gewisse Anzahl Parteien t ihre Anteile des Geheimnisses kombiniert, das gesamte Geheimnis wiederhergestellt werden kann. Ein solches Verfahren nennt sich (t, n)-Schwellwert-Schema. Dabei verrät in einem sicheren Secret-Sharing-Protokoll eine Kombination von weniger als t Anteilen aber nichts über das gesamte Geheimnis. Diese Eigenschaft ist bekannt als Perfect Privacy und ist in einem MPC-Protokoll essenziell. Ein häufig benutzter Ansatz, um ein Geheimnis unter mehreren Parteien aufzuteilen, ist ein sogenannter Trusted Dealer. Dieser generiert das Geheimnis und die Anteile, ist ansonsten aber nicht in das Protokoll involviert, erhält also keine Daten von den Parteien.

Während sichere (t, n)-Secret-Sharing Protokolle für allgemeine t sehr kompliziert werden können, gibt es ein Verfahren für (n, n)-Secret-Sharing welches sehr einfach zu erklären ist. Dabei sind alle Anteile von allen Parteien nötig, um das Geheimnis zu rekonstruieren.

⊕ ist der XOR-Operator. Wir nehmen einen binären String s von beliebiger Länge. Dann generieren wir n-1 zufällige binäre Strings p_i derselben Länge. Diese verteilen wir an n-1 Parteien. Die letzte Partei erhält den String, der aus folgender Operation resultiert:

p_n = s ⊕ p₁ ⊕ p₂ ⊕ … ⊕ p_n-1

Das Geheimnis lässt sich damit aus dem XOR aller Anteile rekonstruieren, wobei weniger als n Anteile nichts über das Geheimnis s verraten.

p₁ ⊕ p₂ ⊕ … ⊕ p_n-1 ⊕ p_n = p₁ ⊕ p₂ ⊕ … ⊕ p_n-1 ⊕ (s ⊕ p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) = s ⊕ (p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) ⊕ (p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) = s

Threat Model

Wer sich regelmässig mit Sicherheit beschäftigt, mag sich nun fragen, welchen Angreifern diese Protokolle eigentlich standhalten können. Die Antwort ist allgemein: Es kommt auf das verwendete Protokoll an. Es gibt Protokolle, die sich mit aktiven Angreifern, sogenannten “Malicious Adversaries” auseinandersetzen. Solche Angreifer sind in der Lage, beliebig vom vorhergesehenen Ablauf des Protokolls abzuweichen.

Am häufigsten und relevantesten ist aber der semi-honest adversary, auch genannt honest-but-curious oder schlicht passiver Angreifer. Ein passiver Angreifer versucht so viel wie möglich über die anderen Parteien zu lernen, um so an private Informationen zu gelangen. Er weicht dabei allerdings nicht vom Protokoll ab, sondern nimmt ordentlich teil. Wichtig zu berücksichtigen ist aber, dass ein passiver Angreifer mehrere Parteien kompromittieren kann und damit die Ansichten und Daten mehrerer Teilnehmer kombinieren könnte.

Auch in Hinsicht auf unser Beispiel macht dies Sinn. Unsere Ärzte haben beide kein Interesse, ihre Forschung komplett zu sabotieren. Es könnte aber sein, dass einer von beiden gerne ein bisschen mehr über die Patienten des anderen erfahren würde, obwohl er das nicht darf. Die Aufgabe des Protokolls ist es, dafür zu sorgen, dass dies unmöglich ist.

Anwendungen

Im Folgenden werden wir mehrere Anwendungsfelder von MPC betrachten, um ein ganzheitlicheres Bild des Potenzials der Technologie zu erhalten.

Medizin

In der Medizin wird MPC hauptsächlich in Erwägung gezogen, um Forschung trotz starker Patientenschutzgesetze exakter und skalierbarer gestalten zu können. Besonders die Eigenschaft, Daten teilen zu können so dass andere sie zwar nutzen, aber nicht lesen können ist hierbei von Wichtigkeit. In den letzten Jahren ist hier das Interesse stark gewachsen und erste Kommerzialisierungen sind bereits auf dem Markt. In der Schweiz ist hierbei vor allem MedCo erwähnenswert, welches aus einer Zusammenarbeit mit der EPFL entstanden ist und sich dem Teilen und Analysieren von Daten mit MPC und ähnlichen Technologien verschrieben hat.

Privacy-Preserving Genomics

Ein besonders stark reguliertes Feld in der Humanforschung ist die Forschung mit biologischem Material. Besonders Forschung am menschlichen Genom sieht sich immer wieder mit Widerständen konfrontiert, bei denen MPC teilweise eine Erleichterung bieten kann. Ein Wettbewerb namens iDash lässt jedes Jahr Forschungsteams in verschiedenen Tracks ihrer “Secure Genome Analysis Competition” antreten, wo sich regelmässig vielversprechende Lösungen in MPC, homomorpher Verschlüsselung, und anderen Sicherheitstechnologien prämieren lassen.

Auktionen

Eine häufige Anforderung an Auktionen ist, dass Gebote geheim bleiben und nicht manipuliert werden können. Beispiele dafür sind Erst- und Zweitpreisauktionen, bei denen alle Gebote verdeckt abgegeben werden müssen. Diese Eigenschaften können von MPC angeboten werden, da sie nur in die gemeinsam ausgeführte Berechnung eingebettet werden müssen. Auch deshalb ist eines der beliebtesten Beispiele von kommerziellen MPC-Projekten die berühmte dänische Zuckerrübenauktion.

In den 2000er-Jahren sorgte die reduzierte Unterstützung der Zuckerrübenproduktion dafür, dass die Preise für Zuckerrüben neu ausgehandelt werden mussten. Die Zuckerrübenbauern waren besorgt darüber, dass ihre Gebote viel über ihre eigene finanzielle Situation verraten und verlangten deshalb Geheimhaltung vor der Verarbeitungsfirma Danisco, welche in Dänemark ein Monopol darstellte. Die dänische Regierung entwickelte deshalb zusammen mit Forschern die erste MPC-basierte Auktion mit drei Parteien (der Verarbeitungsfirma, den Bauern und den Forschern). Dadurch konnte ein effizientes secret-sharing Protokoll benutzt werden, und die Auktion gilt als grosser Erfolg. Das Projekt führte zur Gründung der Firma Partisia, die weiterhin Firmen Unterstützung für sichere Auktionen anbietet.

Studien

Zwei weitere Projekte, die sehr häufig als erfolgreiche MPC-Projekte erwähnt werden, sind die estländische Studentenstudie und die Lohngleichheitsstudie von Boston.

In Estland zeigten sich Universitäten besorgt darüber, dass viele IT-Studenten ihr Studium frühzeitig abbrachen. In 2015 sollte deshalb mit Hilfe einer Studie festgestellt werden, ob arbeitende Studenten das Studium eher abbrechen als Studenten, die nicht arbeiteten. Um dies festzustellen, sollten Daten der Universität und Steuerdaten analysiert werden. Die verschiedenen Regierungsorgane durften ihre Daten aus Datenschutzgründen nicht miteinander teilen, ausser sie würden aggregiert, was zu einem Genauigkeitsverlust geführt hätte (wobei Möglichkeit trotzdem für eine Vergleichsstudie genutzt wurde). Die Firma Cybernetica bot ihr Framework Sharemind für eine MPC-Lösung an, und die Studie wurde erfolgreich mit drei Parteien durchgeführt. Dabei konnte kein Zusammenhang zwischen Arbeitstätigkeit und Abbruch des Studiums festgestellt werden.

In der Lohngleichheitsstudie von Boston wollte die Stadt und das Boston Women’s Workforce Council vor einigen Jahren Ungleichheiten in Lohnzahlungen untersuchen, doch Datenschutzbedenken hinderten das direkte Teilen von Lohndaten. Forscher der Universität Boston entwickelten daraufhin eine web-basierte MPC Anwendung, in der Angestellte ihren Lohn sicher und geheim angeben konnten. Die Analyse konnte daraufhin erfolgreich durchgeführt werden.

Forschen mit personenbezogenen Daten

In unserem Gedankenexperiment wollen die beiden Ärzte Dr. Alice und Dr. Bob mit Patientendaten forschen. Wir schauen uns nun an, weshalb dies so aufwändig ist, dass sich der Einsatz von MPC lohnt. Grundsätzlich ist für jede Art von Humanforschung die Bestätigung eines Ethikkomitees vonnöten, so auch hier.

Wir wissen, dass die Daten über Krankheit X nicht im Zusammenhang mit einer klinischen Studie, sondern während der üblichen Behandlung von Patienten erhoben wurden. Die Studie von Dr. Alice und Dr. Bob ist eine sogenannte retrospektive Studie. Ausserdem gehen wir davon aus, dass es sich bei den Daten nicht um biologisches Material handelt. Forschung an biologischem Material ist noch strenger reguliert, aber auch hier kann MPC Abhilfe schaffen und Forschung in diese Richtung ist in den letzten Jahren auf immer grösseres Interesse gestossen.

Würden Dr. Alice und Dr. Bob jeweils nur für sich selbst forschen und wollten nicht jeden einzelnen Patienten kontaktieren (Skalierbarkeit), bräuchten sie ein Ethikkomitee davon zu überzeugen, dass das Interesse der Allgemeinheit (durch zum Beispiel bessere Therapien) höher wiegt als das Interesse des Patienten. Dies ist in der medizinischen Forschung meistens gegeben, sofern in einer Veröffentlichung der Forschung keine Rückschlüsse auf die einzelnen Patienten gezogen werden können.

Da die Ärzte miteinander forschen wollen, würden sie unter normalen Umständen auf die Daten des jeweils anderen zugreifen, die sie nicht selbst erhoben haben. Sie müssten deshalb besonders achtgeben, nicht die ärztliche Schweigepflicht zu brechen. Dafür gibt es drei Möglichkeiten. Die Patienten geben ihr Einverständnis, die Daten werden anonymisiert, oder sie halten sich an das spezielle Protokoll für das Teilen nicht-anonymisierter Daten für Forschungszwecke, welches jedoch nur unter sehr spezifischen Bedingungen eingesetzt werden darf.

Hier kommt nun MPC ins Spiel. Wir erinnern uns, dass die Daten nur in verschlüsselter Form geteilt werden, der jeweils andere sie also gar nicht lesen kann. Durch ausreichende Verschlüsselung wird der Aufwand einer Re-Identifikation der Patienten unverhältnismässig hoch und aus Sicht einer Partei ohne Schlüssel sind die Daten als anonymisiert zu qualifizieren. Da es sich nicht um biologisches Material handelt, ist damit die Einwilligung des Patienten nicht mehr vonnöten, sofern bei allfälliger Veröffentlichung der Forschung ebenfalls auf die Nicht-Identifizierbarkeit der Patienten geachtet wird. Da wir auf keine möglicherweise aggregationsbasierten Anonymisierungsmechanismen zurückgreifen mussten, droht uns kein Verlust von Genauigkeit.

In der Schweiz gelten anonymisierte, pseudonymisierte und damit auch ausreichend verschlüsselte Daten insgesamt nicht mehr als personenbezogene Daten. Die gängigsten Anonymisierungs- und Pseudonymisierungsverfahren sind allerdings sehr aufwändig und häufig verlustreich, sofern sie mit der entsprechenden Sorgfalt durchgeführt werden. Deshalb ist MPC auch für nicht-medizinische Studien mit hohem Anspruch an Genauigkeit von Relevanz.

Bei aller Begeisterung darf allerdings nicht vergessen werden, dass wie bei klassischen Studien viel statistische Aussagekraft davon abhängt, in welchem Format und welcher Genauigkeit die Daten ursprünglich erfasst wurden. MPC kann in erster Linie Berechnungen durchführen, was beim Finden von Gemeinsamkeiten, Korrelationen und Vergleichen hilft. MPC ist nicht in der Lage, freien Text zu interpretieren oder Daten aus verschiedenen Formaten zu importieren. Diese Art von Arbeit gehört zur Vorbereitung einer Studie mit MPC und je nach Datenlage ist der Aufwand nicht zu unterschätzen. Man kann allerdings annehmen, dass ein ähnlicher Aufwand bei jeder qualitativ hochwertigen, statistisch aussagekräftigen Studie anfallen würde.

Digitalisierung in der Schweiz und Vergleich

Der föderalistische, mehrsprachige Gesundheitssektor der Schweiz bringt nicht wenige Hindernisse mit sich, und viele Ziele der eHealth Strategie des Bundes sind bei weitem nicht erreicht. Es lohnt sich jedoch, sich die verschiedenen vielversprechenden Forschungsprojekte des Swiss Personalized Health Network anzusehen, von denen viele eng mit Sicherheitstechnologien verknüpft sind.

Als leuchtendes Beispiel für die Digitalisierung öffentlicher Dienste wird meist Estland genannt. Interessant ist hier nicht nur die Technologie, dank der die verschiedenen Sektoren miteinander interagieren können, sondern auch, wie an der öffentlichen Akzeptanz dieser Technologien gearbeitet wurde.

Fazit

Secure Multi-Party Computation ist eine Technologie, die Forschung unter Wahrung starker Datenschutzgesetze möglich macht. Dadurch können Datensätze verbunden und Korrelationen festgestellt werden, wo eine genaue Analyse zuvor unmöglich war. Verschiedene Parteien sind nicht mehr gezwungen, einander ihre Daten anzuvertrauen. Diese Eigenschaft ist für viele Forschungsfelder, aber auch für die Industrie von grosser Bedeutung und kann einen entscheidenden Digitalisierungsvorsprung bringen.

Die meisten bisher durchgeführten Projekte waren jedoch mit erhöhtem technischem Aufwand verbunden, da sie spezifisch auf das jeweilige Projekt zugeschnitten werden mussten. Die nötige Entwicklung geht daher in die Richtung allgemeinerer Frameworks, die kommerziell vertrieben werden. Bis MPC wirklich einfach und schnell zu benutzen wird, dürfte es allerdings noch eine Weile dauern.

Zu guter Letzt haben Dr. Alice und Dr. Bob über Institutionen hinweg und unter Wahrung der Schweizer Datenschutz- und Humanforschungsgesetze die Leiden ihrer Patienten analysieren und auswerten können und festgestellt, dass Krankheit X nicht zu einer Anfälligkeit für Krankheit Y führt.

Weiterführendes Material

Über die Autorin

Lena Csomor macht gegenwärtig ihren Master im Informatik-Studium an der ETH Zürich mit Schwerpunkt Secure and Reliable Systems. Sie hat zwei Praktika als Security Consultant und bei R&D eines IoT-Herstellers absolviert. Ihr Fokus besteht in Technologien zum Schutz der Privatsphäre (MPC, FHE, Differential Privacy). (ORCID 0000-0002-9537-4253)

Herausforderung Datenschutz-Grundverordnung DSGVO?

Unsere Spezialisten kontaktieren Sie gern!