Curve Selection
Let \(E\) be an elliptic curve defined over a field \(\mathbb{F}_q\). Let \(r\) be a prime dividing \(\#E(\mathbb{F}_q)\). The subgroup of the group of points of \(E(\mathbb{F}_q)\) 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 \(q^k - 1\). 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 = p^m\) and let \(k\) be the embedding degree. Then the six classes are:
-
\(k = 2\) : \(t= 0\) and \(E(\mathbb{F}_q) \cong \mathbb{Z}_{q+1}\)
-
\(k=2\) : \(t= 0\) and \(E(\mathbb{F}_q) \cong \mathbb{Z}_{(q+1)/2} \oplus \mathbb{Z}_2\) (and \(q = 3 mod 4\))
-
\(k=3\) : \(t^2=q\) (and \(m\) is even)
-
\(k=4\) : \(t^2=2q\) (and \(p = 2\) and \(m\) is odd)
-
\(k=6\) : \(t^2=3q\) (and \(p = 3\) and \(m\) is odd)
-
\(k=1\) : \(t^2=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(\mathbb{F}_q) = q + 1 - c_1\). Then \(\#E(\mathbb{F}_{q^n}) = q^n + 1 - c_n\) where
and \(c_0 = 2\). See p.105 of Blake, Seroussi and Smart.