💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Cet article propose des protocoles efficaces d'intersection de jeux flous (FPSI) pour les métriques de distance $L_p$ qui, en exploitant des opérations à clé symétrique et une technique de préfixe, surpassent significativement les constructions existantes en termes de temps d'exécution et de coût de communication.

Auteurs originaux : Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

Publié 2026-04-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

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 Dilemme des "Jumeaux" : Comment trouver des ressemblances sans se montrer ?

Imaginez deux personnes, Alice (l'expéditrice) et Bob (le receveur).

Alice a une liste de photos de visages (son ensemble de données).
Bob a une liste de photos de visages aussi (son ensemble de données).

Leur but est de trouver les visages qui se ressemblent. Mais il y a un problème : ils ne veulent pas se montrer leurs listes. Ils veulent garder leurs données secrètes.

Le problème du "Fuzzy" (Flou)

Dans la vie réelle, les choses ne sont jamais parfaites.

Si Alice a une photo de son visage souriant et Bob a une photo de son visage en train de rire, ce sont techniquement deux images différentes.
Pourtant, ce sont le même visage.

Les systèmes classiques de sécurité (appelés PSI) sont trop rigides : ils disent "C'est soit exactement la même image, soit ce n'est rien". Ils ne comprennent pas les nuances (comme un peu de lumière différente, un angle différent, ou un peu de bruit). C'est ce qu'on appelle le Fuzzy PSI (Intersection de Jeux Flous) : trouver les éléments qui sont suffisamment proches, même s'ils ne sont pas identiques.

🚧 L'ancien problème : Trop lent et trop cher

Jusqu'à présent, pour faire ce genre de comparaison secrète, les chercheurs utilisaient des méthodes mathématiques très lourdes, un peu comme essayer de déverrouiller un coffre-fort avec une clé en diamant pour chaque petite serrure.

Le coût : C'était extrêmement lent (des heures de calcul) et demandait beaucoup de données à échanger (comme envoyer une bibliothèque entière pour trouver un seul mot).
La complexité : Plus les photos étaient détaillées (plus il y avait de dimensions), plus le système devenait inutilisable.

💡 La solution de ce papier : Des clés secrètes et des filtres intelligents

Les auteurs de ce papier (Yang, Hao, et al.) ont inventé une nouvelle méthode beaucoup plus rapide et légère. Voici comment ils font, avec des analogies simples :

1. La "Clé Magique Partagée" (so-OPPRF)

Imaginez que Alice et Bob ont une machine à café secrète.

Au lieu de donner leur liste complète à l'autre, ils utilisent une clé mathématique partagée.
Cette machine permet de vérifier si deux éléments sont proches sans jamais révéler ce qu'ils sont.
C'est comme si Alice disait : "J'ai un objet qui ressemble à ça" et Bob répondait : "Moi aussi, j'ai un objet qui ressemble à ça", sans jamais montrer l'objet réel. Ils ne se disent que : "Oui, ça correspond" ou "Non".

2. Le "Filtre de Tri" (Fuzzy Mapping)

Avant de comparer chaque photo de Alice avec chaque photo de Bob (ce qui prendrait des siècles), ils utilisent un système de codes postaux.

Ils placent chaque photo dans un "quartier" (un identifiant) basé sur sa forme.
Si deux visages sont proches (dans le rayon de tolérance $\delta$ ), ils se retrouvent automatiquement dans le même quartier.
Cela réduit le travail : au lieu de comparer 1 million de photos avec 1 million d'autres, ils ne comparent que celles qui sont dans le même quartier.

3. Le "Filtre Fin" (Refined Filtering)

Parfois, le système de quartier fait des erreurs et met deux visages différents dans le même quartier (ce sont de faux positifs).

Les auteurs ajoutent une seconde étape de vérification très rapide pour s'assurer que les visages sont vraiment proches.
C'est comme un gardien de sécurité qui vérifie l'identité exacte de ceux qui sont dans le bon quartier avant de les laisser passer.

4. L'astuce des "Préfixes" (Pour les grands espaces)

Si la zone de recherche est très grande (par exemple, on cherche des visages qui se ressemblent même s'ils sont très différents), comparer tout devient lent.

Les auteurs utilisent une technique de préfixe (comme les préfixes de numéros de téléphone).
Au lieu de vérifier chaque chiffre d'un numéro un par un, ils vérifient d'abord les premiers chiffres. Si le préfixe ne correspond pas, ils arrêtent tout de suite. Cela rend le processus exponentiellement plus rapide quand la zone de recherche est grande.

🏆 Les Résultats : Une révolution de vitesse

Les auteurs ont testé leur système et les résultats sont impressionnants :

Vitesse : Leur méthode est 12 à 145 fois plus rapide que les meilleures méthodes précédentes. C'est comme passer d'une voiture de ville à un avion de chasse.
Communication : Ils envoient 3 à 8 fois moins de données sur le réseau. C'est comme envoyer un SMS au lieu d'un colis de 50kg.
Économie : Ils utilisent des opérations mathématiques simples (symétriques) au lieu de calculs complexes (cryptographie lourde), ce qui économise énormément d'énergie et de temps.

🎯 En résumé

Ce papier propose un nouveau moyen de trouver des "cousins" (des données similaires) dans deux listes secrètes, sans jamais se montrer les listes.

Avant : C'était lent, cher et lourd.
Maintenant : C'est rapide, léger et efficace, grâce à de nouvelles "clés secrètes" partagées et des filtres intelligents.

C'est une avancée majeure pour la protection de la vie privée, permettant par exemple de vérifier si une empreinte digitale correspond à un suspect sans révéler l'empreinte du suspect à la police, ou de vérifier des dossiers médicaux sans les divulguer.

1. Problématique et Contexte

Le Private Set Intersection (PSI) permet à deux parties (un émetteur et un récepteur) de calculer l'intersection de leurs ensembles respectifs sans révéler d'informations supplémentaires. Cependant, les protocoles PSI standards ne fonctionnent que pour des correspondances exactes. Dans de nombreuses applications réelles, comme l'authentification biométrique (empreintes digitales, reconnaissance faciale) ou le traitement de données géospatiales, les données peuvent varier légèrement en raison du bruit ou des erreurs d'extraction de caractéristiques.

Cela a conduit au développement du Fuzzy PSI (FPSI), où le récepteur apprend les éléments de l'émetteur qui sont "proches" (à une distance inférieure ou égale à un seuil $\delta$ ) selon une métrique donnée (généralement $L_p$ avec $p \in [1, \infty]$ ).

Limites des travaux existants :

Les solutions précédentes pour des métriques $L_p$ générales reposent souvent sur des cryptographies homomorphes additivement (AHE) coûteuses (comme ElGamal ou Paillier), entraînant une mauvaise performance pratique.
D'autres approches évitent l'AHE mais souffrent d'une complexité exponentielle par rapport à la dimension des éléments ( $d$ ), ce qui les rend inutilisables pour des données de haute dimension.
Les travaux récents (Gao et al., Dang et al.) ont atteint une complexité linéaire mais au prix d'une forte dépendance aux opérations AHE, limitant leur efficacité concrète.

L'objectif de ce travail est de concevoir des protocoles FPSI concrètement efficaces pour des métriques $L_p$ générales, avec une complexité linéaire par rapport à la taille des ensembles, la dimension et le seuil de distance, tout en évitant les primitives à clé publique coûteuses.

2. Méthodologie et Architecture Technique

Les auteurs proposent une nouvelle architecture modulaire basée principalement sur des opérations de cryptographie symétrique légères.

A. Bloc de construction fondamental : so-OPPRF

Le cœur de la proposition est un nouveau bloc nommé Oblivious Programmable PRF with Secret-shared Outputs (so-OPPRF).

Fonctionnement : C'est une variante de l'OPPRF (Fonction Pseudo-Aléatoire Programmable Oublieuse). Contrairement à un OPPRF standard où le récepteur reçoit la valeur complète, ici, la sortie est partagée secrètement entre l'émetteur et le récepteur ( $y = y_S + y_R$ ).
Implémentation : Il est construit en combinant un Oblivious Key-Value Store (OKVS) avec un OPRF à sortie partagée (so-OPRF). Cela permet d'évaluer des fonctions programmées sans révéler les sorties à aucune des parties individuellement, tout en utilisant des opérations symétriques rapides.

B. Protocole de Cartographie Floue (Fuzzy Mapping)

Pour gérer la distance floue, le protocole utilise une approche en deux étapes :

Cartographie Locale : Chaque partie mappe ses éléments à des identifiants locaux. Pour garantir que deux éléments proches ( $\le \delta$ ) obtiennent le même ID, les parties utilisent le so-OPPRF. L'émetteur programme des intervalles de valeurs dans l'OKVS, et le récepteur interroge ces intervalles de manière oblique.
Cartographie Globale : Pour éviter les fuites d'information sur les correspondances partielles (qui pourraient révéler la position des éléments), les parties utilisent un OPRF à entrées partagées (si-OPRF). Elles combinent les parts de la cartographie locale avec une clé PRF partagée pour générer des IDs globaux sécurisés.

C. Filtrage Raffiné (Refined Filtering)

La phase de cartographie peut introduire des faux positifs. Une seconde phase utilise à nouveau le so-OPPRF pour vérifier la distance exacte :

Pour la distance $L_\infty$ : Les parties vérifient si la somme des parts secrètes est égale à 0 (Test d'Égalité Privé - PEQT).
Pour la distance $L_p$ ( $p \ge 1$ ) : Le protocole intègre une conversion booléenne-arithmétique (B2A) et un test d'intervalle privé pour vérifier si la somme des distances élevées à la puissance $p$ est inférieure à $\delta^p$ .

D. Optimisation par Préfixe (Prefix Optimization)

Pour les grands seuils de distance $\delta$ , la complexité linéaire en $\delta$ devient un goulot d'étranglement. Les auteurs intègrent une technique de représentation par préfixe :

Au lieu de programmer l'intervalle complet de taille $2\delta + 1$ , l'émetteur ne programme que $O(\log \delta)$ préfixes qui couvrent l'intervalle.
Cela réduit la complexité de communication et de calcul de $O(\delta)$ à $O(\log \delta)$ .

3. Contributions Clés

so-OPPRF : Introduction d'un nouveau primitif cryptographique permettant des évaluations de PRF programmables avec des sorties partagées, essentiel pour masquer les informations tout en permettant des calculs distribués.
Cartographie Floue Modulaire : Conception d'un protocole de mapping utilisant so-OPPRF et si-OPRF, simplifiant la compréhension et l'instanciation efficace.
Efficacité Linéaire : Proposition de protocoles FPSI pour les métriques $L_p$ ( $p \in [1, \infty]$ ) avec une complexité linéaire en la taille des ensembles ( $m, n$ ), la dimension ( $d$ ) et le seuil ( $\delta$ ), reposant uniquement sur des opérations symétriques.
Optimisation Logarithmique : Intégration de techniques de préfixe pour réduire la dépendance au seuil $\delta$ à une complexité logarithmique, rendant le protocole scalable pour de grands seuils.
Évaluations Étendues : Implémentation complète et comparaison avec l'état de l'art.

4. Résultats Expérimentaux

Les auteurs ont implémenté leurs protocoles en C++ et comparé leurs performances avec les travaux de référence de Gao et al. (ASIACRYPT'24) et Dang et al. (CCS'25).

Performance Globale : Les protocoles proposés surpassent systématiquement les travaux existants.
- Temps d'exécution : Accélération de 12 à 145 fois par rapport à Gao et al., et de 9 à 80 fois par rapport à Dang et al.
- Coût de Communication : Réduction de 3 à 8 fois par rapport à Gao et al., et de 5 à 19 fois par rapport à Dang et al.
Impact de l'Optimisation par Préfixe : Pour des seuils de distance élevés ( $\delta \ge 64$ ), l'optimisation par préfixe réduit considérablement le coût de communication (jusqu'à 11 fois moins pour $\delta=1024$ ) et améliore le temps d'exécution.
Scalabilité : Les gains de performance sont encore plus marqués pour des ensembles de données de grande taille (ex: $2^{16}$ éléments), car les coûts fixes des protocoles sous-jacents (comme le Silent OT) sont amortis.

5. Signification et Impact

Ce travail représente une avancée significative dans le domaine de la confidentialité des données et du calcul sécurisé multipartite (MPC) :

Passage à l'échelle pratique : En éliminant la dépendance aux cryptographies homomorphes coûteuses et en réduisant la complexité exponentielle, ce travail rend le FPSI viable pour des applications réelles à haute dimension (biométrie, géolocalisation, génomique).
Efficacité Concrète : La démonstration de gains de vitesse d'un ordre de grandeur (jusqu'à 145x) par rapport aux solutions linéaires précédentes établit un nouveau standard de performance pour le FPSI.
Flexibilité : La prise en charge de toutes les métriques $L_p$ avec une seule architecture modulaire offre une grande flexibilité pour différents cas d'usage.
Limitations et Perspectives : Les auteurs reconnaissent que leurs protocoles reposent sur des hypothèses de distribution des données (projection disjointe) et que la sécurité contre des adversaires malveillants reste un défi à relever sans trop sacrifier l'efficacité.

En résumé, cette recherche propose une solution concrètement efficace, modulaire et évolutive pour l'intersection de jeux de données flous, comblant le fossé entre la théorie complexe et les besoins pratiques de la protection de la vie privée dans les systèmes modernes.