Score:4

If a curve $E/\mathbb{F}_q$ is secure, what can be said about $E/\mathbb{F}_{q^2}$

au flag

Let $E$ be a known, "secure" curve, defined over a field $\mathbb{F}_q$ where $q$ is either a prime $\geq 5$ or a power of $2$. Denote by $n$ the amount of rational points of $E$.

Consider $E/\mathbb{F}_{q^2}$, the same curve but defined over the 2-degree extension field. It is clear that any $E(\mathbb{F}_q)$ is a subgroup of $E(\mathbb{F}_{q^2})$, so by Lagrange, $m := |E(\mathbb{F}_{q^2})| = nl$. Actually, with Weil's conjectures, one has $m = n (2q + 2 - n)$.

With this we see that the discrete logarithm in the extended curve is controlled by the largest prime factor of $n$ or $2q + 2 - n$, so not much bits of security are gained by considering this curve against the known attacks on the discrete logarithm (for instance, if $n$ is the largest prime factor of $m$, literally no security is gained). But that's fine for my purposes.

My question is; is the extended structure useful to the attacker, e.g., is it possible for the curve $E(\mathbb{F}_{q^2})$ to be less secure than $E(\mathbb{F}_q$)? My intuition says no, because it that was the case, then one embeds any DLOG instance on the extended curve, and solve that. But there is security degradation when higher-degree extensions are used, by means of discrete log transfers! (e.g. see 1 and 2)

Myria avatar
in flag
Do those cited references show a case where discrete logs in $E(\mathbb{F}_{p^n})$ are faster than in $E(\mathbb{F}_p)$ for $n>1$?
au flag
Not easy to answer that simply, since it depends on $n$ and the characteristic size. So I'm asking for the particular case $n=2$ and large $p$, is there anything better than computing DLOGs directly in $E(\mathbb{F}_{p^2})$.
mangohost

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.