Cryptographie multivariée

La cryptographie multivariée regroupe un ensemble de techniques cryptographiques à clé publique reposant sur l'utilisation de polynômes multivariés à coefficients dans un corps fini. Il s'agit d'une des directions de recherches considérées pour développer la cryptographie post-quantique. Pour l'essentiel, la sécurité des constructions issues de cette direction de recherche découle du fait que la résolution de systèmes d'équations polynomiales est un problème NP-difficile en général.

Histoire

Le premier schéma de chiffrement de cette famille fut décrit par Tsutomu Matsumoto et Hideki Imai en 1988^[1]. Bien que rapidement cryptanalysé^[2], il inspira de nombreuses variantes dont HFE^[3], dû à Jacques Patarin. Si HFE tel qu'initialement décrit est aujourd'hui considéré comme cassé^{[4],[5],[6],[7],[8],[9]}, des variantes telles que UOV^[10], HFE^{v−[11],[12]}, ou Rainbow^[13] sont encore viables^{[14],[15],[16],[17]}. De même, le schéma de signature Sflash^[18], proposé à la compétition NESSIE, est aujourd'hui complètement cassé^[19],[20].

Tous ces cryptosystèmes ont en commun que la clé publique est constituée d'un ensemble de polynômes multivariés, généralement des polynômes quadratiques pour des raisons d'efficacité algorithmique et de taille des clés.

Principe général

On fixe un corps fini ${\displaystyle \mathbb {F} }$, la clé publique est donnée par un ensemble :

${\displaystyle G(x_{1},\dotsc ,x_{n})=\left(G_{1}(x_{1},\dotsc ,x_{n}),\dotsc ,G_{m}(x_{1},\dotsc ,x_{n})\right)}$

où chaque ${\displaystyle G_{i}\in \mathbb {F} [x_{1},\dotsc ,x_{n}]}$. Un message clair correspond à une suite ${\displaystyle M=(m_{1},\dotsc ,m_{n})\in \mathbb {F} ^{n}}$, et le chiffrement consiste simplement à évaluer chaque polynôme de la clé publique en ce point:

${\displaystyle C=G(M)=\left(G_{1}(M),\dotsc ,G_{m}(M)\right).}$

On voit ici apparaître un des intérêts de cette famille de techniques cryptographiques : l'évaluation polynomiale est calculatoirement très efficace (et même, dans une certaine mesure, parallélisable), ce qui permet un chiffrement relativement très rapide. Jusqu'ici la description ci-dessus s'applique à tous les procédés de chiffrement multivariés.

Pour déchiffrer, il faut posséder comme clé secrète un moyen d'inverser ${\displaystyle G}$, noté généralement ${\displaystyle G^{-1}}$. Ce moyen est spécifique au chiffrement multivarié considéré, et c'est souvent en étudiant la manière dont ${\displaystyle G}$ et son inverse sont choisis qu'une attaque a été découverte : en effet, il s'agit souvent d'une opération aisément inversible « masquée » par deux transformations, de manière tout à fait analogue à l'approche utilisée pour les chiffrements à base de codes, tels que le cryptosystème de McEliece, pour cacher le code.

Pour un ensemble de polynômes ${\displaystyle G}$ général (c'est-à-dire ne présentant pas de structure particulière exploitable par l'attaquant), le problème de l'inversion est prouvé NP-difficile. Supposant P ≠ NP il est donc conjecturé que même un ordinateur quantique ne peut résoudre ce problème efficacement. Comme les polynômes utilisés en cryptographie multivariée ne sont pas tout à fait aléatoires, mais sont choisis avec une structure cachée, l'argument de sécurité n'est toutefois qu'heuristique.

En calculant l'inverse ${\displaystyle G^{-1}(M)}$ au lieu de ${\displaystyle G(M)}$, on obtient un schéma de signature au lieu d'un schéma de chiffrement, où cette fois c'est la vérification publique de la signature qui est particulièrement efficace. Un des attraits de la cryptographie multivariée pour la génération de signatures est leur taille réduite comparée à d'autres approches.

Exemple

