Résumé technique : Comment la connaissance de la distribution des requêtes compromet les requêtes de plage multidimensionnelles chiffrées

Énoncé du problème

L'article traite de la vulnérabilité des requêtes de plage multidimensionnelles chiffrées dans les schémas de recherche sur données chiffrées (Searchable Encryption, SE). Bien que le SE permette une recherche efficace sur des données chiffrées, il fuite inévitablement des informations via les motifs d'accès (quelles enregistrements sont récupérés) et les motifs de requêtes. Les précédentes attaques par abus de fuite sur les bases de données multidimensionnelles ont rencontré des limitations significatives :

1. Limitations de sortie : Les attaques les plus avancées (State-of-the-art, SOTA) (par exemple, Even Less [40], Remin [34]) produisent généralement une intégration de graphe représentant uniquement la topologie des données (relations de voisinage relatives) plutôt que des coordonnées en clair concrètes. Pour obtenir des coordonnées, ces attaques nécessitent des transformations a posteriori (rotation, mise à l'échelle, translation) qu'un véritable attaquant ne peut effectuer sans connaître la vérité terrain.
2. Modèles de menace irréalistes : Certaines variantes (par exemple, Remin+) parviennent à reconstruire les coordonnées mais reposent sur l'hypothèse irréaliste qu'un attaquant peut injecter des enregistrements en clair choisis de manière adversaire dans la base de données pour servir de points d'ancrage.
3. Absence de garanties : Les attaques multidimensionnelles antérieures manquent de garanties théoriques rigoureuses concernant le nombre de requêtes nécessaires, la paramétrisation optimale ou la qualité de la reconstruction dans le pire des cas.

Les auteurs postulent que la connaissance de la distribution des requêtes (la distribution statistique des requêtes émises par les utilisateurs), combinée à la fuite des motifs d'accès, suffit à briser ces schémas avec des garanties prouvables, sans nécessiter d'injection de données ni de transformations a posteriori.

Méthodologie : LAMa

Les auteurs introduisent LAMa (Leakage-Abuse via Matching), un cadre à trois composants qui reconstruit les coordonnées en clair dans des dimensions arbitraires en revisitant et en formalisant le concept de correspondance de fréquence.

Concept de base

L'attaque repose sur l'observation que si un attaquant connaît la distribution des requêtes ($QD$), il peut précalculer la probabilité théorique qu'une valeur en clair spécifique (ou un ensemble de valeurs) soit récupérée par une requête aléatoire. En observant la fréquence empirique avec laquelle les enregistrements chiffrés sont récupérés depuis le serveur, l'attaquant peut faire correspondre ces fréquences aux probabilités précalculées pour déduire les valeurs en clair sous-jacentes.

Composants du cadre

1. Sélecteur : Détermine quels sous-ensembles d'enregistrements chiffrés analyser. L'article propose une stratégie universelle, $T_{2k}$, qui sélectionne toutes les intersections d'au plus $2k$ enregistrements (où $k$ est le nombre de dimensions). Les auteurs prouvent que cette taille de sous-ensemble spécifique est nécessaire et suffisante pour contraindre l'espace de reconstruction à sa limite informationnelle.
2. Traducteur : Convertit les observations de correspondance de fréquence en une formule de programmation par contraintes (CP). Il identifie toutes les affectations de valeurs en clair candidates qui satisfont les fréquences observées (dans une approximation $\epsilon$) et encode l'exclusivité mutuelle et la cohérence simultanée de ces affectations dans une formule logique.
3. Résolveur : Résout la formule CP pour trouver des affectations satisfaisantes de valeurs aux enregistrements chiffrés. Le résolveur peut énumérer toutes les solutions valides, garantissant que la vraie base de données se trouve parmi elles à la limite.

Garanties théoriques

L'article fournit les premières garanties rigoureuses pour la correspondance de fréquence multidimensionnelle :

• Optimalité : Le sélecteur $T_{2k}$ garantit que l'ensemble des reconstructions possibles est exactement l'Espace de Reconstruction ($RS_{QD}(DB)$), défini comme l'ensemble de toutes les bases de données indiscernables de la vraie base de données sous la distribution de requêtes et le profil de fuite donnés.
• Complexité des requêtes : En utilisant la théorie de la dimension VC, les auteurs dérivent des bornes sur le nombre de requêtes observées nécessaires pour approximer les fréquences de récupération avec une erreur $\epsilon$ et une confiance $1-\delta$.
• Qualité de sortie : L'article propose deux stratégies pour sélectionner une seule sortie à partir de l'espace de reconstruction : le Diamètre (pessimiste, borne du pire cas) et le Centroïde (optimiste, position moyenne). Il fournit des bornes formelles sur l'erreur de reconstruction pour ces stratégies.

Analyse de la distribution des requêtes

Les auteurs enquêtent sur quelles distributions de requêtes maximisent l'incertitude de reconstruction. Ils prouvent qu'une distribution « référence » rendant la reconstruction impossible (en rendant toutes les bases de données indiscernables) ne peut pas exister pour des distributions de requêtes expressives. Cependant, ils construisent une distribution spécifique (via l'Algorithme 2) qui égalise les probabilités de récupération pour toutes les paires de valeurs ayant la même distance $L_1$. Sous cette distribution, l'attaquant ne peut récupérer que les distances par paires, et non les coordonnées absolues, étendant ainsi l'espace de reconstruction à son maximum théorique pour ce contexte.

Contributions clés

1. Reconstruction au niveau des coordonnées sans injection : LAMa est la première attaque à reconstruire des coordonnées en clair concrètes dans des dimensions arbitraires sans nécessiter d'injection de données ni de transformations géométriques a posteriori.
2. Garanties rigoureuses : Ce travail établit les premières garanties formelles pour la correspondance de fréquence multidimensionnelle, couvrant la complexité des requêtes, la paramétrisation optimale ($T_{2k}$) et la qualité de sortie dans le pire des cas.
3. Caractérisation des limites de reconstruction : L'article définit l'espace de reconstruction pour les attaques basées sur la distribution des requêtes et construit une distribution de requêtes spécifique qui maximise l'incertitude tout en restant expressive.
4. Performance empirique supérieure : Les expériences démontrent que LAMa surpasse systématiquement les attaques SOTA (Even Less, Remin, Remin+) en termes de précision de reconstruction (Erreur Quadratique Moyenne) et de taille de l'espace des solutions.

Résultats expérimentaux

Les auteurs ont évalué LAMa sur des ensembles de données réels (Spitz, Californie, Shanghai, Amsterdam, Manhattan, Paris) et des grilles synthétiques sous diverses distributions de requêtes (Uniforme, Gaussienne, Bêta).

• Cas idéal : Lorsque les fréquences sont exactes, LAMa atteint une MSE = 0 (reconstruction parfaite) sur tous les ensembles de données. En revanche, les attaques SOTA produisent des milliers de solutions avec une MSE nettement plus élevée, échouant souvent à récupérer la topologie ou les coordonnées correctes sans transformation manuelle.
• Cas réaliste : Avec une observation partielle des requêtes (10-30 % des requêtes), l'erreur de reconstruction de LAMa diminue de manière monotone à mesure que davantage de requêtes sont observées. Les attaques SOTA ne montrent aucune amélioration cohérente avec l'augmentation du volume de requêtes et maintiennent une variance élevée.
• Qualité de sortie : Les stratégies de centroïde et de diamètre de LAMa produisent des bornes d'erreur nettement inférieures aux méthodes SOTA, même lorsque les méthodes SOTA bénéficient de l'avantage de l'injection de données en clair (Remin+).
• Hautes dimensions : LAMa reconstruit avec succès des données dans les dimensions 2 à 6 avec une faible erreur, tandis que les codebases SOTA étaient limités dans leur capacité à gérer des dimensions plus élevées.

Signification et revendications

L'article affirme que la correspondance de fréquence, précédemment considérée comme une technique folklorique limitée à une dimension, est une fondation principielle et puissante pour la cryptanalyse des fuites multidimensionnelles lorsqu'elle est combinée à la connaissance de la distribution des requêtes.

Les auteurs soulignent que leur travail :

• Briser la barrière « Topologie uniquement » : Contrairement aux attaques multidimensionnelles précédentes qui ne récupéraient que la structure relative, LAMa récupère les coordonnées absolues.
• Opère sous des modèles de menace plus faibles : Il ne nécessite pas la capacité irréaliste d'injecter des données dans la base de données de la victime.
• Fournit des limites de sécurité prouvables : En définissant l'espace de reconstruction et en prouvant l'optimalité du sélecteur $T_{2k}$, l'article établit les limites théoriques de ce qui est possible à récupérer, montrant que si une reconstruction parfaite est souvent réalisable, des distributions de requêtes spécifiques peuvent limiter l'attaquant à la récupération de distances relatives uniquement.

Le travail conclut que la connaissance de la distribution des requêtes est une vulnérabilité critique pour les requêtes de plage multidimensionnelles chiffrées, rendant les techniques actuelles de suppression des fuites insuffisantes face aux attaques par correspondance de fréquence qui sont à la fois conceptuellement simples et rigoureusement garanties.