⚛️ quantum physics

MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)

Cet article généralise le paradigme du MPC-in-the-head au cadre quantique, permettant la construction d'arguments de connaissance nulle à trois tours pour NP et QMA dans le modèle de chaîne de référence commune qui restent sécurisés contre les attaques de superposition basées sur l'hypothèse standard Learning With Errors (LWE).

Auteurs originaux : Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

Publié 2026-07-08

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Andrea Coladangelo, Ruta Jawale, Dakshita Khurana, Giulio Malavolta, Hendrik Waldner

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

La vue d'ensemble : Prouver que vous connaissez un secret sans le montrer

Imaginez que vous avez un mot de passe secret (un « témoin » ou witness) qui prouve que vous êtes autorisé à entrer dans un bâtiment sécurisé. Vous voulez convaincre un garde (le « vérificateur ») que vous connaissez le mot de passe sans pour autant lui dire lequel c'est. C'est ce qu'on appelle une Preuve à Divulgation Nulle de Connaissance (Zero-Knowledge Proof).

Dans le monde classique (le monde des ordinateurs ordinaires), il existe un tour célèbre appelé « MPC-in-the-Head » pour faire cela.

L'analogie : Imaginez que vous êtes une seule personne, mais que vous prétendez être une équipe de cinq amis assis dans une pièce. Vous divisez votre mot de passe secret en cinq morceaux (des parts) et vous donnez une part à chaque « ami » à l'intérieur de votre tête.
Le jeu : Vous menez une conversation entre ces cinq amis pour prouver que le mot de passe fonctionne. Ensuite, le garde demande à voir les notes de seulement deux des amis.
Le résultat : Si les notes concordent et sont cohérentes, le garde est convaincu que toute l'équipe (et donc vous) connaît le mot de passe. Mais comme le garde n'a vu les notes de deux amis, il ne peut pas découvrir le mot de passe complet.

Le nouveau problème : Le voleur de « Superposition »

Cet article s'attaque à un nouveau problème effrayant : Et si le garde était un ordinateur quantique ?

Dans le monde quantique, une « superposition » est comme être à deux endroits à la fois. Un adversaire quantique (le méchant) ne demande pas seulement à voir les notes de l'ami A ou de l'ami B. Il peut demander à voir une superposition des deux en même temps.

La métaphore : Imaginez que le garde ne se contente pas de regarder le papier ; il place le papier dans une boîte magique qui lui permet de jeter un coup d'œil à toutes les combinaisons possibles de notes d'amis simultanément.
Le risque : Dans les anciens tours, si vous ne montriez que deux amis, le secret était en sécurité. Mais si le garde peut jeter un œil à une « superposition » des notes, il pourrait être capable de reconstruire mathématiquement tout le mot de passe, brisant ainsi la sécurité.

Les auteurs se demandent : Pouvons-nous construire une preuve à divulgation nulle de connaissance qui reste sûre même si le garde utilise ce super-pouvoir de « superposition » ?

La solution : « MPC in the Quantum Head »

Les auteurs disent oui, et ils le font en améliorant le tour « MPC-in-the-Head » pour le monde quantique. Ils appellent leur nouvelle méthode « MPC in the Quantum Head ».

Voici comment ils résolvent les deux principaux défis :

1. Pour les secrets classiques (Problèmes NP)

L'ancien problème : Les tentatives précédentes pour rendre cela sûr face au quantique reposaient sur un type spécial de « verrou magique » (un schéma d'engagement ou commitment scheme) qui était parfaitement caché. Mais personne ne sait comment construire ces verrous en utilisant des hypothèses mathématiques standards.
Le nouveau tour : Les auteurs utilisent un autre type de verrou appelé « Engagement à double mode » (Dual-Mode Commitment).
- L'analogie : Imaginez un coffre-fort qui possède deux clés.
  - Clé A (Liaison/Binding) : Le coffre est verrouillé hermétiquement. Une fois que vous avez mis une note à l'intérieur, vous ne pouvez plus la changer. Mais si vous possédez un ordinateur surpuissant, vous pourriez être capable de deviner la note.
  - Clé B (Dissimulation/Hiding) : Le coffre est si opaque que même un ordinateur surpuissant ne peut pas voir ce qu'il y a à l'intérieur. Mais, si vous possédez une « porte dérobée » spéciale (que le prouveur possède), vous pouvez l'ouvrir pour révéler tout ce que vous voulez.
