zbMATH — the first resource for mathematics

Genus 2 hyperelliptic curve families with explicit Jacobian order evaluation and pairing-friendly constructions. (English) Zbl 1305.94053
Abdalla, Michel (ed.) et al., Pairing-based cryptography – Pairing 2012. 5th international conference, Cologne, Germany, May 16–18, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-36333-7/pbk). Lecture Notes in Computer Science 7708, 234-253 (2013).
Summary: The use of elliptic and hyperelliptic curves in cryptography relies on the ability to compute the Jacobian order of a given curve. Recently, T. Satoh [Eurocrypt 2009, Lect. Notes Comput. Sci. 5479, 536–553 (2009; Zbl 1239.94065)] 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 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 propose two algorithms which complement those of Freeman and Satoh to produce genus 2 pairing-friendly 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 show that the previous security considerations about embedding degree are valid for an elliptic curve and can be lightened for a Jacobian. We demonstrate this method by constructing several interesting curves with \(\rho \)-values around 4 with a Cocks-Pinch-like method and around 3 with a Brezing-Weng-like method.
For the entire collection see [Zbl 1258.94002].

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry
68W40 Analysis of algorithms
Full Text: DOI