Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Résumé Technique : Malleabilité des Transformations sur le Chiffrement dans le cadre du Chiffrement à Clé Publique Quantique Bruité

Énoncé du Problème
Cet article traite du défi consistant à formuler rigoureusement la « sécurité éternelle » pour le chiffrement à clé publique quantique (QPKE) et la distribution de clés quantiques (QKD) en présence de bruit. Alors que les travaux précédents de Malavolta et Walter [3] ont établi un cadre pour la sécurité éternelle dans un environnement sans bruit — démontrant que la sécurité peut être atteinte après seulement deux cycles d'interaction entre Alice et Bob — ce travail examine comment l'introduction de bruit affecte les seuils de sécurité du protocole. Plus précisément, l'article explore la relation entre la malléabilité des transformations de texte chiffré et la sécurité du protocole lorsque du bruit est injecté dans les opérations cryptographiques. Le problème central est de généraliser la fonction de négligeabilité (qui quantifie l'avantage de l'adversaire) du cas idéal sans bruit vers un cadre bruité, en utilisant des hypothèses concernant la malléabilité des transformations de texte clair et de texte chiffré.

Méthodologie
Les auteurs emploient une combinaison de la théorie de l'information quantique et de la cryptographie abstraite pour analyser le protocole QPKE-QKD bruité. La méthodologie est structurée autour des composantes clés suivantes :

1. Injection de Bruit via la Malléabilité : L'article adapte le concept de malléabilité, introduit initialement par Maurer et Tackmann [9] pour comparer les protocoles « authentifier puis chiffrer » et « chiffrer puis authentifier ». Les auteurs définissent des transformations bruitées sur l'espace de texte clair caractérisées par trois probabilités d'erreur : l'erreur de transmission (forwarding error), l'erreur de suppression (deleting error) et l'erreur de reconstruction (reconstruction error). Ces erreurs sont utilisées pour modéliser l'impact du bruit sur le texte chiffré.
2. Distance de Trace et Lemme de Mesure Douce (GML) : Un outil technique central est l'adaptation du Lemme de Mesure Douce de la théorie de l'information quantique [18]. Les auteurs utilisent ce lemme pour établir une borne supérieure sur la distance de trace entre deux états quantiques (représentant les expériences réelle et idéale) basée sur une borne inférieure de la trace d'un opérateur spécifique. Cela permet de généraliser la fonction de négligeabilité en présence de bruit.
3. Machines Quantiques Polynomiales de Temps Noisy (NQPT) : L'article formalise le cadre bruité en définissant des machines de temps polynomial quantiques bruitées (NQPT) et des applications CPTP (Completely Positive Trace Preserving) bruitées. Ces objets remplacent leurs homologues sans bruit pour modéliser le comportement d'Alice, Bob et de l'adversaire (Eve) dans des conditions bruitées.
4. Opérateurs de Projection et Décomposition d'État : L'analyse implique la construction d'opérateurs de projection bruités ($\tilde{\Pi}$) qui intègrent des termes de bruit (par exemple, $|\sigma + \text{bruit}\rangle$) dans l'opérateur de projection standard $\Pi$ utilisé dans le protocole QPKE-QKD sans bruit. Les auteurs dérivent des bornes supérieures sur la distance de trace en comparant les ratios des opérateurs de projection sans bruit et bruités, les opérations de trace, ainsi que les états ket/bra.
5. Approche par la Théorie des Ressources : L'article utilise le cadre de la théorie des ressources de [9], définissant la sécurité et la disponibilité en termes d'indistinguabilité des ressources construites par les protocoles. Cela inclut l'analyse de la composition des protocoles et de l'indistinguabilité des expériences hybrides.

Principales Contributions

