💻 computer science

HE-DAP: Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization for Statistical Computation

HE-DAP ist ein plattformübergreifendes Optimierungsframework, das den Kompromiss zwischen Polynom-Evaluierung und Bootstrapping in der homomorphen Verschlüsselung automatisch anpasst, um die Berechnung der Kehrwertwurzel signifikant zu beschleunigen und die End-to-End-Performance für datenschutzwahrende statistische Analysen über verschiedene Hardwareumgebungen hinweg zu verbessern.

Ursprüngliche Autoren: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

Veröffentlicht 2026-06-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

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 versuchen, eine geheime Nachricht an einen Freund zu senden, aber Sie können dies nur über ein sehr strenges, paranoides Postamt tun. Dieses Postamt (das Homomorphe Verschlüsselungssystem) erlaubt es Ihnen, mathematische Operationen an Ihren verschlossenen Boxen durchzuführen, ohne diese jemals zu öffnen. Das ist großartig für die Privatsphäre, hat aber einen Haken: Das Postamt ist unglaublich langsam. Jedes Mal, wenn Sie eine Berechnung durchführen, werden die Boxen schwerer und zerbrechlicher. Wenn Sie zu viele Berechnungen durchführen, gehen die Boxen kaputt und Ihr Geheimnis geht verloren.

Eines der häufigsten mathematischen Probleme, die man in der Statistik lösen muss, ist das Finden der Inversen Quadratwurzel (denken Sie an die „Quadratwurzel eines Bruchs“). Dies ist ein entscheidender Schritt bei vielen Datenanalysen, wie zum Beispiel beim Ermitteln, wie ungewöhnlich ein bestimmter Datenpunkt ist.

Das Problem: Ein „Einheitsrezept“-Fehler

Zuvor hatten Forscher ein Rezept, um dieses Problem der inversen Quadratwurzel innerhalb dieser verschlossenen Boxen zu lösen. Sie nannten dies PP-STAT.

Stellen Sie sich PP-STAT wie ein festes Rezept zum Backen eines Kuchens vor. Das Rezept besagt: „Verwenden Sie genau 29 Tassen Mehl und backen Sie für genau 6 Stunden.“

Das Problem: Dieses Rezept wurde nur in einer ganz bestimmten Küche getestet (einem speziellen Computerchip namens CPU unter Verwendung einer Bibliothek namens Lattigo). In dieser Küche funktionierte das Rezept ganz gut.
Die Realität: Aber was ist, wenn Sie in eine andere Küche umziehen? Vielleicht haben Sie einen superschnellen Ofen (eine GPU) oder einen anderen Herd (eine andere Softwarebibliothek namens HEaaN). In diesen neuen Küchen könnte es ewig dauern, die „29 Tassen Mehl“ zu mischen, während die „6 Stunden Backzeit“ der langsame Teil sein könnte.
Das Ergebnis: Die Verwendung desselben festen Rezepts in einer neuen Küche ist ineffizient. Man verbringt vielleicht 6 Stunden damit, die Zutaten zu mischen, obwohl man sie in 1 Stunde hätte mischen können, oder man verbringt zu viel Zeit mit dem Backen, während man eigentlich schneller fertig gewesen wäre. Die Arbeit zeigte, dass das alte Rezept in einigen Umgebungen fast 6-mal langsamer war, als es hätte sein können, weil es das Falsche zur falschen Zeit tat.

Die Lösung: HE-DAP (Der smarte Küchenassistent)

Die Autoren entwickelten ein neues Werkzeug namens HE-DAP. Stellen Sie sich HE-DAP wie einen smarten Küchenassistenten vor, der nicht einfach nur ein Rezept befolgt, sondern zuerst „die Küche schmeckt“.

Bevor Sie mit Ihrer eigentlichen Arbeit beginnen, führt HE-DAP eine Reihe schneller Tests auf dem spezifischen Computer und der Software durch, die Sie verwenden. Es fragt:

„Ist das Mischen des Mehls (die Mathematik) hier langsam, oder ist die Backzeit (das Zurücksetzen der Boxen) der langsame Teil?“
„Wenn ich weniger Mehl verwende, aber länger backe, ist das schneller?“
„Wenn ich mehr Mehl verwende, aber kürzer backe, ist das schneller?“

