Cryptographie post-quantique

La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un calculateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité.

En l'effet, les algorithmes quantiques de Shor, de Grover et de Simon étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique. S'il n'existe pas à l'heure actuelle de calculateur quantique représentant une menace concrète sur la sécurité des cryptosystèmes déployés, ces algorithmes permettent conceptuellement de résoudre certains problèmes calculatoires sur lesquels sont fondés plusieurs primitives populaires.

Algorithmes quantiques et cryptographie

En 1995, Peter Shor a publié un algorithme permettant de résoudre le problème du logarithme discret et le problème de la factorisation des entiers. Cet algorithme, utilisant les spécificités d'un calculateur quantique (dont on n'avait alors pas encore construit de prototypes), produit une réponse en temps polynomial. En comparaison, les meilleurs algorithmes classiques connus pour ces problèmes ont une complexité exponentielle en général, et sous-exponentielle mais sur-polynomiale pour les corps finis. En résumé, pour ces deux problèmes, aucun algorithme classique efficace n'est connu, mais puisqu'un algorithme quantique efficace est disponible, on dit qu'ils appartiennent à la classe de complexité BQP.

En conséquence, les constructions cryptographiques dont la sécurité repose sur le problème du logarithme discret (notamment l'échange de clé de Diffie-Hellman et la signature ECDSA), ou sur le problème de la factorisation d'entiers (notamment la signature RSA) seraient vulnérables à un attaquant disposant d'un calculateur quantique suffisamment grand et fiable.

L'algorithme de Grover, quant à lui, améliore de manière faible mais générique l'efficacité des problèmes de recherche. Contrairement à l'algorithme de Shor, il ne dote pas l'attaquant d'un avantage exponentiel, mais seulement quadratique, c'est-à-dire qu'il divise le niveau de sécurité d'un problème de recherche par deux.

Cryptographie symétrique

En 2018, le principal algorithme quantique affectant les cryptosystèmes symétriques est l'algorithme de Grover. Cet algorithme est générique, c'est-à-dire qu'il s'applique en principe à toute primitive indépendamment de sa construction, et permet d’effectuer une recherche parmi $n$ éléments en temps $O(n^{1/2})$ à la place de $O(n)$ dans le cas classiques.

Par conséquent, la sécurité des algorithmes n'est affectée que par un facteur 2. Autrement dit, pour atteindre la même sécurité que dans le modèle classique, il suffit de doubler la taille des clefs utilisées, ce qui ne pose aucune difficulté conceptuelle, mais peut nécessiter des ajustement techniques. En effet, de nombreux algorithmes symétriques sont conçus et analysés avec une taille de clef fixe.

Dans certains cas, il est possible qu'une construction symétrique soit sujette à des attaques spécialisées par l'algorithme de Simon, ce qui s'est produit pour un schéma proposé à la compétition CAESAR. Enfin, l'algorithme d'Ambainis permet de gagner un facteur polynomial la recherche de collisions.

Cryptographie à clef publique

Pour les problèmes de la factorisation d'un entier $n$, le meilleur algorithme classique connu est en complexité temporelle heuristique $$L_{n}\left[{\frac {1}{3}},{\sqrt[{3}]{\frac {64}{9}}}\right].$$ Ce qui permet d'appuyer la sécurité d'algorithmes tels que la signature de Rabin à 128 bits en utilisant un module $n$ de 3072 bits. La sécurité d’une signature RSA utilisant un tel module est alors d'au plus 128 bits face à un attaquant classique. Le meilleur algorithme quantique connu possède une complexité quadratique en $n$ ; adapter la sécurité de RSA à ce contexte serait possible, mais requiert des tailles de clef phénoménales, de l'ordre du téraoctet. En pratique, au-delà des problèmes de stockage et de transmission de telles clefs et de tels messages, est que toutes les opérations sont ralenties d'autant. De plus, il n'existe pas de preuves que l'algorithme de Shor soit le plus efficace possible : chercher à sauver RSA dans ce contexte est une course perdue d'avance.

De manière générale, les algorithmes à clef publique reposant sur la factorisation peuvent être considérés cassés par un attaquant quantique : RSA, Paillier, Naccache-Stern, Rabin, Benaloh, Blum-Goldwasser, Damgård–Jurik, Goldwasser-Micali, Okamoto-Uchiyama, Schmidt-Samoa.

Le problème du logarithme discret peut aussi être résolu par une variante du même algorithme, de sorte que les algorithmes à clef publique dont la sécurité repose sur l'hypothèse de la difficulté du logarithme discret sont également cassés par l'algorithme de Shor. Contrairement au cas classique, où le crible du corps de nombres s'applique dans les corps finis mais pas en général dans le groupe des points rationnels d'une courbe elliptique, l'approche de l'algorithme de Shor ne fait aucune différence.

Ainsi, les algorithmes à clef publique reposant sur la difficulté du calcul d'un logarithme discret peuvent être considérés cassés par un attaquant quantique : Diffie-Hellman, Cramer-Shoup, DSA et ECDSA (aussi ses précurseurs Schnorr et ElGamal, et ses variantes comme EdDSA), SRP, etc.

D'autres problèmes classiquement difficiles reposant sur des problèmes d'arithmétique modulaire sont eux aussi affectés par des variantes de l'algorithme de Shor.

Candidats post-quantiques

Plusieurs constructions cryptographiques ne sont pas affectées par les attaques discutées ci-dessus, et constitueraient une solution facile de substitution. Par exemple, on peut espérer construire l'équivalent de constructions à clef publique en n'utilisant que des primitives symétriques. Mais le risque demeure qu'un algorithme quantique (qui n'a pas encore été découvert) puisse les casser.

