Genus 2 curves in pairing-based cryptography and the minimal embedding field

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.