Basierend auf diesen Tests schreibt HE-DAP dynamisch ein neues, maßgeschneidertes Rezept nur für Ihre spezifische Maschine. Es entscheidet genau, wie viel „Mehl“ (mathematische Komplexität) und wie viele „Backvorgänge“ (Iterationen) Sie benötigen, um den perfekten Kuchen (ein genaues Ergebnis) in der kürzestmöglichen Zeit zu erhalten.

Wie es in einfachem Deutsch funktioniert

Der Kompromiss: Um die geheimen Boxen vor dem Zerbrechen zu bewahren, haben Sie zwei Möglichkeiten:
- Option A: Führen Sie eine sehr komplexe Berechnung im Vorfeld durch (wie ein Polynom hohen Grades), um eine sehr gute erste Schätzung zu erhalten. Dies ist schnell, wenn die Berechnung einfach ist, aber langsam, wenn sie schwierig ist.
- Option B: Führen Sie eine einfachere Berechnung durch, aber „setzen Sie die Box zurück“ (einen Prozess namens Bootstrapping), um sie vor dem Zerbrechen zu bewahren. Dieser Reset ist in manchen Küchen sehr teuer, in anderen jedoch günstig.
Die Anpassung: HE-DAP findet heraus, welche Option für Ihren spezifischen Computer kostengünstiger ist.
- Auf einer GPU (einer superschnellen Grafikkarte) ist der „Reset-Knopf“ unglaublich schnell. Also sagt HE-DAP: „Lass uns eine einfache Berechnung durchführen und den Reset-Knopf oft drücken!“
- Auf einer CPU (einem Standardprozessor) ist der „Reset-Knopf“ langsam. Also sagt HE-DAP: „Lass uns eine komplexe Berechnung im Vorfeld durchführen, damit wir den Reset-Knopf nicht so oft drücken müssen!“

Die Ergebnisse: Schneller und intelligenter

Die Autoren testeten dieses neue „smarte Werkzeug“ auf drei verschiedenen Arten von Computer-Setups:

Lattigo (Standard-CPU): Es machte den Prozess 1,96-mal schneller.
HEaaN-CPU: Es machte den Prozess 2,18-mal schneller.
HEaaN-GPU: Es machte den Prozess 2,35-mal schneller.

Entscheidend war, dass es nicht nur die Dinge schneller machte; es behielt die Ergebnisse genauso genau bei. In der Tat war es in einigen Fällen sogar genauer als das alte feste Rezept, weil es die Fehler vermied, die entstehen, wenn man ein schlechtes Rezept auf eine neue Maschine erzwingt.

Warum das wichtig ist

Die Arbeit zeigt, dass wir für die praktische Anwendung der datenschutzwahrenden Datenanalyse nicht einfach nur einen statischen Satz von Regeln verwenden können. Wir benötigen Systeme, die sich an die Hardware anpassen können, auf der sie laufen. HE-DAP beweist, dass wir durch die automatische Abstimmung dieser Einstellungen die datenschutzwahrende Statistik praktisch und effizient machen können, indem wir einen langsamen, sperrigen Prozess in etwas verwandeln, das fast doppelt so schnell läuft, ohne die Sicherheit oder Genauigkeit zu opfern.

Kurz gesagt: HE-DAP ist das Werkzeug, das verhindert, dass Sie im Sommer einen schweren Wintermantel und im Winter ein leichtes T-Shirt tragen. Es prüft das Wetter (Ihre Computerumgebung) und gibt Ihnen die perfekte Kleidung (Ihre mathematischen Parameter), um die Aufgabe schnell und komfortabel zu erledigen.

Technisches Resümee: HE-DAP

Problemstellung

Homomorphe Verschlüsselung (HE) ermöglicht datenschutzfreundliche Analysen auf verschlüsselten Daten, leidet jedoch unter einem hohen Rechenaufwand. Ein kritischer Flaschenhals bei statistischen und maschinellen Lernprozessen ist die Berechnung der Kehrwertwurzel ( $1/\sqrt{a}$ ), eine grundlegende Operation, die für Funktionen wie die Z-Score-Normalisierung, Schiefe (Skewness), Kurtosis und den Pearson-Korrelationskoeffizienten erforderlich ist.