La communauté cryptographique s'est donc tournée vers des approches qu'un attaquant quantique ne peut pas casser. La logique générale est de construire des primitives cryptographiques à partir de problèmes NP-complets, dont on sait qu'un ordinateur quantique (limité à la classe BQP) ne peut les résoudre plus efficacement qu'un ordinateur classique, sous l'hypothèse que P ≠ NP. Les candidats les plus sérieux reposent sur les problèmes suivants :

• Problèmes de vecteurs courts dans les réseaux euclidiens (1996) ;
• Décodage de codes linéaires aléatoires (1978) ;
• Inversion de polynômes multivariés (1995) ;
• Navigation dans les isogénies des courbes elliptiques supersingulières (2006) ;
• Inversion de fonctions de hachage (1978).

Le prix à payer est une perte d'efficacité et des clefs plus larges. Pour essayer de gagner sur ces terrains, plusieurs propositions ont été faites qui n'ont qu'heuristiquement la sécurité d'un problème NP. La conséquence est que parfois, ces variantes s'avèrent vulnérables à des attaques classiques (ou quantiques).

En 2017, le NIST a annoncé une compétition visant à établir une standardisation des algorithmes cryptographiques post-quantiques. Ce protocole de standardisation, a fait émerger 4 candidats pour la standardisation en juillet 2022: un schéma d’encapsulation de clefs, CRYSTALS-Kyber (en) dont la sécurité repose sur la sécurité de problèmes de réseaux euclidiens (structurés), ainsi que trois schémas de signature numérique, CRYSTALS-Dilithium, Falcon (en) et SPHINCS+ (en), les deux premiers reposant sur des hypothèses de sécurité sur les réseaux euclidiens (structurés) et le dernier étant une construction fondée sur les fonctions de hachage.

Réseaux euclidiens

Réseau euclidien engendré par v₁ et v₂ et une base réduite u₁ et u₂

Les premières méthodes pour produire des problèmes difficiles en cas moyen (une propriété importante en cryptographie, c'est ce qui fait par exemple que n'importe quel problème NP-Complet ne peut pas être utilisé en cryptographie étant donné qu'il n'est pas toujours évident de produire une instance difficile) ont été proposées par Ajtai en 1996, mais c'est Oded Regev qui a introduit en 2005 le problème de l'apprentissage avec erreur (LWE en anglais, pour learning with errors), accompagné d'une réduction quantique depuis les problèmes difficiles connus (recherche du vecteur le plus court, et recherche du vecteur le plus proche). Ces analyses ont été ensuite améliorées par Chris Peikert en 2009.

C'est un domaine de recherche actif depuis les travaux de Regev en 2005, et de nombreuses primitives avancées comme le chiffrement complètement homomorphe ne sont possibles que dans ce contexte. Cela a été rendu possible par l'introduction de la délégation de bases, permettant de générer une base aléatoire pour un sur-réseau de celui de travail. Cette méthode a été introduite par Gentry, Peikert et Vaikuntanathan en 2008, puis raffinée par Cash, Hofheinz, Kiltz et Peikert en 2010 puis par Micciancio et Peikert en 2012.

Cette technique permettant de débloquer ces fonctionnalités intéressantes pose néanmoins un problème de performances, étant peu efficace en pratique. En revanche, il existe des cryptosystèmes à base de réseaux euclidiens qui proposent des solutions efficaces, comme NTRU.

Hypothèses de sécurité

La cryptographie sur les réseaux repose principalement sur les hypothèses standards suivantes :

