Soutenance de thèse d'Arthur HERLEDAN LE MERDY

Membres du jury:

Christophe PETIT, Université libre de Bruxelles (Rapporteur)
Katherine E. STANGE, University of Colorado (Rapporteure)
David KOHEL, Aix-Marseille Université (Examinateur)
Annamaria IEZZI, Université Grenoble Alpes (Examinatrice)
Laurent BERGER, Ecole Normale Supérieure de Lyon (Examinateur)
Benjamin WESOLOWSKI, Ecole Normale Supérieure de Lyon/CNRS (Directeur de thèse)

Résumé:

L'émergence des ordinateurs quantiques est un défi pour la cryptographie moderne. Les cryptologues doivent non seulement considérer de nouveaux problèmes calculatoires, supposés difficiles même pour l'algorithmique quantique, mais aussi construire des protocoles dont la sécurité repose sur ces derniers. Le domaine de recherche ayant pour objectif la conception de cryptosystèmes résistants à des adversaires quantiques est appelé cryptographie post-quantique.

Dans cette thèse, nous explorons les fondements d'un des candidats post-quantiques majeurs: la cryptographie à base d'isogénies. Sa sécurité repose initialement sur la difficulté du problème Isogeny, consistant à trouver une ``bonne'' application, appelée isogénie, entre deux courbes elliptiques données. Le développement de ce domaine a mené à l'étude de nombreux autres problèmes: plusieurs versions du problème Isogeny mais aussi du problème du calcul de l'anneau d'endomorphismes d'une courbe (un endomorphisme étant une isogénie d'une courbe vers elle-même).
Il a été prouvé, d'abord sous des hypothèses heuristiques puis sous l'hypothèse de Riemann généralisée, que ces problèmes étaient équivalents. Dans ce travail, nous démontrons leur équivalence inconditionnelle. De plus, nous prouvons des réductions du pire cas au cas moyen qui montrent que l'existence d'une instance difficile du problème Isogeny suffit à assurer la difficulté des instances aléatoires de n'importe quel autre problème. Ces avancées simplifient grandement l'ensemble des hypothèses nécessaires pour fournir un cadre sécurisé à la cryptographie à base d'isogénies.

Par ailleurs, nous nous intéressons aux protocoles qui considèrent des informations additionnelles sur les courbes elliptiques, appelées orientations, permettant de calculer des actions de groupe. Développer des algorithmes calculant des actions de groupe adaptées à la cryptographie post-quantique est un défi important puisque de nombreux protocoles avancés peuvent être construits à partir de ceux-ci. Nous fournissons une analyse rigoureuse de la complexité des problèmes difficiles sous-jacents, remplaçant les précédentes hypothèses heuristiques de la littérature par l'hypothèse de Riemann généralisée. Puis, nous présentons le premier algorithme pratique d'actions de groupe post-quantique adaptable à des niveaux de sécurité élevés: PEGASIS.

Un ingrédient central de ces résultats originaux est l'utilisation d'isogénies en dimension supérieure, développée suite aux attaques de SIDH. Ces nouveaux outils sont cruciaux à la fois pour nos contributions théoriques et pratiques. Dans cette thèse, nous participons à leur développement en généralisant un algorithme de division d'isogénies à partir d'un cas particulier de la littérature.