🤖 AI

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

Le document présente SHARD, une transformation d'incorporation préservant la récupération qui améliore la confidentialité dans la recherche dense en divisant les plongements en un préfixe public et un résidu à clé secrète réparti sur plusieurs cellules, perturbant ainsi les attaques d'alignement géométrique global tout en maintenant une haute précision de classement grâce au reclassement basé sur le chiffrement homomorphe.

Auteurs originaux : Sergey Kurilenko

Publié 2026-06-29

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sergey Kurilenko

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le gros problème : La « Maison de Verre » de la recherche

Imaginez que vous possédez une immense bibliothèque de documents secrets (comme des tickets de support client ou des e-mails privés). Pour les rendre consultables, vous transformez chaque document en une longue liste de nombres appelée embedding. Considérez cette liste comme une « empreinte digitale » unique pour le document.

Actuellement, si quelqu'un vole cette liste d'empreintes digitales, il peut souvent utiliser un ordinateur pour faire l'ingénierie inverse du texte original. C'est comme avoir une maison de verre : même si vous verrouillez la porte, les murs sont transparents, et quiconque regarde à l'intérieur peut voir exactement ce qui s'y trouve.

L'ancienne méthode : La « Pièce Rotative »

Avant ce papier, la défense courante consistait à placer les empreintes dans une pièce et à faire pivoter toute la pièce autour (une « rotation secrète »).

La faille : Le papier soutient que c'est comme faire pivoter une pièce avec une seule clé. Si un voleur dérobe seulement quelques photos « avant et après » (un texte connu et son empreinte), il peut facilement comprendre comment la pièce a pivoté et annuler l'effet. Une fois qu'il connaît la rotation, il peut tout voir à nouveau.
Le compromis : Pour rendre cela plus sûr, les gens coupent souvent les empreintes en deux (en jetant la moitié des données). Cela rend l'inversion plus difficile, mais cela rend aussi le moteur de recherche moins efficace pour trouver les bons documents.

La nouvelle solution : SHARD

Les auteurs introduisent SHARD (Cell-keyed Residual Splitting). Au lieu de faire pivoter toute la pièce, ils décomposent les empreintes en deux parties et les traitent différemment.

1. La « Carte Postale Publique » (Le Préfixe)

Ils prennent les caractéristiques les plus importantes et générales du document (comme le sujet principal) et les placent sur une courte « carte postale » publique.

Analogie : Imaginez une fiche de bibliothèque qui indique simplement « Fiction » ou « Cuisine ». Ce n'est pas secret.
Objectif : Cela aide le moteur de recherche à trouver rapidement un petit groupe de candidats probables (comme trouver la section « Cuisine »). Cela divulgue certaines informations grossières (le sujet), mais pas les détails précis.

2. Les « Pièces de Puzzle Privées » (Le Résiduel)

Le reste de l'empreinte (les détails spécifiques qui rendent le document unique) est le « résiduel ». C'est là que la magie opère.

La division : Les auteurs découpent cette partie privée en de nombreux petits morceaux (cellules).
Les clés : Chaque morceau est verrouillé par sa propre clé secrète et unique.
L'analogie : Imaginez que les détails privés d'un document sont un puzzle. Dans l'ancienne méthode, tout le puzzle était dans une seule boîte avec un seul verrou. Avec SHARD, le puzzle est découpé en 256 pièces séparées, et chaque pièce est verrouillée dans un coffre différent avec une clé différente.

Comment cela fonctionne en pratique

Lorsque vous effectuez une recherche :

Étape 1 (La Carte Postale) : Le système utilise la « carte postale » publique pour trouver une courte liste de 40 correspondances possibles.
Étape 2 (Le Puzzle) : Pour classer ces 40 correspondances, le système doit examiner les pièces du puzzle privées. Il envoie une requête cryptée au serveur. Le serveur déverrouille les pièces de puzzle spécifiques nécessaires pour ces 40 correspondances, les compare, et renvoie les scores.
Le résultat : Le moteur de recherche obtient exactement la même précision que s'il disposait de l'intégralité des données non cryptées, mais le serveur ne voit jamais l'intégralité des données privées.