Pour illustrer le fonctionnement sur un exemple simple (tiré du cryptosystème d'Imai-Matsumoto), on se place dans le corps ${\displaystyle \mathbb {F} =\mathbb {F} _{2^{2}}=\mathbb {F} _{2}[X]/(X^{2}+X+1)}$, qui possède 4 éléments ${\displaystyle 0,1,\alpha ,1+\alpha }$, que l'on va noter respectivement ${\displaystyle 0,1,2,3}$. Supposons la clé publique donnée par

${\displaystyle {\begin{aligned}G_{1}&=1+x_{2}+2x_{0}x_{2}+3x_{1}^{2}+3x_{1}x_{2}+x_{2}^{2}\\G_{2}&=1+3x_{0}+2x_{1}+x_{2}+x_{0}^{2}+x_{0}x_{1}+3x_{0}x_{2}+x_{1}^{2}\\G_{3}&=3x_{2}+x_{0}^{2}+3x_{1}^{2}+x_{1}x_{2}+3x_{2}^{2}\\\end{aligned}}}$

et le message ${\displaystyle M=(1,2,3)}$, alors on obtient le chiffré

${\displaystyle C=G(M)=(0,0,1)}$

Primitives à base de cryptographie multivariée

Schémas de chiffrement :

• Hidden field equations (HFE), et ses variantes HFE⁺, HFE⁻, HFE^v, HFE^f, et HFE^v−.
• Unbalanced oil and vinegar (UOV)

Schémas de signature :

• Sflash
• Quartz^[21]

Références

1. (en) Tsutomu Matsumoto et Hideki Imai, « Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption », Advances in Cryptology — EUROCRYPT ’88, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 25 mai 1988, p. 419–453 (ISBN 3540459618, DOI 10.1007/3-540-45961-8_39, lire en ligne, consulté le 28 février 2018)
2. (en) Jacques Patarin, « Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 », Advances in Cryptology — CRYPTO ’95, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 27 août 1995, p. 248–261 (ISBN 3540447504, DOI 10.1007/3-540-44750-4_20, lire en ligne, consulté le 28 février 2018)
3. (en) Jacques Patarin, « Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms », Advances in Cryptology — EUROCRYPT ’96, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 12 mai 1996, p. 33–48 (ISBN 3540683399, DOI 10.1007/3-540-68339-9_4, lire en ligne, consulté le 28 février 2018)
4. (en) Jean-Charles Faugère et Antoine Joux, « Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases », Advances in Cryptology - CRYPTO 2003, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 17 août 2003, p. 44–60 (ISBN 9783540406747, DOI 10.1007/978-3-540-45146-4_3, lire en ligne, consulté le 28 février 2018)
5. (en) Louis Granboulan, Antoine Joux et Jacques Stern, « Inverting HFE Is Quasipolynomial », Advances in Cryptology - CRYPTO 2006, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 20 août 2006, p. 345–356 (DOI 10.1007/11818175_20, lire en ligne, consulté le 28 février 2018)
6. (en) Aviad Kipnis et Adi Shamir, « Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization », Advances in Cryptology — CRYPTO’ 99, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 15 août 1999, p. 19–30 (ISBN 3540484051, DOI 10.1007/3-540-48405-1_2, lire en ligne, consulté le 28 février 2018)
7. (en) Luk Bettale, Jean-Charles Faugère et Ludovic Perret, « Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic », Designs, Codes and Cryptography, vol. 69, n^o 1,‎ 1^er octobre 2013, p. 1–52 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-012-9617-2, lire en ligne, consulté le 28 février 2018)
8. (en) Jeremy Vates et Daniel Smith-Tone, « Key Recovery Attack for All Parameters of HFE- », Post-Quantum Cryptography, Springer, Cham, lecture Notes in Computer Science,‎ 26 juin 2017, p. 272–288 (ISBN 9783319598789, DOI 10.1007/978-3-319-59879-6_16, lire en ligne, consulté le 28 février 2018)
9. (en) Nicolas T. Courtois, « The Security of Hidden Field Equations (HFE) », Topics in Cryptology — CT-RSA 2001, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 8 avril 2001, p. 266–281 (ISBN 3540453539, DOI 10.1007/3-540-45353-9_20, lire en ligne, consulté le 28 février 2018)
10. (en) Aviad Kipnis, Jacques Patarin et Louis Goubin, « Unbalanced Oil and Vinegar Signature Schemes », Advances in Cryptology — EUROCRYPT ’99, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 2 mai 1999, p. 206–222 (ISBN 354048910X, DOI 10.1007/3-540-48910-x_15, lire en ligne, consulté le 28 février 2018)
11. (en) Ryann Cartor, Ryan Gipson, Daniel Smith-Tone et Jeremy Vates, « On the Differential Security of the HFEv- Signature Primitive », Post-Quantum Cryptography, Springer, Cham, lecture Notes in Computer Science,‎ 24 février 2016, p. 162–181 (ISBN 9783319293592, DOI 10.1007/978-3-319-29360-8_11, lire en ligne, consulté le 28 février 2018)
12. (en) Albrecht Petzoldt, Ming-Shing Chen, Bo-Yin Yang et Chengdong Tao, « Design Principles for HFEv- Based Multivariate Signature Schemes », Advances in Cryptology -- ASIACRYPT 2015, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 29 novembre 2015, p. 311–334 (ISBN 9783662487969, DOI 10.1007/978-3-662-48797-6_14, lire en ligne, consulté le 28 février 2018)
13. (en) Jintai Ding et Dieter Schmidt, « Rainbow, a New Multivariable Polynomial Signature Scheme », Applied Cryptography and Network Security, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 7 juin 2005, p. 164–175 (DOI 10.1007/11496137_12, lire en ligne, consulté le 28 février 2018)
14. (en) An Braeken, Christopher Wolf et Bart Preneel, « A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes », Topics in Cryptology – CT-RSA 2005, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 14 février 2005, p. 29–43 (ISBN 9783540243991, DOI 10.1007/978-3-540-30574-3_4, lire en ligne, consulté le 28 février 2018)
15. (en) Koichi Sakumoto, Taizo Shirai et Harunaga Hiwatari, « On Provable Security of UOV and HFE Signature Schemes against Chosen-Message Attack », Post-Quantum Cryptography, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 29 novembre 2011, p. 68–82 (ISBN 9783642254048, DOI 10.1007/978-3-642-25405-5_5, lire en ligne, consulté le 28 février 2018)
16. (en) Nicolas T. Courtois, Magnus Daum et Patrick Felke, « On the Security of HFE, HFEv- and Quartz », Public Key Cryptography — PKC 2003, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 6 janvier 2003, p. 337–350 (ISBN 3540362886, DOI 10.1007/3-540-36288-6_25, lire en ligne, consulté le 28 février 2018)
17. (en) J. Ding et A. Petzoldt, « Current State of Multivariate Cryptography », IEEE Security Privacy, vol. 15, n^o 4,‎ 2017, p. 28–36 (ISSN 1540-7993, DOI 10.1109/msp.2017.3151328, lire en ligne, consulté le 28 février 2018)
18. (en) Mehdi-Laurent Akkar, Nicolas T. Courtois, Romain Duteuil et Louis Goubin, « A Fast and Secure Implementation of Sflash », Public Key Cryptography — PKC 2003, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 6 janvier 2003, p. 267–278 (ISBN 3540362886, DOI 10.1007/3-540-36288-6_20, lire en ligne, consulté le 28 février 2018)
19. (en) Vivien Dubois, Pierre-Alain Fouque, Adi Shamir et Jacques Stern, « Practical Cryptanalysis of SFLASH », Advances in Cryptology - CRYPTO 2007, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 19 août 2007, p. 1–12 (ISBN 9783540741428, DOI 10.1007/978-3-540-74143-5_1, lire en ligne, consulté le 28 février 2018)
20. (en) Charles Bouillaguet, Pierre-Alain Fouque et Gilles Macario-Rat, « Practical Key-Recovery for All Possible Parameters of SFLASH », Advances in Cryptology – ASIACRYPT 2011, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 4 décembre 2011, p. 667–685 (ISBN 9783642253843, DOI 10.1007/978-3-642-25385-0_36, lire en ligne, consulté le 28 février 2018)
21. (en) Jacques Patarin, Nicolas Courtois et Louis Goubin, « QUARTZ, 128-Bit Long Digital Signatures », Topics in Cryptology — CT-RSA 2001, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 8 avril 2001, p. 282–297 (ISBN 3540453539, DOI 10.1007/3-540-45353-9_21, lire en ligne, consulté le 28 février 2018)

• Portail de la cryptologie