🤖 AI

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

Das Paper stellt SHARD vor, eine retrieval-erhaltende Embedding-Transformation, die die Privatsphäre bei Dense Retrieval verbessert, indem sie Embeddings in ein öffentliches Präfix und ein mit einem geheimen Schlüssel versehenes Residuum aufteilt, welches über mehrere Zellen verteilt ist, wodurch Angriffe auf die globale geometrische Ausrichtung gestört werden, während gleichzeitig eine hohe Ranking-Genauigkeit durch Homomorphe Verschlüsselung-basiertes Reranking aufrechterhalten wird.

Ursprüngliche Autoren: Sergey Kurilenko

Veröffentlicht 2026-06-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sergey Kurilenko

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

Das große Problem: Das „Glashaus“ der Suche

Stellen Sie sich vor, Sie besitzen eine riesige Bibliothek mit geheimen Dokumenten (wie Kundensupport-Tickets oder privaten E-Mails). Um diese durchsuchbar zu machen, wandeln Sie jedes Dokument in eine lange Liste von Zahlen um, die ein Embedding genannt wird. Betrachten Sie diese Liste als einen einzigartigen „Fingerabdruck“ des Dokuments.

Derzeit gilt: Wenn jemand diese Liste der Fingerabdrücke stiehlt, kann er oft einen Computer nutzen, um den ursprünglichen Text zu rekonstruieren. Es ist wie ein Glashaus: Selbst wenn man die Tür abschließt, sind die Wände transparent, und jeder, der hineinsieht, kann genau erkennen, was sich darin befindet.

Der alte Weg: Das „rotierende Zimmer“

Vor dieser Arbeit war die gängige Verteidigungsmethode, die Fingerabdrücke in einen Raum zu legen und den gesamten Raum zu drehen (eine „geheime Rotation“).

Der Fehler: Das Paper argumentiert, dass dies so ist, als würde man einen Raum mit einem einzigen Schlüssel drehen. Wenn ein Dieb nur ein paar „Vorher-Nachher“-Fotos (bekannter Text und sein dazugehöriger Fingerabdruck) stiehlt, kann er leicht herausfinden, wie der Raum gedreht wurde, und die Drehung rückgängig machen. Sobald er die Drehung kennt, kann er wieder alles sehen.
Der Kompromiss: Um dies sicherer zu machen, haben Menschen oft die Fingerabdrücke halbiert (indem sie die Hälfte der Daten wegwerfen). Dies macht die Rekonstruktion schwieriger, führt aber auch dazu, dass die Suchmaschine schlechter darin wird, die richtigen Dokumente zu finden.

Die neue Lösung: SHARD

Die Autoren stellen SHARD (Cell-keyed Residual Splitting) vor. Anstatt den ganzen Raum zu drehen, teilen sie die Fingerabdrücke in zwei Teile auf und behandeln diese unterschiedlich.

1. Die „Öffentliche Postkarte“ (Das Präfix)

Sie nehmen die wichtigsten, groben Merkmale des Dokuments (wie das Hauptthema) und setzen sie auf eine kurze, öffentliche „Postkarte“.

Analogie: Stellen Sie sich eine Bibliothekskarte vor, auf der nur „Belletristik“ oder „Kochen“ steht. Das ist nicht geheim.
Zweck: Dies hilft der Suchmaschine, schnell eine kleine Gruppe wahrscheinlicher Kandidaten zu finden (wie das Finden der Abteilung „Kochen“). Es werden zwar einige grobe Informationen preisgegeben (das Thema), aber nicht die feinen Details.

2. Die „Privaten Puzzleteile“ (Das Residuum)

Der Rest des Fingerabdrucks (die spezifischen Details, die das Dokument einzigartig machen) ist das „Residuum“. Hier geschieht die Magie.