Pourquoi est-ce meilleur ? (Les trois victoires)

1. Cela ne casse pas le moteur de recherche
Comme le système réassemble l'image complète pour effectuer le classement final, il ne perd pas en précision. L'ancienne méthode (couper les données en deux) dégradait la qualité de la recherche. SHARD préserve une précision parfaite.

2. Cela rend le piratage beaucoup plus difficile
C'est la plus grande victoire.

L'ancienne méthode : Si un voleur dérobait 200 exemples « avant et après », il pourrait comprendre la rotation et tout déverrouiller.
La méthode SHARD : Comme les données privées sont divisées en 256 cellules différentes avec des clés différentes, le voleur doit dérober 200 exemples pour chaque cellule spécifique.
Le calcul : Si vous avez 256 cellules, le voleur a besoin d'environ 256 fois plus d'exemples volés (plus de 100 000 au lieu de 200) pour craquer le système. C'est comme essayer de crocheter 256 serrures différentes au lieu d'une seule.

3. Cela protège même si vous connaissez le sujet
Même si un voleur connaît la « carte postale » (le sujet), il ne peut toujours pas voir les détails spécifiques car ceux-ci sont verrouillés dans les pièces du puzzle privé.

Ce que SHARD NE FAIT PAS (Les limites)

Les auteurs sont très honnêtes sur ce que ce système ne peut pas faire :