- Comment ça marche : Le prouveur utilise le mode « Dissimulation » pour envoyer les notes. Comme les notes sont cachées, le garde quantique ne peut pas apprendre le secret, même s'il les regarde en superposition. Les auteurs prouvent que même avec ce verrou légèrement plus faible, la mathématique tient bon.

2. Pour les secrets quantiques (Problèmes QMA)

C'est la partie la plus difficile. Et si le secret lui-même était un état quantique (comme un nuage de probabilité délicat et invisible) plutôt qu'un simple mot de passe ?

Le défi : Dans la version classique, les « amis » s'échangent des notes. Dans la version quantique, les « amis » s'échangent des particules quantiques (des qubits). On ne peut pas simplement « écrire » les notes d'une particule quantique sans détruire le secret. Il n'y a pas de « transcription » à vérifier.
Le nouveau tour : Les auteurs utilisent une technique appelée « Réduction Circuit-to-Hamiltonian ».
- L'analogie : Imaginez que la conversation quantique entre les amis est un film. Habituellement, vous ne pouvez pas vérifier le film sans le regarder en entier.
- Au lieu de cela, ils transforment le film en une sculpture figée (un Hamiltonien). Cette sculpture a une forme spécifique. Si les amis ont joué correctement, la sculpture a une « énergie » très basse (elle est lisse et parfaite). S'ils ont triché, la sculpture est bosselée et possède une énergie élevée.
- La vérification : Le garde ne demande pas à voir tout le film. Il se contente de piquer la sculpture à quelques endroits aléatoires pour mesurer l'énergie.
  - Si l'énergie est basse, le jeu a été joué correctement.
  - Comme la sculpture est composée de beaucoup de petites parties, piquer quelques endroits ne révèle pas tout le film (le secret).
Le « Quantum Head » : Le prouveur divise le secret quantique entre les amis, le chiffre, et crée cette « sculpture figée » de la conversation. Le garde vérifie l'énergie de la sculpture.

