Genus 2 Hyperelliptic Curve Families with Explicit Jacobian Order Evaluation and Pairing-Friendly Constructions

Aurore Guillevic 1, 2 Damien Vergnaud 1, 2, 3
1 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : The use of (hyper)elliptic curves in cryptography relies on the ability to compute the Jacobian order of a given curve. Recently, Satoh proposed a probabilistic polynomial time algorithm to test whether the Jacobian -- over a finite field $\mathbb{F}_q$ -- of a hyperelliptic curve of the form $Y^2 = X^5 + aX^3 + bX$ (with $a,b \in \mathbb{F}_q^*$) has a large prime factor. His approach is to obtain candidates for the zeta function of the Jacobian over $\mathbb{F}_q^*$ from its zeta function over an extension field where the Jacobian splits. We extend and generalize Satoh's idea to provide \emph{explicit} formulas for the zeta function of the Jacobian of genus 2 hyperelliptic curves of the form $Y^2 = X^5 + aX^3 + bX$ and $Y^2 = X^6 + aX^3 + b$ (with $a,b \in \mathbb{F}_q^*$). Our results are proved by elementary (but intricate) polynomial root-finding techniques. Hyperelliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Using our closed formulas for the Jacobian order, we present several algorithms to obtain so-called \emph{pairing-friendly} genus 2 hyperelliptic curves. Our method relies on techniques initially proposed to produce pairing-friendly elliptic curves (namely, the Cocks-Pinch method and the Brezing-Weng method). We demonstrate this method by constructing several interesting curves with $\rho$-values around 3. We found for each embedding degree $5 \leqslant k \leqslant 35$ a family of curves of $\rho$-value between $2.25$ and $4$.
Type de document :
Communication dans un congrès
Michel Abdalla; Tanja Lange. Pairing-Based Cryptography - Pairing 2012, May 2012, Cologne, Germany. Springer, 7708, pp.234-253, 2013, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-36334-4_16〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00871327
Contributeur : Damien Vergnaud <>
Soumis le : mercredi 9 octobre 2013 - 14:31:32
Dernière modification le : mardi 17 avril 2018 - 11:29:32

Identifiants

Collections

Citation

Aurore Guillevic, Damien Vergnaud. Genus 2 Hyperelliptic Curve Families with Explicit Jacobian Order Evaluation and Pairing-Friendly Constructions. Michel Abdalla; Tanja Lange. Pairing-Based Cryptography - Pairing 2012, May 2012, Cologne, Germany. Springer, 7708, pp.234-253, 2013, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-642-36334-4_16〉. 〈hal-00871327〉

Partager

Métriques

Consultations de la notice

245