Applications of theta functions to hyperelliptic curves cryptography

Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques

Romain Cosset (1)

1 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications

Since the mid 1980's, abelian varieties have been widely used in cryptography: the discrete logarithm problem and the protocols that rely on it allow asymmetric encryption, signatures, authentification... For cryptographic applications, one of the most interesting examples of principally polarized abelian varieties is given by the Jacobians of hyperelliptic curves. The theory of theta functions provides efficient algorithms to compute with abelian varieties. In particular, using decomposable curves of genus 2, we present a generalization of the ECM algorithm. In this thesis, we also study the correspondences between Mumford coordinates and theta functions. This led to the construction of complete addition laws in genus 2. Finally we present an algorithm to compute isogenies between abelian varieties. Most of the results of this thesis are valid for hyperelliptic curves of arbitrary genus. More specifically we emphasize on genus 2 hyperelliptic curves, which is the most relevant case in cryptography. These results have been implemented in a Magma package called AVIsogenies

Depuis le milieu des années 1980, les variétés abéliennes ont été abondamment utilisées en cryptographie à clé publique: le problème du logarithme discret et les protocoles qui s'appuient sur celles-ci permettent le chiffrement asymétrique, la signature, l'authentification. Dans cette perspective, les jacobiennes de courbes hyperelliptiques constituent l'un des exemples les plus intéressants de variétés abéliennes principalement polarisées. L'utilisation des fonctions thêta permet d'avoir des algorithmes efficaces sur ces variétés. En particulier nous proposons dans cette thèse une variante de l'algorithme ECM utilisant les jacobiennes de courbes de genre 2 décomposables. Par ailleurs, nous étudions les correspondances entre les coordonnées de Mumford et les fonctions thêta. Ce travail a permis la construction de lois d'additions complètes en genre 2. Finalement nous présentons un algorithme de calcul d'isogénies entre variétés abéliennes. La majorité des résultats de cette thèse sont valides pour des courbes hyperelliptiques de genre quelconque. Nous nous sommes cependant concentré sur le cas du genre 2, le plus intéressant en pratique. Ces résultats ont été implémentés dans un package Magma appelé AVIsogenies

Mots clés: Cryptographie; Courbes hyperelliptiques; Variétés abéliennes; Fonctions thêta; Factorisation; Isogénies; Cryptographie à clé publique; Courbes elliptiques; Algorithmes

Domaines: Autre [cs.OH]

Romain Cosset. Applications des fonctions thêta à la cryptographie sur courbes hyperelliptiques. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 2011. Français. ⟨NNT : 2011NAN10145⟩. ⟨tel-01746303⟩