Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

Diese Arbeit stellt optimierte MPC-Algorithmen für die Multiplikation von geheimgeteilten dünnbesetzten Matrizen vor, die Speicher- und Kommunikationskosten im Vergleich zu dichten Verfahren drastisch senken und so datenschutzkonformes maschinelles Lernen für Anwendungen mit hochdimensionalen dünnbesetzten Daten wie Empfehlungssystemen oder Genomik ermöglichen.

Das Wesentliche

Das große Problem: Der überfüllte Lagerkeller

Stellen Sie sich vor, Sie und viele andere Personen wollen gemeinsam ein riesiges Puzzle legen, aber niemand darf sehen, welche Teile die anderen haben. Das ist das Ziel von Multi-Party Computation (MPC): Sichere Berechnungen auf geheimen Daten.

Das Problem ist jedoch die Art der Daten. In der echten Welt (z. B. bei Filmempfehlungen oder medizinischen Gen-Daten) sind die meisten Daten leer.

• Die Analogie: Stellen Sie sich einen riesigen Lagerkeller vor, der mit Regalen gefüllt ist. In einem typischen Datensatz sind 99,9 % der Regale leer. Nur 0,1 % enthalten tatsächlich etwas (z. B. einen Film, den ein Nutzer gesehen hat).

Bisherige sichere Rechenmethoden behandelten diesen Keller so, als wäre er vollgestopft. Sie zählten jedes einzelne Regal, auch die leeren.

• Das Ergebnis: Der Keller wurde so voll mit "leeren Regalen", dass er zusammenbrach (Speicherüberlauf). Die Kommunikation zwischen den Teilnehmern wurde so langsam, dass es Jahre dauern würde, nur um eine einfache Frage zu beantworten. Es war wie der Versuch, ein ganzes Schiff mit Wasser zu füllen, nur um eine einzige Flasche Wein zu transportieren.

Die Lösung: Der "Sparsame" Ansatz

Die Autoren dieses Papers (Marc Damie und Kollegen) haben einen neuen Weg gefunden: Sichere Multiplikation mit dünnbesetzten (sparse) Matrizen.

Statt den ganzen leeren Keller zu zählen, haben sie eine Methode entwickelt, bei der die Teilnehmer nur die gefüllten Regale betrachten.

1. Die neue Methode: "Nur das Wichtige zählen"

Stellen Sie sich vor, Sie haben eine Liste von Freunden, die Sie kennengelernt haben.

• Der alte Weg (Dicht): Sie schreiben eine Liste mit allen 10.000 Menschen der Welt auf und markieren mit einem "X", ob Sie sie kennen oder nicht. Dann vergleichen Sie diese Liste mit einer anderen. Das dauert ewig und braucht riesigen Platz.
• Der neue Weg (Dünn): Sie schreiben nur die Namen der 50 Menschen auf, die Sie tatsächlich kennen. Wenn Sie diese Liste mit einer anderen vergleichen, müssen Sie nur diese 50 Namen prüfen.

Die Autoren haben Algorithmen entwickelt, die genau das tun: Sie ignorieren die Nullen (die leeren Regale) komplett und konzentrieren sich nur auf die echten Werte.

2. Der Trick: Das "Geheime Sortieren"

Wie können Sie sicher vergleichen, ohne zu verraten, welche Werte Sie haben?
Die Autoren nutzen einen cleveren Trick namens "Oblivious Sorting" (blindes Sortieren).

• Die Analogie: Stellen Sie sich vor, Sie und Ihre Freunde haben Karten mit Zahlen. Niemand darf die Zahlen sehen. Sie werfen alle Karten in einen Mixer, der sie zufällig durcheinanderwirbelt, sortiert sie dann aber trotzdem nach Größe – ohne dass jemand weiß, welche Karte welche Zahl hatte.
• Sobald die Karten sortiert sind, können die Computer sehen: "Aha, hier liegen zwei Karten nebeneinander, die denselben Namen haben. Diese beiden müssen multipliziert werden." Alles andere wird ignoriert.

Warum ist das so wichtig? (Die Ergebnisse)

