💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

SafeStats ist ein effizientes Toolkit für sichere Zwei-Parteien-Berechnungen, das speziell auf statistische Analysen zugeschnitten ist und durch spezialisierte Protokolle die Häufigkeitszählung, Sortierung und nichtlineare mathematische Funktionen optimiert, wodurch im Vergleich zu Allzweck-Bibliotheken signifikante Geschwindigkeitssteigerungen und Reduzierungen des Kommunikationsaufwands erzielt werden.

Ursprüngliche Autoren: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

Veröffentlicht 2026-07-29

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie und ein Freund versuchen, gemeinsam ein Rätsel zu lösen, aber Sie haben beide eine strikte Regel: Sie dürfen Ihre privaten Hinweise niemals untereinander zeigen. Vielleicht vergleichen Sie Ihre Bankkonten, um zu sehen, wer mehr Geld hat, ohne die tatsächlichen Zahlen preiszugeben, oder Sie prüfen, ob Ihre Krankenakten mit einem bestimmten Krankheitsmuster übereinstimmen, ohne Ihre Krankengeschichte offenzulegen. Dies ist die Welt der Secure Two-Party Computation (2PC). Denken Sie an ein magisches, verschlossenes Zimmer, in dem zwei Personen ihre geheimen Zutaten mischen können, um einen Kuchen (das Ergebnis) zu backen, ohne dass die andere Person jemals in ihren eigenen Vorratsschrank spähen darf. Lange Zeit haben Wissenschaftler erstaunliche Werkzeuge gebaut, die bei einfacher Mathematik in diesem verschlossenen Zimmer helfen, wie etwa das Addieren oder Multiplizieren geheimer Zahlen. Aber wenn es um komplexere Aufgaben geht – wie das Sortieren einer Liste geheimer Alter oder das Zählen, wie viele Menschen in bestimmte Kategorien passen – waren die alten Werkzeuge langsam, klobig und oft zu teuer für den Einsatz in der Praxis.

Hier kommt SAFESTATS ins Spiel, ein neues Toolkit, das von den Forschern Tanren Liu und seinem Team entwickelt wurde, um diese statistischen Rätsel viel einfacher zu lösen. Wenn die alten Methoden so wären, als würde man versuchen, ein Kartendeck zu sortieren, indem man jede einzelne Karte mit jeder anderen Karte einzeln vergleicht, dann ist SAFESTATS wie ein superintelligenter Assistent, der das ganze Deck in einer einzigen, schnellen Bewegung sortiert. Das Team erkannte, dass die meisten statistischen Aufgaben im Wesentlichen auf drei Hauptaufgaben basieren: Zählen, wie oft Dinge vorkommen, sie in eine Reihenfolge bringen oder einige knifflige nicht-lineare Mathematik durchführen. Durch die Erfindung cleverer Abkürzungen für diese drei Aufgaben haben sie ein System geschaffen, das signifikant schneller ist und viel weniger „Reden“ (Kommunikation) zwischen den beiden Geheimnisträgern erfordert. In Tests war ihre neue Methode für bestimmte Aufgaben bis zu 20 Mal schneller als bisherige Versuche, was beweist, dass man komplexe Datenanalysen auf privaten Informationen durchführen kann, ohne ewig auf die Antwort zu warten.

Die drei Zaubertricks von SAFESTATS

Die Forscher begannen damit, ein Standard-Tabellenprogramm (wie Microsoft Excel) zu untersuchen, um zu sehen, was Menschen tatsächlich tun, wenn sie Daten analysieren. Sie fanden heraus, dass fast alles – ob man nun den „häufigsten“ Wert (den Modus), den „mittleren“ Wert (den Median) ermittelt oder einen Chi-Quadrat-Test durchführt – auf nur drei Kernbausteinen beruht. SAFESTATS hat diese drei Bausteine neu erfunden, damit sie geheim und effizient funktionieren.

