Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Cribles: Améliorations Théoriques et Résolution Effective du Logarithme Discret. – CATREL

CATREL

Cribles : Améliorations Théoriques et Résolution Effective du Logarithme discret

Enjeux et objectifs

Étude et amélioration des algorithmes de logarithme discret sur les corps finis. La difficulté de ce problème est cruciale pour l'évaluation de la sécurité de nombreux cryptosystèmes.

Crible algébrique, algorithmique, programmation, optimisation logicielle.

Les publications du projet sont en ligne:

catrel.loria.fr/publications.fr.html

Le projet a pour vocation de produire de nouveaux algorithmes, ainsi que d'établir de nouveaux calculs faisant référence pour l'appréciation de l''etat de l'art sur le problème..

Les publications du projet sont en ligne:

catrel.loria.fr/publications.fr.html

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.

Coordination du projet

Emmanuel THOMÉ (Centre de Recherche INRIA Nancy Grand Est) – Emmanuel.Thome@gmail.com

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

INRIA Centre de Recherche INRIA Nancy Grand Est
Centre de Recherche Inria Saclay-Ile-de-France - équipe projet TANC Institut National de Recherche en Informatique et en Automatiques - Centre de Recherche Inria Saclay-Île-de-France équipe TANC
CNRS - LIRMM Laboratoire d'informatique, de robotique et de microéléctronique de Montpellier

Aide de l'ANR 673 202 euros
Début et durée du projet scientifique : décembre 2012 - 36 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter