💻 computer science

Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

Cet article présente un protocole de preuve à divulgation nulle de connaissance relativiste asymétrique, efficace et vérifié expérimentalement, qui atteint une sécurité inconditionnelle contre les attaques quantiques en exploitant la relativité spéciale et la non-localité quantique, surmontant ainsi la complexité de ronde impraticable des approches symétriques précédentes.

Auteurs originaux : Chen-Xun Weng, Ming-Yang Li, Nai-Rui Xu, Yanglin Hu, Ian George, Jiawei Wu, Shengjun Wu, Hua-Lei Yin, Zeng-Bing Chen

Publié 2026-06-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Chen-Xun Weng, Ming-Yang Li, Nai-Rui Xu, Yanglin Hu, Ian George, Jiawei Wu, Shengjun Wu, Hua-Lei Yin, Zeng-Bing Chen

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 révéler

Imaginez que vous possédez la carte secrète d'un trésor et que vous voulez convaincre un garde sceptique que vous possédez réellement cette carte. Vous ne voulez pas lui montrer la carte (car il pourrait vous la voler), et vous ne voulez pas non plus lui dire où se trouve le trésor. Vous voulez simplement prouver : « Je connais le chemin. »

Dans le monde numérique, on appelle cela une Preuve à Divulgation Nulle de Connaissance (Zero-Knowledge Proof ou ZKP). C'est le tour de magie qui vous permet de prouver que vous êtes bien qui vous prétendez être, ou que vous avez assez d'argent pour une transaction, sans révéler votre mot de passe ou votre solde bancaire.

Le problème : Le monstre quantique

Pendant des décennies, ces tours de magie numériques reposaient sur des énigmes mathématiques difficiles à résoudre pour les humains, mais faciles pour les ordinateurs. Cependant, les scientifiques construisent des ordinateurs quantiques qui sont comme des monstres super-rapides. Ces monstons peuvent résoudre ces anciennes énigmes mathématiques presque instantanément, brisant ainsi la sécurité de nos verrous numériques actuels.

Nous avons besoin d'un nouveau type de verrou qui ne repose pas sur des énigmes mathématiques, mais sur les lois de la physique.

La solution : Le verrou de la « vitesse de la lumière »

Ce papier présente un nouveau type de preuve appelé Preuve à Divulgation Nulle de Connaissance Relativiste. Au lieu de s'appuyer sur des mathématiques difficiles, elle s'appuie sur la vitesse de la lumière.

L'analogie : Le dragon à deux têtes
Imaginez que vous avez un dragon avec deux têtes (appelons-les Tête A et Tête B). Vous voulez prouver à un juge que le dragon est réel, mais vous ne pouvez pas laisser les têtes communiquer entre elles.