1. Der „Shift“-Trick zum Zählen
Stellen Sie sich vor, Sie haben eine Reihe von 100 leeren Boxen und möchten zählen, wie oft eine geheime Zahl, sagen wir die „7“, in einer Liste von Daten vorkommt. Der alte Weg bestand darin zu fragen: „Ist diese Zahl 7?“ – und das für jedes einzelne Element in der Liste. Wenn Sie eine Million Elemente hätten, müssten Sie eine Million Fragen stellen, was ewig dauert.
SAFESTATS nutzt stattdessen einen „Shift“-Trick (Verschiebe-Trick). Stellen Sie sich vor, Sie haben einen einzigen Lichtschalter, der eingeschaltet ist, während alle anderen Schalter ausgeschaltet sind. Wenn Ihre geheime Zahl 7 ist, schieben Sie dieses „An“-Licht einfach sieben Positionen nach rechts. Jetzt befindet sich das Licht in der 7. Box. Dies machen Sie für jedes Element in Ihrer geheilen Liste, aber Sie tun dies auf eine Weise, dass niemand weiß, in welche Box Sie das Licht bewegen. Am Ende addieren Sie einfach alle Lichter in jeder Box auf. Wenn die 7. Box 50 Lichter hat, wissen Sie, dass die Zahl 7 genau 50 Mal vorkam. Diese „gleitende“ Methode ist unglaublich schnell, weil sie die langsamen, repetitiven „Ist es gleich?“-Fragen vermeidet. Das Team fand heraus, dass dieser Ansatz das Zählen 4- bis fast 8-mal schneller machte und die Menge der zwischen den beiden Parteien ausgetauschten Daten in ähnlichem Maße reduzierte.

2. Der „Bucket“-Trick zum Sortieren
Das Sortieren geheimer Daten ist normalerweise ein Albtraum, da es erfordert, Zahlen zu vergleichen, um zu sehen, welche größer ist. Aber was wäre, wenn Sie gar keinen Vergleich benötigen? SAFESTATS nutzt eine Methode namens „Counting Sort“ (Zählsortierung), die perfekt ist, wenn die Zahlen, die Sie sortieren, nicht riesig sind (wie etwa das Sortieren von Alterswerten von 0 bis 100, statt zufälliger, riesiger Zahlen).
Denken Sie an eine Post mit 100 Ablagefächern. Anstatt zu fragen: „Ist dieser Brief für Fach 5 oder Fach 6?“, werfen Sie den Brief einfach in das Fach, das seiner Nummer entspricht. SAFESTATS macht dies geheim. Sie verwenden ein spezielles „Segment-Indikator“-Protokoll. Stellen Sie sich vor, Sie haben eine geheime Liste von Zahlen. Anstatt die Zahlen einzeln zu sortieren, erstellt das System eine „Karte“, die besagt: „Alle 5er gehören in diesen spezifischen Bereich der endgültigen Liste.“ Dann werden alle 5er in einem großen Schwung in diesen Bereich geworfen. Dies umgeht die Notwendigkeit langsamer, geheimer Vergleiche. Bei Datensätzen mit kleinen Wertebereichen wurde festgestellt, dass diese neue Methode 3,4- bis 20,5-mal schneller ist als die besten bestehenden Methoden und die Kommunikationskosten um bis zu das 7,6-fache senkt.

3. Der „Bisection“-Trick für schwere Mathematik
Einige statistische Formeln beinhalten knifflige Mathematik, wie Quadratwurzeln oder Logarithmen, die schwer geheim zu berechnen sind. Der übliche Weg besteht darin, die Zahl zuerst auf eine handhabbare Größe zu schrumpfen (wie das Herauszoomen auf einer Landkarte) und dann die Antwort mit einer Polynomialformel zu erraten. Der langsame Teil war dabei, herauszufinden, wie weit man herauszoomen muss.
Die alte Methode war wie das Durchsuchen eines Buches Seite für Seite, um ein bestimmtes Wort zu finden. SAFESTs nutzt eine „Bisection“-Methode (Bisection/Halbierung), was wie das Spiel „Größer oder Kleiner“ funktioniert. Anstatt jede Seite zu prüfen, teilen Sie das Buch in der Mitte, prüfen, ob das Wort in der ersten oder zweiten Hälfte steht, und teilen dann diese Hälfte erneut. Sie halbieren den Suchraum immer weiter, bis Sie genau gefunden haben, wo die Zahl angepasst werden muss. Dieser „Teile und Herrsche“-Ansatz reduzierte die benötigte Zeit für diese mathematischen Funktionen um das 1,2- bis 1,7-fache und sparte auch etwas Kommunikationszeit ein.

