Cryptographie post-quantique

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[6], mais c'est Oded Regev qui a introduit en 2005[7] 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[7], 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[8], puis raffinée par Cash, Hofheinz, Kiltz et Peikert en 2010[9] puis par Micciancio et Peikert en 2012[10].

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

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 ${\displaystyle (\mathbf {A} ,\mathbf {A} \cdot \mathbf {s} +\mathbf {e} )}$ de la distribution ${\displaystyle (\mathbf {A} ,\mathbf {r} )}$ pour ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \mathbf {s} \in \mathbb {Z} ^{m}}$ tel que ${\displaystyle \mathbf {A} \cdot \mathbf {s} =\mathbf {0} {\bmod {q}}}$ et ${\displaystyle \|\mathbf {s} \|_{2}\leq \beta }$ étant donné une matrice ${\displaystyle \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 ${\displaystyle \mathbf {A} \cdot \mathbf {s} =\mathbf {u} }$ pour un vecteur cible ${\displaystyle \mathbf {u} \in \mathbb {Z} _{q}^{n}}$.

Ces hypothèses ont été introduites par Oded Regev dans son article fondateur[7]. 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.

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[8] dans le modèle de l'oracle aléatoire, ou celui d'Agrawal, Boneh et Boyen[12] dans le modèle standard.
• Le chiffrement complètement homomorphe de Gentry, Sahai et Waters[13].

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[14]. 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[14]), 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[15].

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 ${\displaystyle \mathbf {H} \in \mathbb {F} _{2}^{m\times n}}$, un entier ${\displaystyle w\leq n}$ et un syndrome ${\displaystyle \mathbf {u} \in \mathbb {F} _{2}^{m}}$, le problème consiste à trouver un vecteur ${\displaystyle \mathbf {x} \in \mathbb {F} _{2}^{n}}$ solution de l'équation ${\displaystyle \mathbf {H} \cdot \mathbf {x} =\mathbf {u} }$ et tel que son poids de Hamming soit fixé à ${\displaystyle w}$.

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

Des attaques efficaces ont été proposées sur la plupart des réalisations (Kipnis-Shamir'99[17], Faugère-Joux'03[18]), mais il reste Rainbow[19], 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[20].

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 ${\displaystyle E_{1}}$ et ${\displaystyle E_{2}}$ telles qu'il existe une isogénie ${\displaystyle \varphi }$ telle que ${\displaystyle \varphi (E_{1})=E_{2}}$, trouver ${\displaystyle \varphi }$) comme étant un problème difficile date de 2006, et a été proposé par Rostovtsev et Stolbunov[21] pour faire de l'échange de clefs. Mais cette proposition a été cryptanalysée par Childs, Jao et Soukharev[22] qui ont proposé une attaque quantique efficace.

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

• [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)

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