Le juge se tient loin de la Tête A.
Un autre juge se tient loin de la Tête B.
La distance est si grande que même un rayon lumineux (la chose la plus rapide de l'univers) ne peut pas voyager de la Tête A à la Tête B dans le temps nécessaire pour répondre à une question.

Parce que la Tête A et la Tête B ne peuvent pas communiquer assez vite pour coordonner un mensonge, elles sont forcées de dire la vérité. Si elles tentent de tricher, les lois de la physique (plus précisément, le fait que rien ne voyage plus vite que la lumière) les démasquent.

Ce que cette équipe a accompli

Les chercheurs ont construit une version fonctionnelle de cette preuve de la « vitesse de la lumière ». Voici comment ils l'ont améliorée :

L'ancienne méthode était trop lente : Les tentatives précédentes de cette preuve du « dragon à deux têtes » étaient comme essayer de résoudre un labyrinthe géant en parcourant chaque chemin un par un. Si la carte (le graphe) était grande, il aurait fallu des milliers d'années pour terminer la preuve. C'était théoriquement possible, mais pratiquement inutile.
La nouvelle méthode est rapide : L'équipe a conçu une version asymétrique plus intelligente. Pensez à cela comme si une tête du dragon faisait tout le gros du travail pendant que l'autre tête se contentait de surveiller.
- Le résultat : Ils ont réduit le temps nécessaire de « milliers d'années » à 0,22 seconde.
- Le coût : Ils ont utilisé un peu plus de « hasard » (comme mélanger un jeu de cartes plus de fois), mais la quantité totale de données utilisées était toujours assez petite pour tenir sur un disque dur moderne (environ 430 Mo).

L'expérience

Pour prouver que cela fonctionne dans le monde réel, ils ont mis en place une expérience à l'Université de Nanjing :

Ils ont placé deux ordinateurs (les « têtes ») dans deux bâtiments différents espacés de 300 mètres.
Ils ont utilisé des lasers haute vitesse et des horloges GPS pour s'assurer que les ordinateurs ne pouvaient pas communiquer plus vite que la lumière.
Ils ont demandé aux ordinateurs de prouver qu'ils savaient comment colorier une carte complexe avec seulement trois couleurs (une énigme mathématique classique) sans montrer les couleurs.
Le résultat : Les ordinateurs ont terminé l'intégralité de la preuve en 0,22 seconde.

Pourquoi c'est important

Le papier affirme qu'il s'agit d'une étape majeure car :

C'est compatible avec le quantique (Quantum-Safe) : Même si un ordinateur quantique tente de briser le code, il ne peut pas tricher car il ne peut pas briser les lois de la physique (la vitesse de la lumière).
C'est pratique : Contrairement aux versions précédentes qui étaient trop lentes pour être utilisées, celle-ci est assez rapide pour un usage réel, comme sécuriser les services bancaires en ligne ou le vote.
C'est inconditionnel : Cela ne repose pas sur « nous pensons que ce calcul est difficile », mais sur « nous savons que la lumière a une limite de vitesse ».

Résumé

Les chercheurs ont pris une idée théorique — utiliser la vitesse de la lumière pour empêcher les menteurs — et ont construit une machine fonctionnelle qui réalise cela en une fraction de seconde. Ils ont résolu le problème de la lenteur en faisant en sorte qu'un côté du système effectue plus de travail, ce qui a permis au processus entier d'être incroyablement rapide et sécurisé contre les futurs ordinateurs quantiques.

Résumé Technique : Preuves à Divulgation Nulle Relativistes Asymétriques Expérimentales avec Sécurité Inconditionnelle

Énoncé du Problème

Les preuves à divulgation nulle (ZKP - Zero-Knowledge Proofs) sont cruciales pour établir la confiance et la confidentialité dans les économies numériques, telles que les cryptomonnaies et les contrats intelligents. Cependant, les protocoles de ZKP classiques reposent sur des hypothèses computationnelles (par exemple, l'existence de fonctions à sens unique), ce qui les rend vulnérables aux futures attaques quantiques. Bien que les ZKP quantiques offrent une alternative potentielle, elles font face à des obstacles de mise en œuvre importants, notamment le théorème de non-clonage qui complique le renvoi (rewinding) quantique, ainsi que l'impossibilité de l'engagement de bits quantiques avec une sécurité inconditionnelle.

Les RZKP (Relativistic Zero-Knowledge Proofs) sont apparues comme une solution en remplaçant les hypothèses computationnelles par les principes de la relativité restreinte (spécifiquement le principe de non-signalisation). Une percée récente a démontré une RZKP symétrique pour le problème de la coloration ternaire de graphe. Cependant, ce protocole symétrique souffre d'inefficiences prohibitives lorsqu'il s'agit de garantir la solidité quantique (sécurité contre des prouveurs partageant de l'intrication quantique). Pour atteindre cette solidité quantique, le protocole symétrique nécessite une complexité de tours de $O(|E|^4)$ (où $|E|$ est le nombre d'arêtes), conduisant à des temps d'exécution irréalistes et à des coûts de hasard massifs pour des graphes de taille réaliste.

Méthodologie

Les auteurs proposent et implémentent expérimentalement un protocole RZKP GMW asymétrique relativiste conçu pour surmonter les limitations d'efficacité des approches symétriques précédentes tout en maintenant une sécurité inconditionnelle contre des prouveurs corrélés quantiquement.

Conception du Protocole

Le protocole implique deux paires prouveur-vérificateur spatialement séparées ( $P_1-V_1$ et $P_2-V_2$ ) et opère sur $m$ tours interactifs pour prouver qu'un graphe $G(V, E)$ est colorable avec trois couleurs sans révéler la coloration.

Préparation : Les prouveurs $P_1$ et $P_2$ partagent une permutation de couleurs aléatoire $\pi$ et un ensemble de valeurs aléatoires $B = \{b_k\}$ .
Phase de Requête : Le vérificateur $V_1$ envoie des requêtes aléatoires $X = \{x_k\}$ à $P_1$ .
Phase d'Engagement : $P_1$ calcule des engagements $A = \{a_k\}$ où $a_k = x_k \cdot y_k - b_k$ (avec $y_k$ étant la couleur) et les envoie à $V_1$ .
Phase de Défi : Le vérificateur $V_2$ sélectionne une arête aléatoire $C = \{i, j\}$ et l'envoie à $P_2$ .
Phase de Révélation : $P_2$ révèle les couleurs $Y(C)$ et les valeurs correspondantes $B(C)$ à $V_2$ .
Phase de Vérification : Les vérificateurs vérifient les contraintes relativistes (assurant l'absence de signalisation entre $P_1$ et $P_2 en vérifiant les délais temporels$ |t_1 - t_4| < \tau$ et $|t_2 - t_3| < \tau$ , où $\tau = d/c$ ) et la cohérence logique (les couleurs sont distinctes et correspondent aux engagements).

Analyse Théorique

Les auteurs abordent le défi de la solidité quantique. Contrairement aux protocoles classiques où l'engagement de bits est fortement contraignant, les engagements de bits relativistes ne garantissent que la "somme-contrainte" (sum-binding). Les auteurs démontrent que la probabilité que des prouveurs quantiques malveillants réussissent à tricher sur une arête invalide est bornée supérieurement par la valeur quantique d'un jeu CHSH $_{Q(2)}$ non local. En reliant l'erreur de solidité du protocole à ce jeu, ils dérivent une borne supérieure rigoureuse pour l'erreur de solidité quantique $\delta$ .

Implémentation Expérimentale

L'équipe a implémenté une expérience de preuve de concept utilisant :

Matériel : Des circuits logiques programmables (FPGA) pour un traitement à faible latence et des serveurs de synchronisation temporelle GPS de haute précision (avec horloges atomiques) pour le cadencement.
Configuration : Deux paires prouveur-vérificateur séparées de 300 mètres (correspondant à une séparation temporelle $\tau = 1000$ ns).
Graphe : Un graphe trois-colorable avec $|V| = 588$ sommets et $|E| = 1097$ arêtes.
Exécution : L'expérience a complété tous les tours interactifs requis en environ 0,22 seconde.

Contributions Clés

Protocole Asymétrique Efficace : Les auteurs ont conçu un ZKP GMW relativiste asymétrique qui réduit la complexité de tours de $O(|E|^4)$ (dans les précédents protocoles symétriques à solidité quantique) à $O(|E|)$ . Ceci est réalisé en utilisant des engagements de bits relativistes à deux prouveurs au sein du cadre GMW, permettant que la preuve et les vérifications de cohérence se produisent simultanément en un seul tour.
Preuve de Solidité Quantique : Ils ont fourni une preuve rigoureuse de solidité quantique en reliant la probabilité de triche des prouveurs intriqués au jeu non local CHSH $_{Q(2)}$ , établissant une borne supérieure sur l'erreur de solidité sans dépendre d'hypothèses computationnelles.
Réalisation Expérimentale : Ils ont exécuté avec succès le protocole sur une séparation de 300 mètres, démontrant que le temps d'exécution et le coût de hasard requis sont réalisables pour un déploiement réel.

Résultats

Complexité de Tours : Le protocole nécessite $m = 2k|E|$ tours pour atteindre une erreur de solidité de $e^{-k}$ . Pour les paramètres expérimentaux ( $|E|=1097, k=100$ ), cela a résulté en environ $2,2 \times 10^5$ tours.
Temps d'Exécution : L'expérience complète a duré 0,22 seconde. En revanche, le protocole symétrique quantique précédent [23] aurait nécessité environ $6,72 \times 10^4$ années pour atteindre le même niveau de sécurité avec le même graphe.
Coût de Hasard : Le coût total de hasard pour l'expérience était de 430,81 Mo. Le protocole symétrique [23] aurait nécessité environ $5,92 \times 10^9$ Go (5,92 exaoctets) pour la même tâche.
Sécurité : Les différences de temps $|t_1 - t_4|$ et $|t_2 - t_3|$ ont été mesurées de manière constante en dessous du seuil de 1000 ns, satisfaisant les contraintes de non-signalisation relativistes même en tenant compte des erreurs de synchronisation GPS.

Signification et Revendications

L'article affirme que ce travail illustre le potentiel puissant de l'intégration de la relativité restreinte avec la théorie quantique pour créer des systèmes cryptographiques sans confiance (trustless) qui sont sécurisés contre les attaques quantiques sans dépendre d'hypothèses de dureté computationnelle.

Les principales revendications concernant la signification incluent :

Faisabilité Pratique : La réduction de la complexité de tours de $O(|E|^4)$ à $O(|E|)$ transforme les RZKP de constructions théoriques en technologies déployables pour des scénarios réels impliquant des graphes de taille raisonnable.
Sécurité Inconditionnelle : Le protocole offre une solidité quantique et des propriétés de divulgation nulle basées uniquement sur le principe de non-signalisation, ce qui le rend robuste face aux futures avancées de l'informatique quantique.
Potentiel de Scalabilité : Bien que la nature asymétrique impose une charge de calcul plus élevée à une paire prouveur-vérificateur ( $V_1-P_1$ ), les auteurs soutiennent que ce compromis est nécessaire pour obtenir des temps d'exécution réalisables. Ils suggèrent que le protocole pourrait être implémenté sur des appareils du quotidien comme les smartphones.
Applications Futures : Les auteurs soulignent des applications potentielles dans des domaines sensibles à la confidentialité tels que les blockchains, les contrats intelligents, le vote électronique anonyme et les enchères en ligne. Ils notent également le potentiel d'étendre ce cadre aux Preuves de Connaissance à Divulgation Nulle (ZKPoK) pour la vérification d'identité.

Les auteurs restent modestes quant aux défis de scalabilité, reconnaissant que le déploiement pratique dans les réseaux de fibre optique fait toujours face à des obstacles tels que la vérification de la position précise des prouveurs et la gestion des charges de calcul, qu'ils identifient comme des problèmes ouverts pour la recherche future.