Die Forscher haben zwei Dinge bewiesen:

1. Platzersparnis: Bei extrem dünnbesetzten Daten (wie bei Netflix-Empfehlungen) sparen sie 19 Terabyte an Speicherplatz im Vergleich zu den alten Methoden. Das ist wie der Unterschied zwischen einem ganzen Lagerhaus und einem kleinen Schrank.
2. Geschwindigkeit: Die Kommunikation zwischen den Servern wurde um das 1.000-fache beschleunigt.
   • Beispiel: Eine Aufgabe, die früher einen ganzen Tag gedauert hätte, ist jetzt in Minuten erledigt.

Zwei echte Anwendungen

Die Autoren haben ihre Methode in zwei echten Szenarien getestet, die mit alten Methoden unmöglich gewesen wären:

1. Der Film-Empfehlungs-Algorithmus:

   • Szenario: Ein Nutzer sucht nach einem Film. Das System muss prüfen, welche anderen Nutzer ähnliche Filme gesehen haben.
   • Problem: Jeder Nutzer hat nur einen winzigen Bruchteil aller Filme gesehen. Die Daten sind extrem dünn.
   • Ergebnis: Mit der alten Methode wäre der Server explodiert (Speicher voll). Mit der neuen Methode lief es in ca. 48 Minuten.

2. Der Sicherheits-Check (Zugangskontrolle):

   • Szenario: Ein Krankenhaus will prüfen, ob ein Zugriff auf Patientendaten verdächtig ist, ohne die Daten zu enthüllen.
   • Problem: Die Daten sind riesig und fast leer (die meisten Zugriffe sind normal).
   • Ergebnis: Die alte Methode scheiterte an der Speichergröße. Die neue Methode schaffte es in 5 Stunden.

Das Geheimnis: Wie viel darf man verraten?

Ein kleines Problem bleibt: Damit der Algorithmus weiß, wie er sortieren muss, muss er wissen, wie viele gefüllte Regale es pro Zeile gibt (z. B. "Nutzer A hat 5 Filme gesehen").

• Das Dilemma: Wenn man das verrät, weiß man vielleicht zu viel über einen Nutzer.
• Die Lösung: Die Autoren haben drei Tricks entwickelt, um dieses Wissen zu minimieren:
  1. Anonymisierung: Man weiß nur die Verteilung (z. B. "Die meisten haben 1-10 Filme gesehen"), aber nicht, wer genau wie viele hat.
  2. Aufpolsteren (Padding): Man füllt leere Zeilen künstlich mit "Schein-Regalen" auf, damit alle gleich aussehen. Das ist ineffizient, aber sicher.
  3. Der "Schablone"-Trick (Matrix Templating): Das ist der beste Trick. Man erstellt eine Schablone mit verschiedenen Kategorien (z. B. "Gruppe A: 1-10 Filme", "Gruppe B: 11-50 Filme"). Jeder passt sich dieser Schablone an. So weiß niemand, wie viele Filme genau ein einzelner Nutzer gesehen hat, aber der Algorithmus funktioniert trotzdem perfekt.

Fazit

Dieses Papier ist wie die Erfindung eines neuen Lagersystems für geheime Daten. Anstatt alles blind und ineffizient zu zählen, nutzen die neuen Algorithmen die Tatsache, dass die meisten Daten leer sind, um die Arbeit extrem schnell und platzsparend zu erledigen.

Kurz gesagt: Sie haben einen Weg gefunden, wie man ein riesiges, fast leeres Puzzle sicher zusammenlegt, ohne den ganzen Raum mit leeren Teilen zu füllen. Das macht sichere KI-Anwendungen (wie medizinische Analysen oder Filmempfehlungen) endlich in der Praxis möglich.

Technische Zusammenfassung

1. Problemstellung

Multi-Party Computation (MPC) ermöglicht die Ausführung von Machine-Learning (ML)-Algorithmen auf privaten Daten, ohne diese offenzulegen. Ein zentrales Problem bestehender MPC-Frameworks ist jedoch die fehlende Optimierung für sparse (dünnbesetzte) Daten.

