Embedding degree of curves of characteristic 2 and ECDLP transfer

crypcrypcryp

7/23/23, 9:57 AM

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.

0 + 0

elliptic-curves

discrete-logarithm

Score:1

Crypto

Daniel S

7/23/23, 2:05 PM

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

0 + 0

crypcrypcryp

7/23/23, 2:38 PM

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?

Daniel S

7/23/23, 3:19 PM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Embedding degree of curves of characteristic 2 and ECDLP transfer

TH: ระดับการฝังของเส้นโค้งของคุณลักษณะ 2 และการถ่ายโอน ECDLP

RO: Gradul de încorporare al curbelor caracteristicii 2 și transferul ECDLP

RU: Степень вложения кривых характеристики 2 и переноса ЭПДРП

VI: Mức độ nhúng của các đường cong của đặc tính 2 và chuyển ECDLP

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.