Vers une union privée améliorée, efficace et résistante aux fuites

Pourquoi le partage de listes peut menacer la vie privée

De nombreuses organisations conservent des listes sensibles — par exemple des adresses IP suspectes, des identifiants clients ou des participants à des études médicales — qu’elles aimeraient combiner avec la liste d’un autre acteur sans exposer leurs propres données. Un outil appelé union d’ensembles privée promet justement cela : il permet à deux parties d’apprendre la liste combinée des éléments uniques, et rien d’autre. Cet article montre que même des versions de pointe de cet outil peuvent discrètement divulguer des informations supplémentaires pendant leur exécution, et présente une nouvelle conception qui préserve les bénéfices tout en réduisant fortement ces risques cachés et le coût informatique.

Ce que l’union d’ensembles privée cherche à protéger

Imaginez deux entreprises comparant des listes noires d’attaques informatiques. Chacune souhaite obtenir la liste complète de toutes les adresses IP suspectes observées par l’une ou l’autre afin d’améliorer la défense de ses réseaux. En même temps, les méthodes de détection de chaque entreprise — et donc leur liste noire exacte — sont des secrets commerciaux. Si l’on pouvait déduire quelles adresses l’autre possède ou n’a pas, on pourrait remonter à ces méthodes. Les protocoles classiques d’union d’ensembles privée masquent déjà le recoupement direct entre les listes, mais des recherches récentes ont montré qu’ils peuvent encore révéler des indices pendant le calcul lui‑même ou via des motifs dans la façon dont les éléments sont organisés dans des structures de données internes.

Fuites cachées dans des méthodes rapides antérieures

Les schémas évolutifs antérieurs reposaient sur une recette consistant d’abord à vérifier, élément par élément, si chaque élément d’une liste apparaissait dans l’autre, puis à utiliser ces réponses pour livrer uniquement les éléments « nouveaux ». Des travaux ultérieurs ont montré que ce processus révèle intrinsèquement, avant la fin du protocole, combien d’éléments les listes partagent. Un participant curieux peut exploiter cela en interrompant et relançant le protocole avec des entrées légèrement modifiées, apprenant progressivement quels éléments se recoupent précisément. D’autres schémas rapides utilisaient le hachage — en plaçant les éléments dans des bacs selon une fonction de hachage — pour organiser les données. Une fois qu’une partie apprend quels éléments de l’autre sont uniques, elle peut recouper le motif des bacs remplis et vides pour déduire lesquels de ses propres éléments n’apparaissent définitivement pas dans l’autre liste, une forme de fuite « basée sur le hachage ».

Verrouiller les éléments derrière des déguisements aléatoires

Le nouveau protocole s’attaque à ces deux problèmes simultanément. Avant tout hachage, chaque partie exécute un échange cryptographique qui transforme chaque élément en un jeton à l’apparence aléatoire. La propriété cruciale est que les éléments identiques dans les deux listes sont transformés en jetons identiques, tandis que des éléments différents donnent des jetons sans relation — et aucune des parties n’apprend la clé secrète qui relie les jetons aux valeurs réelles. Ces jetons déguisés sont ensuite placés dans des tables basées sur le hachage et passés à travers une série d’étapes aléatoires et soigneusement structurées qui décident, en substance, si des jetons correspondent, sans révéler quel jeton se trouve dans quel bac. Répéter ce processus avec de la nouveauté aléatoire à chaque exécution empêche un attaquant de corréler des informations entre plusieurs runs.

Réduire le coût grâce à une structure de données plus intelligente

La sécurité seule ne suffit pas si un protocole est trop lourd pour être utilisé à grande échelle. Les auteurs repensent donc l’un des composants les plus coûteux : un module interne qui reposait auparavant sur un primitif cryptographique par lots pour comparer de nombreux éléments en une fois. Ils le remplacent par un magasin clé‑valeur oblivieux « bidirectionnel », une structure compacte qui permet à une partie d’encoder des paires clé–valeur afin que l’autre puisse les interroger sans apprendre autre chose que la présence d’une clé. En disposant deux encodages de ce type pour interagir, le protocole peut détecter quand des jetons s’alignent entre les deux listes tout en évitant de travailler sur des bacs vides ou factices. Ce changement réduit à la fois la quantité de données envoyées sur le réseau et le temps de calcul, en particulier pour de grandes listes.

Ce que montrent les expériences en pratique

Pour tester leurs idées, les auteurs ont implémenté leur protocole et l’ont comparé à la meilleure conception existante d’union d’ensembles privée améliorée sous les mêmes objectifs de confidentialité renforcée. Sur une large gamme de tailles de listes et de conditions réseau, leur méthode a systématiquement réduit la communication d’environ 1,1 à 3 fois et accéléré le temps d’exécution d’environ 1,0 à 1,7 fois. Il est important de noter que ces gains persistent même après l’ajout de la couche cryptographique supplémentaire qui empêche la fuite basée sur le hachage, que les schémas efficaces antérieurs négligeaient. Les résultats suggèrent qu’une protection renforcée n’implique pas nécessairement une lourde pénalité de performance.

Pourquoi cela compte pour le partage de données dans le monde réel

Concrètement, ce travail montre comment deux parties peuvent combiner des listes sensibles tout en limitant fortement ce que chacune peut déduire des données de l’autre — y compris à partir d’effets secondaires subtils pendant le protocole. En déguisant les éléments avant le hachage et en utilisant des structures internes plus sobres, la nouvelle conception ferme des canaux de fuite connus et reste suffisamment rapide pour des ensembles de données très volumineux. Cela rend l’union préservant la confidentialité de listes noires, d’identifiants clients ou d’autres identifiants plus pratique pour les entreprises et institutions qui doivent collaborer sans dévoiler les motifs contenus dans leurs propres données.

Citation: Liu, Q., Bae, J. & Lee, JW. Towards an improved efficient leakage-resilient enhanced private set union. Sci Rep 16, 10134 (2026). https://doi.org/10.1038/s41598-026-40531-5

Mots-clés: union d’ensembles privée, confidentialité des données, protocoles cryptographiques, partage sécurisé de données, résilience aux fuites