Score:1

On the bit security of elliptic curves

pa flag

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!

Score:3
my flag

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)

bobby avatar
pa flag
I am aware of the difference, and perhaps it was misworded in my original question. I still don't see where $60$ comes from.
tr flag
@bobby That particular number comes from the Lenstra estimates from https://www.keylength.com/en/compare/ . It's an estimate considering the most efficient methods at the time.
poncho avatar
my flag
@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)
bobby avatar
pa flag
I think the question has been adequately answered. Thank you for clarifying it to me!
I sit in a Tesla and translated this thread with Ai:

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.