Cryptographie post-quantique

La cryptographie post-quantique désigne une branche de la cryptographie visant à garantir la sécurité même face à un attaquant quantique en utilisant nos ordinateurs dit classiques. Il ne faut pas la confondre avec la cryptographie quantique, qui consiste à utiliser des méthodes quantiques pour protéger d’un adversaire quantique.

La plupart de nos algorithmes cryptographiques actuels ne sont pas résistant face à de telles attaques, par exemple le cryptosystème RSA dont la sécurité tombe si la factorisation peut être résolue facilement ne l'est pas, puisqu’il existe un algorithme quantique pour factoriser un nombre fonctionnant en temps polynomial : l'algorithme de Shor. Pour être plus précis, la factorisation et le logarithme discret (et sa version elliptique, ce qui élimine aussi la cryptographie à base de couplages), qui sont deux problèmes sur lesquels repose la sécurité des algorithmes de chiffrement actuels (chiffrement RSA, cryptosystème El Gamal,...), sont résolus par cet attaque.

Méthodes utilisées

À l'heure actuelle, la cryptographie post-quantique repose sur différentes méthodes concurrentes.

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ée 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é raffinés 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 modèle. 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ées 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.

Codes correcteurs d'erreur

Illustration d'un code correcteur

La cryptographie sur les codes est une autre alternative pour concevoir des cryptosystèmes post-quantiques. 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 clé privée étant la matrice génératrice du code (permettant de corriger l'erreur), et la clé 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.

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 la plupart des réalisations (Knipsis-Shamir'99, Faugère-Joux'03), mais il reste Rainbow, construite sur le mélange non-équilibré d'huile et de vinaigre (en) (en anglais UOV pour Unbalanced Oil and Vinegar) semblent prometteuses.

Cryptographie symétrique

En 2016, la seule amélioration connue des attaques sur les cryptosystèmes symétriques est l'algorithme de Grover qui permet d’effectuer une recherche en temps ${\mathcal {O}}({\sqrt {N}})$ à la place du ${\mathcal {O}}(N)$ dans le cas générique qui est alors obtenu avec des ordinateurs classiques. Par conséquent, la sécurité des algorithme n'est affecté que par un facteur 2. Autrement dit, pour atteindre la même sécurité qu'en 2016, il suffirait de doubler la taille des clefs utilisées.

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

• [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)
• [Billet 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)
• [Faugère 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 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 fo Theory of Computing,‎ 2008 (DOI 10.1145/1374376.1374407, lire en ligne)
• [Knipsis Shamir 1999] (en) Aviad Knipsis 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)
• [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)
• [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