Description
Date depot: 1 janvier 1900
Titre: Calcul d'indice et nombre de classes d'Arakelov, calcul effectif et applications cryptographiques
Directeur de thèse:
Antoine JOUX (CISPA Helmholtz Center for Information Sec)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
L’une des voies privilégiées pour la construction de cryptosystèmes à clef publique est l’utilisation dans des groupes finis de l’exponentiation discrète, dont le problème inverse, celui du logarithme discret est réputé difficile. Plusieurs groupes sont classiquement utilisés, le groupe multiplicatif de corps finis ou la Jacobienne de courbes algébriques définies sur des corps finis. Le groupe de classe de corps de nombre est un autre candidat qui a parfois été proposé. Pour étudier sa viabilité, il est important de bien cerner la difficulté pour ce type de groupe de déterminer sa cardinalité, sa structure et la difficulté éventuelle du problème du logarithme discret. Ces problèmes ont été partiellement étudiés dans les années 1990 par le groupe de recherche de J. Buchmann. Plus récemment, René Schoof, l’inventeur de la méthode de comptage de points qui a permis l’utilisation des courbes elliptiques en cryptographie, vient de proposer une nouvelle approche pour améliorer les algorithmes permettant de déterminer la structure d’un groupe de classe en utilisant un objet mathématique un plus riche, le groupe de classe (orienté) d’Arakelov. En l’état actuel des choses, cet algorithme mathématique n’est pas présenté sous une forme suffisamment effective pour en permettre l’utilisation en cryptographie.
Le but principal de la thèse sera donc de rendre effectif cet algorithme afin de pouvoir réaliser la détermination de la structure de groupe suffisamment gros pour être utilisable en cryptographie. On recherchera également des améliorations théoriques et pratiques de l’algorithme et on considérera également son utilisation pour le calcul d’indice dans ces groupes.
Quand on considère des corps de nombres, c’est à dire des extensions algébriques du corps des rationnels, deux structures intéressantes apparaissent naturellement, le groupe des éléments unités et celui des idéaux. Ces groupes sont infinis et donc, a priori, difficiles à manipuler de façon explicite. Toutefois, il existe des structures finies intéressantes permettant de représenter l’essentiel de la structure. Pour le groupe des unités, on sait qu’il possède un ensemble fini de générateurs, on peut donc légitimement se poser la question de déterminer un tel ensemble. La difficulté principale réside dans le fait que les coefficients qui interviennent pour exprimer les unités appartenant à cet ensemble de générateurs peuvent être très grands. Il faut donc disposer de méthodes les plus efficaces possibles pour les manipuler. De l’autre côté, pour le groupe des idéaux, on peut obtenir un groupe fini, appelé groupe de classe en quotientant par le sous-groupe des idéaux principaux.
Parmi les corps de nombres, le cas des corps quadratiques est un cas simple assez représentatif. Il se divise en deux sous cas, celui des corps quadratiques imaginaires pour lequel le groupe des unités est dégénéré et le nombre de classes plutôt grand et celui des corps quadratiques réels pour lesquels le nombre de classes est petit alors que la structure des unités est plus complexe. Traditionnellement, on a donc deux algorithmes différents pour traiter ces deux cas. Pour le calcul des unités, on dispose de l’algorithme « d’infrastucture » de Shanks qui manipule des objets dans une structure proche de celle d’un groupe. Pour le calcul du nombre de classes (la cardinalité du groupe de classes) et la structure du groupe de classe, on utilise un algorithme dû à J. Buchmann, qui s’apparente par certains côtés au Number Field Sieve utilisé pour la factorisation et le calcul de logarithme discret. Le fait de disposer de deux algorithmes bien distincts devient problématique pour les corps de nombres de degré plus élevé pour lesquels on a à la fois un groupe de classes complexe et un groupe des unités non trivial.
Dans [1], Schoof présente un référentiel mathématique permettant de gérer simultanément les informations relatives à ces deux types d’objets et offre donc la possibilité de traiter des corps de degré d’extension plus élevé. Ce référentiel est celui de la théorie d’Arakelov. La première partie de cette thèse consistera à comprendre les objets mathématiques utilisés et à les manipuler de façon effective dans de petits exemples.
Cette compréhension initiale permettra de faire ressortir les difficultés inhérentes à cet algorithme et, en particulier, de mieux comprendre l’enjeu en termes de précision numérique des calculs apporté par la gestion des unités. Idéalement, cela devrait conduire à déterminer la complexité algorithmique de l’approche proposée par Schoof en nombre d’opérations élémentaires (et non pas en nombre d’opérations arithmétiques à précision infinie). Pour cela, il faudra se poser la question de trouver une représentation la plus efficace possible permettant la manipulation algorithmique des diviseurs d’Arakelov orientés.
A l’issue de cette première partie, il sera possible de réaliser une implantation efficace de l’algorithme de Schoof
Doctorant.e: Gelin Alexandre