• Herausforderung: Viele reale ML-Anwendungen (z. B. Empfehlungssysteme, Genomik, NLP) arbeiten mit hochdimensionalen Daten, die zu über 99 % aus Nullen bestehen.
• Speicherproblem: Herkömmliche „dichte" (dense) Darstellungen und Multiplikationsalgorithmen speichern jede Zelle (auch Nullen). Bei großen Datensätzen führt dies zu prohibitiv hohem Speicherbedarf, der selbst in Klartext-Umgebungen oft nicht handhabbar ist. In MPC verschärft sich dies durch die Notwendigkeit, Shares zu speichern.
• Kommunikationskosten: Dichte MPC-Protokolle haben Kommunikationskosten, die linear oder kubisch von der Matrixgröße abhängen, nicht von der Anzahl der Nicht-Null-Elemente. Dies macht sie für hochdimensionale, sparse Daten unpraktikabel.
• Lücke in der Forschung: Bisherige sichere sparse Multiplikationen erfordern oft, dass eine Partei den Klartext der Sparsity kennt (z. B. bei Zwei-Parteien-Setups) oder sind nicht für das „outsourced"-Setting geeignet, bei dem Datenbesitzer ihre Daten an Server übergeben und sich dann trennen.

2. Methodik und Ansatz

Die Autoren entwickeln dedizierte MPC-Algorithmen zur Multiplikation von geheimgeteilten (secret-shared) sparse Matrizen. Der Kernansatz basiert auf der Nutzung der Sparsity, um Speicher- und Kommunikationskosten drastisch zu reduzieren.

• Datendarstellung: Statt dichter Matrizen wird das Tuple-Format (COO-Format) verwendet. Jede sparse Matrix wird als Liste von Tupeln (Index, Wert) für die Nicht-Null-Elemente dargestellt.
• Grundlegende Primitive: Die Algorithmen nutzen sichere Additionen, Multiplikationen, Vergleiche sowie oblivious shuffling (verdecktes Mischen) und oblivious sorting (verdecktes Sortieren).
  • Oblivious Sorting: Sortiert geheime Werte, ohne die Werte oder die Permutation offenzulegen (z. B. mittels Sortier-Netzwerken oder Radix-Sort).
• Algorithmen:
  1. Sparse Vektor-Vektor-Multiplikation: Zwei Tupellisten werden konkateniert, nach Koordinaten sortiert und bei übereinstimmenden Koordinaten multipliziert und summiert.
  2. Sparse Matrix-Vektor-Multiplikation: Statt zeilenweiser Berechnung (ineffizient), werden Elemente so gruppiert, dass sie nach Spalten sortiert werden. Dies ermöglicht eine effiziente Aggregation ohne lineare Abhängigkeit von der Anzahl der Zeilen.
  3. Sparse Matrix-Matrix-Multiplikation: Nutzt das Wissen über die Sparsity pro Spalte der ersten Matrix und pro Zeile der zweiten Matrix. Es werden alle skalaren Produkte berechnet, die Tupel nach Koordinaten sortiert und aggregiert.
• Öffentliches Wissen (Public Knowledge): Effiziente sparse Algorithmen benötigen zwingend Informationen über die Sparsity (z. B. Anzahl der Nicht-Null-Elemente pro Zeile). Die Autoren akzeptieren dies als notwendige Annahme, minimieren sie aber jedoch durch neue Techniken (siehe unten).

3. Schlüsselbeiträge

1. Neue MPC-Algorithmen: Entwicklung von zwei sicheren Algorithmen für Matrix-Vektor- und Matrix-Matrix-Multiplikation auf secret-shared sparse Daten. Diese sind kompatibel mit dem „outsourced"-Setting (unbegrenzte Anzahl von Datenbesitzern).
2. Ressourcenoptimierung:
   • Speicher: Vermeidung von Speicherüberläufen, die bei dichten Darstellungen unvermeidbar sind.
   • Kommunikation: Reduktion der Kommunikationskosten um den Faktor bis zu 1000 im Vergleich zu dichten Baselines für realistische Sparsity-Level.
