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:

  1. $k = 2$ : $t= 0$ and $E(\mathbb{F}_q) \cong \mathbb{Z}_{q+1}$

  2. $k=2$ : $t= 0$ and $E(\mathbb{F}_q) \cong \mathbb{Z}_{(q+1)/2} \oplus \mathbb{Z}_2$ (and $q = 3 mod 4$)

  3. $k=3$ : $t^2=q$ (and $m$ is even)

  4. $k=4$ : $t^2=2q$ (and $p = 2$ and $m$ is odd)

  5. $k=6$ : $t^2=3q$ (and $p = 3$ and $m$ is odd)

  6. $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

\[ c_n = c_1 c_{n-1} - q c_{n-2} \]

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