Paper 2011/604

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

Aurore Guillevic and Damien Vergnaud

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+a{X}^3+bX$ (with $a,b\in {\mathbb{F}}_q^{\ast }$) has a large prime factor. His approach is to obtain candidates for the zeta function of the Jacobian over ${\mathbb{F}}_q^{\ast }$ 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+a{X}^3+bX$ and $Y^2=X^6+a{X}^3+b$ (with $a,b\in {\mathbb{F}}_q^{\ast }$). 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 $$-values around 3. We found for each embedding degree $$ a family of curves of $$-value between $$ and $$.