Geométrie algébrique et théorie des codes pour la cryptographie – Manta

Cette proposition vise à étudier les codes correcteurs algébriques
construits à l’aide de théories mathématiques avancées (géométrie
algébrique, théorie des nombres), et à explorer de nouveaux champs
d'application en cryptographie à clé publique, calcul multipartite,
et en informatique théorique (complexité algorithmique) où de
nombreuses questions nouvelles et pertinentes sont soulevées.

Les questions théoriques que nous étudierons en théorie algébrique des
codes seront principalement celles qui auront des applications dans
ces domaines, et notre approche consistera à faire appel à des objets
et méthodes issus de la géométrie algébrique et de la théorie des
nombres pour aborder les problèmes de manière plus mathématique et
élaborée qu'ils ne le sont en général en cryptographie, en théorie des
codes, en informatique théorique, etc.

Notre structurations en trois tâches est simple :
propriétés multiplicatives des codes (tâche "computing", 25% de
l'activité), nouveaux problèmes de décodage (tâche "decoding", 25% de
l'activité, applications en théorie de la complexité), géométrie
algébrique pour étudier des familles plus larges de codes (tâche
"geometry", 50% de l'activité).

La tâche "computing", qui a des applications en "calcul multipartite",
en complexité algébrique, en cryptanalyse du système de McEliece,
s'intéresse aux propriétés multiplicatives des
codes. Il s'agit d'étudier les propriétés des codes sous le produit
terme-à-terme de leurs composantes. Ces considérations ont été
introduites par Chudnovsky et Chudnoksy pour étudier la
complexité bilinéaire de la multiplication sur les corps finis, mais
d'aautres applications, comme celles
citées précédemment, sont apparues. Ces propriétés multiplicatives peuvent
s'étudier avec les méthodes de la théorie additive des nombres.

La tâche "decoding" étudie de nouvelles problématiques de décodage
(décodage en liste, décodage local). Le décodage en liste a connu
plusieurs percées importantes depuis 15 ans, notamment le décodage des
codes de Reed-Solomon "repliés" (Folded), et la généralisation à des
courbes de genre différent de zéro est prometteuse. De même le
décodage local repose sur des constructions de codes en dimension
supérieure à deux, mais seul l'espace affine a été considéré en
standard. Nous proposons donc de considérer des variétés plus riches
(variétés toriques, variétés rationnellement connexes) dans le but de
construire de meilleurs codes localement décodables.

La tâche "geometry" propose d'une part des voies de recherches
nouvelles en théorie des codes (codes sur les variétés de dimension
supérieure, codes en famille, variétés rationnellement connexes). Il
ne fait d’autre part aucun doute que ceds problèmes récents de
théorie des codes sont reliés à de nouvelles questions purement
géométriques ou arithmétiques, comme l’a déjà été durant ces
dernières décennies la constructions de tours de corps de fonctions
asymptotiquement bonnes. Un des objectifs, plus exploratoire, de cette
tâche sera d’effectuer un travail de "traduction" de problèmes
provenant de l’informatique en des problèmes géométriques ou
arithmétiques, puis d’avancer sur ces nouveaux
problèmes.

Ces trois tâches sont interconnectées. Afin d’assurer une bonne
circulation des idées, nous organiserons deux retraites francophones
les deux premières années, et la troisième année, une école de jeunes
chercheurs internationale, six mois avant le colloque ACGT 2019, où
nous espérons présenter nos résultats post-manta. De manière plus
régulière, les membres non parisiens du projet viendront une fois par
mois aux séminaires de Télécom Paris Tech ou de l'INRIA.

Notre groupe, de taille importante, rassemble des mathématiciens
spécialistes en arithmétique, en géométrie et en combinatoire, ainsi
que des codeurs et des cryptographes.