Interpolation polynomiale multivariée, codes et cryptographie.

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