⚛️ quantum physics

Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

Cet article propose un protocole quantique d'intersection d'ensembles privés à seuil multipartite présentant un test de cardinalité explicite, lequel utilise une construction à photon unique basée sur la rotation et des primitives cryptographiques pour permettre à un tiers d'effectuer des mesures sans interpréter les résultats tout en ne révélant de manière sécurisée que si la taille de l'intersection atteint un seuil.

Auteurs originaux : Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Publié 2026-06-29

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

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 un groupe d'amis qui possèdent chacun une liste secrète de leurs films préférés. Ils veulent savoir : « Sommes-nous tous d'accord sur au moins trois films ? »

Si la réponse est oui, ils veulent voir la liste de ces trois films.
Si la réponse est non, ils ne veulent rien savoir — pas même combien de films ils avaient en commun.

C'est le problème de l'Intersection d'Ensembles Privée à Seuil (TPSI - Threshold Private Set Intersection). Le document propose une nouvelle façon de résoudre cela en utilisant la mécanique quantique (plus précisément des photons de lumière) et des mathématiques astucieuses, garantissant que même la personne qui dirige l'expérience ne peut pas tricher ou espionner les secrets.

Voici comment la solution du document fonctionne, décomposée en concepts simples :

1. Le problème des anciennes méthodes

Dans les tentatives quantiques précédentes, le groupe s'appuyait sur un « Référent » (appelé Partie Tierce ou TP) pour compter les correspondances.

La faille : Le Référent comptait les correspondances, comparait ce nombre au seuil (par exemple, « Est-ce 3 ? »), puis décidait de ce qu'il devait dire au groupe.
Le risque : Cela signifiait que le Référent voyait le nombre exact de correspondances. Si le groupe n'avait que 2 correspondances, le Référent le savait. Or, le groupe voulait seulement savoir s'ils avaient assez (3 ou plus), pas le compte exact. C'est comme demander à un juge : « L'accusé est-il coupable ? », mais le juge doit d'abord écrire une biographie complète du crime avant de répondre.

2. La nouvelle solution : Le « Référent aux yeux bandés »

Les auteurs ont créé un protocole où le Référent effectue les mesures mais est aveugle quant à la signification des résultats.

La configuration : Le code secret

Avant que l'expérience ne commence, les amis (les participants) conviennent d'un code secret entre eux. Ils mélangent également leurs vraies listes de films avec des listes fictives de « leurres » (ancres) que le Référent ne connaît pas.

La clé de dissimulation : Ils mélangent les positions de leurs films en utilisant une clé secrète. Pour le Référent, les listes ressemblent à du bruit aléatoire.
Le basculement (The Flip) : Ils conviennent d'un « basculement » secret (comme un code secret) qui change la signification des résultats. Si une lumière est sur « On », elle peut en réalité signifier « Off » selon ce basculement secret.

La danse quantique (La rotation)

L'expérience utilise des photons (particules de lumière) comme messagers.

Le Référent prépare une ligne de photons et les envoie au premier ami.
L'Ami 1 regarde sa liste secrète. S'il possède un film spécifique à un endroit donné, il donne au photon une légère « rotation » (spin). S'il ne l'a pas, il ne fait rien. Il ajoute également une rotation de « masque » secrète que lui seul et le Référent connaissent.
La chaîne : Les photons voyagent vers l'Ami 2, puis l'Ami 3, et ainsi de suite. Chaque ami ajoute sa propre rotation basée sur sa liste secrète.
Le retour : Les photons reviennent au Référent.

La magie des « Étiquettes cachées »

Lorsque les photons reviennent, le Référent retire ses propres masques et mesure la lumière.

Le résultat : Le Référent voit un motif de « Même » ou « Opposé ».
Le piège : À cause du « basculement » secret convenu par les amis, le Référent ne peut pas comprendre ce que signifie le motif. Un résultat « Même » peut signifier « Correspondance » ou « Pas de correspondance » selon un bit secret que seuls les amis connaissent. Le Référent a les données, mais elles ressemblent à du charabia pour lui.

3. La vérification finale : Le « Vote aveugle »

Maintenant, les amis et le Référent doivent décider : « Avons-nous atteint le seuil ? » sans que le Référent ne connaisse le compte exact.

L'astuce mathématique (OLE) : Ils utilisent un outil cryptographique appelé Évaluation Linéaire Oblivieuse (OLE). Considérez cela comme une calculatrice sécurisée où le Référent insère ses nombres « charabia » et les amis insèrent leurs « clés sectoires ».
Le Circuit Garbled (Garbled Circuit) : Ils exécutent un petit programme informatique verrouillé (un circuit garbled). Ce programme additionne les nombres en interne.
Le résultat : Le programme ne produit qu'un seul bit : 1 (Oui, nous avons assez de correspondances) ou 0 (Non, nous n'en avons pas assez).
- Si la réponse est 1, les amis révèlent la clé secrète pour décoder le motif « charabia » du Référent, et ils voient les films correspondants.
- Si la réponse est 0, ils jettent tout. Le Référent ne connaît jamais le nombre exact de correspondances, seulement qu'il n'était pas assez élevé.

