Paper 2007/001

Families of genus 2 curves with small embedding degree

Laura Hitt


Hyperelliptic curves of small genus have the advantage of providing a group of comparable size as that of elliptic curves, while working over a field of smaller size. Pairing-friendly hyperelliptic curves are those whose order of the Jacobian is divisible by a large prime, whose embedding degree is small enough for computations to be feasible, and whose minimal embedding field is large enough for the discrete logarithm problem in it to be difficult. We give a sequence of $\F_q$-isogeny classes for a family of Jacobians of genus two curves over $\F_{q}$, for $q=2^m$, and their corresponding small embedding degrees. We give examples of the parameters for such curves with embedding degree $k<(\log q)^2$, such as $k=8,13,16,23,26,37,46,52$. For secure and efficient implementation of pairing-based cryptography on genus g curves over $\F_q$, it is desirable that the ratio $\rho=\frac{g\log_2 q}{\log_2N}$ be approximately 1, where $N$ is the order of the subgroup with embedding degree $k$. We show that for our family of curves, $\rho$ is often near 1 and never more than 2. We also give a sequence of $\F_q$-isogeny classes for a family of Jacobians of genus 2 curves over $\F_{q}$ whose minimal embedding field is much smaller than the finite field indicated by the embedding degree $k$. That is, the extension degrees in this example differ by a factor of $m$, where $q=2^m$, demonstrating that the embedding degree can be a far from accurate measure of security. As a result, we use an indicator $k'=\frac{\ord_N2}{m}$ to examine the cryptographic security of our family of curves.

Note: updated details in proofs

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
embedding degreegenus 2hyperelliptic curvesbinary curvespairing-based cryptosystems
Contact author(s)
hitt36 @ gmail com
2009-02-13: last of 4 revisions
2007-01-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Laura Hitt},
      title = {Families of genus 2 curves with small embedding degree},
      howpublished = {Cryptology ePrint Archive, Paper 2007/001},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.