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

  • $\begingroup$ 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)$. $\endgroup$ – Luca Dec 18 '17 at 16:14
  • $\begingroup$ 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. $\endgroup$ – Luca Dec 18 '17 at 17:09

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.

Your Answer

