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
modifierLe 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], HFEv−[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
modifierOn fixe un corps fini , la clé publique est donnée par un ensemble :
où chaque . Un message clair correspond à une suite , et le chiffrement consiste simplement à évaluer chaque polynôme de la clé publique en ce point:
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 , noté généralement . Ce moyen est spécifique au chiffrement multivarié considéré, et c'est souvent en étudiant la manière dont 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 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 au lieu de , 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
modifierPour illustrer le fonctionnement sur un exemple simple (tiré du cryptosystème d'Imai-Matsumoto), on se place dans le corps , qui possède 4 éléments , que l'on va noter respectivement . Supposons la clé publique donnée par
et le message , alors on obtient le chiffré
Primitives à base de cryptographie multivariée
modifierSchémas de chiffrement :
- Hidden field equations (HFE), et ses variantes HFE+, HFE−, HFEv, HFEf, et HFEv−.
- Unbalanced oil and vinegar (UOV)
Schémas de signature :
- Sflash
- Quartz[21]
Références
modifier- (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, , p. 419–453 (ISBN 3540459618, DOI 10.1007/3-540-45961-8_39, lire en ligne, consulté le )
- (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, , p. 248–261 (ISBN 3540447504, DOI 10.1007/3-540-44750-4_20, lire en ligne, consulté le )
- (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, , p. 33–48 (ISBN 3540683399, DOI 10.1007/3-540-68339-9_4, lire en ligne, consulté le )
- (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, , p. 44–60 (ISBN 9783540406747, DOI 10.1007/978-3-540-45146-4_3, lire en ligne, consulté le )
- (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, , p. 345–356 (DOI 10.1007/11818175_20, lire en ligne, consulté le )
- (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, , p. 19–30 (ISBN 3540484051, DOI 10.1007/3-540-48405-1_2, lire en ligne, consulté le )
- (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, no 1, , p. 1–52 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-012-9617-2, lire en ligne, consulté le )
- (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, , p. 272–288 (ISBN 9783319598789, DOI 10.1007/978-3-319-59879-6_16, lire en ligne, consulté le )
- (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, , p. 266–281 (ISBN 3540453539, DOI 10.1007/3-540-45353-9_20, lire en ligne, consulté le )
- (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, , p. 206–222 (ISBN 354048910X, DOI 10.1007/3-540-48910-x_15, lire en ligne, consulté le )
- (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, , p. 162–181 (ISBN 9783319293592, DOI 10.1007/978-3-319-29360-8_11, lire en ligne, consulté le )
- (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, , p. 311–334 (ISBN 9783662487969, DOI 10.1007/978-3-662-48797-6_14, lire en ligne, consulté le )
- (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, , p. 164–175 (DOI 10.1007/11496137_12, lire en ligne, consulté le )
- (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, , p. 29–43 (ISBN 9783540243991, DOI 10.1007/978-3-540-30574-3_4, lire en ligne, consulté le )
- (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, , p. 68–82 (ISBN 9783642254048, DOI 10.1007/978-3-642-25405-5_5, lire en ligne, consulté le )
- (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, , p. 337–350 (ISBN 3540362886, DOI 10.1007/3-540-36288-6_25, lire en ligne, consulté le )
- (en) J. Ding et A. Petzoldt, « Current State of Multivariate Cryptography », IEEE Security Privacy, vol. 15, no 4, , p. 28–36 (ISSN 1540-7993, DOI 10.1109/msp.2017.3151328, lire en ligne, consulté le )
- (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, , p. 267–278 (ISBN 3540362886, DOI 10.1007/3-540-36288-6_20, lire en ligne, consulté le )
- (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, , p. 1–12 (ISBN 9783540741428, DOI 10.1007/978-3-540-74143-5_1, lire en ligne, consulté le )
- (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, , p. 667–685 (ISBN 9783642253843, DOI 10.1007/978-3-642-25385-0_36, lire en ligne, consulté le )
- (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, , p. 282–297 (ISBN 3540453539, DOI 10.1007/3-540-45353-9_21, lire en ligne, consulté le )