Sur les fondements de la cryptographie à base d'isogénies supersingulières

Résumé de la thèse

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, une 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 pire-cas moyen-cas 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 plus grande dimension, développée suite aux attaques de SIDH. Ces nouveaux outils sont cruciaux à la fois pour nos contributions théoriques et pratiques. Pendant 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.

The emergence of quantum computers constitutes a challenge for cryptography; we need to develop new computational problems that are presumably hard for quantum computers, together with new schemes relying on them. Post-quantum cryptography is the domain of research investigating schemes resistant to quantum adversaries.

In this thesis, we explore the foundations of the isogeny-based candidate for post-quantum cryptography. The security of isogeny-based schemes initially relies on the difficulty of the Isogeny problem, which asks to compute a “nice” map, an isogeny, between two given elliptic curves. During the development of this field, several other hard problems have arisen, such as variants of the Isogeny problem or of the problem of computing endomorphism rings (an endomorphism being an isogeny from a curve to itself). It has been proven, first under heuristic assumptions then under the generalised Riemann hypothesis, that these problems are equivalent. We provide an unconditional equivalence result. In addition, we prove worst-case to average-case reductions showing that assuming the existence of a single hard instance of the Isogeny problem is enough to ensure that random instances of the other problems are hard. These advances greatly simplify the set of necessary assumptions to provide a secure setup for isogeny-based cryptography.

We also focus our attention on schemes adding data to elliptic curves, called orientations, to perform group actions. Having access to a practical group action framework, for post-quantum cryptography, is an important challenge for cryptographers as it could lead to many advanced protocols. We provide a rigorous complexity analysis of the underlying hard problems, substituting the previous heuristic assumptions in the literature with the generalised Riemann hypothesis. Then, we present the first practical and scalable post-quantum framework for effective group action: Pegasis.

A central ingredient for these original results is the higher dimensional machinery developed from the SIDH attack. This is crucial both for our theoretical and practical contributions. During this thesis, we participate in the development of those higher dimensional tools by generalising an efficient division algorithm for isogenies from a specific case in the literature.