Alles zusammenfügen: Der Chi-Quadrat-Test

Um zu beweisen, dass ihr Toolkit funktioniert, testeten die Forscher SAFESTATS in 14 verschiedenen realen statistischen Szenarien. Ein herausragendes Beispiel war der Chi-Quadrat-Test, eine gängige Methode, um zu sehen, ob zwei Dinge miteinander in Beziehung stehen (wie etwa, ob das Tragen eines roten Hemdes Ihr Glück beeinflusst).
Als sie versuchten, diesen Test mit den alten, universell einsetzbaren Werkzeugen durchzuführen, war er langsam und „gesprächig“. Doch als sie SAFESTATS verwendeten, waren die Ergebnisse beeindruckend: Der Test lief 1,5-mal schneller und die Menge der Daten, die die beiden Parteien hin und her schicken mussten, wurde um das 4,2-fache reduziert.

Das Paper behauptet diese Ergebnisse nicht nur; die Forscher haben das System tatsächlich gebaut und die Zahlen ausgewertet. Sie zeigten, dass sie durch die Konzentration auf die spezifischen Bedürfnisse der statistischen Analyse – anstatt zu versuchen, ein „Einheitswerkzeug für alles“ zu bauen – einen viel effizienteren Weg schaffen konnten, um Daten privat zu halten und dennoch die Antworten zu erhalten, die wir benötigen. Es ist eine Erinnerung daran, dass der beste Weg, ein Problem zu lösen, manchmal nicht darin besteht, einen größeren Hammer zu bauen, sondern einen besseren Schraubendreher zu erfinden.

Technisches Resümee: SAFESTATS

Problemstellung

Die statistische Analyse auf sensiblen Datensätzen (z. B. medizinische Unterlagen, Finanztransaktionen) ist entscheidend für die Entscheidungsfindung, wirft jedoch erhebliche Datenschutzbedenken auf. Während die sichere Zwei-Parteien-Berechnung (Secure Two-Party Computation, 2PC) bei grundlegenden Primitiven (Addition, Multiplikation) und Machine-Learning-Anwendungen bereits signifikante Fortschritte gemacht hat, bleibt sie für spezifische statistische Funktionen ineffizient. Bestehende Ansätze versuchen typischerweise, statistische Operationen (z. B. Median, Rang, Modus) durch direkte Komposition allgemeiner 2PC-Primitive zu reproduzieren. Diese „naive“ Komposition führt zu prohibitiven Overheads; so kann beispielsweise die Berechnung einer Rangfunktion über $2^{12}$ Elemente selbst mit hochmodernen Protokollen über 18 Minuten dauern. Die primären Engpässe sind die Abhängigkeit von teuren sicheren Gleichheitstests, sicheren Vergleichen und sequenziellen Schaltkreis-Tiefen, die nicht gut skalieren, wenn es um statistische Aufgaben mit großen Datensätzen und kleinen, enumerierbaren Merkmalsdomänen geht.

Methodik

Die Autoren schlagen SAFESTATS vor, ein sicheres Toolkit, das speziell für die 2PC-statistische Analyse maßgeschneidert ist. Der Entwicklungsprozess beinhaltete eine Analyse der Microsoft Excel Statistikbibliothek, um festzustellen, dass die meisten statistischen Operationen auf drei Kernbausteinen beruhen: Häufigkeitszählung, Sortierung und nicht-lineare mathematische Funktionen. SAFESTATS führt spezialisierte, effiziente 2PC-Protokolle für jeden dieser Blöcke ein und vermeidet dabei nach Möglichkeit allgemeine Primitiven.

