Invitation à la soutenance de thèse de Luk Bettale

Bonjour,

J'ai le plaisir de vous inviter à ma soutenance de thèse intitulée:
"Cryptanalyse algébrique : outils et applications"

La soutenance aura lieu le Lundi 3 Octobre à 13h00 à l'UPMC (Jussieu),
Tour 25-26, 1er étage, salle 105 devant le jury suivant:

Jean-Claude Bajard, examinateur, professeur à l'UPMC,

Jean-Charles Faugère, directeur de thèse, directeur de recherche à l'INRIA,

Pierre-Alain Fouque, rapporteur, maître de conférences à l'ÉNS,

Jaime Gutierrez, rapporteur, professeur à l'Universidad de Cantabria,
Santander (Espagne),

Franck Landelle, examinateur, ingénieur à la DGA maîtrise de l'information,

Ludovic Perret, co-encadrant, maître de conférences à l'UPMC.

Vous êtes également invité au pot qui suivra.

résumé de la thèse (a summary in english is following):
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.

summary:
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.

Bien cordialement,

--
Luk Bettale