Die Aufteilung: Die Autoren zerlegen diesen privaten Teil in viele kleine Stücke (Zellen).
Die Schlüssel: Jedes Stück wird mit seinem eigenen, geheimen Schlüssel verschlossen.
Die Analogie: Stellen Sie sich vor, die privaten Details eines Dokuments sind ein Puzzle. Auf die alte Art war das ganze Puzzle in einem Karton mit einem einzigen Schloss. In SHARD wird das Puzzle in 256 einzelne Teile zerlegt, und jedes Teil ist in einem anderen Tresor mit einem anderen Schlüssel eingeschlossen.

Wie es in der Praxis funktioniert

Wenn Sie suchen:

Schritt 1 (Die Postkarte): Das System nutzt die öffentliche „Postkarte“, um eine kurze Liste von etwa 40 möglichen Treffern zu finden.
Schritt 2 (Das Puzzle): Um diese 40 Treffer zu bewerten, muss das System die privaten Puzzleteile betrachten. Es sendet eine verschlüsselte Anfrage an den Server. Der Server entsperrt die spezifischen Puzzleteile, die für diese 40 Treffer benötigt werden, vergleicht sie und gibt die Scores zurück.
Das Ergebnis: Die Suchmaschine erhält die exakt gleiche Genauigkeit, als hätte sie die vollständigen, unverschlüsselten Daten, aber der Server sieht nie die vollständigen privaten Daten.

Warum ist das besser? (Die drei Siege)

1. Es macht die Suchmaschine nicht kaputt
Da das System das vollständige Bild rekonstruiert, um das endgültige Ranking durchzuführen, verliert es keine Genauigkeit. Die alte Methode (die Daten zu halbieren) verschlechterte die Suchergebnisse. SHARD hält die Suchergebnisse perfekt.

2. Es macht Hacking viel schwieriger
Dies ist der größte Sieg.

Der alte Weg: Wenn ein Dieb 200 „Vorher-Nachher“-Beispiele stiehlt, kann er die Rotation berechnen und alles entschlüsseln.
Der SHARD-Weg: Da die privaten Daten in 256 verschiedene Zellen mit unterschiedlichen Schlüsseln aufgeteilt sind, muss ein Dieb 200 Beispiele für jede spezifische Zelle stehlen.
Die Mathematik: Wenn Sie 256 Zellen haben, benötigt ein Dieb etwa 256-mal mehr gestohlene Beispiele (über 100.000 statt 200), um das System zu knacken. Es ist, als müsste man 256 verschiedene Schlösser knacken anstatt nur eines.

3. Es schützt selbst, wenn man das Thema kennt
Selbst wenn ein Dieb die „Postkarte“ (das Thema) kennt, kann er die spezifischen Details immer noch nicht sehen, da diese in den privaten Puzzleteilen verschlossen sind.

Was SHARD NICHT tut (Die Grenzen)

Die Autoren sind sehr ehrlich darüber, was dieses System nicht leisten kann:

Es ist kein magischer Schutzschild: Wenn ein Dieb bereits den Originaltext in einer öffentlichen Datenbank hat (wie einem geleakten Nachrichtenarchiv) und diesen mit der „Postkarte“ abgleicht, kann er immer noch herausfinden, welches Dokument welches ist. SHARD schützt vor der Rekonstruktion des Textes aus den Zahlen, nicht vor dem Abgleich mit einem bekannten Leak.
Es verbirgt nicht, wonach Sie suchen: Das System weiß, welche Dokumente Sie aufrufen (das Zugriffsmuster). Wenn Sie jeden Tag nach „Herzinfarkt“ suchen, weiß der Server, dass Sie an Herzinfarkten interessiert sind, auch wenn er die spezifischen Dokumente nicht lesen kann.
Es ist nicht unknackbar: Wenn sich ein Dieb mit aller Energie auf nur ein spezifisches Dokument konzentriert und genug Beispiele für genau diese eine „Zelle“ stiehlt, kann er dieses eine Dokument entschlüsseln. Er kann aber nicht die gesamte Bibliothek auf einmal entschlüsseln.

