Thèse la Géométrie des Codes Matriciels et leurs Applications H/F - Institut Polytechnique de Paris École polytechnique

Établissement : Institut Polytechnique de Paris École polytechnique
École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris
Laboratoire de recherche : LIX - Laboratoire d'informatique
Direction de la thèse : Alain COUVREUR ORCID 0000000345546720
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-04-15T23:59:59

Ce projet de doctorat porte sur l'étude des codes en métrique rang, un domaine central de la théorie des codes qui se situe à l'interface entre algèbre, géométrie finie, combinatoire et cryptographie. Dans ce cadre, les mots de code sont représentés par des matrices sur des corps finis et la distance entre deux mots est mesurée par le rang de leur différence. Cette métrique permet de modéliser des erreurs structurées affectant des lignes, des colonnes ou des blocs de données entiers. Dans les dernières décennies, ces codes se sont avérés être des objets fondamentaux pour un large variété d'applications telles que le routage réseau (network coding), le stockage distribué et la cryptographie post quantique.
Le projet s'articule autour de deux objectifs principaux. Le premier consiste à approfondir l'étude géométrique des codes linéaires en métrique rang, en particulier des codes possédant des propriétés spécifiques de support, comme les codes intersectants. Malgré des avancées récentes, la construction de telles familles de codes au-delà des cas les plus simples reste largement ouverte. L'objectif est donc d'explorer de nouvelles approches, notamment en combinant des outils issus de la géométrie finie, de l'algèbre et de la théorie des représentations, afin de mieux comprendre la structure de ces codes et leurs propriétés. Une attention particulière sera également portée aux applications potentielles de ces objets en cryptographie, en s'inspirant des nombreuses utilisations des codes intersectants en métrique de Hamming.
Le second objectif du projet, plus exploratoire, vise à initier une étude géométrique systématique des codes matriciels en métrique rang, un domaine encore largement inexploré. L'idée est de développer un cadre géométrique dans lequel les objets associés aux codes matriciels seraient décrits en termes de familles de sous-espaces, plutôt que de points. Cette perspective pourrait permettre d'introduire de nouveaux invariants géométriques et d'étudier certaines classes particulières de codes, comme les codes minimaux ou intersectants dans le cas matriciel. Elle pourrait également offrir de nouveaux outils pour analyser des paramètres fondamentaux tels que le rayon de recouvrement.
La méthodologie du projet combinera analyse théorique et expérimentation informatique. Dans un premier temps, une étude approfondie de la littérature permettra de situer les questions ouvertes et d'identifier les approches les plus prometteuses. Parallèlement, des expérimentations seront menées à l'aide de logiciels de calcul formels, notamment SageMath, afin de construire des exemples, explorer des cas particuliers et formuler des conjectures. Ces observations guideront ensuite le développement de résultats théoriques, dans un dialogue constant entre intuition géométrique et formalisation mathématique.À travers cette approche, le projet vise à enrichir la compréhension des structures géométriques associées aux codes en métrique rang et à ouvrir de nouvelles directions de recherche à l'intersection entre théorie des codes, géométrie finie et cryptographie.

