PhD graduated
Team : PolSys
Departure date : 09/30/2012

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.

Defence : 10/03/2011

Jury members :

Jean-Claude Bajard, professeur UPMC
Jean-Charles Faugère, directeur de recherche INRIA
Pierre-Alain Fouque, maître de conférences ENS [Rapporteur]
Jaime Gutierrez, professeur Universidad de Cantabria, Santander (Espagne) [Rapporteur]
Franck Landelle, ingénieur DGA maîtrise de l'information
Ludovic Perret, maître de conférences UPMC

Departure date : 09/30/2012

2009-2024 Publications