Date de l'exposé : 21 novembre 2018
Soutenance de thèse (exceptionnellement mercredi à 13h30 en salle Petri-Turing à l'IRISA): Algorithmes d'algèbre linéaire pour la cryptographie
Dans cette thèse, nous discutons d’aspects algorithmiques de trois
différents problèmes, en lien avec la cryptographie.
La première partie est consacrée à l’algèbre linéaire creuse. Nous
y présentons un nouvel algorithme de pivot de Gauss pour matrices
creuses à coefficients exacts, ainsi qu’une nouvelle heuristique de
selection de pivots, qui rend l’entière procédure particulièrement
efficace dans certains cas.
La deuxième partie porte sur une variante du problème des anniversaires,
avec trois listes. Ce problème, que nous appelons problème 3XOR,
consiste
intuitivement à trouver trois chaînes de caractères uniformément
aléatoires de longueur fixée, telles que leur XOR soit la chaîne nulle.
Nous discutons des considérations pratiques qui émanent de ce problème
et proposons un nouvel algorithme plus rapide à la fois en théorie et
en pratique que les précédents.
La troisième partie est en lien avec le problème Learning With Errors
(LWE). Ce problème est connu pour être l’un des principaux problèmes
difficiles sur lesquels repose la cryptographie à base de réseaux
euclidiens. Nous introduisons d’abord un générateur pseudo-aléatoire,
basé sur la variante dé-randomisé Learning With Rounding de LWE, dont
le temps d’évaluation est comparable avec celui d’AES. Dans un second
temps, nous présentons une variante de LWE sur l’anneau des entiers.
Nous montrerons que dans ce cas le problème est facile à résoudre et
nous proposons une application intéressante en re-visitant une attaque
par canaux auxiliaires contre le schéma de signature BLISS.