Zusammenfassung

SHARD ist eine neue Art, private Suchdaten zu schützen. Anstatt den ganzen Raum zu drehen (was leicht rückgängig zu machen ist) oder die Hälfte der Möbel wegzuwerfen (was den Raum unbrauchbar macht), zerlegt es die geheimen Details in hunderte winzige, einzeln verschlossene Boxen. Dies macht es für Hacker extrem teuer und schwierig, die Geheimnisse zu rekonstruieren, während die Suchmaschine gleichzeitig schnell und präzise bleibt.

Technisches Resümee: SHARD – Zell-basierte Residual-Splittung für alignment-resistente private dichte Suche

1. Problemstellung

Dichte Einbettungen (Dense Embeddings) bilden das Fundament moderner semantischer Suche und Retrieval-Augmented Generation (RAG). Ein geleakter Vektorraum kompromittiert jedoch effektiv die zugrunde liegenden Texte, wie jüngste Angriffe demonstriert haben, darunter Few-Shot-Alignment, Zero-Shot-Inversion und unüberwachte Cross-Space-Translation. Diese Angriffe nutzen eine fundamentale Schwäche bestehender leichtgewichtiger Abwehrmechanismen aus: Der geschützte Vektorraum stellt eine einzelne globale Geometrie dar.

Aktuelle Verteidigungsstrategien verlassen sich oft auf einen „global-linearen“ Ansatz: Komprimierung der Einbettungen mittels SVD-Trunkierung, Anwendung einer einzigen geheimen orthogonalen Rotation und Verwendung von Product Quantization (PQ) für die Indizierung. Die Arbeit argumentiert, dass dieser Ansatz fragil ist, da jede einzelne globale Geometrie auf einen bekannten Referenzraum ausgerichtet werden kann. Sobald ein Angreifer die geheime Rotation rekonstruiert (unter Verwendung von etwa $k = d/2$ bekannter Plaintext-Paare via Orthogonal Procrustes), bricht der Schutz zusammen, was eine nahezu exakte Textwiederherstellung ermöglicht. Darüber hinaus stehen Standard-Verteidigungen vor einem Zielkonflikt: Differential Privacy (DP) zerstört die Ranking-Nützlichkeit (Utility), bevor sie eine bedeutsame Privatsphäre bietet, während Fully Homomorphic Encryption (FHE) für die großskalige Top- $k$ -Suche zu rechenintensiv ist.

2. Methodik: Die Shard-Konstruktion

Das Paper führt Shard ein, eine abrufserhaltende Embedding-Transformation, die darauf abzielt, die „schwache Achse“ der globalen Ausrichtung zu eliminieren, anstatt lediglich Verzerrungen zu maskieren. Shard teilt den Einbettungsraum in zwei Komponenten auf und wendet auf jede unterschiedliche Schutzmaßnahmen an:

Öffentliches Präfix ( $u$ ): Die Einbettung wird zentriert und rotiert. Die obersten $d_{pub}$ Hauptkomponenten (Varianz-reiche Richtungen) bilden ein kurzes öffentliches Präfix. Dieses wird für die grobe Stage-1-Suche (ANN) über einen öffentlichen Product-Quantization-Index verwendet.
Privates Residuum ( $r$ ): Die verbleibenden Dimensionen ( $d_{priv} = d - d_{pub}$ $d_{p r i v} = d - d_{p u b}$ ) bilden das private Residuum.
- Zell-basierte Splittung (Cell-Keyed Splitting): Der Residualraum wird in $C$ grobe Zellen unterteilt (definiert durch das öffentliche Präfix $u$ ).
- Lokale Schlüssel: Jede Zelle $c$ erhält einen eindeutigen geheimen orthogonalen Schlüssel $H_c$ (ein Produkt von Householder-Reflektionen).
- Speicherung: Der Server speichert das Präfix $u_i$ und das schlüsselbasierte Residual-Shard $z_i = H_{c(i)} r_i$ .
- Abfrageverarbeitung:
  - Stage 1: Der Client nutzt das öffentliche Präfix $u_q$ , um lokal eine Short-List von Kandidaten abzurufen.
  - Stage 2 (Reranking): Für jeden Kandidaten verschlüsselt der Client das Abfrage-Residuum $r_q$ mittels CKKS (homomorphe Verschlüsselung) als $H_{c(i)} r_q$ . Der Server berechnet das Skalarprodukt $\langle H_{c(i)} r_q, z_i \rangle$ im Ciphertext-Plaintext-Modus.
  - Exakte Rekonstruktion: Da $H_c$ orthogonal ist, kürzen sich die Schlüssel heraus: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$ . Der Server liefert verschlüsselte Scores zurück, die das exakte Skalarprodukt der ursprünglichen Residuen ergeben.

