💻 computer science

Private Embedding Lookup with Encrypted Compact Queries under Fully Homomorphic Encryption

Dit artikel stelt Independent Vector Evaluation (IVE) voor, een nieuwe methode voor private embedding lookup onder Fully Homomorphic Encryption die de kostbare generatie van one-hot vectoren vervangt door een lineair onafhankelijke representatie om een versnelling van tot wel 78,4x in geamortiseerde lookup-tijd te bereiken.

Oorspronkelijke auteurs: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

Gepubliceerd 2026-06-03

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Daehyun Jang, Jaehee Kang, Hanee Rhee, Jung Hee Cheon

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, geheime bibliotheek met boeken hebt (de embedding table) die op een gigantische server is opgeslagen. Elk boek vertegenwoordigt een specifiek woord of idee, en in elk boek zit een unieke "vingerafdruk" (een embedding vector) die een computer helpt de betekenis van dat woord te begrijpen.

Normaal gesproken, wanneer je de server een vraag wilt stellen, stuur je het een woord. De server zoekt dat woord op in zijn bibliotheek, pakt de bijbehorende vingerafdruk en gebruikt deze om je een antwoord te geven.

Het Privacyprobleem:
Je wilt niet dat de server weet welk woord je hebt opgevraagd. Misschien vraag je naar een medisch symptoom, een financieel geheim of iets anders gevoeligs. Als je gewoon het woord stuurt, ziet de server het. Als je een geheime code stuurt, kan de server het niet lezen om het juiste boek te vinden.

De Oude Manier (De "One-Hot" Methode):
In het verleden moest je, om je vraag geheim te houden, een speciale versleutelde lijst sturen. Stel je voor dat deze lijst een plek heeft voor elk afzonderlijk woord in de bibliotheek (miljoenen plekken). Je versleutelt een "1" in de plek van jouw woord en een "0" overal elders.

Het Problem: De server moet elke enkele plek controleren om te zien welke de "1" is. Het is alsof de server door elke gang van een enorme bibliotheek moet lopen en elk boek moet controleren, alleen maar om het boek te vinden dat jij wilt. Dit kost een enorme hoeveelheid tijd en rekenkracht, waardoor het hele proces erg traag wordt.

De Nieuwe Manier (IVE - Independent Vector Evaluation):
Dit artikel stelt een slimme afkorting voor. In plaats van een lijst met een "1 en 0's" te sturen, realiseerden de auteurs zich dat de server die specifieke lijst eigenlijk niet nodig heeft. De server heeft alleen een unieke code nodig die naar het juiste boek wijst, zolang de server weet hoe hij die code weer kan vertalen naar de juiste vingerafdruk.

Denk hierover na als volgt:

De Oolden Manier: Je stuurt een kaart met een grote rode "X" op één specifiek huis en lege ruimtes overal omheen. De server moet de hele kaart scannen om de "X" te vinden.
De Nieuwe Manier (IVE): Je stuurt een eenvoudige set coördinaten (zoals "Sla linksaf, en ga dan 3 blokken verder"). De server kent een geheime formule (een verandering van basis) die die coördinaten direct omzet in het exacte adres van het huis dat je wilt.

Hoe het werkt (De Magische Truc):

De Geheime Code: In plaats van een "1 en 0's" lijst, stuurt de cliënt een compact, versleuteld getal.
De Wiskundige Magie: De server gebruikt een wiskundig hulpmiddel genaamd Discrete Cosine Transform (DCT). Zie dit als een speciale vertaler. Het neemt jouw eenvoudige versleutelde getal en zet het snel om in een unieke "vingerafdruk"-code met behulp van eenvoudige wiskunde (machten van een getal), in plaats van trage, zware controles.
De Vertaling: De server heeft een vooraf berekende "woordenlijst" (de matrix van de verandering van basis) die weet hoe hij jouw nieuwe "vingerafdruk"-code weer kan omzetten naar exact dezelfde boek-vingerafdruk die de oude methode gevonden zou hebben.

Waarom dit belangrijk is:

Snelheid: De oude methode was als het doorlopen van elke gang. De nieuwe methode is als het gebruiken van een GPS. Het paper laat zien dat dit de zoekopdracht tot wel 78 keer sneller maakt.
Efficiëntie: Het bespaart een enorme hoeveelheid computerenergie. In tests daalde de tijd die besteed werd aan alleen maar het "vinden van het boek" van 99,6% van de totale tijd naar slechts 66,3%.
Privacy: De server leert nog steeds niets over jouw specifieke woord, maar krijgt het antwoord veel sneller.

