1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Mar 23 at 14:38
  • $\begingroup$ I do not know of any constructions for (non-supersingular) binary curves with unusually low-embedding degree. There are constructions for ternary curves with embedding degree 6 (see Harrison, Page and Smart "Software implementation of finite fields of characteristic three, for use in pairing-based crypto systems") BUT SUCH CURVES ARE NOT SUITABLE FOR CRYPTOGRAPHY due to recent attacks on discrete logs in small charactersitics fields by Granger, Joux et al. $\endgroup$
    – Daniel S
    Mar 23 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.