logo EDITE Sujets de doctorat

Calcul d'indice et nombre de classes d'Arakelov, calcul effectif et applications cryptographiques

Sujet proposé par
Directeur de thèse:
Doctorant: Alexandre GELIN
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

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 et de réaliser des calculs de grande taille avec cette implantation. Par exemple, on pourra tenter de battre les records de calcul de groupe de classes pour des corps quadratique imaginaire et de calcul de régulateur pour des corps quadratiques réels. L’étape suivante sera bien sûr de considérer des corps de degré plus élevé, restant à définir en fonction des propriétés de l’implantation.

Une fois cette base consolidée, la suite de la thèse visera à améliorer d’un point de vue à la fois pratique et théorique, les algorithmes utilisant le groupe de classe d’Arakelov et leur spectre d’application. Les extensions possibles sont nombreuses. Par exemple, on pourra considérer l’utilisation de ces méthodes pour tenter d’améliorer les cryptanalyses du système de chiffrement NICE, qui travaille dans « l’infrastructure » des unités d’un corps quadratique réel. On pourra aussi considérer les extensions de l’échange de clef de Diffie-Hellman basées sur les groupes de classes de corps quadratique imaginaires. Pour cela, il faudra étudier la possibilité d’utiliser une variante de l’algorithme de Schoof pour le calcul d’indice dans ces groupes.

Un autre problème plus théorique et, sans doute, beaucoup plus ambitieux et difficile est de trouver une variante de ces algorithmes disposant d’une complexité sous-exponentielle de complexité similaire à celle de la factorisation d’entiers, c’est à dire en L(1/3). L’obstacle majeur pour cela est de trouver une représentation du corps de nombres considéré (et fixe) qui permettent une chute de la complexité en faisant apparaitre des coefficients plus petits dans les polynômes utilisés pour la description du corps de nombres, quitte bien sûr à faire croître leur degré.

Enjeux

Mise en oeuvre algorithmique effective de la méthode proposée par Schoof. Recherche d'une version en L(1/3).