Cryptographie post-quantique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

La plupart des algorithmes cryptographiques classiques 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 classiques (chiffrement RSA, cryptosystème El Gamaletc.), sont résolus par cette attaque[1].

Méthodes utilisées[modifier | modifier le code]

La cryptographie post-quantique repose sur différentes méthodes concurrentes.

Réseaux euclidiens[modifier | modifier le code]

Article détaillé : Réseau euclidien.
Réduction de réseaux
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[2], mais c'est Oded Regev qui a introduit en 2005[3] 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[3], 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[4], puis raffinée par Cash, Hofheinz, Kiltz et Peikert en 2010[5] puis par Micciancio et Peikert en 2012[6].

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[7].

Hypothèses de sécurité[modifier | modifier le code]

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

  • L’apprentissage avec erreurs (en) (learning with errors ou LWE en anglais), qui consiste à distinguer la distribution de la distribution pour prises uniformément, et 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 tel que et étant donné une matrice . 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 pour un vecteur cible .

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

Constructions[modifier | modifier le code]

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

Codes correcteurs d'erreur[modifier | modifier le code]

Error correcting code
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[10]. 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[10]), 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[11].

Hypothèses de sécurité[modifier | modifier le code]

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 , un entier et un syndrome , le problème consiste à trouver un vecteur solution de l'équation et tel que son poids de Hamming soit fixé à .

Polynômes multivariés[modifier | modifier le code]

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é[12].

Des attaques efficaces ont été proposées sur la plupart des réalisations (Knipsis-Shamir'99[13], Faugère-Joux'03[14]), mais il reste Rainbow[15], construite sur le mélange non-équilibré d'huile et de vinaigre (en) (en anglais UOV pour Unbalanced Oil and Vinegar) qui semble être prometteur[16].

Recherche d'isogénie de courbes supersingulières[modifier | modifier le code]

Courbes elliptiques
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 et telles qu'il existe une isogénie telle que , trouver ) comme étant un problème difficile date de 2006, et a été proposé par Rostovtsev et Stolbunov[17] pour faire de l'échange de clefs. Mais cette proposition a été cryptanalysée par Childs, Jao et Soukharev[18] qui ont proposé une attaque quantique efficace.

Cette attaque a été réparée en 2011 par Jao et de Feo[19] 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[10]), ou la cryptographie sur les réseaux euclidiens (1996[2]), elle possède encore peu d'applications, mais offre des tailles de clefs très compétitives comparées à ses concurrents[20].

Cryptographie symétrique[modifier | modifier le code]

En 2016, la principale amélioration connue des attaques sur les cryptosystèmes symétriques est l'algorithme de Grover qui permet d’effectuer une recherche en temps à la place du 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é que dans le modèle classique, il suffirait de doubler la taille des clefs utilisées.

Néanmoins, certains schémas proposés lors de la compétition CAESAR[21] se sont révélés sensibles à des attaques par l'algorithme de Simon (en)[22].

Comparaison de tailles de clefs[modifier | modifier le code]

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-quantique est de fournir des clés plus grandes que leur concurrents actuellement utilisés (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 tailles de clefs ont été évaluées pour le même niveau de sécurité que RSA-1024, dont la clé publique et privée font 1024 bits[réf. nécessaire].

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(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[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • [Agrawal, Boneh et Boyen 2010] (en) Shweta Agrawal, Dan Boneh et Xavier Boyen, « Efficient lattice (H) IBE in the standard model », Eurocrypt,‎ (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,‎ (DOI 10.1145/237814.237838, lire en ligne)
  • [Billet et Gilbert 2006] (en) Olivier Billet et Henri Gilbert, « Cryptanalysis of Rainbow », Security and Cryptography for Networks (SCN),‎ (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,‎ (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,‎ (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,‎ , 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,‎ (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,‎ (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,‎ (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,‎ (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,‎ , 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,‎ (DOI 10.1007/978-3-662-53008-5_8, arXiv 1602.05973)
  • [Knipsis et Shamir 1999] (en) Aviad Knipsis et Adi Shamir, « Cryptanalysis of the HFE Public Key Cryptosystem by relinearisation », Crypto,‎ (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,‎ , p. 42–44 (lire en ligne)
  • [Micciancio et Peikert 2012] (en) Daniele Micciancio et Chris Peikert, « Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller », Eurocrypt,‎ (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,‎ , p. 95–145 (DOI 10.1007/978-3-540-88702-7_4, lire en ligne)
  • [Patarin 1996] (en) Jacques Patarin, « Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms », Eurocrypt,‎ (DOI 10.1007/3-540-68339-9_4, lire en ligne)
  • [Peikert 2015] (en) Chris Peikert, « A Decade of Lattice Cryptography », ePrint archive,‎ (lire en ligne)
  • [Regev 2005] (en) Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », Symposium on Theory of Computing,‎ (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,‎ (lire en ligne)
  • [Shor 1999] (en) Peter W. Shor, « Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer », SIAM Review,‎ (DOI 10.1137/S0036144598347011, lire en ligne)

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]