Si la métrique rang est connue depuis longtemps, son application à la correction d'erreurs remonte seulement à la construction par Gabidulin en 1985 d'une famille de codes optimaux décodables en temps polynomial. Cette métrique convenait mieux que la métrique de Hamming à la description d'un canal où les vecteurs transmis sont des matrices, et les erreurs surviennent le long des lignes ou des colonnes, comme c'est le cas pour le stockage sur bande magnétique.

Depuis quelques années, elle connaît un très gros regain de popularité, dû à l'apparition du modèle de canal de transmission sans fils multiantennes en émission et/ou réception et dont l'information transmise est modélisable sous forme de matrices et le modèle d'erreur est modélisé par le rang des matrices.

Entre temps, à partir de 1991, on commença à l'utiliser dans la conception de primitives cryptographiques. Le principal intérêt cryptographique de cette métrique réside dans le fait que les algorithmes de décodage génériques sont de complexité significativement plus grande que leurs équivalents en métrique de Hamming, ce qui permet ainsi de diminuer la taille des clés publiques.

Dans un premier temps, nous dérivons des bornes sur l'existence de codes en métrique rang. En particulier, nous montrons qu'il n'existe pas de codes parfaits pour cette métrique. Nous déduisons un asymptotique de la distance rang minimale de codes dits "sur GV". Nous montrons que les problèmes de décodage sont reliés à des problèmes mettant en jeu un anneau non-commutatif de polynômes, les $q$-polynômes.

Après avoir introduit la famille des codes d'évaluation des $q$-polynômes (les codes de Gabidulin) pour laquelle existent des algorithmes de décodage en temps cubique, nous construisons un algorithme de décodage en temps quadratique. Pour ce faire, nous résolvons le problème du décodage en liste lorsque celle-ci a au plus un élément. Nous regardons également quel est l'effet produit par la projection des codes sur des sous-espaces.

Enfin nous présentons les deux types majeurs de cryptosystèmes utilisant la métrique rang :

• l'un, de type McEliece et ses évolutions qui conduisirent à la construction d'un système avec des arguments de sécurité contre les attaques par rejeu et par réaction.
• l'autre reposant sur la difficulté de résoudre le problème du décodage en liste des codes de Gabidulin au-delà de leur capacité de correction.

Parallèlement nous discutons du problème de la structure des codes employés et de la sécurité de ces systèmes contre des attaques récentes qui exploitent précisément cette structure.

La soutenance se déroulera devant le jury composé de :

Rapporteurs :

• M. Tom Hoeholdt, Technical University of Denmark (Danemark),
• M. Grigory Kabatiansky, IPPI (Russie),
• M. Gilles Zémor, Université de Bordeaux I.

Examinateurs

• M. Thierry Berger, Université de Limoges,
• M. Daniel Lazard, Université Paris 6,
• M. François Morain, Ecole Polytechnique,
• M. Nicolas Sendrier, INRIA Rocquencourt,
• M. Gilles Villard, INRIA Rhône-Alpes.