3. Minimierung öffentlichen Wissens: Da die genaue Sparsity pro Zeile oft sensibel ist, schlagen die Autoren drei Techniken vor, um dieses Wissen zu minimieren:
   • Row Anonymization: Datenbesitzer anonymisieren ihre Identität (z. B. via Tor), sodass nur die Verteilung der Sparsity bekannt ist, nicht die Zuordnung zu einzelnen Nutzern.
   • Max-Row Padding: Alle Zeilen werden auf die maximale Sparsity aufgefüllt (Dummy-Nicht-Nullen), um nur eine Obergrenze offenzulegen.
   • Matrix Templating: Eine fortschrittlichere Methode, bei der die Matrix in Submatrizen unterteilt wird, die auf Quantilen der Sparsity-Verteilung basieren. Dies reduziert den Overhead durch Dummy-Elemente erheblich im Vergleich zum globalen Padding.
4. Privatsphärenerhaltende Schätzung: Methoden zur privaten Berechnung der Matrix-Templates mittels MPC oder Differential Privacy (DP), um die Sparsity-Statistiken ohne Offenlegung der Rohdaten zu ermitteln.

4. Ergebnisse und Experimente

Die Autoren validierten ihre Algorithmen in zwei realen ML-Anwendungsfällen und verglichen sie mit dichten Baselines (unter der Annahme einer ehrlichen Mehrheit der Server).

• Experimentelles Setup: Simulation mit 3 Parteien (MPyC Framework), 188 GB RAM. Getestet bei Sparsity-Leveln von 99 %, 99,9 % und 99,99 %.
• Matrix-Vektor (Empfehlungssystem):
  • Anwendung: Ein Empfehlungssystem auf dem Bookcrossing-Datensatz (99,998 % Nullen).
  • Ergebnis: Der dichte Algorithmus scheiterte an einem Speicherüberlauf (benötigt ~19 TB für dichte Darstellung). Der sparse Algorithmus lief erfolgreich (ca. 48 Minuten Laufzeit).
• Matrix-Matrix (Zugriffskontrolle):
  • Anwendung: Training eines Zugriffskontrollmodells (Lineare Diskriminanzanalyse) auf dem Amazon-Datensatz (99,95 % Nullen).
  • Ergebnis: Der dichte Algorithmus scheiterte erneut am Speicher. Der sparse Algorithmus schaffte das Training in 5 Stunden.
  • Kommunikationskosten: Bei 99,99 % Sparsity reduzierte sich die Kommunikation um den Faktor 1000 gegenüber der dichten Variante.
• Speicher-Overhead der Minimierungstechniken:
  • Das „Max-Row Padding" führte bei stark variierenden Datensätzen (z. B. Bookcrossing) zu einem massiven Overhead (nahezu dichte Matrix).
  • Die Matrix Templating-Methode reduzierte diesen Overhead drastisch (z. B. bei MovieLens nur Faktor 2 statt Faktor 100).

5. Bedeutung und Fazit

Dieses Paper schließt eine kritische Lücke in der Privacy-Preserving Machine Learning (PPML)-Forschung.

• Praktische Relevanz: Es macht ML-Anwendungen auf hochdimensionalen, sparse Daten (wie Empfehlungssysteme oder Genomik) in MPC überhaupt erst durchführbar, da dichte Ansätze hier an Speicher- und Kommunikationsgrenzen stoßen.
• Skalierbarkeit: Die vorgestellten Algorithmen skalieren mit der Anzahl der Nicht-Null-Elemente ($nnz$) und nicht mit der Gesamtgröße der Matrix ($n \times m$), was für reale Big-Data-Szenarien essenziell ist.
• Privatsphäre: Durch die vorgeschlagenen Techniken zur Minimierung öffentlichen Wissens (Templating, DP) wird sichergestellt, dass auch die Metadaten über die Datenstruktur (Sparsity) geschützt bleiben können.

Die Implementierung ist Open Source verfügbar und kann direkt in bestehende MPC-Frameworks integriert werden, was den Weg für skalierbare, sichere ML-Anwendungen auf realen, sparse Datensätzen ebnet.