Der Parameter $C$ interpoliert zwischen der globalen Baseline ( $C=1$ , ein globaler Schlüssel) und pro-Dokument-Mikroschlüsseln ( $C=N$ , ein Schlüssel pro Dokument).

3. Zentrale Beiträge

Das Paper leistet folgende spezifische Beiträge im Vergleich zur vorangegangenen Arbeit der Autoren (ihrem global-linearen Hybrid-System):

Zell-basierte Residual-Splittung: Eine Konstruktion, die eine einzelne globale Geometrie durch $C$ lokal verschlüsselte Subräume ersetzt und so verhindert, dass ein einzener Alignment-Angriff den gesamten Speicher rekonstruiert.
Vollständiges dimensionales Reranking: Im Gegensatz zu SVD-Trunkierungs-Baselines, die im reduzierten Raum reranken, führt Shard das Reranking im vollen dimensionalen Raum (Präfix + Residuum) durch und stellt so die ursprüngliche Retrieval-Qualität wieder her, die durch die Trunkierung verloren gegangen wäre.
Skalierbare Alignment-Resistenz: Das Paper etabliert ein Skalierungsgesetz, bei dem die Kosten eines diffusen Known-Plaintext-Alignment-Angriffs um den Faktor $\approx C$ steigen. Die Rekonstruktion des nativen Rahmens erfordert $O(C \cdot d_{priv})$ Anker statt $O(d)$ .
Reduzierte öffentliche Leckage: Durch die Exposition eines nur kurzen Präfixes ( $d_{pub} \ll d$ ) anstelle der Hälfte des Raums wird die Nachbarschaftsstruktur im öffentlichen Index signifikant weniger preisgegeben.
Angriffsorientierte Evaluierung: Das Paper evaluiert Shard gegen stärkere Angreiferfamilien (learned-linear, non-linear MLP und unsupervised) und vergleicht es mit verzerrungsbewussten Abwehrmechanismen (DP-Rauschen), wobei gezeigt wird, dass Keying dort Resistenz bietet, wo Rauschen versagt.

4. Experimentelle Ergebnisse

Die Experimente wurden anhand von gecachten Embeddings von fünf Encodern (darunter multilingual-E5 und BGE-M3) auf BEIR, MIRACL und einem 1-Million-Dokument starken russischen Wikipedia-Korpus durchgeführt.

