Description
Date depot: 1 janvier 1900
Titre: Calcul de Logarithmes Discrets dans les corps finis
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é:
Dans plusieurs articles récents, nous avons montré qu’il est possible d’améliorer grandement le calcul de logarithmes discrets dans certains corps finis. Le premier résultat concerne les corps finis contenant un sous-corps de taille moyenne et a permis d’établir deux nouveaux records de calcul sur des corps finis de taille respectives 1175 et 1425 bits. Ces deux corps sont de la forme GF(p^k) avec p premier et k valant respectivement 47 et 57.
Ce premier travail a d’ailleurs donné lieu à une adaptation en caractéristique 2 par une équipe de recherche irlandaise.
Le second résultat est une extension des idées initiales qui permet de travailler à partir d’un sous-corps nettement plus petit (de taille logarithmique et non plus sous-exponentielle en fonction du corps considéré). Cela conduit à des améliorations importantes, à la fois sur le plan pratique et sur celui de la complexité asymptotique. En effet, grâce à ces techniques, il devient pour la première fois possible d’obtenir un algorithme de calcul de logarithmes discrets dans certains corps finis de complexité inférieure à L(1/3) (i.e. exp(log(N)^(1/3)*log(log(n))^(2/3)) où N est la cardinalité du corps étudié). Plus précisément, l’algorithme obtenu a dans un premier temps atteint une complexité heuristique en L(1/4+epsilon), pour un epsilon arbitrairement petit. Puis, en collaboration avec le Loria, il a été amélioré pour atteindre une complexité asymptotique quasi-polynomiale.
Compte-tenu du rôle important joué par le problème du logarithme discret en cryptographie à clef publique, approfondir et étendre ces résultats est à la fois un axe de recherche important pour le laboratoire et un projet de thèse ambitieux.
{{Programme de Travail}}
L’objectif de la thèse sera d’étendre ces résultats dans plusieurs directions. En premier lieu, sur le plan théorique, il est important de pouvoir établir plus précisément la structure précise de tous les corps finis concernés par cet algorithme. La version actuelle de l’algorithme n’atteint en effet sa meilleure complexité que pour une caractéristique très petite, avec la condition supplémentaire de trouver une représentation du corps fini ayant une structure très particulière. Dans un premier temps, on s’attachera à prouver qu’il est effectivement possible de construire les représentations désirées pour des corps arbitraire, en raffinant ou en supprimant les arguments heuristiques actuellement utilisés pour prédire l’existence de ces bonnes représentations.
Pour la suite, il semble naturel de combiner cette nouvelle approche avec la notion de bases elliptiques introduites par Lercier et Couveignes dans pour améliorer des algorithmes de logarithmes discrets d’une génération précédente. Cela permettrait d’accélérer notablement la phase initiale de l’algorithme, celle qui calcule les logarithmes des éléments de la base de lissité.
Sur le plan pratique, la réalisation de calculs représentatifs permettra de cerner les retombées précises sur les systèmes cryptographiques actuels. En particulier, l’impact sur les systèmes utilisant des couplages en caractéristiques 2 et 3 devra être étudié. De plus, ces calculs permettront d’améliorer les choix de paramètres et, en conséquence, autoriseront de nouveaux records de calcul.
Dans une autre direction, il sera intéressant de voir si une partie des idées fonctionnant en petite caractéristique serait applicable en caractéristique plus grande. A l’extrême, obtenir un progrès de même envergure sur le number field sieve serait de nature à remettre en cause une grande partie des systèmes de chiffrement à clef publique actuellement existants. Pour l'instant, nous avons pu obtenir que des résultats partiels qui améliore seulement la seconde constant de la complexité du NFS et ceux dans un cas restrictif de caractéristiques 'spéciales'.
Cette partie de la thèse est celle qui présente le plus de difficultés, mais aussi celle dont les retombées auraient le plus de conséquences. Les difficultés sont dues au fait que de nombreux aspects de l’algorithme actuellement proposé reposent fondamentalement sur la petitesse de la caractéristique du corps considéré. Par exemple, les équations sont générées à partir de la factorisation systématique d’un polynôme de la forme X^q-X où q est une puissance de la caractéristique. Lorsque celle-ci devient grande, il n’est plus possible de manipuler de tel polynômes efficacement. De plus, la taille de la base de lissité utilisée est une puissance de q. Malgré tout, certaines des idées, comme l’utilisation d’homographies pour démultiplier des relations entre polynômes restent utilisables et pourraient permettre de nouvelles avancées. Il est intéressant de noter, qu’historiquement, toutes les avancées sur le problèmes du logarithme discret en caractéristique petite, ont finis par se généraliser, au prix d’une complexité théorique parfois important, au logarithme discret en grande caractéristique et à la factorisation.
Enfin,
Doctorant.e: Pierrot Cecile