MPC-Anwendungen: Private Set Intersection und ML

MPC überführt Theorie in die Praxis. Private Set Intersection (PSI) und datenschutzwahrendes ML gehören heute zu den am häufigsten eingesetzten MPC-Anwendungen in der Industrie.

Bei PSI besitzt Alice die Menge A und Bob die Menge B. Beide berechnen A∩B, ohne Elemente aus A\B oder B\A zu erfahren. Das Verfahren wird bei der Kontaktverfolgung von Google und Apple, zur Erkennung von Anzeigenbetrug und zum Austausch von Informationen über Bedrohungen eingesetzt.

Beide Mengen zu hashen und zu vergleichen ist unsicher, wenn die Mengen klein sind – ein Angreifer probiert alle Elemente aus. Ein sicheres PSI muss gewährleisten, dass selbst die Größe der Schnittmenge verborgen bleibt (oder nur die Schnittmenge offengelegt wird).

Oblivious PRF (OPRF): Bob wertet eine PRF für Alices Elemente aus, ohne sie zu erfahren. Alice erhält für jedes x∈A den Wert PRF(k, x). Sie vergleicht ihn mit Bobs vorberechneten Werten PRF(k, y) für y∈B.

Circuit-PSI berechnet die Schnittmenge innerhalb einer MPC-Schaltung. Dadurch sind weitere Berechnungen mit den Elementen der Schnittmenge möglich, beispielsweise das Addieren von Kaufbeträgen, ohne offenzulegen, welche Elemente sich überschneiden.

PPML trainiert Modelle oder führt Inferenz mit Daten mehrerer Parteien durch. Beim föderierten Lernen bleiben die Daten lokal; MPC geht noch weiter: Selbst das Modell oder aggregierte Gradienten werden mittels Secret Sharing geheim gehalten.

Das Secure-Aggregation-Protokoll von Google aus dem Jahr 2017: Jeder Client teilt sein Gradienten-Update mittels Secret Sharing auf. Der Server rekonstruiert nur die Summe. Einzelne Updates werden niemals offengelegt, auch nicht gegenüber dem Server.

CrypTen (Facebook/Meta) und MOTION unterstützen die Ausführung von neuronalen Netzen im PyTorch-Stil mit Secret-Shared-Eingaben. Lineare Schichten erfordern wenig Rechenaufwand; Nichtlinearitäten wie ReLU benötigen eine Umwandlung von Boolean- in arithmetische Werte.

ReLU(x) = max(0,x) erfordert den Vergleich von x mit 0 – eine nichtlineare, nichtarithmetische Operation. Dies geschieht mit Garbled Circuits oder Bitzerlegung und ist der größte Kostenfaktor in PPML.

Apples Private Relay verwendet PSI. Meta nutzt MPC für die private Werbemessung. Das IETF-PRIO-Protokoll, das in Firefox Telemetry verwendet wird, nutzt mittels Secret Sharing geschützte aggregierte Statistiken.

Welche Partei hält bei PSI auf OPRF-Basis den PRF-Schlüssel, und was erfährt die andere Partei?

Mit PSI können Parteien die Schnittmenge von Mengen privat über ein OPRF berechnen. Circuit-PSI ermöglicht weitere Berechnungen mit den Daten der Schnittmenge. PPML nutzt MPC zur Aggregation beim föderierten Lernen und für die Modellinferenz mit verschlüsselten Eingaben. ReLU ist der wichtigste Kostenengpass in PPML.