4
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – Myria
    Commented May 18, 2022 at 22:51
  • $\begingroup$ 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})$. $\endgroup$
    – zugzwang
    Commented May 19, 2022 at 6:10
  • $\begingroup$ @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}$ $\endgroup$
    – Ruggero
    Commented Jun 14, 2022 at 8:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "The proof...E(F_p^2)"=> It doesn't seem obvious at all to me. If the hard instances are only in E(F_p), the inclusion is not enough. $\endgroup$
    – Ievgeni
    Commented Jun 14, 2022 at 7:20
  • $\begingroup$ the subgroup=> Can you precise about which subgroup are you speaking? $\endgroup$
    – Ievgeni
    Commented Jun 14, 2022 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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