(2007-08) Hitt, Laura Michelle, 1979-; Voloch, José Felipe

Show more

A pairing-friendly hyperelliptic curve over a finite field Fq is one whose
group of Fq-rational points of its Jacobian has size divisible by a large prime
and whose embedding degree is small enough for computations to be feasible
but large enough for the discrete logarithm problem in the embedding field to
be difficult. We give a sequence of Fq-isogeny classes for a family of Jacobians of
curves of genus 2 over Fq, for q = 2m, and their corresponding small embedding
degrees for the subgroup with large prime order. 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 pairingbased
cryptography on curves of genus g over Fq, it is desirable that the ratio
ρ =
g log2
q
log2
`
be approximately 1, where ` is the order of the subgroup with
embedding degree k. We show that for our family of curves, ρ is often near 1
and never more than 2.
We construct examples to show that the minimal embedding field can
be significantly smaller than Fq
k . This has the implication that attacks on
the DLP can be dramatically faster than expected, so there could be “pairingfriendly”
curves that may not be as secure as previously believed.