🤖 AI

SHARD: cell-keyed residual splitting for alignment-resistant private dense retrieval

Het artikel introduceert SHARD, een retrieval-preserverende embedding-transformatie die de privacy in dense retrieval verbetert door embeddings te splitsen in een publieke prefix en een met een geheime sleutel beveiligde residu die over meerdere cellen is verdeeld, waardoor geometrische alignment-aanvallen op globale schaal worden verstoord terwijl een hoge rangschikkingsnauwkeurigheid behouden blijft door middel van homomorfe encryptie-gebaseerde herrangschikking.

Oorspronkelijke auteurs: Sergey Kurilenko

Gepubliceerd 2026-06-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sergey Kurilenko

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

Het Grote Probleem: Het "Glazen Huis" van Zoeken

Stel je voor dat je een enorme bibliotheek hebt met geheime documenten (zoals klantenservice-tickets of privé-e-mails). Om deze doorzoekbaar te maken, verander je elk document in een lange lijst met getallen die een embedding wordt genoemd. Zie deze lijst als een unieke "vingerafdruk" van het document.

Momenteel, als iemand deze lijst met vingerafdrukken steelt, kan een computer vaak de oorspronkelijke tekst reconstrueren. Het is als een glazen huis: zelfs als je de deur op slot doet, zijn de muren transparant en kan iedereen die naar binnen kijkt precies zien wat er binnen is.

De Oude Manier: De "Roterende Kamer"

Voordat dit artikel verscheen, was de gebruikelijke verdediging om de vingerafdrukken in een kamer te plaatsen en de hele kamer rond te draaien (een "geheime rotatie").

De Fout: Het artikel stelt dat dit is als het draaien van een kamer met één enkele sleutel. Als een dief slechts een paar "voor en na" foto's steelt (bekende tekst en de bijbehorende vingerafdruk), kan hij gemakkelijk uitzoeken hoe de kamer is gedraaid en dit ongedaan maken. Zodra hij de draaiing weet, kan hij alles weer zien.
De Afweging: Om dit veiliger te maken, gooien mensen de vingerafdrukken vaak voor de helft weg (ze gooien de helft van de data weg). Dit maakt het moeilijker om te reconstrueren, maar het maakt de zoekmachine ook slechter in het vinden van de juiste documenten.

De Nieuwe Oplossing: SHARD

De auteurs introduceren SHARD (Cell-keyed Residual Splitting). In plaats van de hele kamer te draaien, breken ze de vingerafdrukken in twee delen en behandelen ze deze verschillend.

1. De "Openbare Postkaart" (De Prefix)

Ze nemen de belangrijkste, brede kenmerken van het document (zoals het hoofdonderwerp) en zetten deze op een korte, openbare "postkaart".

Analogie: Stel je een bibliotheekkaart voor waarop alleen "Fictie" of "Koken" staat. Dit is niet geheim.
Doel: Dit helpt de zoekmachine om snel een kleine groep waarschijnlijke kandidaten te vinden (zoals het zoeken in de sectie "Koken"). Het lekt wat grove informatie (het onderwerp), maar niet de fijne details.

2. De "Privé Puzzelstukjes" (De Residual)

De rest van de vingerafdruk (de specifieke details die het document uniek maken) is de "residual". Hier gebeurt de magie.

De Splitsing: De auteurs hakken dit privégedeelte in veel kleine stukjes (cellen).
De Sleutels: Elk stukje wordt vergrendeld met zijn eigen unieke, geheime sleutel.
De Analogie: Stel je voor dat de privédetails van een document een legpuzzel zijn. In de oude methode zat de hele puzzel in één doos met één slot. In SHARD wordt de puzzel in 256 afzonderlijke stukjes gehakt, en elk stukje wordt in een andere kluis bewaard met een andere sleutel.

Hoe het in de praktijk werkt

Wanneer je zoekt:

