Curve Selection

Let E be an elliptic curve defined over a field Fq. Let r be a prime dividing #E(Fq). The subgroup of the group of points of E(Fq) of order r can be used for cryptography provided it is sufficiently large.

Now define the embedding degree k (with respect to r) as the smallest positive integer such that r divides qk1. For pairing-based cryptography, we require curves with low embedding degrees.

Supersingular curves provide six families of curves with embedding degree at most 6 [MOV]. Let q=pm and let k be the embedding degree. Then the six classes are:

  1. k=2 : t=0 and E(Fq)Zq+1

  2. k=2 : t=0 and E(Fq)Z(q+1)/2Z2 (and q=3mod4)

  3. k=3 : t2=q (and m is even)

  4. k=4 : t2=2q (and p=2 and m is odd)

  5. k=6 : t2=3q (and p=3 and m is odd)

  6. k=1 : t2=4q (and m is even)

[TODO: more on supersingular curves, link to examples in pairing.html page. (Separate page for this?)]

MNT curves are an alternative to supersingular curves. They have the advantage of using fields of high characteristic when k>2 thus are safe from the Coppersmith attack. They use the complex multiplication (CM) method of generating elliptic curves.

Curve Orders

Suppose #E(Fq)=q+1c1. Then #E(Fqn)=qn+1cn where

cn=c1cn1qcn2

and c0=2. See p.105 of Blake, Seroussi and Smart.


Ben Lynn blynn@cs.stanford.edu 💡