Nützlichkeit (nDCG@10): Shard erreicht die obere Grenze des Rankings im Rohraum. In BEIR-Aufgaben, bei denen SVD-Trunkierung zu einem Rückgang von 2–8 Punkten im nDCG@10 führte, erreichte Shard die Leistung der Roh-Baseline (z. B. 0.638 vs. 0.637 Rohwert), während der öffentliche Kanal nur 1/4 bis 1/2 so breit war.
Alignment-Resistenz:
- Globale Baseline: Rekonstruiert mit ~200 Ankern (für $d=384$ ).
- Shard ( $C=64$ ): Erforderte ~25.600 Anker.
- Shard ( $C=256$ ): Erforderte ~102.400 Anker (Median).
- Angreifer-Robustheit: Learned-linear, non-linear MLP und unsupervised Angreifer schnitten nicht besser ab als der Standard-Orthogonal-Procrustes-Angriff; keiner übertraf den Schwellenwert von $d_{priv}$ Ankern für eine einzelne Zelle.
Öffentliche Index-Leckage: Das öffentliche Präfix offenbarte signifikant weniger Nachbarschaftsstrukturen als die Baseline. Für ein $d/4$ Präfix sank der NN-Overlap@10 von 0.76 (Baseline) auf 0.55 (Shard).
Mikro-Key-Limit: Wenn $C=N$ (pro-Dokument-Schlüssel), sinkt die Leckage des Residual-Graphen auf 0.00 und das System wird ununterscheidbar (Re-Keying AUC $\approx 0.5$ ).
Vergleich zu DP-Rauschen: Eine verzerrungsbewusste DP-Verteidigung erreichte die Nützlichkeit von Shard nur bei $\sigma=0$ (kein Rauschen), wo die De-Anonymisierung bei 100 % lag. Jegliches hinzugefügte Rauschen zur Reduktion der De-Anonymisierung senkte die Nützlichkeit unter die Performance von Shard. Shard erreichte hohe Nützlichkeit bei 0 % De-Anonymisierung.
Beobachtete Limitationen:
- Gezielte Angriffe: Ein gezielter Angreifer, der Anker in einer spezifischen Zelle eines Opfers konzentriert, benötigt nur $\approx d_{priv}$ Anker, unabhängig von $C$ .
- Überlappender Referenzkorpus: Falls ein Angreifer einen überlappenden Referenzkorpus besitzt, erlaubt das öffentliche Präfix (selbst wenn es mit einem einzigen globalen Schlüssel versehen ist) die De-Anonymisierung, sobald dieser Schlüssel rekonstruiert wurde.
- Zugriffsmuster: Wie die Baseline verbirgt auch Shard keine Zugriffsmuster (welche Dokumente für das Reranking aufgerufen werden).

5. Bedeutung und Ansprüche

Das Paper positioniert Shard als eine angriffsorientierte geometrische Verteidigung und stellt explizit klar, dass es keine kryptographische Garantie für die gespeicherten Dokumente darstellt.

Kernleistung: Shard verschiebt den Trade-off zwischen Privatsphäre und Genauigkeit, indem es die Schwachstelle der „einzelnen globalen Geometrie“ beseitigt. Es ermöglicht exaktes, voll-dimensionales Reranking (Erhalt der Nützlichkeit), während es die Ausrichtung des privaten Residuums für diffuse Angreifer rechenintensiv macht.
Design-Philosophie: Die Arbeit bewegt die Embedding-Privatsphäre weg von der Optimierung gegen eine Verzerrungssurrogat ( $\sigma_{rec}$ ) hin zur Härtung gegen spezifische Angriffsflächen (Alignment und Index-Leckage).
Bescheidene Ansprüche: Die Autoren sind explizit darüber, was Shard nicht tut:
- Es schützt nicht vor gezielten Angriffen, die sich auf eine einzige Zelle konzentrieren.
- Es verhindert keine De-Anonymisierung über überlappende Referenzkorpora, falls der Schlüssel des öffentlichen Präfixes rekonstruiert wird.
- Es verbirgt keine Zugriffsmuster.
- Die geheime Rotation ist eine empirische Obfuskationsschicht, kein kryptographisches Primitiv.

Das Paper schließt mit der Feststellung, dass Shard eine abstimmbare Familie von Transformationen (über den Parameter $C$ ) bietet, die auf Zellebene widerrufen werden können. Dies bietet eine praktische, messbare Verteidigung gegen moderne Alignment-Angriffe in dichten Suchsystemen, sofern das System mit anderen Primitiven (wie PIR) kombiniert wird, um Zugriffsmuster und Referenz-Überlappungen zu handhaben.