Stap 1 (De Postkaart): Het systeem gebruikt de openbare "postkaart" om een korte lijst van 40 mogelijke matches te vinden.
Stap 2 (De Puzzel): Om deze 40 matches te rangschikken, moet het systeem naar de privé puzzelstukjes kijken. Het stuurt een versleuteld verzoek naar de server. De server ontgrendelt de specifieke puzzelstukjes die nodig zijn voor die 40 matches, vergelijkt ze en geeft de scores terug.
Het Resultaat: De zoekmachine krijgt exact dezelfde nauwkeurigheid als wanneer het de volledige, ongeëncrypteerde data had gehad, maar de server ziet nooit de volledige privédata.

Waarom is dit beter? (De Drie Winsten)

1. Het breekt de zoekmachine niet
Omdat het systeem het volledige plaatje weer samenvoegt om de uiteindelijke rangschikking te doen, gaat het niet aan nauwkeurigheid verloren. De oude methode (het halveren van de data) maakte de zoekresultaten slechter. SHARD houdt de zoekresultaten perfect.

2. Het maakt hacken veel moeilijker
Dit is de grootste winst.

De Oude Manier: Als een dief 200 "voor en na" voorbeelden steelt, kan hij de rotatie uitzoeken en alles ontgrendelen.
De SHARD-manier: Omdat de privédata is opgesplitst in 256 verschillende cellen met verschillende sleutels, moet een dief 200 voorbeelden stelen voor elke specifieke cel.
De Rekensom: Als je 256 cellen hebt, heeft een dief ongeveer 256 keer meer gestolen voorbeelden nodig (meer dan 100.000 in plaats van 200) om het systeem te kraken. Het is alsof je probeert 256 verschillende sloten te kraken in plaats van slechts één slot.

3. Het beschermt zelfs als je het onderwerp weet
Zelfs als een dief de "postkaart" (het onderwerp) kent, kan hij de specifieke details nog steeds niet zien, omdat die vergrendeld zitten in de privé puzzelstukjes.

Wat SHARD NIET doet (De Limieten)

De auteurs zijn zeer eerlijk over wat dit systeem niet kan doen:

Het is geen magisch schild: Als een dief de originele tekst al in een openbare database heeft (zoals een gelekt nieuwsarchief) en deze koppelt aan de "postkaart", kan hij nog steeds uitzoeken welk document welk document is. SHARD beschermt tegen het reconstrueren van de tekst uit de getallen, niet tegen het matchen met een bekende lek.
Het verbergt niet wie je zoekt: Het systeem weet welke documenten je bekijkt (het "access pattern"). Als je elke dag zoekt op "Hartaanval", weet de server dat je geïnteresseerd bent in hartaanvallen, zelfs als hij de specifieke documenten niet kan lezen.
Het is niet onkraakbaar: Als een dief al zijn energie richt op slechts één specifelijk document en genoeg voorbeelden steelt voor die specifieke "cel", kan hij dat ene document ontgrendelen. Maar hij kan niet de hele bibliotheek tegelijk ontgrendelen.

Samenvatting

SHARD is een nieuwe manier om privé zoekgegevens te beschermen. In plaats van de hele kamer te draaien (wat makkelijk ongedaan te maken is) of de helft van de meubels weg te gooien (wat de kamer onbruikbaar maakt), breekt het de geheime details op in honderden kleine, individueel vergrendelde dozen. Dit maakt het extreem duur en moeilijk voor hackers om de geheimen te reconstrueren, terwijl de zoekmachine snel en nauwkeurig blijft.

Technische Samenvatting: SHARD – Cell-Keyed Residual Splitting voor Alignment-Resistente Private Dense Retrieval

1. Probleemstelling

Dense embeddings vormen de basis van moderne semantische zoekopdrachten en Retrieval-Augmented Generation (RAG). Echter, een gelekt vectorbestand compromitteert effectief de onderliggende tekst, zoals aangetoond door recente aanvallen waaronder few-shot alignment, zero-shot inversie en unsupervised cross-space translatie. Deze aanvallen maken misbruik van een fundamentele zwakte in bestaande lichtgewicht defensies: de beschermde vectorstore is een enkele globale geometrie.

