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 \gt 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.