Projet ANR-12-BS02-0001 – CATREL : Cribles: Améliorations Théoriques et Résolution Effective du Logarithme
  Discret.
Programme : Blanc - SIMI 2 - Science informatique et applications (Blanc SIMI 2) 2012
Année de financement : 2012
Coordinateur du projet : Monsieur Emmanuel THOMÉ (Centre de Recherche INRIA Nancy Grand Est)
Partenaires : Inria Centre Nancy - Grand Est; Théorie Algorithmique des Nombres pour la Cryptologie; Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Montant : 673202.0 euros
Date de début : 2013
Durée : 36 mois
Résumé : Le calcul du logarithme discret (LD) dans les corps finis est un des problèmes sur lesquels s'ancre la sécurité d'une grande partie de la cryptographie moderne à clef publique. Les protocoles d'échange de clefs, par exemple, reposent sur la difficulté supposée de ce problème dans les corps finis. La cryptologie à base de couplages, qui a atteint sa maturité en l'espace de 10 ans, est un des autres contextes dans lequels ce problème est crucial.
Les algorithmes de résolution de LD dans les corps finis les plus performants actuellement sont le crible du corps de fonctions (Function Field Sieve -- FFS) et celui du crible algébrique (Number Fiels Sieve -- NFS). Le temps de calcul de ces algorithmes dits sous-exponentiels est difficile à prédire dans les faits : les estimations fournies par la théorie de la complexité ne fournissent pas de prédictions fiables. La difficulté des calculs est mieux démontrée par la pratique, par exemple en établissaant de nouveaux records. Alors que les algorithmes utilisés en factorisation d'entiers (NFS, encore lui) ont reçu beaucoup d'attention de la part des chercheurs, ce n'est pas le cas pour le LD. Le projet que nous proposons se promet d'étudier les aspects théoriques et pratiques de NFS-LD/FFS, accompagnés d'une implantation complète qui sera validée en pratique par de nouveaux records.
Le travail proposé est un des constituants principaux de l'évaluation de la sécurité des cryptosystèmes qui s'appuient sur la difficulté du problème LD dans les corps finis, qui permettra entre autres d'établir des tailles de clefs sûres. De tels choix sont rendus encore plus nécessaires par les efforts de standardisation de la cryptographie à base de couplages. Ce type de choix de sécurité ne peut se comprendre qu'à travers des doonées expérimentales, données que le projet se promet de fournir.
Des allers-retours entre algorithmique et implantation seront mutuellement bénéfiques. Les améliorations pratiques ne peuvent venir que d'études algorithmiques approfondies, algorithmes qui devront être eux-mêmes redéfinis pour plus de performances. Notre plan de travail vise à atteindre ces deux objectifs. Plus précisément, le contenu du projet est le suivant :
* Fournir des logiciels accessibles et polyvalents pour le LD.  Les nouvelles plateformes de travail, comme les GPU (\emph{graphics processing units}) et les FPGA (\emph{field-programmable gate arrays}) peuvent contribuer à des calculs de plusieurs façons décisives.
* Démontrer et faire la publicité de notre travail par de nouveaux records, qui seront des jalons très visibles, utilisables pour établir la sécurité réelle des cryptosystèmes basés sur le LD.
* Chercher à comprendre en profondeur les algorithmes NFS-LD et FFS et leurs applications à d'autres contextes.
Un but plus stratégique du projet est d'affirmer la position des auteurs comme étant des acteurs incontournables du sujet à l'échelon mondial.