Huidige defensies vertrouwen vaak op een "globale-lineaire" aanpak: het comprimeren van embeddings via SVD-truncatie, het toepassen van een enkele geheime orthogonale rotatie, en het gebruik van Product Quantization (PQ) voor indexering. Het paper betoogt dat deze aanpak fragiel is omdat elke enkele globale geometrie kan worden uitgelijnd naar een bekende referentieruimte. Zodra een aanvaller de geheime rotatie herstelt (met behulp van ongeveer $k = d/2$ bekende plaintext-paren via Orthogonal Procrustes), stort de bescherming in, wat bijna exacte tekstherstel mogelijk maakt. Bovendien staan standaard defensies voor een trade-off: Differential Privacy (DP) vernietigt de ranking-utility voordat het betekenisvolle privacy biedt, terwijl Fully Homomorphic Encryption (FHE) te computationeel duur is voor grootschalige top- $k$ zoekopdrachten.

2. Methodologie: De Shard-constructie

Het paper introduceert Shard, een retrieval-preserverende embedding-transformatie die ontworpen is om de "zwakke as" van globale alignment te elimineren in plaats van vervorming te maskeren. Shard splitst de embedding-ruimte in twee componenten en past verschillende beschermingen toe op elk deel:

Public Prefix ( $u$ ): De embedding wordt gecentreerd en geroteerd. De top $d_{pub}$ hoofdcomponenten (hoog-variante richtingen) vormen een korte publieke prefix. Deze wordt gebruikt voor grove Stage-1 retrieval (ANN) via een publieke Product Quantization-index.
Private Residual ( $r$ ): De resterende dimensies ( $d_{priv} = d - d_{pub}$ $d_{p r i v} = d - d_{p u b}$ ) vormen de private residual.
- Cell-Keyed Splitting: De residual-ruimte wordt gepartitioneerd in $C$ grove cellen (gedefinieerd door de publieke prefix $u$ ).
- Lokale Keys: Elke cel $c$ krijgt een unieke geheime orthogonale sleutel $H_c$ (een product van Householder-reflecties).
- Opslag: De server slaat de prefix $u_i$ en de keyed residual shard $z_i = H_{c(i)} r_i$ op.
- Query Verwerking:
  - Stage 1: De client gebruikt de publieke prefix $u_q$ om lokaal een shortlist van kandidaten op te halen.
  - Stage 2 (Reranking): Voor elke kandidaat versleutelt de client de query-residual $r_q$ onder CKKS (homomorfe encryptie) als $H_{c(i)} r_q$ . De server berekent het inwendig product $\langle H_{c(i)} r_q, z_i \rangle$ in ciphertext-plaintext modus.
  - Exacte Recovery: Omdat $H_c$ orthogonaal is, vallen de sleutels weg: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$ . De server retourneert versleutelde scores die de exacte inwendige producten van de originele residuals ontsleutelen.

De parameter $C$ interpoleert tussen de globale baseline ( $C=1$ , één globale sleutel) en per-document micro-keys ( $C=N$ , één sleutel per document).

3. Belangrijkste Bijdragen

Het paper levert de volgende specifieke bijdragen ten opzichte van eerder werk (specifiek het eerdere globale-lineaire hybride systeem van de auteurs):

Cell-Keyed Residual Splitting: Een constructie die een enkele globale geometrie vervangt door $C$ lokaal gekeyde subspaces, waardoor voorkomt dat een enkele alignment-aanval de volledige store herstelt.
Full-Dimensional Reranking: In tegenstelling tot SVD-truncatie baselines die reranken in een gereduceerde ruimte, rerankt Shard in de volledige dimensionaliteit (prefix + residual), waardoor de verloren raw retrieval quality van truncatie wordt hersteld.
Schaalbare Alignment Resistance: Het paper stelt een schaalwet vast waarbij de kosten van een diffuse bekende-plaintext alignment-aanval met een factor $\approx C$ toenemen. Het herstellen van het natuurlijke frame vereist $O(C \cdot d_{priv})$ anchors in plaats van $O(d)$ .
Verminderde Public Leakage: Door slechts een korte prefix ( $d_{pub} \ll d$ ) te exposeren in plaats van de helft van de ruimte, lekt de publieke index aanzienlijk minder buurstructuur.
Attack-Aware Evaluatie: Het paper evalueert Shard tegen sterkere aanvallersfamilies (learned-linear, non-linear MLP, en unsupervised) en vergelijkt het met vervormingsbewuste defensies (DP noise), waarbij het aantoont dat keying weerstand biedt waar ruis faalt.