1. Sichere Häufigkeitszählung (Shift-basierte Strategie)

Traditionelle Methoden berechnen die Häufigkeit, indem sie für jedes Eingabeelement $m$ Gleichheitstests durchführen, was zu $O(m\ell)$ Oblivious-Transfer-Aufrufen (OT) führt.

Innovation: SAFESTATS stellt fest, dass das Ergebnis der Prüfung, ob ein Eingang $x$ einem Wert $v \in [0, m-1]$ entspricht, einen booleschen Einheitsvektor $\vec{e}_x$ bildet. Anstatt diesen durch $m$ Gleichheitstests zu konstruieren, behandelt das Protokoll $\vec{e}_x$ als eine nach rechts verschobene Version eines Basis-Einheitsvektors $\vec{e}_0$ mit dem Versatz $x$ .
Mechanismus: Das Protokoll nutzt eine sichere shift-basierte Strategie mittels Random Vector Oblivious Shift Evaluation ( $F_{RVOSE}$ ). Es ersetzt $m$ Gleichheitstests durch eine einzige Vektorshift-Operation.
Optimierung: Für Fälle, in denen die Modus-Häufigkeit $n/2$ übersteigt, führen die Autoren eine Optimierung auf Basis des Chinesischen Restsatzes (CRT) ein. Dies zerlegt die große Merkmalsdomäne in kleinere, teilerfremde Subdomänen, was die Konstruktion kürzerer Häufigkeitsvektoren und die lokale Rekonstruktion des Modus ermöglicht.

2. Sicheres Sortieren (Zählbasierte Methode mit Segment-Indikatoren)

Allgemeine sichere Sortierverfahren (z. B. basierend auf sicherem Vergleich) leiden unter hoher Schaltkreistiefe und Kommunikationsrunden, die primär durch die Kosten des sicheren Vergleichs dominiert werden.

Innovation: SAFESTATS schlägt ein sicheres zählbasiertes Sortierverfahren vor, das den Bedarf an sicheren Vergleichen eliminiert.
Mechanismus: Das Protokoll besteht aus der Konstruktion des Häufigkeitsvektors (mit der oben genannten Methode) und dem Einfügen von Elementen. Für das Einfügen wird ein sicheres Segment-Indikator-Protokoll eingeführt. Dieses Protokoll generiert einen geheimnisgeteilten Vektor, der über einem spezifischen Intervall $[a, b]$ den Wert 1 und andernorts 0 aufweist.
Effizienz: Durch die Verwendung des Segment-Indikators können alle Elemente mit demsem Wert über eine einzige elementweise Multiplikation in den Ausgabevektor eingefügt werden, wodurch eine konstante ( $O(1)$ ) Schaltkreistiefe für die Einfügephase erreicht wird. Dies reduziert die OT-Komplexität von $O(n \log n \log(nm))$ auf $O(n(m + \log m))$ .
Spezialfall (Perzentile): In Anerkennung dessen, dass Perzentile keine vollständige Sortierung erfordern, formulieren die Autoren das Problem als Intervall-Test-Problem um. Indem sie prüfen, welches Intervall des Präfixsummen-Häufigkeitsvektors den Zielrang $k$ enthält, vermeiden sie die vollständige Sortierung und optimieren so die Performance für kleine Merkmalsdomänen weiter.

3. Sichere nicht-lineare mathematische Funktionen (Bisektions-basierte Bereichsreduktion)

Die sichere Evaluierung nicht-linearer Funktionen (z. B. Logarithmus, Quadratwurzel) folgt typischerweise einem „Reduziere-dann-Approximiere“-Paradigma, wobei die kostspieligste Phase die Bereichsreduktion (Identifizierung des bedeutendsten nicht-Null-Bits, MSNZ) ist.