• Formalisation de la Sécurité Éternelle Bruité : L'article définit la « sécurité éternelle » pour un protocole QPKE bruité (Définition 37), établissant que la distance de trace entre les expériences hybrides bruitées est bornée par une fonction de négligeabilité dépendant du paramètre de sécurité bruité $\lambda'$.
• Généralisation de la Fonction de Négligeabilité : Les auteurs dérivent une relation entre la distance de trace dans le cadre bruité et la fonction de négligeabilité $NEGL(\lambda')$. Ils démontrent que, sous des hypothèses spécifiques sur le bruit, la fonction de négligeabilité dans le cadre bruité est liée à un seuil de sécurité plus élevé par rapport au cas sans bruit.
• Bornes de Distance de Trace via GML : Une contribution technique primaire est la dérivation d'une borne supérieure sur la distance de trace en utilisant le Lemme de Mesure Douce. Les auteurs montrent que :
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Ceci est réalisé en prouvant une borne inférieure sur la trace d'un opérateur spécifique impliquant la différence entre les états bruités et sans bruit ($\tilde{\rho} - \tau$).
• Hypothèses de Malléabilité : Le travail lie explicitement la sécurité du protocole à la malléabilité des transformations de texte chiffré. Il quantifie comment les probabilités d'erreur de transmission, de suppression et de reconstruction des transformations bruitées se rapportent à l'écart de seuil de sécurité entre les protocoles sans bruit ($\lambda$) et bruités ($\lambda'$).
• Compromis de Temps d'Exécution Computationnel : L'article analyse les compromis entre le temps d'exécution computationnel des protocoles bruités et sans bruit (encodage, décodage et génération de clés). Il suggère que si le temps d'exécution du protocole bruité est significativement plus grand, l'écart du seuil de sécurité $\lambda' - \lambda$ évolue d'une manière spécifique, potentiellement liée à des fonctions exponentielles ou polynomiales de la différence de temps d'exécution.

Résultats

• Théorème Principal : L'article prouve que pour un protocole QPKE-QKD bruité satisfaisant les conditions de correction, la distance de trace entre les expériences hybrides bruitées (initialisées avec les bits 0 et 1) est bornée par la fonction de négligeabilité du paramètre de sécurité bruité :
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corollaire sur les Fonctions d'Avantage : Les auteurs montrent que les fonctions d'avantage bruitées pour différentes expériences hybrides ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) sont toutes bornées par la même fonction de négligeabilité $NEGL(\lambda')$, confirmant la cohérence de la définition de la sécurité à travers différents montages expérimentaux.
• Borne Inférieure sur la Trace : L'article fournit une dérivation détaillée montrant que la trace d'un opérateur spécifique impliquant la différence entre les états bruités et sans bruit est bornée inférieurement par une constante fois l'inverse de la fonction de négligeabilité, ce qui est un prérequis pour l'application du Lemme de Mesure Douce.

Signification et Revendications
L'article affirme fournir un cadre mathématique rigoureux pour étendre la notion de sécurité éternelle au chiffrement à clé publique quantique bruité. En adaptant le Lemme de Mesure Douce, les auteurs démontrent que les garanties de sécurité du protocole sans bruit peuvent être généralisées au cadre bruité, à condition que le bruit soit caractérisé par des hypothèses de malléabilité sur les transformations de texte chiffré.

Les auteurs soulignent que, bien que l'introduction de bruit mène généralement à un seuil de sécurité plus élevé (impliquant une garantie de sécurité potentiellement plus faible en termes du paramètre $\lambda'$), les bornes dérivées permettent une comparaison quantitative entre les protocoles bruités et sans bruit. Le travail est présenté comme une étape théorique, notant que bien que les exigences pour une sécurité inconditionnelle et éternelle soient difficiles à réaliser expérimentalement, le cadre proposé offre un point de départ précieux pour analyser les limites du calcul quantique bruité dans des contextes cryptographiques. L'article conclut en suggérant que les calculs dérivés pour borner la distance de trace pourraient être examinés plus avant dans des cadres centrés sur des approches de la théorie des jeux, bien qu'il ne propose pas d'implémentations expérimentales spécifiques ou d'applications immédiates au-delà de l'analyse théorique.