A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes

Cette note établit l'équivalence entre les codes à connaissance nulle et les codes quantiques CSS, permettant ainsi de construire des codes localement testables à connaissance nulle asymptotiquement optimaux.

L'essentiel

Voici une explication de ce papier de recherche, traduite en langage simple et imagé pour le grand public.

🕵️‍♂️ Le Secret de la Double Identité : Quand le "Zéro Connaissance" rencontre le "Quantique"

Imaginez que vous avez deux mondes qui semblent très différents l'un de l'autre :

1. Le monde du secret parfait (Zéro Connaissance) : C'est comme un coffre-fort où, si vous volez quelques petits morceaux de la serrure, vous ne pouvez absolument rien deviner sur ce qu'il y a à l'intérieur. C'est la base de la cryptographie moderne.
2. Le monde de l'ordinateur quantique (Codes CSS) : C'est un système de protection pour les ordinateurs du futur, conçu pour réparer les erreurs causées par le bruit ou les interférences, un peu comme un filet de sécurité pour un acrobate.

Ce papier, écrit par Noga Ron-Zewi et Mor Weiss, révèle une surprise incroyable : ces deux mondes sont en fait la même chose, juste habillés différemment.

---

🧩 L'Analogie du Puzzle et du Miroir

Pour comprendre leur découverte, imaginons un grand puzzle géant.

1. Le Code "Zéro Connaissance" (Le Secret)

Imaginez que vous voulez envoyer un message secret (un dessin) à un ami. Pour le protéger, vous ne lui envoyez pas le dessin tel quel. Vous le transformez en un puzzle géant avec des pièces supplémentaires (du "bruit" aléatoire).

• La règle d'or : Si votre ennemi vole quelques pièces (disons 10 pièces au hasard) de ce puzzle, il ne doit absolument pas pouvoir deviner à quoi ressemble le dessin original. Même s'il a toutes les pièces volées, le dessin pourrait être n'importe quoi. C'est ce qu'on appelle le "Zéro Connaissance".

2. Le Code CSS Quantique (La Protection)

Maintenant, imaginez un ordinateur quantique qui a besoin de protéger ses données. Il utilise deux types de filets de sécurité (appelés $C_X$ et $C_Z$).

• Ces filets sont conçus de manière très précise : ils sont "orthogonaux", ce qui signifie qu'ils ne se touchent jamais de manière confuse.
• Si une erreur survient (un morceau du filet se rompt), le système doit pouvoir le réparer. Pour cela, il faut que les "trous" dans le filet soient assez grands pour être détectés, mais pas trop petits pour ne pas être confondus avec le message lui-même.

3. La Révélation : C'est le même objet !

Les auteurs disent : "Attendez une minute ! Si vous prenez un code Zéro Connaissance et que vous le regardez sous un angle différent (comme dans un miroir), vous obtenez exactement un code CSS quantique."

• La propriété "Zéro Connaissance" (ne rien apprendre en regardant quelques pièces) correspond exactement à la taille des trous dans le deuxième filet de sécurité quantique.
• La capacité de "réparer les erreurs" (décoder le message) correspond à la taille des trous dans le premier filet.

C'est comme si vous aviez une pièce de monnaie. D'un côté, il y a écrit "Secret". De l'autre, il y a écrit "Réparation Quantique". Ce sont deux faces de la même pièce.

---

