1
$\begingroup$

My understanding is that an elliptic curve $E$ over a finite field $\mathbf{F}_q$ has a bit security of $\sqrt{q}$ assuming Pollard rho or Baby-step giant-step. In this thread, it is explained that the field $\mathbf{F}_{2^{256}}$ has a bit security of $128$, but the field $\mathbf{F}_{2^{256^{2}}}$ supposedly only has a bit security of $\approx60$. I struggle to understand why this is.

Thank you for your time!

$\endgroup$

1 Answer 1

3
$\begingroup$

It is explained that the field $\mathbf{F}_{2^{256}}$ has a bit security of $128$

Actually, the reference was to an elliptic curve based on the field $\mathbf{F}_q$ (where $q \approx 2^{256}$)

but the field $\mathbf{F}_{2^{256^{2}}}$ supposedly only has a bit security of $\approx60$

That reference was to the multiplicative group in the finite field $\mathbf{F}_{q^2}$ (again, with $q \approx 2^{256}$)

These are two different thing; the first is an elliptic curve group, the second is the multiplicative group within a finite field, which has a lot more structure. In particular, there are various attacks that use this structure (such as sieving methods) that apply to the second case that don't apply to the first case (assuming, of course, that the embedding degree in the first case is large)

$\endgroup$
4
  • $\begingroup$ I am aware of the difference, and perhaps it was misworded in my original question. I still don't see where $60$ comes from. $\endgroup$
    – bobby
    Jul 11, 2023 at 17:05
  • $\begingroup$ @bobby That particular number comes from the Lenstra estimates from keylength.com/en/compare . It's an estimate considering the most efficient methods at the time. $\endgroup$
    – Conrado
    Jul 11, 2023 at 18:26
  • $\begingroup$ @bobby: $2^{60}$ is approximately the number of steps needed to perform a discrete log in the finite field $\mathbb{F}_{q^2}$ using the best known algorithm (which I believe, in this case, is the number field sieve) $\endgroup$
    – poncho
    Jul 11, 2023 at 18:26
  • $\begingroup$ I think the question has been adequately answered. Thank you for clarifying it to me! $\endgroup$
    – bobby
    Jul 11, 2023 at 18:48

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.