Bestehende State-of-the-Art-Methoden, wie PP-STAT [13] und HEaaN-STAT [24], verlassen sich auf feste Parameterkonfigurationen für die Berechnung der Kehrwertwurzel. Diese Konfigurationen beinhalten typischerweise einen spezifischen Grad für die Chebyshev-Polynomapproximation (verwendet zur Initialisierung der Newton-Verfahren) und eine feste Anzahl an Newton-Raphson-Iterationen. Die Autoren identifizieren einen grundlegenden Mangel in diesem statischen Ansatz: Die relativen Rechenkosten der zwei primären HE-Operationen – Chebyshev-Polynom-Evaluierung und Bootstrapping (Rauschmanagement) – variieren drastisch (um bis zu das 6-fache) zwischen verschiedenen HE-Bibliotheken (z. B. Lattigo vs. HEaaN) und Hardwareumgebungen (CPU vs. GPU).

Folglich ist eine Konfiguration, die für eine Umgebung optimiert ist (z. B. Lattigo auf einer CPU, wo Bootstrapping langsam ist und hochgradige Polynome bevorzugt werden), in einer anderen Umgebung (z. B. HEaaN-GPU, wo Bootstrapping schnell und die Polynom-Evaluierung der Flaschenhals ist) suboptimal oder ineffizient. Diese Abhängigkeit von der Umgebung macht bestehende Frameworks nicht generalisierbar und ineffizient, wenn sie in heterogenen Systemen eingesetzt werden.

Methodik: HE-DAP

Um dies zu adressen, schlagen die Autoren HE-DAP (Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization) vor, ein plattformübergreifendes Framework, das automatisch die optimalen Parameter für die Berechnung der Kehrwertwurzel basierend auf der spezifischen Ausführungsumgebung bestimmt.

Kernmechanismus

HE-DAP operiert während einer Bereitstellungsphase (vor der eigentlichen Datenverarbeitung), um die Leistungscharakteristika des Zielservers zu profilieren. Es wählt dynamisch drei Schlüsselparameter für den CryptoInvSqrt-Algorithmus aus:

$d$ : Der Grad der Chebyshev-Polynomapproximation.
$c$ : Ein binärer Indikator für Pre-Bootstrapping (Anwendung von Bootstrapping auf den Eingabe-Ciphertext vor der Berechnung der Kehrwertwurzel).
$i$ : Die Anzahl der Newton-Raphson-Iterationen.

Algorithmischer Arbeitsablauf

Profilierung: HE-DAP evaluiert alle möglichen Eingabe-Ciphertext-Level ( $l$ ) im Bereich von $l_{BTS} + 1$ bis $l_{max}$ .
Exploration des Suchraums: Für jedes Level testet es Kombinationen aus Polynomgraden ( $d$ $d$ ), Pre-BTS-Indikatoren ( $c$ $c$ ) und Iterationszahlen ( $i$ $i$ ).
- Wenn das Eingabe-Level unzureichend für die Polynomtiefe ist, wird Pre-BTS ( $c=1$ ) in Betracht gezogen.
- Wenn das Level ausreichend ist, wird ohne Pre-BTS fortgefahren ( $c=0$ ).
Optimierungskriterien: Für jede Kombination misst das System den mittleren relativen Fehler (MRE) und die Laufzeit. Es identifiziert die optimale Iterationszahl ( $i$ ), die einen Ziel-MRE-Schwellenwert erfüllt.
Parameterwahl: Das Framework speichert zwei optimale Tupel für jedes Level:
- Genauigkeitsorientiert: Minimiert die Laufzeit unter Einhaltung einer strikten MRE-Beschränkung.
- Geschwindigkeitsorientiert: Minimiert die Laufzeit unabhängig vom MRE (nützlich für Anwendungen, die höhere Fehler tolerieren).
Laufzeit-Anwendung: Während der eigentlichen statistischen Analyse verwendet der Server die vorab berechneten optimalen Parameter entsprechend dem aktuellen Ciphertext-Level, wodurch manuelle Abstimmungen oder feste, suboptimale Standardwerte entfallen.

Zentrale Beiträge

