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

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)

• 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$? Commented May 18, 2022 at 22:51
• 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})$. Commented May 19, 2022 at 6:10
• @zugzwang please note that the papers you cited are capable of attacking curves defined over extension fields, but natively (meaning $|E(\mathbb{F}_{q^n})|\simeq |\mathbb{F}_{q^n}|$). The strategy won't work to attack a curve $E(\mathbb{F}_{q})$ by embedding it in $\mathbb{F}_{q^n}$ Commented Jun 14, 2022 at 8:22

If you can solve DLP in $$E(\mathbb F_{p^2})$$, you can solve DLP in $$E(\mathbb F_p)$$. The "proof" is simply that $$E(\mathbb F_p)\subseteq E(\mathbb F_{p^2})$$.
What's more, the subgroup of $$E(\mathbb F_{p^2})$$ of order $$n' := \#E(\mathbb F_{p^2})/\#E(\mathbb F_p)$$ also can't be weaker than a group with the same structure living on a curve defined over $$\mathbb F_p$$, since that's exactly what it is: Applying an isomorphism turns this subgroup into the group of $$\mathbb F_p$$‑rational points on the quadratic twist $$\tilde E$$ of $$E$$.
Therefore: If $$n$$ and $$n'$$ contain large distinct* prime divisors $$\ell$$ and $$\ell'$$, the ECDLP for a point in $$E(\mathbb F_{p^2})$$ of order divisible by $$\ell$$ or $$\ell'$$ is at least as hard as the ECDLP in the $$\ell$$‑subgroup of $$E(\mathbb F_p)$$ or the ECDLP in the $$\ell'$$‑subgroup of $$\tilde E(\mathbb F_p)$$, whichever one is easier.
* If $$\gcd(n,n')>4\sqrt p$$, then $$E$$ is supersingular.
If $$n$$ doesn't have a large prime divisor, then $$E(\mathbb F_p)$$ is insecure. If $$n'$$ doesn't have a large prime divisor, this means any security is concentrated in the $$\mathbb F_p$$‑part of the group $$E(\mathbb F_{p^2})$$, which suggests that working in the extension either didn't really do anything, or worse, made your protocol insecure.