## 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.

Ben Lynn blynn@cs.stanford.edu 💡