Résumé technique : Signatures numériques avec des ombres classiques sur des ordinateurs quantiques de l'ère NISQ

Énoncé du problème

Les schémas de signature numérique traditionnels reposent sur l'existence de fonctions à sens unique (OWF), telles que la factorisation d'entiers (RSA) ou les problèmes basés sur les réseaux (LWE). Ces hypothèses sont vulnérables aux ordinateurs quantiques tolérants aux fautes (par exemple, l'algorithme de Shor) et font l'objet de recherches continues concernant leur sécurité face à des adversaires quantiques. Bien que la mécanique quantique offre des primitives cryptographiques alternatives fondées sur des lois physiques plutôt que sur la dureté mathématique, les propositions existantes de signatures numériques quantiques (QDS) nécessitent généralement la transmission et le stockage cohérent d'états quantiques en tant que clés publiques. Cette dépendance à une communication quantique à faible bruit et à une mémoire quantique à longue durée de vie rend les propositions actuelles peu pratiques pour les dispositifs quantiques de l'ère NISQ (Noisy Intermediate-Scale Quantum).

Le défi central abordé dans ce travail est la réalisation d'un schéma de signature numérique quantique qui :

1. Ne repose pas sur les OWF ou sur l'existence de fonctions à sens unique.
2. Opère en utilisant uniquement une communication classique, éliminant ainsi le besoin de mémoire quantique ou de transmission quantique des clés publiques.
3. Est réalisable sur du matériel quantique de type NISQ (bruyant et à échelle intermédiaire).

Méthodologie

Concept central : Les ombres classiques comme clés publiques

Les auteurs proposent un schéma de signature où les clés publiques ne sont pas des états quantiques, mais des ombres classiques d'états quantiques.

• Clé secrète : Deux circuits quantiques aléatoires, $C_0$ et $C_1$.
• Clé publique : Des ombres classiques, $S(|C_0\rangle)$ et $S(|C_1\rangle)$, générées en effectuant des mesures aléatoires sur les états $|C_b\rangle = C_b|0\rangle$.
• Signature : Pour signer un bit $b$, l'expéditeur révèle la description classique du circuit $C_b$.
• Vérification : Le receveur utilise les ombres publiques et le circuit révélé pour vérifier que le circuit $C_b$ produit un état cohérent avec les ombres publiques. Cela est réalisé via un protocole de recouvrement d'ombres (shadow overlap protocol).

Hypothèse de sécurité : Non-apprentissage computationnel (CNL)

La sécurité du schéma repose sur la conjecture de Non-apprentissage Computationnel (CNL) à partir des ombres. Cette conjecture postule qu'il est computationnellement infaisable pour un adversaire d'apprendre la description d'un circuit quantique aléatoire à partir de ses ombres classiques (échantillons de longueur polynomiale de mesures aléatoires).

• Cette hypothèse est distincte et plus faible que la conjecture standard de « non-apprentissage à partir des états », car les ombres sont dérivées de copies d'états via des mesures simples.
• Les auteurs fournissent des preuves théoriques que les algorithmes d'apprentissage existants (par exemple, ceux basés sur l'inversion locale ou les arguments de cône de lumière) échouent à apprendre ces circuits sous les contraintes du protocole (apprentissage approprié, géométrie arbitraire et accès limité aux ombres uniquement).
• Les auteurs démontrent une séparation entre le temps requis pour vérifier une signature (exponentiel en $n$ mais faisable pour le vérificateur) et le temps requis pour apprendre (usurper) le circuit (exponentiellement plus difficile), créant ainsi un écart de sécurité.

Innovations techniques

Pour rendre le schéma viable sur du matériel bruyant, les auteurs introduisent deux améliorations techniques clés :