Un code en métrique rang est un ensemble de matrices sur un corps fini, où la distance entre deux matrices est mesurée par le rang de leur différence. Dans ce cadre, les erreurs ne sont pas comptées comme des fautes sur des symboles individuels, mais comme des modifications de la structure de la matrice, ce qui rend ces codes particulièrement adaptés à la correction d'erreurs affectant simultanément des lignes, des colonnes ou des blocs de données entiers. Les codes en métrique rang constituent un sujet central de la théorie des codes depuis leur introduction formelle par Delsarte en 1978 [De78]. Conçus initialement pour leur élégance mathématique et leurs liens avec les schémas d'association et l'algèbre linéaire, ces codes ont rapidement montré une polyvalence remarquable. Leur intérêt dépasse largement la théorie pure, trouvant des applications naturelles dans le routage réseau, le stockage distribué, la correction d'erreurs dites criss-cross et, plus récemment, en cryptographie post quantique. Une famille importante de codes optimaux pour la métrique rang sont les codes de Gabidulin [Ga85], qui constituent l'analogue en métrique rang des codes Reed-Solomon en métrique de Hamming. Les codes de Gabidulin sont construits en évaluant des polynômes linéaires de degré borné sur des ensembles de points linéairement indépendants, de la même manière que les codes Reed-Solomon sont définis en évaluant des polynômes ordinaires de degré borné sur des points distincts. Comme les codes Reed-Solomon, les codes de Gabidulin disposent d'un algorithme de décodage efficace, ouvrant la voie à des applications concrètes.
Le potentiel cryptographique des codes en métrique rang a été reconnu très tôt : en 1991, le premier système de cryptographie à clé publique basé sur les codes de Gabidulin a été proposé [GPT91]. Cependant, à l'époque, l'intérêt restait limité par rapport à des schémas codés plus établis. La situation a considérablement évolué avec l'avènement de la cryptographie post-quantique, où la résistance aux attaques par des algorithmes quantiques est devenue un critère central. Les codes en métrique rang, avec leurs hypothèses de difficulté différentes, sont apparus comme des candidats prometteurs. Actuellement plusieurs schémas de signature utilisant des codes en métrique rang sont en lice pour une possible standardisation.
Cet intérêt repose sur un avantage fondamental : les codes en métrique rang offrent une alternative attractive aux systèmes en métrique de Hamming, combinant une efficacité comparable en termes de bande passante à des propriétés structurelles ouvrant la voie à de nouvelles constructions cryptographiques. Parallèlement, la richesse mathématique de la métrique rang - reliant l'algèbre linéaire sur corps finis, la géométrie finie et la combinatoire - garantit que leur étude reste un domaine de recherche dynamique et fructueux. En ce sens, les codes en métrique rang occupent une position unique, au carrefour de la théorie des codes théorique et de la cryptographie appliquée, et leur exploration continue révèle de nouvelles perspectives, méthodes et applications.

Les principaux objectifs du projet peuvent être regroupés en deux grandes catégories :
A. Poursuivre l'étude géométrique des codes linéaires (ou vectoriels) en métrique rang, en approfondissant les problèmes ouverts présentés dans différents travaux sur le sujet.
B. Initier une étude géométrique systématique des codes matriciels en métrique rang.
Concernant l'objectif A, nous détaillons quelques développements clés :

A.1 Dans des études récentes sur les codes intersectants en métrique rang [BBMS25], le problème de constructions au-delà des cas les plus simples, qui impliquent des codes optimaux, reste essentiellement ouvert. Il est donc souhaitable de mener une investigation plus approfondie, nécessitant très certainement l'interaction avec des experts en géométrie finie, mais en appliquant aussi des méthodes issues de la théorie des représentations.
A.2 Les codes intersectants en métrique de Hamming ont de nombreuses applications, allant du partage de secret à l'empreinte digitale et aux protocoles de transfert inconscient (oblivious transfer). Récemment, un schéma de partage de secret basé sur les codes en métrique rang a été proposé [DBFH25]. Il serait donc intéressant d'explorer davantage les applications possibles des codes intersectants en métrique rang dans d'autres primitives cryptographiques avancées, en s'inspirant de ce travail et de ses analogues en métrique de Hamming.

Concernant l'objectif B, qui reste à ce jour complètement inexploré, plusieurs développements concrets sont envisagés :