🚀 Pourquoi est-ce une si bonne nouvelle ? (L'Application)

Pourquoi s'embêter à faire ce lien ? Parce que cela permet de voler des idées d'un domaine pour les appliquer à l'autre !

Le problème :
Les chercheurs en cryptographie (Zéro Connaissance) cherchent depuis longtemps à créer des codes qui sont à la fois :

1. Très efficaces (ils ne gaspillent pas trop d'espace).
2. Très secrets (on ne peut rien deviner même en regardant beaucoup de pièces).
3. Vérifiables rapidement (on peut tester si le message est valide sans tout lire, comme vérifier un code-barres avec un scanner).

Ces codes "parfaits" sont très difficiles à construire manuellement.

La solution magique :
Les chercheurs en informatique quantique ont récemment réussi à construire des "filets de sécurité" (codes CSS) qui sont parfaits sur ces trois points (grâce à des travaux récents de 2024-2025).

Grâce à la découverte de Ron-Zewi et Weiss, ils ont dit : "Super ! On prend ces codes quantiques parfaits, on les retourne (grâce à notre équivalence), et hop ! On obtient instantanément des codes Zéro Connaissance parfaits pour la cryptographie classique."

🎯 En résumé

Ce papier est une petite note qui dit : "Ne cherchez plus à construire ces codes complexes de zéro. Utilisez ce que les physiciens quantiques ont déjà inventé !"

• Avant : On essayait de construire des coffres-forts secrets à la main, c'était lent et difficile.
• Maintenant : On utilise les filets de sécurité des ordinateurs quantiques, on les retourne, et on obtient des coffres-forts secrets ultra-performants, prêts à l'emploi.

C'est un exemple magnifique de comment deux domaines scientifiques qui semblaient ne jamais se rencontrer (la cryptographie classique et l'informatique quantique) peuvent s'entraider pour résoudre des problèmes impossibles.

Résumé technique

Voici un résumé technique détaillé de l'article « A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes » en français.

1. Problématique et Contexte

L'article s'attaque à la relation fondamentale entre deux familles de codes correcteurs d'erreurs, initialement développées dans des contextes distincts :

• Les codes à connaissance nulle (Zero-Knowledge ou ZK) : Introduits par Decatur, Goldreich et Ron, ces codes sont utilisés en cryptographie (partage de secrets, calcul multipartite sécurisé, preuves interactives). Leur propriété clé est qu'un petit nombre de symboles du mot de code ne révèle aucune information sur le message codé.
• Les codes CSS quantiques : Introduits par Calderbank, Shor et Steane, ces codes sont conçus pour la correction d'erreurs dans les ordinateurs quantiques et jouent un rôle central en théorie de la complexité quantique (notamment pour la conjecture PCP quantique).

Bien que ces deux familles aient des applications différentes, les auteurs posent l'hypothèse qu'elles sont structurellement équivalentes. Le défi consiste à formaliser cette équivalence et à l'exploiter pour transférer les avancées récentes dans un domaine vers l'autre, en particulier pour obtenir des constructions explicites de codes ZK aux paramètres optimaux.

2. Méthodologie

Les auteurs établissent une correspondance bijective (une équivalence) entre les codes ZK linéaires parfaits et les codes CSS quantiques. La méthodologie repose sur les étapes suivantes :

1. Définitions formelles :

   • Un code ZK est défini par une application de codage randomisée linéaire $\text{Enc} : \mathbb{F}^{k'} \to C \subseteq \mathbb{F}^n$. Il est dit $t$-ZK si la distribution des $t$ symboles interrogés est identique pour tout couple de messages. Il doit également être décodable (résistant aux erreurs).
   • Un code CSS est une paire de codes linéaires $(C_X, C_Z)$ tels que leurs duaux $C_X^\perp$ et $C_Z^\perp$ sont orthogonaux. La distance du code est déterminée par le poids minimal des vecteurs dans $C_X \setminus C_Z^\perp$ et $C_Z \setminus C_X^\perp$.

2. Transformation directe (Théorème 3.1) :

   • À partir d'un code ZK défini par une matrice génératrice $G$ (avec des dimensions de message $k'$ et de randomisation $k-k'$), on construit un code CSS.
   • On pose $C_X = C$ (le code linéaire sous-jacent).
   • On définit $C_Z$ comme le sous-espace orthogonal à l'espace engendré par les $k-k'$ dernières colonnes de $G$.
   • Les auteurs démontrent que la propriété de détectabilité des erreurs (décodabilité) du code ZK correspond à la distance $d_X$ du code CSS, et que la propriété ZK correspond à la distance $d_Z$.

3. Transformation inverse (Corollaire 3.2) :

   • À partir d'un code CSS $(C_X, C_Z)$, on reconstruit un code ZK en utilisant $C_X$ comme code de base et en choisissant une matrice génératrice dont les dernières colonnes forment une base de $C_Z^\perp$.
   • Cela permet de traduire les garanties de distance du code CSS en garanties de sécurité ZK et de correction d'erreurs pour le code classique.

4. Preuve technique :

   • La preuve repose sur une caractérisation alternative des codes ZK (Lemme 3.3) : un code est $t$-ZK si et seulement si aucune combinaison linéaire de $t$ lignes de la matrice génératrice ne produit un vecteur non nul dont les composantes correspondant aux bits de message sont nulles. Cette condition est ensuite mise en correspondance avec la définition de la distance $d_Z$ dans le cadre CSS.

3. Contributions Clés

• Équivalence théorique : La contribution principale est la démonstration rigoureuse que les codes ZK (linéaires, parfaits) et les codes CSS quantiques sont deux faces d'une même pièce. Les paramètres de sécurité ZK et de décodage d'un code correspondent exactement aux distances $d_Z$ et $d_X$ d'un code CSS associé.
• Nouvelle construction explicite : En utilisant cette équivalence, les auteurs transforment les récentes percées sur les codes quantiques LDPC (Low-Density Parity-Check) en codes ZK classiques.
• Résolution d'un problème ouvert : Ils fournissent la première famille explicite de codes ZK localement testables (ZK-LTC) qui sont asymptotiquement bons (taux et distance constants) et où le seuil ZK est linéaire en la longueur du code, tout en étant testable avec un nombre de requêtes polylogarithmique.

4. Résultats Principaux

Le résultat le plus significatif est présenté dans le Corollaire 4.3 :

• Existence de ZK-LTCs explicites : Il existe une famille infinie explicite de codes linéaires $C_n \subseteq \mathbb{F}^n$ qui sont :
  1. Asymptotiquement bons : Ils ont un taux constant et une distance linéaire $\Omega(n)$.
  2. Localement testables : Ils peuvent être testés avec un nombre de requêtes $O(\text{poly}(\log n))$.
  3. À connaissance nulle : Le seuil de connaissance nulle est $\Omega(n)$ (linéaire), ce qui signifie qu'on peut révéler une fraction constante du mot de code sans rien apprendre du message.
  4. Déchiffrables : Ils permettent de corriger un nombre linéaire d'erreurs.

Ces codes sont construits en prenant les codes CSS quantiques localement testables récents (de [DLV24, KP25, WLH25]) et en appliquant la transformation inverse décrite dans le Corollaire 3.2.

5. Signification et Impact

• Synergie entre Cryptographie et Calcul Quantique : L'article brise le silo entre la théorie des codes pour la cryptographie classique (ZK) et la théorie des codes pour le calcul quantique (CSS). Il montre que les avancées dans la construction de codes quantiques robustes (nécessaires pour l'informatique quantique à grande échelle) peuvent être directement réutilisées pour améliorer les protocoles cryptographiques classiques.
• Amélioration des Protocoles ZK : Les codes ZK sont des briques fondamentales pour les Preuves Vérifiables à Connaissance Nulle (ZK-PCP, ZK-IOP). L'obtention de codes ZK localement testables explicites et asymptotiquement bons est cruciale pour améliorer l'efficacité (taille de la preuve, temps de vérification) de ces protocoles.
• Ouverture de nouvelles voies de recherche : Cette équivalence suggère que d'autres constructions de codes quantiques pourraient être traduites en codes classiques avec des propriétés de sécurité intéressantes, et vice-versa. Elle offre un cadre unifié pour l'analyse des paramètres de ces codes.

En résumé, cet article établit un pont théorique solide qui permet d'importer les constructions de codes quantiques de pointe vers le domaine de la cryptographie classique, aboutissant à la première construction explicite de codes ZK localement testables aux paramètres optimaux.