In een Notendop:
De auteurs hebben een manier gevonden om te voorkomen dat de server een miljoen kleine controles moet uitvoeren om jouw geheime woord te vinden. In plaats daarvan gaven ze het een eenvoudige versleutelde aanwijzing en een magische vertaalsleutel. Dit zorgt ervoor dat de server de juiste informatie bijna onmiddellijk kan vinden, terwijl je geheimen veilig blijven zonder dat de computer eeuwig moet wachten.

Technische Samenvatting: Private Embedding Lookup met Versleutelde Compacte Queries onder Volledig Homomorfe Encryptie

Probleemstelling

In privacy-bewuste machine learning (PPML) met behulp van Fully Homomorphic Encryption (FHE), ontstaat een kritieke bottleneck tijdens de inferentie van modellen die vertrouwen op discrete inputs, zoals Natural Language Processing (NLP) en aanbevelingssystemen. Deze modellen beginnen doorgaans met een embedding layer, die een discrete index (bijv. een woordtoken) mapt naar een continue vector.

Onder FHE kan de server geen standaard geheugentoegang uitvoeren op basis van een versleutelde index. In plaats daarvan moet de lookup worden gerealiseerd via homomorfe aritmetiek. Bestaande benaderingen kampen met een trade-off:

Client-zijde lookup: De client stuurt de versleutelde embedding vector. Dit veroorzaakt een enorme communicatie-overhead proportioneel aan de embedding dimensie ( $d$ ), wat prohibitief is voor grote tabellen (bijv. GloVe met 1,9M tokens).
Server-zijde lookup met One-Hot Generatie: De client stuurt een compacte versleutelde scalaire index. De server moet vervolgens homomorfisch een one-hot vector construeren om de embedding te selecteren. Voorgaand werk (Kim et al., ICML 2024) bereikt dit met een Encrypted Indicator Function (EIF), maar dit vereist $O(p \log p)$ homomorfe operaties (waarbij $p$ de tabelgrootte is), wat een aanzienlijke multiplicatieve diepte consumeert en de dominante kostenpost wordt in de inferentie-pipeline.

Het doel is om Private Embedding Lookup (PEL) te bereiken dat compacte client-communicatie behoudt (het verzenden van slechts een scalaire index) terwijl de server-zijde homomorfe computationele kosten worden geminimaliseerd, waarbij de dure one-hot generatie stap wordt vermeden.

Methodologie: Independent Vector Evaluation (IVE)

De auteurs stellen Independent Vector Evaluation (IVE) voor, een methode die de constructie van een one-hot vector volledig omzeilt.

Kerninzicht

De server heeft strikt genomen geen one-hot vector ( $e_j$ ) nodig om de embedding $M_j$ op te halen. Het heeft alleen een representatie van de index $j$ nodig die lineair onafhankelijk is over verschillende indices. Als een set vectoren $\{v_j\}$ lineair onafhankelijk is, bestaat er een veranderingsmatrix $L$ zodanig dat $L v_j = e_j$ . Bijgevolg kan de embedding retrieval worden herschreven als:
$M_j = M e_j = M (L v_j) = (M L) v_j$
Aangezien $M$ en $L$ in plaintext bekend zijn, kan de server de matrix $M' = ML$ vooraf berekenen. De online taak verschuift dan van het genereren van een one-hot vector naar het evalueren van de vector $v_j$ homomorfisch.

Vectorconstructie en Stabiliteit

Om efficiëntie en numerieke stabiliteit te garanderen onder het CKKS-schema (dat benaderende aritmetiek ondersteunt):

Efficiëntie: De vectoren $v_j$ worden geconstrueerd met opeenvolgende machten van een enkele versleutelde waarde $\alpha_j$ . Dit stelt de server in staat om de componenten van de vector te genereren met standaard rekenoperaties (vermenigvuldigingen) in plaats van complexe gelijkheidstests.
Stabiliteit: Om foutversterking tijdens de basisverandering te voorkomen, moet de matrix $L$ goed conditioneerbaar zijn (bij voorkeur orthogonaal). De auteurs maken gebruik van een Discrete Cosine Transform (DCT) matrix. Door wortels van eenheid te gebruiken en reële en imaginaire delen te scheiden, construeren zij een orthogonale basis die aansluit bij de complexe rekenmogelijkheden van CKKS.

Algoritmische Flow

