# What are the fastest attacks on ECDLP?

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)?

• I have the same question! I think there is also the index calculus method, but this applies ony to a certain kind of curves. For pollard-rho there are speed ups (parallize it, or use automorphisms if your elliptic curve allows it (which secp256k1, the Bitcoin-curve does)...). I am not sure enough to post this as an answer though. I would be happy if someone would say what they think about this: I think that for general curves the parallized pollard rho (it can be applied to any kind of curve?) is the most efficient with $~\frac{1}{m}\sqrt{\frac{\pi n}{2}}$, where $m=#$Processors, $n=#(G)$. – Luca Dec 18 '17 at 16:14
• I forgot that you can speed-up on general curves using the negation map. Then you get another speedup of $\sqrt(2)$ I think... Then we have ''The rho method breaks ECDLP using, on average, approximately $0.886 \sqrt(l)$ additions.'' as stated in safecurves.cr.yp.to/rho.html. (This webpage is very good to verify the strength of a certain curve. With a lot of literature-links) Again, I hope someone can verify what I state. I am not entirely sure that this is the 'greatest general threat. – Luca Dec 18 '17 at 17:09

• 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.