Direction de recherche : Jean-Charles FAUGÈRE

Co-encadrement : PERRET Ludovic

Cryptanalyse algébrique : outils et applications

Cette thèse traite de la cryptanalyse algébrique qui consiste à modéliser une primitive cryptographique en un système d'équations polynomiales en plusieurs variables dans le but de le résoudre (ou au moins d'en estimer la difficulté). Pour la résolution, nous utilisons des outils provenant du calcul formel (bases de Gröbner). Un première axe a été la modélisation et la recherche d'antécédents sur des fonctions de hachages cryptographiques. Nos travaux permettent d'estimer que le coût d'une recherche d'antécédent est inférieure à la recherche exhaustive pour les fonctions les plus courantes. Nous observons même une meilleure complexité que les attaques existantes. Un deuxième axe a été la conception et l'étude d'algorithmes qui tirent parti du contexte d'application (corps finis). Notre méthode mélange l'énumération exhaustive des éléments du corps avec le calcul de bases de Gröbner. Nous donnons une étude fine de sa complexité et nous quantifions le gain apporté (un gain exponentiel en le nombre de variables). La conception de ces algorithmes est motivée par l'attaque de cryptosystèmes multivariés. Nos résultats permettent de montrer la faiblesse de certains paramètres proposés (pour le schéma UOV par exemple). Nous analysons également les schémas HFE et leurs généralisations Multi-HFE. Nous donnons dans cette thèse une attaque en recouvrement de clé qui est polynomiale en la taille du chiffré. Notre attaque permet aussi de montrer que les schémas Multi-HFE sont moins sûrs que les schémas HFE originels. Enfin, nous donnons des adaptations qui permettent d'attaquer aussi les variantes sensées renforcer le schéma.

Publications 2009-2024

• 2024
  • L. Bettale, D. Kahrobaei, L. Perret, J. Verbel : “Biscuit: New MPCitH Signature Scheme from Structured Multivariate Polynomials”, Applied Cryptography and Network Security (ACNS), vol. 14583, Lecture Notes in Computer Science, Abu Dhabi, United Arab Emirates, pp. 457-486, (Springer Nature Switzerland) (2024)
• 2023
  • L. Bettale, L. Perret, D. Kahrobaei, J. Verbel : “Biscuit: Shorter MPC-based Signature from PoSSo”, (2023)
• 2013
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic”, Designs, Codes and Cryptography, vol. 69 (1), pp. 1-52, (Springer Verlag) (2013)
• 2012
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Solving Polynomial Systems over Finite Fields: Improved Analysis of the Hybrid Approach”, ISSAC 2012 - 37^th International Symposium on Symbolic and Algebraic Computation, Grenoble, France, pp. 67-74, (ACM) (2012)
• 2011
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Cryptanalysis of Multivariate and Odd-Characteristic HFE Variants”, Public Key Cryptography - PKC 2011, vol. 6571, Lecture Notes in Computer Science, Taormina, Italy, pp. 441-458, (Springer Berlin / Heidelberg) (2011)
• 2010
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Hybrid Approach : a Tool for Multivariate Cryptography”, Tools'10: Proceedings of the Workshop on Tools for Cryptanalysis 2010, London, United Kingdom, pp. 15-23, (Ecrypt II) (2010)
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Hybrid approach for solving multivariate systems over finite fields”, Journal of Mathematical Cryptology, vol. 3 (3), pp. 177-197, (De Gruyter) (2010)
• 2009
  • L. Bettale, J.‑Ch. Faugère, L. Perret : “Security Analysis of Multivariate Polynomials for Hashing”, Information Security and Cryptology: 4^th International Conference, Inscrypt 2008, Revised Selected Papers, vol. 5487, Lecture Notes in Computer Science, Beijing, China, pp. 115-124, (Springer-Verlag) (2009)