4. Experimentele Resultaten

Experimenten werden uitgevoerd op gecachte embeddings van vijf encoders (waaronder multilingual-E5 en BGE-M3) over BEIR, MIRACL en een 1-miljoen documenten tellend Russisch Wikipedia-corpus.

Utility (nDCG@10): Shard herstelt de raw-space ranking ceiling. Op BEIR-taken waar SVD-truncatie zorgde voor een daling van 2–8 punten in nDCG@10, matchte Shard de raw baseline (bijv. 0.638 vs. 0.637 raw) terwijl het een publiek kanaal exposeerde dat slechts 1/4 tot 1/2 zo breed was.
Alignment Resistance:
- Global Baseline: Hersteld met ~200 anchors (voor $d=384$ ).
- Shard ( $C=64$ ): Vereiste ~25.600 anchors.
- Shard ( $C=256$ ): Vereiste ~102.400 anchors (mediaan).
- Attacker Robustness: Learned-linear, non-linear MLP en unsupervised aanvallers presteerden niet beter dan de standaard Orthogonal Procrustes aanval; geen van hen overtrof de $d_{priv}$ anchor-drempel voor een enkele cel.
Public Index Leakage: De publieke prefix onthulde aanzienlijk minder buurstructuur dan de baseline. Voor een $d/4$ prefix daalde de NN-overlap@10 van 0.76 (baseline) naar 0.55 (Shard).
Micro-Key Limiet: Wanneer $C=N$ (per-document keys), daalt de residual graph leak naar 0.00 en wordt het systeem onkoppelbaar (re-keying AUC $\approx 0.5$ ).
Vergelijking met DP Noise: Een distortion-aware DP defensie matchte de utility van Shard alleen bij $\sigma=0$ (geen ruis), waar de-anonymization 100% was. Elke toegevoegde ruis om de-anonymization te verminderen, degradeerde de utility onder de prestaties van Shard. Shard bereikte hoge utility met 0% de-anonymization.
Geobserveerde Beperkingen:
- Targeted Attacks: Een gerichte aanvaller die zich concentreert op anchors in een specifieke cel van een slachtoffer heeft slechts $\approx d_{priv}$ anchors nodig, onafhankelijk van $C$ .
- Overlap Reference: Als een aanvaller over een overlappende referentie-corpus beschikt, staat de publieke prefix (zelfs als deze met een enkele globale sleutel is gekeyed) de-anonymization toe zodra die sleutel is hersteld.
- Access Patterns: Net als de baseline verbergt Shard geen access patterns (welke documenten worden gereranked).

5. Betekenis en Claims

Het paper positioneert Shard als een attack-aware geometric defense, en stelt expliciet dat het geen cryptografische garantie is voor de opgeslagen documenten.

Kernprestatie: Shard verschuift de privacy/accuracy trade-off door de kwetsbaarheid van de "single global geometry" te verwijderen. Het staat exacte, full-dimensional reranking toe (behoud van utility) terwijl het de alignment van de private residual computationeel duur maakt voor diffuse aanvallers.
Ontwerpfilosofie: Het werk verplaatst embedding-privacy van het optimaliseren tegen een distortie-surrogaat ( $\sigma_{rec}$ ) naar het harden tegen specifieke aanvalsoppervlakken (alignment en index leakage).
Bescheiden Claims: De auteurs zijn expliciet over wat Shard niet doet:
- Het beschermt niet tegen gerichte aanvallen die zich concentreren op een enkele cel.
- Het voorkomt geen de-anonymization via overlappende referentie-corpora als de publieke prefix sleutel wordt hersteld.
- Het verbergt geen access patterns.
- De geheime rotatie is een empirische obscuratie-laag, geen cryptografisch primitief.

Het paper concludeert dat Shard een instelbare familie van transformaties biedt (via parameter $C$ ) die op cel-niveau kunnen worden ingetrokken, wat een praktische, gemeten defensie biedt tegen moderne alignment-aanvallen in dense retrieval systemen, mits het systeem is samengesteld met andere primitieven (zoals PIR) om access patterns en referentie-overlaps te behandelen.