BETTALE Luk

Docteur
Équipe : SALSA
Date de départ : 31/12/2011
https://lip6.fr/Luk.Bettale

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.

Soutenance : 03/10/2011

Membres du jury :

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

Date de départ : 31/12/2011

Publications 2009-2023

Mentions légales
Carte du site