100, rue des maths 38610 Gières / GPS : 45.193055, 5.772076 / Directeur : Thierry Gallay

Interpolation polynomiale multivariée, codes et cryptographie.

Mercredi, 5 Avril, 2006 - 16:30
Prénom de l'orateur : 
Philippe
Nom de l'orateur : 
GABORIT
Résumé : 

Dans cet exposé nous nous intéressons à  l'interpolation polynomiale
multivariée et à  ses applications. Nous présenterons tout d'abord des
applications connues comme le décodage en liste des codes de Reed-Solomon (pour lequel Madhu Sudan a recu le prix Nevanlinna), mais aussi des applications nouvelles comme le décodage en liste des effacements des codes de Reed-Muller ou encore l'application au calcul de l'immunité algébrique. Ce dernier concept a de très fortes applications en cryptographie pour contrer les attaques algébriques qui récemment ont permis d'obtenir des attaques très efficaces sur les registres linéaires filtrés, utilisés pour le chiffrement à  flot ou sur certains systèmes à  clé symétrique. Ensuite nous présenterons un nouvel algorithme qui permet d'effectuer l'interpolation polynomiale multivariée à  plusieurs variables en temps quadratique, améliorant la complexité cubique connue jusqu'ici pour résoudre certains des problèmes précédents.

Il s'agit d'un travail en commun avec O. Ruatta

Institution de l'orateur : 
Laco, Université de Limoges
Thème de recherche : 
Théorie des nombres
Salle : 
04
logo uga logo cnrs