Supervision : Jean-Charles FAUGÈRE

Co-supervision : PERRET Ludovic

Cryptanalyse algébrique : outils et applications

This thesis is about algebraic cryptanalysis, a technique consisting in modeling a cryptographic primitive with a system of multivariate polynomial equations. The goal is to solve it (or at least, estimate the difficulty). For the solving step, we use tools from computer algebra (Gröbner bases). A first direction was the modeling and preimage attacks on cryptographic hash fuctions. Our work allows to estimate that the cost of an algebraic preimage attack is lesser than the exhaustive search. We observe a better complexity than existing attacks. A second direction was the design and study of solving algorithms for finite fields. Our approach (hybrid approach) mixes exhaustive search and Gröbner bases computation. We give the precise asymptotic complexity of the approach, and we estimate the gain brought over classical methods (an exponential gain in the number of variables). The design of this approach is motivated by attacks on multivariate cryptosystems. Our results permit to show the weakness of parameters proposed for such schemes (for example the UOV scheme). We also studied HFE schemes and their generalization Multi-HFE. We give in this thesis a (practical) key recovery attack whose complexity is proved to be polynomial in the size of the ciphertext. Our attack shows that Multi-HFE schemes are less secure than original HFE schemes. Finally, we adapt our attack to attack several variants supposed to strengthen the schemes.

2009-2024 Publications

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