• L’apprentissage avec erreurs (learning with errors ou LWE en anglais), qui consiste à distinguer la distribution $(\mathbf {A} ,\mathbf {A} \cdot \mathbf {s} +\mathbf {e} )$ de la distribution $(\mathbf {A} ,\mathbf {r} )$ pour $\mathbf {A} \in \mathbb {Z} _{q}^{m\times n},\mathbf {s} \in \mathbb {Z} _{q}^{n},\mathbf {r} \in \mathbb {Z} _{q}^{m}$ prises uniformément, et $\mathbf {e} \in \mathbb {Z} ^{m}$ tirée suivant une gaussienne d'écart-type σ. Ce problème est paramétré par n, q, et α = σ/q dont le choix va faire varier la difficulté du problème.
• La recherche d’une solution entière courte (en) (short integer solution ou SIS en anglais), qui consiste à calculer un vecteur solution $\mathbf {s} \in \mathbb {Z} ^{m}$ tel que $\mathbf {A} \cdot \mathbf {s} =\mathbf {0} {\bmod {q}}$ et $\|\mathbf {s} \|_{2}\leq \beta$ étant donné une matrice $\mathbf {A} \in \mathbb {Z} _{q}^{n\times m}$. Ce problème est paramétré par n, q et β, et possède une variante inhomogène: ISIS (pour Inhomogeneous SIS), où au lieu de résoudre une équation linéaire homogène (ou le second terme est nul), on résout l'équation $\mathbf {A} \cdot \mathbf {s} =\mathbf {u}$ pour un vecteur cible $\mathbf {u} \in \mathbb {Z} _{q}^{n}$.

Ces hypothèses ont été introduites par Oded Regev dans son article fondateur. Elles ont leur pendant sur des anneaux de polynômes (Ring-LWE (en) par exemple), qui sont plus compactes, mais qui souffrent d’une cryptanalyse moins poussée.

Constructions

Parmi les constructions reposant sur des hypothèses sur la difficulté des problèmes sur les réseaux euclidiens, on peut citer :

• Le chiffrement NTRU.
• Le schéma de signature BLISS (en).
• Le chiffrement fondé sur l'identité de Gentry, Peikert et Vaikuntanathan dans le modèle de l'oracle aléatoire, ou celui d'Agrawal, Boneh et Boyen dans le modèle standard.
• Le chiffrement complètement homomorphe de Gentry, Sahai et Waters.

Codes correcteurs d'erreur

Illustration d'un code correcteur

