Embedding degree of curves of characteristic 2 and ECDLP transfer

Question

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.

Answer 1

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