💻 computer science

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

Dieses Paper schlägt die Independent Vector Evaluation (IVE) vor, eine neuartige Methode für den privaten Embedding-Lookup unter vollhomomorpher Verschlüsselung, welche die kostspielige Generierung von One-Hot-Vektoren durch eine linear unabhängige Repräsentation ersetzt, um eine bis zu 78,4-fache Beschleunigung der amortisierten Lookup-Zeit zu erreichen.

Ursprüngliche Autoren: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

Veröffentlicht 2026-06-03

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

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 besitzen eine riesige, geheime Bibliothek von Büchern (die Embedding-Tabelle), die auf einem gigantischen Server gespeichert ist. Jedes Buch repräsentiert ein bestimmtes Wort oder eine bestimmte Idee, und in jedem Buch befindet sich ein einzigartiger „Fingerabdruck“ (ein Embedding-Vektor), der einem Computer hilft, die Bedeutung dieses Wortes zu verstehen.

Normalerweise, wenn Sie dem Server eine Frage stellen wollen, senden Sie ihm ein Wort. Der Server sucht dieses Wort in seiner Bibliothek, greift seinen Fingerabdruck heraus und nutzt ihn, um Ihnen eine Antwort zu geben.

Das Privatsphäre-Problem:
Sie möchten nicht, dass der Server weiß, welches Wort Sie angefragt haben. Vielleicht fragen Sie nach einem medizinischen Symptom, einem Finanzgeheimnis oder etwas Sensiblem. Wenn Sie einfach das Wort senden, sieht der Server es. Wenn Sie einen Geheimcode senden, kann der Server ihn nicht lesen, um das richtige Buch zu finden.

Die alte Methode (Die „One-Hot“-Methode):
Früher mussten Sie, um Ihre Frage geheim zu halten, eine spezielle verschlüsselte Liste senden. Stellen Sie sich vor, diese Liste hat einen Platz für jedes einzelne Wort in der Bibliothek (Millionen von Plätzen). Sie verschlüsseln eine „1“ an der Stelle für Ihr Wort und eine „0“ überall sonst.

Das Problem: Der Server muss jeden einzelnen Platz überprüfen, um zu sehen, wo die „1“ steht. Es ist, als müsste der Server durch jede einzelne Gasse einer riesigen Bibliothek gehen und jedes einzelne Buch prüfen, nur um das eine zu finden, das Sie wollen. Das kostet eine enorme Menge Zeit und Rechenleistung, was den gesamten Prozess sehr langsam macht.

Die neue Methode (IVE – Independent Vector Evaluation):
Dieses Paper schlägt eine clevere Abkürzung vor. Anstatt eine Liste mit einer „1“ und Millionen von „0“en zu senden, haben die Autoren erkannt, dass der Server nicht eigentlich diese spezifische Liste benötigt. Er benötigt nur irgendeinen eindeutigen Code, der auf das richtige Buch verweist, solange der Server weiß, wie er diesen Code wieder in den richtigen Fingerabdruck übersetzen kann.

Stellen Sie sich das so vor:

Die alte Methode: Sie senden eine Karte mit einem riesigen roten „X“ an einem spezifischen Haus und leeren Flächen überall sonst. Der Server muss die ganze Karte scannen, um das „X“ zu finden.
Die neue Methode (IVE): Sie senden einen einfachen Satz von Koordinaten (wie „Links abbiegen, dann 3 Häuserblocks weit gehen“). Der Server kennt eine geheime Formel (einen Basiswechsel), die diese Koordinaten sofort in die exakte Adresse des Hauses verwandelt, das Sie suchen.

Wie es funktioniert (Der Zaubertrick):

Der geheime Code: Anstatt einer „1 und 0s“-Liste sendet der Client eine kompakte, verschlüsselte Zahl.
Die mathematische Magie: Der Server verwendet ein mathematisches Werkzeug namens Diskrete Kosinustransformation (DCT). Denken Sie an die DCT als einen speziellen Übersetzer. Er nimmt Ihre einfache verschlüsselte Zahl und verwandelt sie schnell in einen eindeutigen „Fingerabdruck“-Code unter Verwendung einfacher Mathematik (Potenzen einer Zahl), anstatt langsame, schwere Prüfungen durchzuführen.
Die Übersetzung: Der Server verfügt über ein vorberechnetes „Wörterbuch“ (eine Basiswechsel-Matrix), das weiß, wie er Ihren neuen „Fingerabdruck“-Code zurück in densün exakt gleichen Buch-Fingerabdruck übersetzt, den die alte Methode gefunden hätte.

Warum das wichtig ist:

Geschwindigkeit: Die alte Methode war, als würde man durch jede einzelne Gasse gehen. Die neue Methode ist wie die Nutzung eines GPS. Das Paper zeigt, dass dies die Suche um das bis zu 78-fache beschleunigt.
Effizienz: Es spart eine enorme Menge an Computerenergie. In Tests sank die Zeit, die allein für das „Finden des Buches“ aufgewendet wurde, von 99,6 % der Gesamtzeit auf nur 66,3 %.
Privatsphäre: Der Server erfährt immer noch nichts über Ihr spezifisches Wort, aber er findet die Antwort viel schneller.

