Algèbres de Quaternions et cryptographie à base d'isogénies

L'avènement de l'ordinateur quantique est une menace pour la cryptographie en permettant de résoudre les problèmes sur lesquels reposent la sécurité de nombreux protocoles. La cryptographie à base d'isogénies est une famille de protocoles reposant sur la difficulté de trouver une isogénie entre deux courbes elliptiques supersingulières, un problème supposé dur pour un ordinateur quantique.Dans cette thèse, nous étudions la connexion entre isogénies et les algèbres de quaternion nommée la correspondance de Deuring.Nous divisons cette thèse en deux parties : la première est dédiée à l'étude théorique et algorithmique des objets mathématiques de la correspondance de Deuring. La seconde présente des protocoles, construits sur les résultats et algorithmes de la première partie.Dans le chapitre 1, nous couvrons les résultats mathématiques standards sur isogénies, et algèbres de quaternions.Dans le chapitre 2, nous présentons les bases de la correspondance de Deuring, avant de passer à des résultats moins standards sur les ordres d'Eichler. Ces ordres et leurs classes d'idéaux peuvent être mis en correspondance avec l'ensemble des isogénies d'un degré donné. Nous proposons une preuve de cette propriété dont nous réutiliserons une bonne partie des résultats intermédiaires.Ce chapitre se termine sur la preuve de la première borne générique sur le nombre de courbes supersingulières dites orientables pour un certain ordre quadratique imaginaire, c'est à dire qui admettent un plongement de cet ordre quadratique dans leur anneau d'endomorphisme.Dans le chapitre 3, nous nous intéressons au problème de résoudre des équations de normes dans certaines familles d'ordres et d'idéaux. Ces algorithmes seront des ingrédients primordiaux dans un bon nombre des protocoles cryptographiques et algorithmes que nous introduirons par la suite. Nous étendons les résultats initiaux de Kohel, Lauter, Petit et Tignol (KLPT) à tous les ordres dont la clôture de Gorenstein est un ordre d'Eichler, ainsi qu'aux idéaux associés.Dans le chapitre 4, nous regardons les représentations d'isogénies : pour évaluer et calculer une isogénie. La méthode classique est d'utiliser les formules de Vélu et nous introduisons un nouvel algorithme permettant de passer à une complexité en la racine du degré pour les calculer. Ensuite, nous nous intéressons à la représentation à base d'idéaux qui est dérivée de la correspondance de Deuring et permet d'obtenir des complexités logarithmiques en le degré. Nous présentons de nouveaux algorithmes, plus efficaces en pratique, pour cette représentation.Enfin, nous présentons une troisième représentation, basée sur des sous-ordres de l'anneau d'endomorphisme. Cette représentation n'est pas équivalente à celle à base d'idéaux, ce qui motive son étude.Dans le chapitre 5, nous présentons SQISign, un protocole de signature basé sur la preuve de connaissance d'anneaux d'endomorphismes. Ce schéma est une amélioration de la signature de Galbraith, Petit et Silva et se base sur une généralisation de l'algorithme KLPT. Nous avons effectué une implémentation en utilisant les algorithmes efficaces du chapitre 4.La sécurité de SQISign est basée sur un nouveau problème calculatoire analysée à la fin de ce chapitre.Dans le chapitre 6, nous introduisons Séta, un protocole de chiffrement à clé publique. Cette primitive est dérivée d'une fonction à trappe à sens unqiue obtenue en modifiant les attaques par points de torsion de Petit en 2017 et nous l'avons implémenté par dessus le code de SQISign.Ce chapitre se finit sur la présentation d'une nouvelle hypothèse de sécurité générique que nous appelons "uber-isogeny assumption". Nous montrons comment ce nouveau problème est en fait relié à la plupart des protocoles de la cryptographie à bases d'isogénies.Dans le chapitre 7, nous décrivons des résultats portant sur les applications cryptographiques de notre nouvelle représentation d'isogénies présentéeau chapitre 4.