Innovation: Bestehende Protokolle identifizieren das MSNZ-Bit über einen linearen, sequenziellen Scan der Ziffern, was $O(d)$ Kommunikationsrunden erfordert.
Mechanismus: SAFESTATS führt ein bisektions-basiertes Bereichsreduktionsprotokoll ein. Anstatt sequenziell zu scannen, partitioniert das Protokoll die Eingabe rekursiv und wählt in jedem Schritt die nicht-null Hälfte aus.
Effizienz: Dies reduziert die Kommunikationsrunden für die MSNZ-Identifizierung von $O(d)$ auf $O(\log d)$ und senkt damit die Latenz für die Evaluierung nicht-linearer Funktionen erheblich.

Wichtigste Beiträge

Sichere Zählfunktion: Ein shift-basiertes Häufigkeitszählungsprotokoll, das die OT-Aufrufe von $O(m\ell)$ auf $O(\log m)$ reduziert, inklusive einer CRT-basierten Variante zur Modus-Berechnung.
Sichere Sortierfunktion: Ein zählbasiertes Sortierprotokoll unter Verwendung eines sicheren Segment-Indikator-Mechanismus, um konstante Kommunikationsrunden zu erreichen und sichere Vergleiche zu vermeiden, ergänzt durch einen Intervall-Test-Ansatz für Perzentile.
Sichere nicht-lineare Funktionen: Ein bisektions-basiertes MSNZ-Identifikationsprotokoll, das die Kommunikationsrunden von $O(n)$ auf $O(\log n)$ reduziert, zusammen mit einer Analyse von Polynom-Approximationsbereichen für die Intervallkompression.
Implementierung und Evaluierung: Eine vollständige Implementierung von SAFESTATS, die gegen 14 gängige statistische Fälle (einschließlich Modus, Median, Rang, Chi-Quadrat-Test usw.) getestet und gegen allgemeine 2PC-Bibliotheken (z. B. EzPC) verglichen wurde.

Ergebnisse

Die Autoren haben SAFESTATS implementiert und auf 14 statistischen Analysefällen getestet. Die Ergebnisse zeigen konsistente Verbesserungen gegenüber Baselines, die direkt allgemeine 2PC-Primitive verwenden:

Chi-Quadrat-Test: Erzielte eine 1,5 $\times$ schnellere Laufzeit und eine 4,2 $\times$ Reduktion der Kommunikation.
Häufigkeitszählung: Erzielte eine 4,0–7,9 $\times$ Verbesserung der Laufzeit und eine 3,1–8,6 $\times$ Verbesserung der Kommunikation im Vergleich zu Gleichheits-basierten Methoden.
Sicheres Sortieren: Erzielte eine 3,4–20,5 $\times$ schnellere Laufzeit und eine 1,3–7,6 $\times$ Reduktion der Kommunikation im Vergleich zu bisherigen vergleichsbasierten Sortierverfahren (für Szenarien, in denen $m \le \log_2 n$ ).
Nicht-lineare Funktionen: Erzielte eine 1,2–1,7 $\times$ Reduktion der Laufzeit und eine 1,15–1,16 $\times$ Reduktion der Kommunikation im Vergleich zum aktuellen Stand der Technik.

Bedeutung

Das Paper behauptet, dass SAFESTATS ein praktisches und effizientes Toolkit für die datenschutzwahrende statistische Analyse bereitstellt und damit eine Lücke schließt, in der bestehende 2PC-Lösungen für reale statistische Anwendungen zu langsam sind. Durch die Zerlegung statistischer Operationen in drei Kernfunktionen und das Design spezialisierter Protokolle für jede dieser Funktionen reduziert SAFESTATS signifikant den Rechen- und Kommunikationsaufwand der sicheren statistischen Analyse. Die Arbeit ist im Rahmen der Universal Composability (UC) formal sicher gegen semi-ehrliche Angreifer nachgewiesen. Die Autoren betonen, dass ihr Ansatz die sichere statistische Analyse für Anwendungen mit großen Datensätzen und kleinen Merkmalsdomänen, wie etwa die Analyse der Beziehung zwischen Einkommensniveau und Bildungsstand, praktikabel macht.