Zusammenfassend:
Die Autoren haben einen Weg gefunden, damit der Server nicht mehr Millionen kleiner Prüfungen durchführen muss, um Ihr geheimes Wort zu finden. Stattdessen geben sie ihm einen einfachen verschlüsselten Hinweis und einen magischen Übersetzungsschlüssel. Dies ermöglicht es dem Server, die gewünschten Informationen fast augenblicklich zu finden, während Ihre Geheimnisse sicher bleiben.

Technisches Resümee: Private Embedding-Abfrage mit verschlüsselten kompakten Abfragen unter Verwendung von Fully Homomorphic Encryption

Problemstellung

In der privatsphärenwahrenden maschinellen Lernverfahren (PPML) unter Verwendung von Fully Homomorphic Encryption (FHE) entsteht ein kritischer Engpass bei der Inferenz von Modellen, die auf diskreten Eingaben basieren, wie etwa bei Natural Language Processing (NLP) und Empfehlungssystemen. Diese Modelle beginnen typischerweise mit einer Embedding-Schicht, welche einen diskreten Index (z. B. ein Wort-Token) auf einen kontinuierlichen Vektor abbildet.

Unter FHE kann der Server keinen Standard-Speicherzugriff basierend auf einem verschlüsselten Index durchführen. Stattdessen muss die Abfrage durch homomorphe Arithmetik realisiert werden. Bestehende Ansätze stehen vor einem Zielkonflikt:

Client-seitige Abfrage: Der Client sendet den verschlüsselten Embedding-Vektor. Dies führt zu einem massiven Kommunikationsaufwand, der proportional zur Dimension des Embeddings ( $d$ ) ist, was für große Tabellen (z. B. GloVe mit 1,9 Mio. Tokens) prohibitiv hoch ist.
Server-seitige Abfrage mit One-Hot-Generierung: Der Client sendet einen kompakten verschlüsselten Skalar-Index. Der Server muss dann einen One-Hot-Vektor homomorph konstruieren, um das Embedding auszuwählen. Vorherige Arbeiten (Kim et al., ICML 2024) erreichen dies mithilfe einer verschlüsselten Indikatorfunktion (EIF), was jedoch $O(p \log p)$ homomorphe Operationen erfordert (wobei $p$ die Tabellengröße ist), was eine erhebliche multiplikative Tiefe verbraucht und zum dominierenden Kostenfaktor in der Inferenz-Pipeline wird.

Das Ziel ist es, eine Private Embedding Lookup (PEL) zu erreichen, die eine kompakte Kommunikation auf der Client-Seite beibehält (Versendung eines skalaren Index) und gleichzeitig die homomorphe Rechenkosten auf der Server-Seite minimiert, indem der teure Schritt der One-Hot-Generierung vermieden wird.

Methodik: Independent Vector Evaluation (IVE)

Die Autoren schlagen die Independent Vector Evaluation (IVE) vor, eine Methode, die die Konstruktion eines One-Hot-Vektors vollständig umgeht.

Kernidee

Der Server benötigt nicht zwingend einen One-Hot-Vektor ( $e_j$ ), um das Embedding $M_j$ abzurufen. Er benötigt lediglich eine Repräsentation des Index $j$ , die über verschiedene Indizes hinweg linear unabhängig ist. Wenn eine Menge von Vektoren $\{v_j\}$ linear unabhängig ist, existiert eine Basiswechselmatrix $L$ , sodass $L v_j = e_j$ gilt. Folglich kann die Embedding-Abfrage als $M_j = M e_j = M (L v_j) = (M L) v_j$ umgeschrieben werden. Da $M$ und $L$ im Klartext bekannt sind, kann der Server die Matrix $M' = ML$ vorberechnen. Die Online-Aufgabe verschiebt sich somit von der Generierung eines One-Hot-Vektors zur Evaluierung des Vektors $v_j$ .

Vektorkonstruktion und Stabilität

Um Effizienz und numerische Stabilität unter dem CKKS-Schema (das approximative Arithmetik unterstützt) zu gewährleisten:

Effizienz: Die Vektoren $v_j$ werden unter Verwendung aufeinanderfolgender Potenzen eines einzelnen verschlüsselten Wertes $\alpha_j$ konstruiert. Dies ermöglicht es dem Server, die Vektor-Komponenten mittels Standard-Arithmetikoperationen (Multiplikationen) zu generieren, anstatt komplexe Gleichheitstests durchzuführen.
Stabilität: Um die Fehlerverstärkung während des Basiswechsels zu verhindern, muss die Matrix $L$ gut konditioniert (idealerweise orthogonal) sein. Die Autoren nutzen eine Diskrete Kosinustransformations-Matrix (DCT). Durch die Verwendung von Einheitswurzeln und der Trennung von Real- und Imaginärteil konstruieren sie eine orthogonale Basis, die mit den komplexen Arithmetikfähigkeiten von CKKS harmoniert.

Algorithmischer Ablauf

