Quaternion Algebra and isogeny-based cryptography - Laboratoire d'informatique de l'école polytechnique Accéder directement au contenu
Thèse Année : 2022

Quaternion Algebra and isogeny-based cryptography

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

Résumé

The quantum computer is a threat to cryptography as it can solve the problems upon which relies the security of a lot of protocols. Isogeny-based cryptography is a family of protocols relying on the hardness of finding an isogeny between two supersingular elliptic curves, a problem assumed hard even for a quantum computer. In this thesis, we study the connection between isogeny-based cryptography and quaternion algebras called the Deuring correspondence. This thesis is divided in two parts: the first is dedicated to the theoretic and algorithmic study of the mathematical objects of the Deuring correspondence. The second presents the protocols built on the results and the algorithms of the first parts. The main axis of research developed throughout this document is the interpretation of some results related to the classification of the orders in a quaternion algebra, such as the theory of Eichler orders, in the context of the Deuring correspondence, and the applications of this interpretation to the concrete algorithmic problems that are related to it. Through the generalization of algorithms to solve norm equations in orders and ideals of quaternion algebras, it is possible to find generic paths in isogeny graphs, a task that has interesting applications in cryptography. For instance, we were able to design a post-quantum signature scheme based on proofs of knowledge of endomorphism ring. This signature protocol has the smallest signature and public key size of all post-quantum solutions. The study of other algorithmic aspects such as the effective translation of the different objects of the Deuring correspondence allowed us to make this protocol practical.
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. L’axe principale de recherche que nous développons tout au long de ce document est l’interprétation de certains résultats de la classification des ordres d’une algèbre de quaternions, comme la théorie des ordres d’Eichler, dans le cadre de la correspondance de Deuring, et l’application de cette interprétation aux problèmes algorithmiques concrets qui y sont liées. A travers la généralisation d’algorithmes d’équations de normes dans les ordres et idéaux d’algèbres de quaternions, il est possible de résoudre de façon générique des problèmes de recherche de chemins dans des graphes d’isogénies, ce qui a des applications très intéressantes en cryptographie. Par exemple, cela nous a permis de créer un protocole de signature post-quantique basée sur la preuve de connaissance d’anneau d’endomorphisme. Ce schéma de signature a la plus petite taille de signature et cl ´e publique parmi les solutions postquantiques. L’études d’autres aspects algorithmiques, comme la traduction effective entre les différents objets de la correspondance de Deuring, nous ont permis de rendre ce protocole utilisable en pratique.
Fichier principal
Vignette du fichier
manuscrit_thèse.pdf (2.06 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-03886810 , version 1 (06-12-2022)
tel-03886810 , version 2 (25-05-2023)

Identifiants

  • HAL Id : tel-03886810 , version 1

Citer

Antonin Leroux. Quaternion Algebra and isogeny-based cryptography. Cryptography and Security [cs.CR]. Ecole doctorale de l’Institut Polytechnique de Paris, 2022. English. ⟨NNT : 2022IPPAX094⟩. ⟨tel-03886810v1⟩
298 Consultations
129 Téléchargements

Partager

Gmail Facebook X LinkedIn More