B.1 Par analogie avec l'interprétation géométrique des codes additifs [BGL23], nous prévoyons de développer une perspective géométrique pour les codes matriciels. Cela consistera vraisemblablement à remplacer les points par des sous-espaces, de sorte que l'objet géométrique associé à un code matriciel soit une collection de sous-espaces. Une fois cette notion clarifiée, nous avons l'intention d'introduire le concept d'un code de Hamming associé et, en particulier, d'étudier les codes dont la distribution des poids est concentrée sur un petit nombre de valeurs, comme par exemple les codes à poids constant. Ces codes constituent le point de départ plus simple pour ensuite aborder une étude plus complexe.
B.2 Lié à B.1, mais en tant que développement supplémentaire, nous envisageons l'étude des codes avec des propriétés spécifiques de support, tels que les codes minimaux et intersectants, dans le cas matriciel - un domaine entièrement inexploré jusqu'à présent. Cela devrait avoir un impact aussi aux applications énoncées précédemment (en A.2.), mais dans le cas matriciel (il faudrait aussi clarifier quelle est le cadre le plus approprié).
B.3 Le rayon de recouvrement des codes matriciels a déjà été défini et étudié (voir par exemple [BR17]), mais une perspective géométrique ouvrirait une nouvelle voie pour l'étude du problème de recouvrement, probablement aussi fructueuse que dans des codes en métrique rang vectoriels (voir [BBB23]).

La méthodologie du projet combine analyse théorique, expérimentation informatique et confrontation avec la littérature existante, selon une approche progressive qui part des cas les plus structurés pour aller vers des contextes de plus en plus généraux. Le travail se développera dans une étroite intégration entre des outils d'algèbre, de géométrie finie et de combinatoire, avec un dialogue constant entre intuition géométrique et formulation formelle des résultats. Dans la première phase du projet, une étude approfondie de l'état de l'art sur les codes dans la métrique rang sera menée, avec une attention particulière aux développements récents de l'approche géométrique fondée sur les ensembles linéaires et sur les variétés projectives associées aux codes. Parallèlement, une activité d'expérimentation computationnelle sera lancée à l'aide de logiciels d'algèbre computationnelle (en particulier SageMath et Magma), visant à construire des exemples, à explorer des cas limites et à formuler des conjectures. La deuxième phase sera consacrée à l'étude des codes linéaires dans la métrique rang à l'aide d'invariants géométriques. Les résultats expérimentaux guideront la démonstration des premiers résultats théoriques, en partant de configurations simples et en augmentant progressivement le niveau de généralité. La troisième phase, de nature plus exploratoire, portera sur le développement d'un cadre géométrique pour les codes matriciels dans la métrique rang. Le plan de travail prévoit de commencer par l'étude de familles de sous-espaces de dimension fixée et de leur représentation par plongements projectifs, puis d'aborder des problèmes structurels tels que la minimalité, l'intersection des supports et le rayon de recouvrement. Étant donné le caractère innovant de cette partie, le travail progressera par étapes successives, avec des vérifications constantes de cohérence et de faisabilité. Tout au long du projet, les résultats seront confrontés à des applications potentielles en cryptographie post-quantique, garantissant la pertinence à la fois théorique et applicative du travail.

Le projet s'adresse à un(e) étudiant(e) possédant une solide formation en mathématiques et/ou en informatique théorique, avec un intérêt marqué pour l'algèbre, la combinatoire, la théorie des codes ou la cryptographie. Une bonne maîtrise des outils mathématiques fondamentaux (notamment en algèbre linéaire et en structures algébriques) est attendue, ainsi qu'une capacité à aborder des problèmes abstraits et à développer des raisonnements rigoureux.
Le/la candidat(e) devra également faire preuve de curiosité scientifique, d'autonomie et d'un goût pour la recherche fondamentale. Un intérêt pour l'interaction entre différentes disciplines mathématiques, en particulier entre théorie des codes, géométrie finie et cryptographie, sera particulièrement apprécié. Enfin, une motivation pour le travail collaboratif et les échanges scientifiques, ainsi qu'une ouverture à l'expérimentation computationnelle à l'aide d'outils d'algèbre computationnelle (par exemple Magma), constitueront des atouts importants pour mener à bien le projet de thèse.