Ce n'est pas un bouclier magique : Si un voleur possède déjà le texte original dans une base de données publique (comme une archive de presse fuitée) et le compare à la « carte postale », il peut toujours identifier de quel document il s'agit. SHARD protège contre la reconstruction du texte à partir des chiffres, pas contre la correspondance avec une fuite connue.
Cela ne cache pas ce que vous recherchez : Le système sait quels documents vous consultez (le « modèle d'accès »). Si vous recherchez « Crise cardiaque » tous les jours, le serveur sait que vous vous intéressez aux crises cardiaques, même s'il ne peut pas lire les documents spécifiques.
Ce n'est pas inviolable : Si un voleur concentre toute son énergie sur un seul document spécifique et dérobe suffisamment d'exemples pour cette « cellule » précise, il peut déverrouiller ce document. Mais il ne peut pas déverrouiller toute la bibliothèque à la fois.

Résumé

SHARD est une nouvelle façon de protéger les données de recherche privées. Au lieu de faire pivoter toute la pièce (ce qui est facile à annuler) ou de jeter la moitié des meubles (ce qui rend la pièce inutile), il décompose les détails secrets en centaines de petites boîtes verrouillées individuellement. Cela rend la reconstruction des secrets incroyablement coûteuse et difficile pour les hackers, tout en maintenant la rapidité et la précision du moteur de recherche.

Résumé Technique : SHARD – Décomposition par Clé de Cellule pour un Fractionnement Résiduel Résistant à l'Alignement pour la Recherche Dense Privée

1. Énoncé du Problème

Les plongements (embeddings) denses constituent le fondement de la recherche sémantique moderne et de la génération augmentée par récupération (RAG). Cependant, un magasin de vecteurs compromis expose efficacement le texte sous-jacent, comme le démontrent des attaques récentes incluant l'alignement en few-shot, l'inversion zero-shot et la traduction de l'espace de manière non supervisée. Ces attaques exploitent une faiblesse fondamentale des défenses légères existantes : le magasin de vecteurs protégé est une géométrie globale unique.

Les défenses actuelles reposent souvent sur une approche « globale-linéaire » : compression des plongements via la troncature SVD, application d'une rotation orthogonale secrète unique, et utilisation de la quantification par produit (PQ) pour l'indexation. L'article soutient que cette approche est fragile car toute géométrie globale peut être alignée sur un espace de référence connu. Une fois que l'attaquant a récupéré la rotation secrète (en utilisant environ $k = d/2$ paires de texte clair connues via la Procruste orthogonale), la protection s'effondre, permettant une récupération quasi exacte du texte. De plus, les défenses standard font face à un arbitrage : la confidentialité différentielle (DP) détruit l'utilité du classement avant de fournir une confidentialité significative, tandis que le chiffrement totalement homomorphe (FHE) est trop coûteux en termes de calcul pour la recherche top- $k$ à grande échelle.

2. Méthodologie : La Construction de Shard

L'article introduit Shard, une transformation de plongement préservant la récupération, conçue pour éliminer l'axe faible de l'alignement global plutôt que de masquer la distorsion. Shard divise l'espace de plongement en deux composantes et applique des protections distinctes à chacune :

Préfixe Public ( $u$ ) : Le plongement est centré et pivoté. Les $d_{pub}$ composantes principales supérieures (directions à haute variance) forment un préfixe public court. Celui-ci est utilisé pour la recherche de l'étape 1 (ANN) via un index de quantification par produit public.
Résiduel Privé ( $r$ ) : Les dimensions restantes ( $d_{priv} = d - d_{pub}$ $d_{p r i v} = d - d_{p u b}$ ) forment le résiduel privé.
- Décomposition par Clé de Cellule : L'espace résiduel est partitionné en $C$ cellules grossières (définies par le préfixe public $u$ ).
- Clés Locales : Chaque cellule $c$ se voit assigner une clé orthogonale secrète unique $H_c$ (un produit de réflexions de Householder).
- Stockage : Le serveur stocke le préfixe $u_i$ et le fragment résiduel clé de la cellule $z_i = H_{c(i)} r_i$ .
- Traitement de la Requête :
  - Étape 1 : Le client utilise le préfixe public $u_q$ pour récupérer localement une liste courte de candidats.
  - Étape 2 (Reclassement) : Pour chaque candidat, le client chiffre le résiduel de la requête $r_q$ sous CKKS (chiffrement homomorphe) en tant que $H_{c(i)} r_q$ . Le serveur calcule le produit scalaire $\langle H_{c(i)} r_q, z_i \rangle$ en mode texte chiffré-texte clair.
  - Récupération Exacte : Parce que $H_c$ est orthogonale, les clés s'annulent : $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$ . Le serveur renvoie des scores chiffrés qui se décryptent en le produit scalaire exact des résiduels originaux.

Le paramètre $C$ interpole entre la base globale ( $C=1$ , une clé globale) et les micro-clés par document ( $C=N$ , une clé par document).

3. Contributions Clés

L'article apporte les contributions spécifiques suivantes par rapport aux travaux antérieurs (notamment le système hybride global-linéaire précédent des auteurs) :

Décomposition par Clèle de Cellule du Résiduel : Une construction qui remplace une géométrie globale unique par $C$ sous-espaces localement clés, empêchant une attaque d'alignement unique de récupérer l'ensemble du magasin.
Reclassement à Pleine Dimension : Contra�à l'approche de base par troncature SVD qui effectue le reclassement dans un espace réduit, Shard effectue le reclassement dans l'espace complet (préfixe + résiduel), récupérant la qualité de recherche brute perdue par la troncature.
Résistance à l'Alignement Scalable : L'article établit une loi d'échelle où le coût d'une attaque d'alignement par texte clair diffus augmente d'un facteur $\approx C$ . Récupérer le cadre natif nécessite $O(C \cdot d_{priv})$ ancres plutôt que $O(d)$ .
Réduction de la Fuite Publique : En n'exposant qu'un préfixe court ( $d_{pub} \ll d$ ), l'index public fuit nettement moins de structure de voisinage.
Évaluation Sensible aux Attaques : L'article évalue Shard contre des familles d'attaquants plus puissantes (linéaire appris, MLP non linéaire et non supervisé) et le compare aux défenses axées sur la distorsion (bruit DP), démontrant que le cléage offre une résistance là où le bruit échoue.

4. Résultats Expérimentaux

Les expériences ont été menées sur des plongements mis en cache de cinq encodeurs (incluant multilingual-E5 et BGE-M3) sur les corpus BEIR, MIRACL et un corpus de 1 million de documents de Wikipédia en russe.

Utilité (nDCG@10) : Shard récupère le plafond de classement de l'espace brut. Sur les tâches BEIR où la troncature SVD causait une chute de 2 à 8 points de nDCG@10, Shard correspond au plafond de base (ex: 0,638 contre 0,637 brut) tout en n'exposant un canal public que 1/4 à 1/2 moins large.
Résistance à l'Alignement :
- Base Globale : Récupérée avec ~200 ancres (pour $d=384$ ).
- Shard ( $C=64$ ) : Nécessite ~25 600 ancres.
- Shard ( $C=256$ ) : Nécessite ~102 400 ancres (médiane).
- Robustesse de l'Attaquant : Les attaquants linéaire appris, MLP non linéaire et non supervisé n'ont pas performé mieux que l'attaque standard de Procruste orthogonale ; aucun n'a dépassé le seuil d'ancres $d_{priv}$ pour une cellule unique.
Fuite de l'Index Public : Le préfixe public révèle nettement moins de structure de voisinage que la base. Pour un préfixe $d/4$ , l'overlap de voisinage @10 est passé de 0,76 (base) à 0,55 (Shard).
Limite des Micro-Clés : Lorsque $C=N$ (clés par document), la fuite du graphe résiduel tombe à 0,00, et le système devient impossible à lier (AUC de re-keying $\approx 0,5$ ).
Comparaison avec le Bruit DP : Une défense DP axée sur la distorsion n'a égalé l'utilité de Shard qu'à $\sigma=0$ (sans bruit), où la désanonymisation était de 100 %. Tout bruit ajouté pour réduire la désanonymisation dégradait l'utilité en dessous de la performance de Shard. Shard a atteint une utilité élevée avec 0 % de désanonymisation.
Limitations Observées :
- Attaques Ciblées : Un attaquant ciblé concentrant des ancres dans la cellule d'une victime spécifique n'a besoin que d'environ $d_{priv}$ ancres, indépendamment de $C$ .
- Référence de Chevauchement : Si un attaquant possède un corpus de référence chevauchant, le préfixe public (même si la clé est une clé globale unique) permet la désanonymisation une fois cette clé récupérée.
- Modèles d'Accès : Comme la base, Shard ne cache pas les modèles d'accès (quels documents sont reclassés).

5. Signification et Revendications

L'article positionne Shard comme une défense géométrique sensible aux attaques, affirmant explicitement qu'il ne s'agit pas d'une garantie cryptographique pour les documents stockés.

Réussite Centrale : Shard déplace le compromis vie privée/précision en supprimant la vulnérabilité de la « géométrie globale unique ». Il permet un reclassement exact et en pleine dimension (préservant l'utilité) tout en rendant l'alignement du résiduel privé coûteux pour les attaquants diffus.
Philosophie de Conception : Ce travail déplace la confidentialité des plongements de l'optimisation d'un substitut de distorsion ( $\sigma_{rec}$ ) vers le durcissement contre des surfaces d'attaque spécifiques (alignement et fuite d'index).
Revendications Modestes : Les auteurs sont explicites sur ce que Shard ne fait pas :
- Il ne protège pas contre les attaques ciblées se concentrant sur une seule cellule.
- Il n'empêche pas la désanonymisation via des corpus de référence chevauchants si la clé du préfixe public est récupérée.
- Il ne cache pas les modèles d'accès.
- La rotation secrète est une couche d'obscurcissement empirique, et non une primitive cryptographique.

L'article conclut que Shard offre une famille de transformations ajustables (via le paramètre $C$ ) qui peuvent être révoquées au niveau de la cellule, fournissant une défense pratique et mesurée contre les attaques d'alignement modernes dans les systèmes de recherche dense, à condition que le système soit composé d'autres primitives (comme le PIR) pour gérer les modèles d'accès et les chevauchements de références.