HE-DAP Framework: Die Einführung eines neuartigen adaptiven Optimierers, der die Kehrwertwurzel-Operation automatisch für diverse HE-Bibliotheken und Hardware konfiguriert und somit von statischen, umgebungsspezifischen Parametern abweicht.
Leistungsgewinne: Nachweis, dass HE-DAP die Kernberechnung der Kehrwertwurzel signifikant beschleunigt. In der HEaaN-GPU-Umgebung erreicht es eine bis zu 2,35-fache Beschleunigung gegenüber der festen Konfiguration von PP-STAT bei gleichzeitiger Beibehaltung einer hohen numerischen Genauigkeit (MRE $\le 3,1 \times 10^{-8}$ ).
Umfassende Evaluierung: Eine rigorose Evaluierung über drei verschiedene Settings (Lattigo, HEaaN-CPU und HEaaN-GPU) und vier Kern-Statistikmaße (Z-Score, Schiefe, Kurtosis, Pearson-Korrelation). Die Ergebnisse bestätigen, dass HE-DAP konsistent optimale Konfigurationen sowohl für CPU- als auch für GPU-Umgebungen findet.
Open Source: Die Veröffentlichung der vollständigen HE-DAP-Implementierung zur Gewährleistung der Reproduzierbarkeit.

Experimentelle Ergebnisse

Die Autoren evaluierten HE-DAP gegen PP-STAT (Lattigo-basiert) und HEaaN-STAT (GPU-basiert) unter Verwendung des CKKS-Schemas.

Leistung der Kehrwertwurzel:
- HEaaN-GPU: HE-DAP beschleunigte PP-STAT um das 2,35-fache bei Level 12 und um das 1,79-fache bei Level 7 (genauigkeitsorientiert) im Vergleich zur festen PP-STAT-Konfiguration. Im Vergleich zu HEaaN-STAT erreichte es eine bis zu 2,15-mal schnellere Laufzeit bei niedrigerem MRE.
- HEaaN-CPU: Erzielte eine 2,18-fache Beschleunigung gegenüber PP-STAT bei Level 12.
- Lattigo: Erzielte eine 1,96-fache Beschleunigung gegenüber PP-STAT bei Level 11, während es gleichzeitig den MRE im Vergleich zum Baseline-PP-STAT um das 79-fache reduzierte.
End-to-End-Statistische Analyse:
- Die Anwendung von HE-DAP auf statistische Maße (ZNorm, Skew, Kurt, PCC) auf realen Datensätzen (UCI Adult und Medical Cost Insurance) führte zu konsistenter Beschleunigung.
- Auf dem Adult-Datensatz reduzierte HE-DAP die Laufzeit im Vergleich zu PP-STAT um 42%–44%, während ein ähnlicher MRE beibehalten wurde.
- Beim Insurance-Datensatz erreichten die Laufzeitreduktionen 44,6%.
Trade-off-Analyse: Der Modus "Geschwindigkeitsorientiert" ermöglichte eine noch größere Beschleunigung (bis zu 6,34-mal schneller als HEaaN-STAT auf der GPU) auf Kosten eines höheren MRE, was die Flexibilität des Frameworks für unterschiedliche Anwendungserfordernisse demonstriert.

Bedeutung und Ansprüche

Das Paper behauptet, dass HE-DAP zeigt, dass eine fundamentale Parameteroptimierung datenschutzfreundliche statistische Analysen in großem Maßstab praktikabel machen kann. Durch die automatisierte Anpassung an heterogene Ausführungsumgebungen löst HE-DAP die Ineffizienz, die durch feste Parameter in bestehenden Frameworks verursacht wird.

Die Autoren betonen, dass ihr Ansatz umgebungswahrnehmend ist, da sie anerkennen, dass das optimale Gleichgewicht zwischen Polynom-Evaluierung und Bootstrapping nicht universell ist, sondern von der spezifischen HE-Bibliothek und Hardware abhängt. Durch das dynamische Navigieren dieses Trade-offs stellt HE-DAP sicher, dass der grundlegende Baustein der statistischen Analyse (Kehrwertwurzel) mit maximaler Effizienz ausgeführt wird, wodurch die Performance komplexer End-to-End-Workflows gesteigert wird, ohne die Datenschutzgarantien der homomorphen Verschlüsselung zu gefährden.

Das Paper schließt mit dem Hinweis, dass die Bereitstellungsphase (Parametersuche) einen Zeitaufwand verursacht (insbesondere bei CPU-Bibliotheken wie Lattigo), dies jedoch ein einmaliger Setup-Aufwand ist, der signifikante, dauerhafte Leistungsvorteile während der eigentlichen Datenverarbeitungsphase liefert. Für die Zukunft wird vorgeschlagen, die Explorationszeit durch die Nutzung messbarer Proxys anstelle einer erschöpfenden Evaluierung zu reduzieren.