0
$\begingroup$

Let's say I want a certain level of security (eg 128 bits) when using ECIES but I also want to minimise communication, does the elliptic curve used matter on the size of the public key? If it does matter, what is the current state of the art elliptic curve and how does it compare with popular elliptic curves such as Curve25519 or secp256k1?

$\endgroup$
7
  • 1
    $\begingroup$ Did you do any research? Curve25519 has 32 bytes for ECDH, and secp256k1 has 33-bytes for compressed... $\endgroup$
    – kelalaka
    Jul 5, 2021 at 14:48
  • 1
    $\begingroup$ @kelalaka: for ECIES, you don't need the y coordinate, and so it'd be 32 bytes for either... $\endgroup$
    – poncho
    Jul 5, 2021 at 14:51
  • $\begingroup$ @poncho yes, exactly, since there is no need for the $y$ coordinate for the ECDH. 33-byte is the standard Bitcoin public key size. $\endgroup$
    – kelalaka
    Jul 5, 2021 at 14:58
  • $\begingroup$ @kelalaka Yes I know that curve25519 uses a 32-byte key but I was wondering if there's any curve that does better? I just read this and was wondering if any curve does better. As far as I can understand this is not possible but I am not an expert and I couldn't find anyone stating this (probably it's obvious) that's why I am searching here. $\endgroup$
    – Theo
    Jul 5, 2021 at 15:16
  • 1
    $\begingroup$ Use keylength.com/en/compare to decide what you need! $\endgroup$
    – kelalaka
    Jul 5, 2021 at 20:40

1 Answer 1

1
$\begingroup$

If it does matter, what is the current state of the art elliptic curve and how does it compare with popular elliptic curves such as Curve25519 or secp256k1?

Well, if you have an elliptic curve with a large subgroup of size $q$ (which is prime), then we know how to compute a discrete log within that subgroup in $O(\sqrt{q})$ time, and this applies to all elliptic curves (actually, all groups).

So, to make this attack take $2^{128}$ time, we need a $q \approx 2^{256}$.

And, because of the Hasse theorem, for a prime curve of characteristic $p$, we have $p + 2\sqrt{p} > q$, or in other words, the smallest $p$ can be is about 256 bits.

The standard way to represent a public key is to give the $x$ coordinate as an integer; this is a value between 0 and $p-1$; that is, a 256 bit value.

Hence, selecting a curve other than Curve25519, secp256k1 or P256 doesn't buy us anything; either that alternative curve would have reduced security or have a public key that's as least as large.

About the only thing you can try to come up with a reduced method of transmitting the $x$ coordinate; one simple-minded approach would be to always select an $x$ coordinate with $k$ bits of 0 at the top (and just not transmit those $k$ bits explicitly); finding such a key using rejection sampling would take $O(2^k)$ time and would save $k$ bits - perhaps doable if you need to save a byte or two - obviously infeasible to save more than that. I don't know of a cleverer approach to find public keys that meet a similar space saving technique.

$\endgroup$

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.