# Embedding degree of curves of characteristic 2 and ECDLP transfer

It is known that we can transfer an ECDLP instance on a curve $$E$$ defined over $$\mathbb{F}_p$$ for prime $$p$$, to a discrete-log instance in $$\mathbb{F}_{p^k}$$ for some $$k$$. It is referred to as the embedding degree, and is the smallest integer $$k$$ such that the order of the curve divides $$p^k-1$$.

(One way to do this is using pairings.)

I am interested in the binary curves, e.g. defined over $$\mathbb{F}_{2^m}$$ and want to do something similar, but I can't find information about the embedding degree in this case (for instance, the databases of curves has no mention of the embedding degree for binary curves, e.g. https://neuromancer.sk/std/secg/sect233k1). Perhaps some algebraic argument fails but I can't see why.

Context: I want to prove a statement in ZK about two discrete logs on different curves. I thought that if one curve is defined in $$\mathbb{F}_{2^m}$$ and the other in $$\mathbb{F}_{2^n}$$, then if I can transfer the two instances to finite fields $$\mathbb{F}_{2^{km}}, \mathbb{F}_{2^{ln}}$$ where $$k,l$$ are the embedding degrees, I can treat this as a field extension and use the arithmetic.

Although the transfer exists for binary curves, embedding degrees are usually much too large to be computationally useful. In pairing-friendly curves, the construction specifically creates an extremely low embedding degree, but typically we expect the embedding degree to be $$O(\ell)$$ where $$\ell$$ is the order of the group.
It is feasible to compute the embedding degree if one can factor $$\ell-1$$. One simply computes the order of 2 modulo $$\ell$$ (in particular if 2 is a primitive root modulo $$\ell$$ then its order is $$\ell-1$$). If we write $$d$$ for the order of 2 and the elliptic curve if taken over the field $$\mathbb F_{2^m}$$ then the embedding degree will be $$md/\mathrm{GCD}(m,d)$$.
• Even if it is not practical, I want to work in $F_{2^km}$ for a logical step in my proof, so if the pairing exists, that's fine. Otherwise, would you know if there are there pairing-friendly curves on fields of characteristic 2? Mar 23 at 14:38