💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Cet article présente de nouveaux protocoles d'Intersection d'Ensembles Privés Flous (FPSI) pour les distances $L_p$ générales qui atteignent une dépendance logarithmique optimale vis-à-vis du seuil de distance $\delta$ en utilisant uniquement le transfert oblique et des primitives à clé symétrique, éliminant ainsi le besoin de chiffrement homomorphe coûteux tout en surpassant de manière significative les solutions de pointe en termes de temps d'exécution et de communication.

Auteurs originaux : Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Publié 2026-06-16

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

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

Imaginez deux personnes, Alice et Bob, qui veulent découvrir s'ils possèdent des articles « similaires » dans leurs collections respectives sans se montrer l'intégralité de leurs listes.

Le Problème : Dans un jeu standard, ils ne feraient correspondre que les articles qui sont exactement les mêmes (par exemple, les deux ont une « Pomme Rouge »).
Le Twist (PSI Flou) : Dans ce nouveau jeu, ils veulent faire correspondre des articles qui sont assez proches. Par exemple, si Alice a une « Pomme Rouge » et que Bob a une « Pomme Rouge légèrement meurtrie », cela doit être compté comme une correspondance. La règle est la suivante : « Si la différence entre nos articles est inférieure à une distance spécifique (appelons-la le Seuil, ou Threshold), nous avons une correspondance. »

Le défi est de faire cela de manière sécurisée. Alice ne doit pas apprendre toute la liste de Bob, et Bob ne doit pas apprendre toute la liste d'Alice. Ils veulent seulement savoir quels articles sont suffisamment proches.

L'Ancienne Méthode : La Recherche Lente et Coûteuse

Les méthodes précédentes pour ce jeu de « correspondance floue » présentaient deux problèmes majeurs :

Le Piège de la « Linéarité » : Si le seuil de « proximité » était important (disons 100 unités), les ordinateurs devaient vérifier 100 possibilités différentes pour chaque article. C'était comme chercher une aiguille dans une botte de foin en vérifiant chaque brin de paille un par un. Plus le seuil était grand, plus c'était lent.
Le Problème de la « Machinerie Lourde » : Pour faire fonctionner cela de manière sécurisée, les anciennes méthodes utilisaient des outils cryptographiques très lourds et lents (comme le chiffrement homomorphe additif). Considérez cela comme essayer d'envoyer un message secret avec un énorme camion gourmand en carburant, alors qu'un vélo suffirait.

La Nouvelle Percée : Le Raccourci du « Préfixe »

Cet article présente une nouvelle façon de jouer au jeu qui est rapide, légère et intelligente.

1. L'Analogie du « Code Postal » (Les Préfixes)