Client: Versleutelt de index $j$ in een waarde $\alpha_j$ (afgeleid van wortels van eenheid) en verzendt deze als een compacte scalaire query.
Server (IVE Fase):
- Ontvangt de versleutelde $\alpha_j$ .
- Berekent de machten $\alpha_j^0, \alpha_j^1, \dots, \alpha_j^{p/2}$ met behulp van een vermenigvuldigingsboom (logaritmische diepte).
- Scheidt de reële en imaginaire delen via conjugatie om de vector $v_j$ te vormen.
- Dit proces vereist $O(p)$ homomorfe operaties, een significante reductie ten opzichte van de $O(p \log p)$ die vereist is voor one-hot generatie.
Server (PCMM Fase):
- Voert een Plaintext-Ciphertext Matrix Multiplication (PCMM) uit tussen de vooraf berekende matrix $M' = ML$ en de gegenereerde vector $v_j$ .
- Dit levert de versleutelde embedding vector op.

Belangrijkste Bijdragen

Independent Vector Evaluation (IVE): Een nieuw algoritme dat de versleutelde one-hot generatie vervangt door de evaluatie van een lineair onafhankelijke vectorfamilie. Dit reduceert de complexiteit van de vectorgeneratie van $O(p \log p)$ naar $O(p)$ homomorfe operaties.
Orthogonale Basis via DCT: De instantiatie van IVE met een DCT-gebaseerde orthogonale matrix zorgt voor numerieke stabiliteit, waardoor foutversterking die inherent is aan de CKKS-benadering bij het uitvoeren van de basisverandering, wordt gemitigeerd.
Geïntegreerde PEL Pipeline: De auteurs integreren IVE met PCMM om gebatchte queries efficiënt af te handelen. Deze pipeline ondersteunt het gelijktijdig verwerken van meerdere token-queries, waarbij de kosten worden geamortiseerd over de CKKS SIMD-slots.
End-to-End Implementatie: De methode is geïmplementeerd binnen een FastText-stijl tekstclassificatie-pipeline, wat de levensvatbaarheid ervan voor praktische, privacygevoelige inferentietaken aantoont.

Experimentele Resultaten

De auteurs evalueerden IVE-PEL tegen de vorige state-of-the-art (Kim et al.) met drie embedding datasets (GloVe.6B.50d, GloVe.42B.300d, en GPT-2) en een end-to-end FastText-inferentie op de Enron-Spam dataset.

Snelheidswinst in Vectorgeneratie: IVE-PEL reduceert de tijd besteed aan vectorgeneratie aanzienlijk. Voor een subtable grootte van $\log p = 10$ , daalde de VecGen-tijd van ~424 ms (Kim et al.) naar ~3,15 ms (IVE-PEL) op GloVe.6B.50d, wat een 134,6× versnelling betekent in deze specifieke fase.
Totale Pipeline Snelheidswinst: De geamortiseerde lookup-tijd verbeterde met 18,5× tot 78,4×, afhankelijk van de dataset en de embedding dimensie. De grootste winsten werden waargenomen in scenario's waar de vectorgeneratie de dominante kostenpost was.
Multiplicatieve Diepte: IVE-PEL consumeert ongeveer 1/3 van de multiplicatieve diepte die vereist is door de one-hot generatiemethode, wat grotere subtable-groottes en betere compressiekwaliteit mogelijk maakt zonder het CKKS-ruisbudget uit te putten.
End-to-End Impact: In de Enron-Spam classificatietaak verminderde het vervangen van de one-hot methode door IVE het aandeel van de vectorgeneratie in de totale versleutelde inferentietijd van 99,6% naar 66,3%, wat de algehele latentie aanzienlijk verlaagt.

Betekenis en Claims

Het artikel claimt dat IVE-PEL het "ontbrekende ontwerppunt" in private embedding lookup aanpakt: het bereiken van compacte client-communicatie (scalaire indices) zonder de prohibitieve server-zijde kosten van homomorfe one-hot generatie te dragen.

Door de noodzaak van een one-hot basis te ontkoppelen van het retrievalproces, laten de auteurs zien dat private embedding lookup praktisch kan worden gemaakt voor lichtgewicht clients en grootschalige modellen. De resultaten suggereren dat IVE-PEL server-side embedding een levensvatbaar alternatief maakt voor client-side embedding, wat efficiënte, privacy-bewuste inferentie voor NLP en aanbevelingsmodellen mogelijk maakt zonder de vertrouwelijkheid van de input-indices van de gebruiker op te offeren. De methode behoudt de nauwkeurigheid van de onderliggende modellen (zoals aangetoond door de IMDB sentiment classificatie en spam detectie resultaten) terwijl de computationele efficiëntie drastisch wordt verbeterd.