1. Protocole de recouvrement d'ombres amélioré : Ils modifient les protocoles de recouvrement d'ombres existants (basés sur la Réf. [30]) en utilisant des circuits de Clifford aléatoires sur des sous-ensembles de qubits plutôt que de simples mesures de Pauli. Cela réduit le « temps de relaxation » ($\tau$) de la chaîne de Markov de certification et diminue la variance de l'estimateur, améliorant considérablement la tolérance au bruit et réduisant la complexité d'échantillonnage requise pour la certification.
2. Détection d'erreurs quantiques (QED) : Pour surmonter l'infidélité du matériel, les auteurs emploient un code de détection d'erreurs de type Iceberg multi-blocs.
   • Le code Iceberg encode $k$ qubits logiques en $k+2$ qubits physiques.
   • Ils utilisent la fixation de jauge (gauge fixing) pour promouvoir certains opérateurs logiques en stabilisateurs, créant des qubits « proxys » qui permettent la parallélisation des portes logiques à un qubit, réduisant ainsi la profondeur du circuit et les erreurs de mémoire.
   • Cette approche atteint une performance « au-delà du seuil de rentabilité » (beyond-break-even), où la fidélité encodée dépasse la fidélité non encodée malgré l'overhead.

Résultats clés

Preuves théoriques

• Difficulté d'apprentissage : Les auteurs montrent que les algorithmes connus pour apprendre des circuits peu profonds ne satisfont pas les conditions nécessaires (apprentissage approprié, géométrie arbitraire, accès aux ombres uniquement) pour briser le schéma.
• Écart de sécurité : Ils prouvent que pour des ensembles de circuits spécifiques (designs approximatifs), la complexité temporelle pour un adversaire apprenant le circuit via des polynômes de bas degré ou un entraînement variationnel est exponentiellement plus grande que le temps requis pour la vérification. Plus précisément, ils montrent que l'entraînement variationnel nécessite un nombre exponentiel de requêtes pour atteindre la fidélité cible pour les profondeurs de circuit utilisées.

Démonstration expérimentale

Les auteurs ont implémenté le protocole sur le processeur à ions piégés Quantinuum H2 (56 qubits physiques).

• Paramètres du circuit : Ils ont généré des ombres pour des états de 32 qubits à l'aide de circuits aléatoires avec $\ge 80$ portes logiques à deux qubits (correspondant à $\ge 582$ portes physiques à deux qubits).
• Fidélité : En utilisant le code Iceberg multi-blocs avec fixation de jauge, ils ont obtenu une fidélité certifiée de $0,90 \pm 0,01$ avec 17 316 échantillons.
• Preuve de concept : L'expérience a démontré avec succès la capacité de distinguer un signataire honnête d'un adversaire. Les auteurs ont calculé qu'augmenter la taille de l'échantillon par un facteur de 19,5 (soit environ 340 000 échantillons) serait suffisant pour atteindre un paramètre de sécurité où la probabilité qu'un adversaire aux capacités de calcul limitées usurpe la signature est négligeable ($< 10^{-5}$).

Signification et affirmations

L'article affirme démontrer la faisabilité à court terme de signatures numériques quantiques qui ne reposent ni sur les OWF, ni sur la communication quantique.

• Indépendance vis-à-vis des OWF : Le schéma fonde sa sécurité sur la difficulté physique d'apprendre des processus quantiques, offrant une voie vers une cryptographie qui reste sécurisée même si les OWF n'existent pas.
• Compatibilité NISQ : En utilisant des ombres classiques et des codes de détection d'erreurs plutôt qu'une correction d'erreurs complète, le protocole opère dans les capacités des matériels quantiques bruyants actuels.
• Primitive fondamentale : Ce travail établit un lien entre les signatures numériques quantiques et les énigmes à sens unique (one-way puzzles), une primitive qui permet la construction d'autres protocoles cryptographiques quantiques (comme les engagements de bits non interactifs) sans supposer l'existence des OWF.

Les auteurs soulignent que, bien que la démonstration actuelle soit une preuve de concept pour une signature d'un seul bit, les primitives sous-jacentes (certification par recouvrement d'ombres et détection d'erreurs) sont évolutives. Ils notent qu'étendre cela à des messages multi-bits est possible en utilisant des codes correcteurs d'erreurs classiques pour réduire les coûts de vérification, et qu'augmenter la taille des circuits permettrait de restaurer davantage la sécurité face à d'éventuelles percées futures des algorithmes d'apprentissage.