# Key size and finite fields in ECC (References)

So somehow I know that the key size in ECC is defined over the number of elements in a finite field or that it is almost equivalent to that (Correct me if I am wrong). However, other than on Wikipedia I cannot seem to find any source (Article, Book, Encyclopedia with a trusted author, etc.) that states this and I am not allowed to use Wikipedia as reference for my work. I have been scrolling back and forth in my book (Cryptography & Network Security, Sixth Edition) and on Google without finding anything that states exactly this except from Wikipedia. Also, I have looked through the references on Wikipedia and they don't really have anything even though they state it themselves. Therefore, I would just kindly ask if someone knows of a trusted source where the author is shown that states this, unless I am wrong of course...

The security level is usually taken to be an estimate of the $\log_2$ of the expected cost in bit operations of the best attack attaining probability near 1 of success. In the case of well-designed elliptic-curve cryptography for a curve $E/k$ over a field $k$, this is usually determined by the cost of the best algorithm for computing discrete logarithms in a subgroup of $E(k)$, the $k$-rational points of $E/k$, with large prime order $\ell$.
The expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, so, e.g., we estimate a 128-bit security level for breaking X25519, which works in a group whose order $\ell$ is 252 bits; see the discussion at SafeCurves for more on Pollard's $\rho$ cost, and for references to other types of attacks on elliptic-curve cryptography. The order $\#E(k) = h \ell$ of the group $E(k)$ can't differ from $\#k$, the cardinality of the field $k$, by more than $2\sqrt{\#k}$, by Hasse's theorem; see an earlier answer I wrote for more on the relationship between field $k$, subgroup order $\ell$, and cofactor $h$.
The private key size is usually taken to be the number of bits it takes to encode a secret scalar in $\mathbb Z/\ell\mathbb Z$. (Again, by Hasse's theorem, $\ell = \#E(k)/h$ can't be much more than $\#k$, and won't be much less unless the group has an unreasonably large cofactor $h$.) This number of bits can't be less than twice the maximum security size because of the generic Pollard's $\rho$ attack cited above. In some cryptosystems, though, we don't exactly store an element of $\mathbb Z/\ell\mathbb Z$ but rather a seed that we hash into one as in standard EdDSA, and in others we store $\mathbb Z/\ell\mathbb Z$ alongside other data as in some nonstandard extensions to EdDSA.
The public key size is usually taken to be the number of bits it takes to encode a curve point in $E(k)$. There are different encoding schemes available. You could naively encode a pair of elements of $k$, but that's a waste of space with a lot of redundancy that attackers can exploit. You could encode one coordinate, and transmit the other as a single bit, which requires some work for the receiver to decompress. You could use fancier compression schemes like Elligator or Decaf, which have better security properties.
• @user164324 There is no straightforward relationship between the $b$ parameter in the short Weierstrass formula $y^2 = x^3 - a x + b$ and the number of points on the curve—you just have to use Schoof's algorithm to count them. Some curves have parameters $a$ and $b$ that were allegedly chosen uniformly at random, rejecting composite numbers of points, like NIST P-256. Some have rigidly selected parameters that are the smallest values satisfying certain criteria, like secp256k1, whose equation is $y^2 = x^3 + 7$. Some were designed like that but for different shapes like Edwards curves. – Squeamish Ossifrage Dec 18 '17 at 0:52