Détail d'une fiche   Version PDF

CARAMEL (SR0449PR)

Cryptologie, Arithmétique : Matériel et Logiciel

CARAMEL (SR0435BR) →  CARAMEL →  CARAMBA (SR0730NR)


Statut: Terminée

Responsable : Pierrick Gaudry

Mots-clés de "A - Thèmes de recherche en Sciences du numérique - 2023" : Aucun mot-clé.

Mots-clés de "B - Autres sciences et domaines d'application - 2023" : Aucun mot-clé.

Domaine : Algorithmique, programmation, logiciels et architectures
Thème : Algorithmique, calcul formel et cryptologie

Période : 01/01/2011 -> 31/12/2015
Dates d'évaluation : 24/03/2011 , 17/03/2015

Etablissement(s) de rattachement : CNRS, U. DE LORRAINE
Laboratoire(s) partenaire(s) : LORIA (UMR7503)

CRI : Centre Inria de l'Université de Lorraine
Localisation : Centre Inria de l'Université de Lorraine
Code structure Inria : 051090-1

Numéro RNSR : 201020971F
N° de structure Inria: SR0449PR

Présentation

Un mot-clef général qui pourrait résumer la plupart de nos objectifs de recherche est arithmétique. En effet, dans la proposition CARAMEL, le but est de repousser les possibilités pour le calcul efficace avec des objets ayant une nature arithmétique. Ceci inclut les nombres entiers, les nombres réels et complexes, les polynômes, les corps finis, et last but not least les courbes algébriques.
Nos domaines d'application principaux sont la cryptographie à clef publique et les systèmes de calcul formel. En ce qui concerne la cryptographie, nous nous concentrons sur l'étude des primitives s'appuyant sur le problème de la factorisation ou du logarithme discret dans les corps finis ou les (jacobiennes de) courbes algébriques. À la fois les aspects constructifs et destructifs sont étudiés. Pour les applications au calcul formel, nous nous intéressons principalement aux briques de bases de l'arithmétique que sont les entiers, les nombres flottants, les polynômes et les corps finis. De plus, des fonctionnalités plus évoluées telles que la factorisation ou le calcul de log discret sont en général souhaitées dans les systèmes de calcul formel.
Comme nous développons notre expertise à tous les niveaux, depuis l'implantation matérielle ou logicielle de briques de base au plus bas niveau jusqu'à des algorithmes haut-niveau compliqués tels que la factorisation ou le comptage de points, nous avons remarqué qu'il est souvent trop naïf de vouloir les séparer: nous pensons que les interactions entre les algorithmes de bas niveau et de haut niveau sont de la plus grande importance pour les applications arithmétiques, et peuvent des améliorations substantielles qui n'auraient pas pu voir le jour avec une vision compartimentée.

Axes de recherche

Nous avons trois directions principales de recherche:
  • Factorisation et calcul de logarithme discret dans les corps finis
    Nous sommes particulièrement intéressés par l'algorithme du crible algébrique (ou number field sieve, NFS), qui est le meilleur algorithme connu pour factoriser des grands entiers comme les clefs RSA et pour résoudre le problème du logarithme discret dans les corps finis premiers. Un algorithme cousin, le crible de corps de fonctions (FFS) est le meilleur algorithme connu pour calculer des logarithmes discrets dans les corps finis de petite caractéristique. Dans tous ces cas, nous comptons améliorer les algorithmes existants, avec un point de vue pratique, afin de pouvoir établir de nouveaux records.
  • Courbes algébriques et cryptographie
    sur ce sujet, nous nous intéressons principalement à deux domaines: la cryptographie utilisant les courbes de genre 2 et l'arithmétique des couplages, dans les deux cas d'un point de vue constructif. Pour les courbes de genre 2, a outil algorithmique que nous souhaitons développer est la calcul d'isogénies explicites; cela fournira un outil algorithmique pour divers calculs liés à la cryptographie tels que le comptage de points en grande caractéristique, la construction par multiplication complexe ou le calcul d'anneaux d'endomorphismes. En ce qui concerne les couplages, notre objectif est d'optimiser les calculs, en particulier en matériel ou en environnement contraint. Nous développerons des outils automatiques pour aider à choisir la courbe (hyper-)elliptique la plus adaptée et générer du matériel efficace pour un niveau de sécurité et un ensemble de contraintes donnés.
  • Arithmétique
    L'arithmétique des entiers, des corps finis et des polynômes est omniprésente dans nos recherches. Nous la considérons pas seulement comme un outil pour d'autres algorithmes, mais bien comme un thème de recherches en soi. Nous nous intéressons aux avancées algorithmiques, en particulier pour les très grandes tailles pour lesquelles les algorithmes asymptotiquement rapides deviennent pertinents en pratique. Nous gardons aussi une importante activité d'implantation, à la fois en logiciel et en matériel.

Relations industrielles et internationales

  • Collaboration à long terme avec Richard Brent (Canberra, Australia) sur l'arithmétique efficace.
  • Collaboration à long terme avec Eric Schost (London, Ontario, Canada) sur le comptage de points en genre 2.
  • Collaboration avec Arjen Lenstra et Thorsten Kleinjung (Lausanne, Switzerland) sur la factorisation d'entiers
  • Co-encadrement d'un doctorant avec Tanja Lange (Eindhoven, Netherlands)
  • Collaboration avec Francisco Rodríguez-Henríquez (Mexico) sur les calculs de couplages