Pairing-friendly curves in small characteristic fields There are several well-known techniques to generate pairing-friendly curves of degrees 1 to 36 on prime fields GF(p): Cocks-Pinch, MNT, Brezing-Weng, and several others.

In extension fields GF(p^n), however, one is confined to supersingular curves. In characteristic 2, embedding degrees are &lt;= 4, and in characteristic 3 they are &lt;= 6. In general, they are &lt;= 2.

The question is: is there any known method to generate ordinary pairing-friendly curves over small characteristic fields, with a reasonable (say, 3-20) embedding degree?
To my knowledge the answer is no.

Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little constraints on its number of points.

(If you're interested in more precise statements and explicit examples, I suggest looking at Lay and Zimmer, Constructing elliptic curves with given group order over large finite fields, which despite its title covers both aspects. Article behind a pay wall unfortunately.)

This works well to find pairing-friendly curves in large characteristic because you have plenty of room to let the cardinal of the base field vary. But it doesn't work well at all over small characteristic fields, because you put both huge constraints on the cardinal of the base field (it has to be a power of the characteristic) and on the number of points on the curve (to achieve a small embedding degree).

In fact, I'd be curious to see even a single example of an ordinary curve with small embedding degree over a not too large binary field, like $\mathbb{F}_{2^{31}}$ say.

Note that this problem is entirely unrelated with the question of constructing ordinary pairing-friendly curves of higher genus over large prime fields, which Freeman's article mentioned above addresses.