Au lieu de vérifier chaque nombre dans une plage (comme vérifier si un nombre est 10, 11, 12... jusqu'à 100), les auteurs utilisent un tour appelé Préfixes.

Imaginez que vous cherchez une maison dans une ville.

Ancienne Méthode : Vous frappez à toutes les portes du quartier pour voir si l'habitant est votre ami.
Nouvelle Méthode : Vous regardez le Code Postal. Si votre ami habite dans le « 10001 », vous n'avez besoin de vérifier que les maisons ayant ce préfixe. Vous n'avez pas besoin de vérifier toute la ville.

Les auteurs ont réalisé que n'importe quelle « plage » de nombres (le seuil) peut être décomposée en seulement quelques « Codes Postaux » (préfixes).

La Magie : Le temps nécessaire pour vérifier ces préfixes ne croît pas avec la taille du seuil ; il croît de manière logarithmique.
- Si le seuil double, le travail n'augmente que très légèrement.
- Si le seuil devient 100 fois plus grand, le travail ne double que.
Analogie : C'est comme trouver un livre dans une bibliothèque. Vérifier chaque livre prend un temps infini. Vérifier l'étiquette de l'étagère (le préfixe) prend quelques secondes, peu importe le nombre de livres sur cette étagère.

2. Les Outils « Légers » (Primitives Symétriques)

Les auteurs ont remplacé les « camions » lourds (chiffrement coûteux) par des « vélos » (primitives à clé symétrique et transfert oblique).

Transfert Oblique (Oblivious Transfer - OT) : Imaginez un serveur qui peut vous donner l'un de deux articles secrets de la carte sans que vous sachiez lequel vous avez choisi, et sans que le serveur ne sache lequel vous avez voulu. Les auteurs utilisent cela pour échanger des informations de manière sécurisée sans révéler toute la liste.
Le Résultat : Leur système est entièrement construit à partir de ces outils légers et rapides.

Les Deux Scénarios : Petites Pièces vs Grands Entrepôts

L'article propose deux stratégies différentes selon la façon dont les données sont « encombrées » (la dimensionnalité) :

Scénario A : Faibles Dimensions (L'Hypothèse de l'« Appartement »)

Le Cadre : Imaginez une petite pièce où les gens se tiennent éloignés les uns des autres (au moins 2 fois la distance du seuil).
La Stratégie : Ils utilisent le Hachage Spatial (Spatial Hashing). Imaginez diviser la pièce en une grille de carreaux. Si deux personnes sont proches, elles doivent se trouver dans le même carreau ou dans des carreaux voisins. Le protocole ne vérifie que ces carreaux spécifiques.
L'Innovation : Ils ont combiné ce système de grille avec leur nouveau raccourci de « Préfixe » et un outil spécial de « Vérification d'Égalité » (appelé ECSS). Cela leur permet de trouver des correspondances instantanément sans vérifier chaque paire.

Scénario B : Hautes Dimensions (L'Hypothèse de la « Séparation »)

Le Cadre : Imaginez un immense entrepôt multidimensionnel. Dans les hautes dimensions, diviser l'espace en une grille crée trop de carreaux vides (la « malédiction de la dimensionnalité »).
La Stratégie : Ils utilisent la Génération d'ID Distribuée. Au lieu d'une grille, ils donnent à chaque article une « carte d'identité » unique basée sur son emplacement.
L'Innovation : Ils ont créé une nouvelle façon de générer ces ID de manière sécurisée en utilisant leur astuce de « Préfixe ». Même dans un immense entrepôt, ils peuvent générer ces ID de sorte que si deux articles sont proches, leurs ID correspondront, sans révéler les emplacements réels des articles.

La « Recette Secrète » : Somme Conditionnelle d'Égalité

Le cœur de leur invention est un nouvel outil mathématique appelé Somme Conditionnelle d'Égalité (Equality Conditional Sum - ECSS).

Comment ça marche : Imaginez qu'Alice et Bob aient tous deux une liste de nombres. Ils veulent additionner les nombres uniquement si une condition spécifique est remplie (par exemple, « Uniquement si les préfixes correspondent »).
La Magie : Ils peuvent effectuer cette addition de manière sécurisée sans qu'aucune des deux parties ne révèle ses nombres. Si les préfixes ne correspondent pas, le résultat n'est que du bruit aléatoire. S'ils correspondent, le résultat est la somme correcte. Cela leur permet de vérifier la proximité des éléments sans jamais voir les valeurs réelles.

Les Résultats : Une Accélération Massive

Les auteurs ont construit une version fonctionnelle de leur système et l'ont testée contre les meilleures méthodes existantes.

Vitesse : Leur système est jusqu'à 43,7 fois plus rapide que la meilleure méthode précédente.
Utilisation de Données : Il utilise jusqu'à 31,3 fois moins de données à envoyer sur le réseau.
Scalabilité (Évolutivité) : Alors que d'autres systèmes s'effondraient (manquaient de mémoire) lorsque les ensembles de données devenaient très importants, leur système continuait de fonctionner de manière fluide.

Résumé

En bref, cet article résout le problème de la « correspondance floue » en :

Remplaçant le chiffrement lent et lourd par des outils rapides et légers.
Utilisant les « Préfixes » (comme les codes postaux) pour transformer une recherche linéaire lente en une recherche logarithmique rapide.
Créant de nouveaux outils de « Somme Secrète » qui permettent à deux parties de vérifier la proximité sans révéler leurs secrets.

Le résultat est un système capable de trouver des articles « similaires » dans des ensembles de données massifs et privés presque instantanément, rendant la correspondance de données respectueuse de la vie privée pratique à grande échelle pour la première fois.

Résumé Technique : FPSI Flou à partir de Primitives Symétriques avec une Dépendance Logarithmique Exacte vis-à-vis du Seuil de Distance

Énoncé du Problème
L'Intersection d'Ensembles Privée Floue (Fuzzy Private Set Intersection - FPSI) permet à un expéditeur possédant un ensemble de vecteurs de dimension $d$ ( $Q$ ) et à un récepteur possédant un ensemble $W$ d'identifier les éléments $q \in Q$ tels qu'il existe un $w \in W$ avec $\text{dist}(q, w) \le \delta$ , sans révéler d'informations supplémentaires. Bien que le PSI standard ait atteint une grande efficacité, les protocoles FPSI existants font face à des goulots d'étranglement théoriques et pratiques importants. Les travaux antérieurs présentent généralement une mise à l'échelle linéaire avec le seuil de distance $\delta$ (c'est-à-dire $O(\delta)$ ), ou n'atteignent une dépendance poly-logarithmique que pour les distances $L_\infty$ . Les protocoles supportant les distances de Minkowski générales ( $L_p$ pour $p \in [1, \infty]$ avec une dépendance logarithmique sur $\delta$ ) ont soit reposé sur un chiffrement homomorphe additif (AHE) coûteux, soit souffert de failles de sécurité et de termes de complexité exponentielle en dimension $d$ . L'objectif est d'obtenir une dépendance logarithmique exacte sur $\delta$ pour les distances $L_p$ générales en utilisant uniquement des primitives à clés symétriques efficaces.

Méthodologie et Techniques Fondamentales
Les auteurs proposent de nouveaux protocoles FPSI construits entièrement à partir de Transferts Obliques (OT) et de primitives à clés symétriques, évitant ainsi les opérations de cryptographie à clé publique comme l'AHE. La construction repose sur deux hypothèses principales : l'hypothèse apart (adaptée aux contextes de faible dimension) et l'hypothèse separate (adaptée aux contextes de haute dimension).

Représentation par Préfixe et Test d'Intervalle :
L'innovation centrale remplace l'énumération de tous les entiers dans un intervalle $[q_k - \delta, q_k + \delta]$ (ce qui coûte $O(\delta)$ ) par une représentation de préfixe utilisant $O(\log \delta)$ préfixes. Cela réduit le coût du test d'intervalle à $O(\log \delta)$ par dimension.
Somme Conditionnelle d'Égalité / Partage de Produit Scalaire Conditionnel (ECSS/ECIPS) :
Pour gérer l'interaction requise par la correspondance de préfixes sans révéler l'entrée de l'expéditeur ni engendrer un surcoût exponentiel, les auteurs introduisent deux nouvelles primitives cryptographiques :
- Partage de Somme Conditionnelle d'Égalité (ECSS) : Utilisé pour la distance $L_\infty$ . Il permet aux parties de calculer une somme de valeurs conditionnellement à une correspondance d'égalité entre les vecteurs d'entrée, en produisant des parts secrètes du résultat.
- Partage de Produit Scalaire Conditionnel d'Égalité (ECIPS) : Utilisé pour les distances $L_p$ générales. Il calcule un produit scalaire conditionnellement à l'égalité, permettant le calcul de $|w_k - q_k|^p$ via l'expansion binomiale sans révéler les termes spécifiques.
  Ces deux primitives sont implémentées efficacement à l'aide d'OT, d'OPPRF (PRF Programmables Obliques) et de protocoles de Permute+Share (PS).
Gestion de Multiples Éléments :
- Faible Dimension ( $L_\infty$ et $L_p$ ) : Les protocoles utilisent le hachage spatial (cellules de grille) combiné au hachage Cuckoo pour réduire le nombre de comparaisons par paires. Les auteurs introduisent des optimisations utilisant l'OPRF partagé (sOPRF) pour éliminer le besoin de valeurs fictives dans les cases vides, masquant ainsi les positions de hachage de l'expéditeur et supprimant le besoin de étapes de permutation globale dans certaines configurations.
- Haute Dimension ( $L_\infty$ et $L_p$ ) : Pour éviter le coût exponentiel $O(2^d)$ du hachage spatial, les auteurs emploient un protocole de Génération d'ID Distribuée (dIDG). Ce protocole génère des ID uniques pour les éléments de sorte que les éléments proches partagent un ID. Les auteurs identifient des failles de sécurité dans les constructions d de dIDG antérieures (spécifiquement dans [DZL25]) liées à la fuite de collision et proposent un dIDG sécurisé basé sur des clés symétriques utilisant sOPRF et ECSS.

Contributions Clés

Nouvelles Primitives : L'introduction d'ECSS et d'ECIPS, qui permettent une correspondance floue avec une dépendance logarithmique exacte sur $\delta$ en utilisant uniquement des primitives symétriques.
Complexité Optimale : Les premiers protocoles FPSI pour les distances $L_p \in [1, \infty]$ générales qui atteignent une complexité strictement logarithmique $O(d \log \delta)$ par rapport au seuil $\delta$ . C'est théoriquement optimal, car distinguer des valeurs dans un intervalle de longueur $O(\delta)$ nécessite $\Omega(\log \delta)$ bits d'information.
Sécurité et Efficacité : Les protocoles éliminent la dépendance à l'AHE, la remplaçant par des opérations OT et des clés symétriques. Les auteurs identifient également et corrigent les vulnérabilités de sécurité des protocoles basés sur les préfixes récents (ex: [DZL25]) qui souffraient de réutilisation de masque et de fuite de collision.
Constructions Scalables : Des constructions distinctes pour les contextes de faible dimension (utilisant le hachage spatial) et de haute dimension (utilisant le dIDG), toutes deux atteignant une complexité asymptotique optimale.

Résultats Expérimentaux
Les auteurs ont implémenté leurs protocoles et les ont comparés aux travaux de l'état de l'art ([GQL+24], [DZL25], [BGMP25]).

Performance : Les nouveaux protocoles surpassent significativement les travaux antérieurs. Dans les contextes de faible dimension, ils atteignent jusqu'à 43,7× plus de rapidité d'exécution et 31,3× moins de surcharge de communication.
Scalabilité : Alors que les travaux antérieurs comme [GQL+24] et [DZL25] rencontraient des dépassements de mémoire à des tailles d'ensembles de $2^{16}$ dans les contextes de haute dimension, les protocoles proposés ont été exécutés avec succès sous les mêmes configurations.
Dépendance au Seuil : Les expériences confirment que le temps d'exécution et les coûts de communication évoluent de manière logarithmique avec $\delta$ , contrastant avec la mise à l'échelle linéaire observée dans les protocoles précédents à dépendance linéaire.

Signification
L'article revendique une percée théorique dans l'optimisation de la mise à l'échelle du seuil pour le FPSI, démontant qu'une dépendance logarithmique exacte sur $\delta$ est réalisable pour les distances $L_p$ générales sans recourir à une cryptographie à clé publique coûteuse. Pratiquement, cela fait progresser la faisabilité des applications FPSI scalables dans des domaines nécessitant la correspondance floue, tels que la comparaison de séquences génomiques, la recherche d'images similaires et la détection d'identifiants compromis, en supprimant les goulots d'étranglement d'efficacité associés à la dimension et au seuil de distance.