La cryptographie sur les codes est une autre solution pour concevoir des cryptosystèmes post-quantiques introduite en 1978 par Robert McEliece. Le problème difficile sous-jacent venant de la théorie des codes provient du fait qu’il est difficile, étant donné une famille de codes, de déterminer quel code a été utilisé pour le codage, la clef privée étant la matrice génératrice du code (permettant de corriger l'erreur), et la clef publique étant une version randomisée de cette matrice (pour le cryptosystème de McEliece), permettant de générer des mots du code, sans pouvoir décoder. Ainsi pour chiffrer un message, l'expéditeur rajoute une erreur à son message encodé, ce qui le rend inintelligible pour une personne ne disposant pas de la matrice génératrice.

La principale difficulté de la cryptographie sur les codes correcteurs étant de trouver une famille de codes efficaces et exhibant la difficulté nécessaire. Une famille qui possède ces propriétés sont les codes de Goppa.

Hypothèses de sécurité

Le cryptosystème de McEliece est prouvé sûr sous l'hypothèse du décodage de syndrome (syndrome decoding problem ou SDP en anglais), qui est similaire à la recherche d’une solution inhomogène entière courte mais dans le cadre des codes. Autrement dit, étant donné une matrice $\mathbf {H} \in \mathbb {F} _{2}^{m\times n}$, un entier $w\leq n$ et un syndrome $\mathbf {u} \in \mathbb {F} _{2}^{m}$, le problème consiste à trouver un vecteur $\mathbf {x} \in \mathbb {F} _{2}^{n}$ solution de l'équation $\mathbf {H} \cdot \mathbf {x} =\mathbf {u}$ et tel que son poids de Hamming soit fixé à $w$.

Polynômes multivariés

La cryptographie à base de polynômes multivariés repose sur le fait qu'il est difficile de résoudre des systèmes polynomiaux à plusieurs variables (appelés aussi multivariés). Pour passer de cette observation à un système permettant de construire des primitives cryptographique, des tentatives de réalisations ont été proposées comme les équations sur un corps caché.

Des attaques efficaces ont été proposées sur de nombreuses réalisations (Kipnis-Shamir'99, Faugère-Joux'03, Beullens'22), mais il reste le mélange non-équilibré d'huile et de vinaigre (en) (en anglais UOV pour Unbalanced Oil and Vinegar) et ses variantes.

Recherche d'isogénie de courbes supersingulières

Courbes elliptiques isogènes

Une isogénie est un morphisme de groupe surjectif et de noyau fini entre deux courbes elliptiques. L'introduction du problème de la recherche d'isogénie de courbes (c'est-à-dire qu'étant donné deux courbes elliptiques $E_{1}$ et $E_{2}$ telles qu'il existe une isogénie $\varphi$ telle que $\varphi (E_{1})=E_{2}$, trouver $\varphi$) comme étant un problème difficile date de 2006, et a été proposé par Rostovtsev et Stolbunov pour faire de l'échange de clefs. Mais cette proposition a été cryptanalysée par Childs, Jao et Soukharev qui ont proposé une attaque quantique efficace.

Cette attaque a été réparée en 2011 par Jao et de Feo qui ont proposé l'utilisation de courbes supersingulières. La raison étant que l'attaque repose principalement sur la commutativité de la composition des isogénies dans le cas général; propriété qui n'est pas vérifiée pour les courbes supersingulières.

Étant une solution jeune comparée à ses concurrents comme la cryptographie à base de code (1978), ou la cryptographie sur les réseaux euclidiens (1996), elle possède encore peu d'applications, mais offre des tailles de clefs très compétitives comparées à ses concurrents.

Comparaison de tailles de clefs

La taille des clefs est importante pour évaluer l'efficacité des systèmes de chiffrement, et s’avère critique sur les systèmes embarqués comme les cartes à puces où la mémoire est critique. Il existe d'autres métriques, comme les temps pour chiffrer/déchiffrer, mais elles sont difficiles à évaluer puisqu’il est possible d’avoir des performances incomparables par l'utilisation de circuits programmables par exemple.

Une caractéristique des cryptosystèmes post-quantiques est de fournir des clefs plus grandes que celles utilisées par leurs concurrents (comme le chiffrement El Gamal sur courbes elliptiques par exemple).

Comparaison de tailles de clefs

Algorithme	Type d'hypothèses	Taille de la clef publique (en bits)	Taille de la clef privée (en bits)
Ring-LWE (en)	Réseaux euclidiens	6 595	14 000
NTRU	Réseaux euclidiens	6 130	6 743
Rainbow	Polynômes multivariés	991 000	740 000
Hash signature	Fonctions de hachage	36 000	36 000
McEliece sur des codes de Goppa	Codes correcteurs	8 373 911	92 027
McEliece sur des codes MDPC quasi-cycliques	Codes correcteurs	65 542	4 384
SIDH (en)	Isogénie de courbes	6 144	6 144

Ces clefs sont évaluées pour un niveau de sécurité de 128 bits face à un attaquant quantique (256 bits face à un attaquant classique). À titre équivalent, un module RSA pour 256 bits de sécurité classique est estimé à 15360 bits (clef publique).

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Post-quantum cryptography » (voir la liste des auteurs).

Annexes

Bibliographie

• [Agrawal, Boneh et Boyen 2010] (en) Shweta Agrawal, Dan Boneh et Xavier Boyen, « Efficient lattice (H) IBE in the standard model », Eurocrypt,‎ 2010 (DOI 10.1007/978-3-642-13190-5_28, lire en ligne)
• [Ajtai 1996] (en) Mikiós Ajtai, « Generating hard instances of lattice problems », Symposium on Theory of Computing,‎ 1996 (DOI 10.1145/237814.237838, lire en ligne)
• [Barker 2016] (en) Elaine Barker, « Recommendation for Key Management Part 1: General », NIST SP 800-57,‎ 2016 (DOI 10.6028/nist.sp.800-57pt1r4, lire en ligne)
• [Bernstein et al. 2017] (en) Daniel J. Bernstein, Nadia Heninger, Paul Lou et Luke Valenta, « Post-quantum RSA », Post-Quantum Cryptography, Springer, Cham, lecture Notes in Computer Science,‎ 26 juin 2017, p. 311–329 (ISBN 9783319598789, DOI 10.1007/978-3-319-59879-6_18, lire en ligne, consulté le 8 mars 2018)
• [Billet et Gilbert 2006] (en) Olivier Billet et Henri Gilbert, « Cryptanalysis of Rainbow », Security and Cryptography for Networks (SCN),‎ 2006 (DOI 10.1007/11832072_23)
• [Cash et al. 2010] (en) David Cash, Dennis Hofheinz, Eike Kiltz et Chris Peikert, « Bonsai Trees, or How to Delegate a Lattice Basis », Eurocrypt,‎ 2010 (DOI 10.1007/978-3-642-13190-5_27, lire en ligne)
• [Costello, Longa et Naehrig 2016] (en) Craig Costello, Patrick Longa et Michael Naehrig, « Efficient algorithms for supersingular isogeny Diffie-Hellman », Crypto,‎ 2016 (lire en ligne)
• [Childs, Jao et Soukharev 2014] (en) Andrew M. Childs, David Jao et Vladimir Soukharev, « Constructing elliptic curve isogenies in quantum subexponential time », Journal of Mathematical Cryptology,‎ 2014, p. 1-29 (lire en ligne)
• [Faugère et Joux 2003] (en) Jean-Charles Faugère et Antoine Joux, « Algebraic Cryptanalysis of Hidden Field Equations (HFE) Cryptosystems using Gröbner Bases », Crypto,‎ 2003 (DOI 10.1007/978-3-540-45146-4_3, lire en ligne)
• [Faugère et Perret 2009] (en) Jean-Charles Faugère et Ludovic Perret, « On the Security of UOV », iacr ePrint Report,‎ 2009 (lire en ligne)
• [Gentry, Peikert et Vaikuntanathan 2008] (en) Craig Gentry, Chris Peikert et Vinod Vaikuntanathan, « Trapdoors for hard lattices and new cryptographic constructions », ACM Symposium for Theory of Computing,‎ 2008 (DOI 10.1145/1374376.1374407, lire en ligne)
• [Gentry, Sahai et Waters 2013] (en) Craig Gentry, Amit Sahai et Brent Waters, « Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based », Crypto,‎ 2013 (DOI 10.1007/978-3-642-40041-4_5, lire en ligne)
• [Jao et de Feo 2011] (en) David Jao et Luca de Feo, « Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies », PQCrypto,‎ 2011, p. 19-34
• [Kaplan et al. 2016] (en) Marc Kaplan, Gaëtan Leurent, Anthony Leverrier et María Naya-Plasencia, « Breaking Symmetric Cryptosystems Using Quantum Period Finding », Crypto,‎ 2016 (DOI 10.1007/978-3-662-53008-5_8, arXiv 1602.05973)
• [Kipnis et Shamir 1999] (en) Aviad Kipnis et Adi Shamir, « Cryptanalysis of the HFE Public Key Cryptosystem by relinearisation », Crypto,‎ 1999 (DOI 10.1007/3-540-48405-1_2, lire en ligne)
• [McEliece 1978] (en) Robert J. McEliece, « A Public-Key Cryptosystem Based on Algebraic Coding Theory », Jet Propulsion Laboratory DSN Progress Report,‎ 1978, p. 42–44 (lire en ligne)
• [Micciancio et Peikert 2012] (en) Daniele Micciancio et Chris Peikert, « Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller », Eurocrypt,‎ 2012 (DOI 10.1007/978-3-642-29011-4_41, lire en ligne)
• [Overbeck et Sendrier 2009] (en) Raphael Overbeck et Nicolas Sendrier, « Code-based cryptography », Post-Quantum Cryptography, Daniel J. Bernstein,‎ 2009, p. 95–145 (DOI 10.1007/978-3-540-88702-7_4, lire en ligne, consulté le 15 mai 2014)
• [Patarin 1996] (en) Jacques Patarin, « Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms », Eurocrypt,‎ 1996 (DOI 10.1007/3-540-68339-9_4, lire en ligne)
• [Peikert 2015] (en) Chris Peikert, « A Decade of Lattice Cryptography », ePrint archive,‎ 2015 (lire en ligne)
• [Regev 2005] (en) Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », Symposium on Theory of Computing,‎ 2005 (DOI 10.1145/1568318.1568324, lire en ligne)
• [Rostovstev et Stolbunov 2006] (en) Alexander Rostovtsev et Anton Stolbunov, « Public-Key Cryptosystem based on Isogenies », iacr ePrint Reports,‎ 2006 (lire en ligne)
• [Shor 1999] (en) Peter W. Shor, « Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer », SIAM Review,‎ 1999 (DOI 10.1137/S0036144598347011, lire en ligne)

Articles connexes

• Cryptographie asymétrique
• Cryptographie symétrique
• Cryptographie quantique

Liens externes

• « L’informatique quantique et la fin de la sécurité », Kasperski, 7 octobre 2013 (consulté le 13 juillet 2017)
• (de) « Infineon zeigt erste Post-Quantum-Kryptographie auf kontaktlosem Chip », 30 mai 2017 (consulté le 13 juillet 2017)