Skip to Main content Skip to Navigation
Theses

Algorithmique des courbes hyperelliptiques et applications à la cryptologie

Abstract : The study of algorithmical aspects of hyperelliptic curves is the natural continuation of the case of elliptic curves, which is now well advanced. Most of the algorithms known for elliptic curves and their applications to cryptography can be more or less easily extended to Jacobians of hyperelliptic curves. In a first part, we investigate some aspects of Igusa's invariants which generalize the j-invariant of elliptic curves. For (2,2)-reducible Jacobians, we relate by explicit formulae the Igusa's invariants to the j-invariants of the quotient elliptic curves. Besides, we study these invariants by the way of Siegel modular forms with a view toward computing modular equations. The second part is dedicated to algorithms for computing the cardinality of a hyperelliptic curve over a finite field. This computation is the first step when one want to use these curves for cryptography. Beside generic algorithms which can be applied to other groups than Jacobians, we propose an effective version of à la Schoof algorithms in genus 2. We present also a first step toward an Elkies-Atkin approach, which has proven to be successful in the elliptic case. The third part deals with algorithms for discrete logarithm computations. The security of some cryptosystems relies on this problem, which is considered to be difficult: if one can solve it in a reasonable amount of time, then the system is weak. After a brief state of the art, we present some algorithms based on the classical ideas of index-calculus. Taking advantage of the particularities of the problems coming from cryptography, we demonstrate with complexity results and practical experiments that the systems based on curves of genus greater or equal to 4 are not secure. Moreover, when combined with the techniques of Weil descent, this allows to attack some elliptic cryptosystems.
Document type :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/tel-00514848
Contributor : Pierrick Gaudry <>
Submitted on : Friday, September 3, 2010 - 2:07:39 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Saturday, December 4, 2010 - 2:49:22 AM

Identifiers

  • HAL Id : tel-00514848, version 1

Collections

Citation

Pierrick Gaudry. Algorithmique des courbes hyperelliptiques et applications à la cryptologie. Génie logiciel [cs.SE]. Ecole Polytechnique X, 2000. Français. ⟨tel-00514848⟩

Share

Metrics

Record views

890

Files downloads

2949