Client: Verschlüsselt den Index $j$ in einen Wert $\alpha_j$ (abgeleitet aus Einheitswurzeln) und überträgt diesen als kompakte skalare Abfrage.
Server (IVE-Phase):
- Empfängt den verschlüsselten $\alpha_j$ .
- Berechnet die Potenzen $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ mithilfe eines Multiplikationsbaums (logarithmische Tiefe).
- Trennt die Real- und Imaginärteile mittels Konjugation, um den Vektor $v_j$ zu bilden.
- Dieser Prozess erfordert $O(p)$ homomorphe Operationen, was eine signifikante Reduktion gegenüber der $O(p \log p)$ erforderlichen One-Hot-Generierung darstellt.
Server (PCMM-Phase):
- Führt eine Plaintext-Ciphertext-Matrixmultiplikation (PCMM) zwischen der vorberechneten Matrix $M' = ML$ und dem generierten Vektor $v_j$ durch.
- Dies liefert den verschlüsselten Embedding-Vektor.

Wichtigste Beiträge

Independent Vector Evaluation (IVE): Ein neuartiger Algorithmus, der die verschlüsselte One-Hot-Generierung durch die Evaluierung einer linear unabhängigen Vektorfamilie ersetzt. Dies reduziert die Komplexität der Vektorgenerierung von $O(p \log p)$ auf $O(p)$ homomorphe Operationen.
Orthogonale Basis via DCT: Die Instanziierung von IVE mittels einer DCT-basierten orthogonalen Matrix gewährleistet die numerische Stabilität und mildert die durch die CKKS-Approximation inhärente Fehlerverstärkung beim Basiswechsel ab.
Integriertes PEL-Pipeline: Die Autoren integrieren IVE mit PCMM, um gebatchte Abfragen effizient zu handhaben. Diese Pipeline unterstützt die gleichzeitige Abfrage mehrerer Token durch Amortisierung der Kosten über die CKKS SIMD-Slots.
End-to-End Implementierung: Die Methode wurde in eine FastText-ähnliche Textklassifizierungs-Pipeline implementiert, die ihre Eignung für praktische, privatsphärensensible Inferenzaufgaben demonstriert.

Experimentelle Ergebnisse

Die Autoren evaluierten IVE-PEL gegenüber dem bisherigen Stand der Technik (Kim et al.) unter Verwendung von drei Embedding-Datensätzen (GloVe.6B.50d, Glove.42B.300d und GPT-2) sowie einer End-to-End FastText-Inferenz auf dem Enron-Spam-Datensatz.

Beschleunigung der Vektorgenerierung: IVE-PEL reduziert die Zeit für die Vektorgenerierung erheblich. Für eine Subtabelle der Größe $\log p = 10$ sank die VecGen-Zeit von ~424 ms (Kim et al.) auf ~3,15 ms (IVE-PEL) bei GloVe.6B.50d, was eine 134,6-fache Beschleunigung in dieser spezifischen Phase darstellt.
Gesamt-Pipeline-Beschleunigung: Die amortisierte Abfragezeit verbesserte sich um das 18,5- bis 78,4-fache, abhängig vom Datensatz und der Embedding-Dimension. Die größten Gewinne wurden in Szenarien erzielt, in denen die Vektorgenerierung den dominierenden Kostenfaktor darstellte.
Multiplikative Tiefe: IVE-PEL verbraucht etwa 1/3 der multiplikativen Tiefe, die für die One-Hot-Generierungsmethode erforderlich ist, was größere Subtabellengrößen und eine bessere Kompressionsqualität ermöglicht, ohne das CKKS-Rauschbudget zu erschöpfen.
End-to-End Auswirkung: In der Enron-Spam-Klassifizierungsaufgabe reduzierte der Ersatz der One-Hot-Methode durch IVE den Anteil der Vektorgenerierung an der gesamten verschlüsselten Inferenzzeit von 99,6 % auf 66,3 %, was die Gesamtlatenz erheblich senkte.

Bedeutung und Ansprüche

Das Paper behauptet, dass IVE-PEL den „fehlenden Designpunkt“ bei der privaten Embedding-Abfrage adressiert: die Erzielung einer kompakten Client-Kommunikation (skalare Indizes) ohne die prohibitiven Server-seitigen Kosten der homomorphen One-Hot-Generierung.

Durch die Entkopplung der Notwendigkeit einer One-Hot-Basis vom Abrufprozess zeigen die Autoren, dass die private Embedding-Abfrage für leichtgewichtige Clients und groß angelegte Modelle praktikabel gemacht werden kann. Die Ergebnisse legen nahe, dass IVE-PEL die serverseitige Embedding-Verarbeitung zu einer praktikablen Alternative für die clientseitige Embedding-Verarbeitung macht, was eine effiziente, privatsphärenwahrende Inferenz für NLP- und Empfehlungsmodelle ermöglicht, ohne die Vertraulichkeit der Benutzereingaben zu gefährden. Die Methode bewahrt die Genauigkeit der zugrunde liegenden Modelle (wie durch die IMDB-Sentiment- und Spam-Erkennungsergebnisse belegt) bei gleichzeitiger drastischer Verbesserung der Recheneffizienz.