Fast computation of higher dimensional isogenies for cryptographic applications

Calcul rapide d’isogénies en dimension supérieure pour les applications cryptographiques Shor a découvert en 1995 un algorithme permettant à un ordinateur quantique suffisamment puissant d’attaquer tous les protocoles cryptographiques à clés publiques fondés sur le logarithme discret et la factorisation des nombres en produit de facteurs premiers, tels que RSA et les courbes elliptiques, largement utilisés aujourd’hui. Depuis, de gros efforts de recherche ont été accomplis pour proposer des protocoles résistants aux attaques quantiques et l’institut de standardisation et des technologies américain (NIST) a organisé deux compétitions internationales en ce sens. La cryptographie à base d’isogénies repose sur la difficulté à trouver des isogénies entre courbes elliptiques. En 2022, le protocole d’échange de clé Supersingular Isogeny Diffie-Hellman (SIDH) proposé au NIST fait l’objet d’attaques majeures. Loin d’entraver l’avenir de la cryptographie à base d’isogénies, ces attaques ont au contraire fortement dynamisé la recherche dans ce domaine. Les idées de ces attaques très efficaces ont en effet inspiré de nouveaux protocoles cryptographiques et l’amélioration de protocoles existants ne souffrant pas des faiblesses de sécurité de SIDH. Nos travaux de thèse ont notamment contribué à des améliorations de Short Quaternion Isogeny Signatures (SQIsign), un protocole de signature électronique également proposé au NIST. SQIsign s’appuie sur la correspondance de Deuring entre isogénies des courbes elliptiques supersingulières et idéaux d’une algèbre de quaternions. Bien que très compact, SQIsign était désavantagé par un algorithme de signature très lent consistant à traduire un idéal d’une algèbre de quaternions en l’isogénie qui lui correspond. Les attaques contre SIDH ont mené à de nouvelles idées pour améliorer cet algorithme de traduction de manière beaucoup plus efficace, tout en améliorant la preuve de sécurité et la compacité du protocole. Ces nouveaux algorithmes de traduction d’idéaux en isogénies ont aussi servi à améliorer le calcul de l’action du groupe des classes d’idéaux sur les courbes elliptiques supersingulières orientées, qui intervient par exemple dans le protocole Commutative Supersingular Isogeny Diffie Helmman (CSIDH). Les attaques contre SIDH et les nouvelles techniques de construction qui ont suivi s’appuient sur le calcul efficace d’isogénies en dimension supérieure à 2 (les courbes elliptiques étant de dimension 1). Cette thèse a ainsi contribué à l’élaboration et à l’implémentation d’algorithmes rapides de calcul d’isogénies en dimensions 2 et 4.