4. Pourquoi est-ce sûr (Sécurité)

Le document prouve trois points de sécurité principaux :

Pas d'espions : Si un espion tente d'intercepter les photons, les lumières « leurres » (que l'espion ne connaît pas) changeront, alertant tout le monde que la ligne a été interceptée.
Le Référent est honnête mais curieux : Même si le Référent essaie de tricher ou d'utiliser des techniques quantiques sophistiquées pour deviner les secrets, les mathématiques garantissent qu'il ne peut pas distinguer les vraies correspondances du bruit. Il est véritablement aveugle au sens des données.
Les amis ne peuvent pas tricher entre eux : Même si deux amis s'allient pour espionner le troisième, ils ne peuvent pas découvrir la liste du troisième ami grâce aux masques secrets et à la façon dont les photons sont pivotés.

5. La preuve par le « Modèle Jouet »

Pour montrer que cela fonctionne réellement, les auteurs ont construit une petite simulation utilisant le simulateur d'ordinateur quantique d'IBM (Qiskit).

Ils ont simulé 3 amis avec de petites listes.
Ils ont ajouté du « bruit » (simulant les imperfections du monde réel).
Le résultat : Le système a correctement identifié que les amis avaient 2 films en commun (ce qui est en dessous de leur seuil de 3). Le système a dit « Non », et les amis n'ont rien appris.
Ils ont ensuite montré que si les amis avaient eu 3 correspondances, le système aurait correctement dit « Oui » et aurait révélé la liste.

Résumé

Ce document présente un protocole de PSI à seuil multi-parties quantiques.

Objectif : Révéler un secret partagé uniquement si le groupe est suffisamment grand.
Innovation : Il sépare l'acte de mesurer (effectué par un Référent) de l'acte d'interpréter (effectué par le groupe).
Mécanisme : Il utilise des photons en rotation et des « basculements » secrets pour créer des « étiquettes cachées » que le Référent ne peut pas lire, garantissant que le compte exact des correspondances reste privé.
Résultat : Le groupe apprend seulement un simple « Oui/Non » concernant le seuil, et ce n'est que si la réponse est « Oui » qu'ils voient les éléments partagés.

Résumé Technique : Intersection d'Ensembles Privés à Seuil Multi-Partie Quantique avec Test de Cardinalité Explicite

Énoncé du Problème
L'Intersection d'Ensembles Privés (PSI - Private Set Intersection) permet à des parties de calculer l'intersection de leurs ensembles privés sans révéler les éléments non intersectants. Le PSI à seuil (TPSI - Threshold PSI) étend cela en ne révélant l'intersection que si sa cardinalité atteint ou dépasse un seuil public $\tau$ . Bien que des protocoles de TPSI classiques existent, les protocoles de TPSI quantiques actuels (par exemple, [MSD+24, LZY+26, WLS+26]) reposent généralement sur une Tierce Partie (TP) pour effectuer les mesures finales et interpréter les résultats. Dans ces schémas, la TP récupère la cardinalité exacte de l'intersection puis la compare à $\tau$ . Cette approche s'écarte du paradigme idéal du TPSI, car elle expose la statistique de cardinalité exacte à la TP plutôt que de ne révéler que le prédicat d'un bit $\mathbb{1}[|\bigcap X_i| \ge \tau]$ . Cela crée un décalage de fonctionnalité et une concentration d'autorité où la TP agit à la fois comme fournisseur de ressources quantiques et comme interprète sémantique des données privées.

Méthodologie
Les auteurs proposent un protocole de MP-QTPSI (Multi-Party Quantum TPSI) qui découple le rôle de mesure du rôle d'interprétation sémantique. Le protocole implique $n$ participants ( $P_1, \dots, P_n$ ) et une TP semi-honnête.

Phase Quantique (Construction de l'Étiquette Cachée) :
- Configuration : Les participants établissent une clé maîtresse via un Accord de Clé de Conférence Quantique (QCKA) sans TP pour dériver une clé de masquage de position $k$ , un vecteur de basculement d'étiquette caché $\mathbf{b}$ et des parts de rotation $\Delta_i$ . La TP et chaque participant établissent des clés par paires pour les masques de rotation $T_i$ .
- Encodage : Les participants augmentent leurs ensembles avec des ensembles d'ancres positifs et appliquent une application de masquage de position $x \mapsto kx \mod M$ . Ils encodent leurs ensembles dans des vecteurs indicateurs $Y_i$ .
- Interaction : La TP prépare des séquences de photons uniques et applique une rotation aveugle initiale. Les séquences traversent les participants séquentiellement. Chaque participant $P_i$ applique une rotation basée sur ses données ($0$ ou $\pi/n$ ), son masque par paire $T_i$ , et sa part de rotation $\Delta_i$ .
- Mesure : La TP supprime ses masques connus et mesure les séquences. En raison des rotations agrégées corrélées, les résultats de mesure sont déterministes uniquement pour les positions où tous les participants détiennent l'élément (intersection) ou aucun ne le détient (non-intersection), mais la signification sémantique de ces résultats (quel label correspond à l'« intersection ») est masquée par le vecteur de basculement caché $\mathbf{b}$ . La TP obtient des vecteurs indicateurs d'étiquettes cachées $z_S$ (identiques) et $z_O$ (opposés) mais ne peut les interpréter sans les informations côté participant.
Phase Classique (Test de Cardinalité) :
- Test de Cohérence Masqué : Le protocole convertit les mesures cachées en un test de cohérence d'étiquette masqué. Les participants détiennent des labels de référence $\rho$ et des masques de sélection pour les domaines réels et d'ancres.
- Évaluation Linéaire Oblivieuse (OLE) : La TP et les participants utilisent l'OIP (Produit Intérieur Oblivieux) basé sur l'OLE pour calculer les parts additives des comptes de cohérence (incohérences $d_{\mathcal{R}}$ et $d_{\mathcal{A}}$ ) sans révéler les vecteurs les uns aux autres.
- Décision de Seuil : Un circuit garbé léger évalue le prédicat $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$ . Celui-ci ne produit que le résultat booléen, garantissant que la cardinalité exacte n'est jamais révélée à la TP.
- Reconstruction : Si $\text{flag}=1$ , la TP diffuse les vecteurs cachés, et les participants utilisent leurs labels de référence et l'inverse de la clé $k^{-1}$ pour reconstruire l'intersection.

Contributions Clés

Test de Cardinalité Explicite : Le protocole est le premier TPSI quantique à respecter strictement le paradigme de test de cardinalité, en ne produisant que le prédicat de seuil $\mathbb{1}[|\bigcap X_i| \ge \tau]$ sans révéler la cardinalité exacte à la TP.
Conception Quantique à Étiquette Cachée : En utilisant les rotations agrégées corrélées côté participant et un vecteur de basculement caché, le protocole garantit que les résultats de mesure de la TP sont sémantiquement aveugles. La TP agit uniquement comme une partie de mesure, incapable de mapper les résultats à des éléments d'ensemble spécifiques ou à la cardinalité.
Sécurité contre la Collusion et la TP : Le protocole prouve sa sécurité contre les espions extérieurs (via des photons de leurre), la TP semi-honnête (qui apprend ni les ensembles ni la cardinalité) et les participants colludants (qui ne peuvent inférer les ensembles des autres grâce aux masques par paires et aux rotations aveugles inconnues).
Détection de Manipulation : L'inclusion d'ensembles d'ancres cachés permet un contrôle de cohérence ( $d_{\mathcal{A}}=0$ ) qui peut détecter si la TP modifie les vecteurs de mesure rapportés.

Résultats

Correction : Les preuves théoriques démontrent que le protocole encode correctement le motif d'intersection et que le sous-protocole classique évalue correctement la condition de seuil.
Simulation : Les auteurs ont implémenté la phase quantique sur la plateforme IBM Qiskit en utilisant un modèle réduit ( $n=3$ , taille du domaine 8). La simulation incluait des erreurs de dépolarisation, de relaxation de phase et de lecture. Les résultats de la simulation bruitée (Tableau 3) correspondaient étroitement aux probabilités théoriques, passant avec succès le test d'ancre et le test de seuil pour reconstruire l'intersection correcte $\{1, 3\}$ .
Complexité : Le coût de communication quantique est de $\mathcal{O}(n(\ell M + \delta))$ , et le coût de calcul est similaire, où $M$ est la taille augmentée du domaine, $\ell$ est le nombre de répétitions, et $\delta$ est le nombre de leurres.

Signification et Revendications
Le papier affirme que sa principale signification réside dans la résolution du « fossé de fonctionnalité » des protocoles de TPSI quantiques existants. En séparant le rôle de mesure quantique du rôle d'interprétation sémantique, le protocole proposé s'aligne sur la définition classique idéale du TPSI où la décision de seuil est un prédicat direct plutôt qu'une étape de post-traitement sur des statistiques révélées. Les auteurs soulignent que leur construction repose uniquement sur des rotations de photons uniques et une étape de post-traitement classique légère (OLE et circuits garbés), évitant la complexité du Chiffrement Homomorphe Quantique (QHE) utilisé dans d'autres travaux récents. Ils affirment que cette conception offre une approche plus respectueuse de la vie privée pour les contextes multi-parties où la TP ne doit pas apprendre la taille de l'intersection. Le papier conclut en notant que le cadre est flexible et pourrait potentiellement être étendu à des seuils pondérés ou basés sur des ratios, bien qu'il opère actuellement sous un modèle de TP semi-honnête.