Pourquoi cela importe (selon l'article)

L'article affirme avoir construit deux outils spécifiques :

Une preuve pour les secrets classiques (NP) : Elle repose sur un problème mathématique standard appelé LWE (Learning With Errors), qui est considéré comme difficile même pour les ordinateurs quantiques.
Une preuve pour les secrets quantiques (QMA) : C'est une avancée majeure. C'est la première fois qu'une preuve à divulgation nulle de connaissance pour des problèmes quantiques est construite de manière à être sûre contre ces attaques de « superposition », également basée sur l'hypothèse LWE.

Résumé

L'article prend un tour classique pour prouver des secrets (« MPC-in-the-Head »), l'améliore pour gérer la mécanique quantique, et résout le problème des « attaques par superposition ». Ils y parviennent en :

Utilisant des verrous spéciaux à « double mode » qui sont difficiles à craquer, même par des ordinateurs quantiques.
Transformant les conversations quantiques en « sculptures figées » (Hamiltoniens) qui peuvent être vérifiées sans révéler le secret.

Cela garantit que même si un futur ordinateur quantique tente de jeter un œil à une preuve dans une « superposition » de toutes les possibilités, le secret reste en sécurité.

Résumé Technique : MPC dans la Tête Quantique (Preuve à Divulgation Nulle Sécurisée en Superposition)

Énoncé du Problème

L'article traite de la construction de protocoles de Preuve à Divulgation Nulle (Zero-Knowledge - ZK) qui restent sécurisés même lorsqu'un vérificateur malveillant peut émettre des défis et recevoir des réponses en superposition quantique. Cette « sécurité en superposition » est un renforcement critique de la sécurité classique, motivé par des scénaux où des adversaires quantiques pourraient interagir avec des dispositifs cryptographiques classiques ou là où des primitives classiques sont intégrées dans des protocoles quantiques plus larges.

Bien que Damgård et al. [19] aient été les pionniers de cette notion pour NP, leur construction reposait sur des engagements à double mode parfaitement cachés et inconditionnellement liants, une primitive dont l'existence n'est pas connue sous les hypothèses cryptographiques standards. De plus, leurs techniques ne se sont pas naturellement étendues à QMA (Quantum Merlin-Arthur), l'analogue quantique de NP, en raison de la difficulté fondamentale de vérifier des calculs quantiques sans révéler le témoin (witness) quantique.

Les alternatives existantes, telles que les preuves de Preuve à Divulgation Nulle Non-Interactives (NIZK), sont soit inconnues pour QMA sous des hypothèses standards, soit reposent sur des modèles heuristiques (par exemple, les oracles aléatoires quantiques ou l'obfuscation). De plus, les NIZK sont généralement plus lourdes que les protocoles $\Sigma$ à trois tours préférés pour l'efficacité.

Méthodologie

Les auteurs proposent une généralisation du paradigme MPC-in-the-Head (MPC dans la tête) [30] au cadre quantique, nommée « MPC dans la Tête Quantique ». La méthodologie centrale implique deux constructions distinctes mais liées :

1. ZK Sécurisée en Superposition pour NP

Les auteurs revisitent le protocole de Damgård et al. [19] mais remplacent l'exigence d'engagements parfaitement cachés par des engagements à double mode (statistiquement cachés, computationnellement liants dans un mode ; parfaitement liants, computationnellement cachés dans l'autre).

Technique : La stratégie de preuve utilise un argument hybride. Dans le monde réel, les engagements portent sur les vues de l'MPC. Dans un hybride, les engagements sont basculés vers le mode statistiquement caché. Crucialement, les auteurs introduisent un hybride où le prouveur s'engage sur 0 (au lieu des vues honnêtes) mais peut toujours les ouvrir vers les vues honnêtes en utilisant la propriété de liaison computationnelle (qui est brisée par un simulateur non borné).
Argument de Sécurité : Une fois que les engagements portent sur 0, les vues ouvertes (un sous-ensemble de parts/shares) et les engagements non ouverts forment un schéma de partage de secret parfaitement sécurisé. Les auteurs exploitent un lemme de [19] stipulant que le partage de secret parfait reste sécurisé contre les attaques en superposition si moins de $2t$ parts sont interrogées (où $t$ est le seuil de confidentialité). Cela permet de procéder à la preuve de sécurité sans nécessiter d'engagements parfaitement cachés.

2. MPC dans la Tête Quantique pour QMA

L'extension à QMA nécessite de gérer des témoins quantiques et des circuits de vérification quantiques.

L'Obstacle : Dans le MPC-in-the-Head classique, le prouveur révèle des « vues » (transcrits) de parties. Dans le Calcul Multipartite Quantique (MPQC), les parties échangent des messages quantiques, ce qui signifie qu'il n'y a pas de transcrit classique à révéler ; une partie ne détient qu'un état quantique final.
La Solution : Les auteurs modélisent le protocole MPQC global comme un circuit quantique (remplaçant le passage de messages par des portes SWAP). Ils appliquent la réduction Circuit-to-Hamiltonian de Kitaev [34] à ce circuit.
- Le « témoin » devient l'état d'histoire (history state) du Hamiltonien, qui possède une faible énergie si et seulement si le MPQC accepte.
- Le prouveur s'engage sur cet état d'histoire (qubit par qubit) en utilisant un Masque Quantique à Usage Unique (Quantum One-Time Pad - QOTP) et s'engage sur les clés du QOTP en utilisant des engagements à double mode.
- Le vérificateur défie le prouveur d'ouvrir des qubits spécifiques correspondant aux termes locaux du Hamiltonien.
Vérification : Le vérificateur mesure les qubits ouverts pour vérifier les termes du Hamiltonien local. Si l'énergie est basse, l'état d'histoire correspond à une exécution valide.
Divulgation Nulle (Zero-Knowledge) : La propriété de ZK repose sur le fait que l'ouverture d'un sous-ensemble de qubits correspondant à un terme du Hamiltonien local ne révèle pas plus d'informations que le contrôle d'un sous-ensemble de parties dans le MPQC sous-jacent. Les auteurs utilisent un protocole MPQC parfaitement $2t$ -privé [17, 39] pour garantir que l'état d'histoire du calcul sur un témoin partagé secrètement est indiscernable d'un état d'histoire sur une entrée fictive, même sous des requêtes en superposition.

Contributions Clés

Généralisation de MPC-in-the-Head : L'article présente la première instanciation du paradigme MPC-in-the-Head pour les fonctionnalités quantiques (MPQC), créant efficacement un « Quantum MPC-in-the-Head ».
ZK Sécurisée en Superposition pour NP : Les auteurs construisent un protocole $\Sigma$ à trois tours pour NP, sécurisé contre les attaques en superposition, basé sur tout engagement à double mode post-quantique (par exemple, issu de LWE). Cela améliore [19] en supprimant la nécessité d'engagements non standards parfaitement cachés.
ZK Sécurisée en Superposition pour QMA : L'article construit la première $\Sigma$ -protocole à trois tours pour QMA sécurisée contre les attaques en superposition, basée sur l'hypothèse du Learning With Errors (LWE). Cela comble une lacune où aucune NIZK pour QMA n'existe sous des hypothèses standards.
Nouvelles Techniques de Preuve :
- Un nouvel argument hybride pour NP qui bascule les engagements vers 0 pour exploiter les propriétés du partage de secret parfait contre les attaques en superposition.
- Une technique pour QMA qui combine la réduction Circuit-to-Hamiltonian avec le MPQC et le QOTP, utilisant l'indiscernabilité des paires EPR et des masques à usage unique pour simuler le protocole en présence de requêtes en superposition.

Résultats

L'article établit les théorèmes suivants (informels) :

Théorème 1.1 : En supposant la sécurité post-quantique de LWE, il existe des protocoles $\Sigma$ à trois tours pour QMA dans le modèle de Chaîne de Référence Commune (CRS) satisfaisant la divulgation nulle contre des vérificateurs malveillants effectuant des requêtes en superposition.
Théorème 1.2 : En supposant l'existence de tout engagement à double mode post-quantique, il existe des protocoles $\Sigma$ à trois tours pour NP dans le modèle CRS satisfaisant la divulgation nulle contre des vérificateurs malveillants effectuant des requêtes en superposition.

Les protocoles atteignent une solidité statistique (statistical soundness) et une divulgation nulle computationnelle (même contre des adversaires quantiques à temps polynomial avec accès en superposition).

Signification et Revendications

Les auteurs positionnent ce travail comme une extension naturelle et nécessaire de la cryptographie à divulgation nulle dans le régime quantique.

Importance Théorique : Il résout le problème ouvert de la construction de la ZK sécurisée en superposition pour QMA sous des hypothèses standards, une tâche auparavant jugée difficile en raison de l'absence de NIZK ou de schémas d'engagement appropriés.
Pertinence Pratique : La structure à trois tours rend ces protocoles nettement plus légers que les NIZK, offrant une voie pratique pour les signatures post-quantiques et les compilateurs de calcul multipartite sécurisé (par exemple, les compilateurs de type GMW) qui doivent rester sécurisés contre les adversaires quantiques capables d'attaques en superposition.
Avancement Conceptuel : Le cadre « MPC dans la Tête Quantique » est présenté comme une technique généralisable qui pourrait être appliquée à d'autres protocoles de type commit-and-open ou cut-and-choose nécessitant une vérification partielle de calculs quantiques.

L'article note explicitement que bien que des NIZK pour QMA existent dans des modèles d'oracle ou avec des vérificateurs désignés, leur focalisation sur des protocoles à trois tours avec des hypothèses standards et une installation publique (CRS) fournit une solution plus directe et efficace pour le modèle de menace spécifique des attaques en superposition.