What are the fastest attacks on ECDLP?

Question

Consider the ECDSA protocol, which is applied in different environments e.g. the Bitcoin system (for user addresses, and transaction signing).

What are the greatest threats in terms of algorithms that could solve the underlying discrete log problem for groups over elliptic curves? I found:

1. General Number Field Sieve
2. Pohlig-Hellman
3. Baby-Step-Giant-Step
4. Pollard's Rho

(excluding quantum algorithms)

to be the most efficient. Are all of them able to solve the ECDLP and if so, what is their complexity (runtime)?

Answer 1

If you wanted to compute secp256k1 discrete logs, you would use Pollard's rho, except of course the cost is far beyond your budget so it won't do you any good anyway.

• The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields. Such elliptic curves are called pairing-friendly, and are not normally used for ordinary ECDH key agreement or ECDSA or EdDSA signatures like Bitcoin—secp256k1, for instance, does not admit such an embedding, so the NFS is inapplicable.
• Pohlig–Hellman is used for groups of composite order: it speeds up the computation by doing it separately modulo each factor; you can then reassemble an answer with the Chinese remainder theorem. Although some elliptic curve groups used for discrete-log-type key agreement or signatures like edwards25519 have composite order, they typically have one large >250-bit prime factor and a very small cofactor like 4 or 8. Secp256k1 has prime order, so Pohlig–Hellman is inapplicable.
• BSGS and Pollard's rho both cost $O(\sqrt n)$ operations where $n$ is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc. However, BSGS also has $O(\sqrt n)$ memory cost, so the area*time cost—which is a proxy for euro or joule cost—is $O(n)$ even if we unrealistically assume $O(1)$ random access to memory. In contrast, Pollard's rho costs $O(\sqrt n)$ time on a machine of constant space and thus $O(\sqrt n)$ area*time. Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost. There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains $O(\sqrt n)$.
• If you knew the secret scalar were in a restricted range $[a,b]$, you could use Pollard's kangaroo, which costs $O(\sqrt{b - a})$ time on a machine of constant size. The kangaroo method too can be parallelized without increasing overall cost. If, say, $b - a \approx 2^{100}$ for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible. But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.