Why can you use shorter keys with elliptic curve Diffie Hellman key exchange?

Question

I am a layperson interested in how cryptography works. I would like to know why you can use shorter keys with elliptic curve Diffie-Hellman (ECDH) than with the discrete log DH key exchange. Both have to be large enough to withstand brute force attacks. So I assume there must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe. Thank you in advance for your help.

Answer 1

There must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe.

Indeed, there are algorithms applicable to DLP in groups that are a subgroup of $\Bbb Z_p^*$, but not to Elliptic Curve (sub)groups:

• A variant of (G)NFS. See e.g. this article about solving a 768-bit DLP. That used to be the record before this December 2019 announcement about solving a 795-bit DLP.
• Index calculus, which in not quite as efficient, but still much more efficient than generic algorithms like baby-step/giant-step and Pollard's rho, which can attack the DLP in any group.

---

This website specifically lists recommendations for key size. Depending on crystal ball hypothesis, 250-bit ECC (giving the equivalent of about 125-bit symmetric security against classical computers running distributed Pollard's rho) is conjectured to be about as safe as 2000 to 8800-bit DLP in $\Bbb Z_p^*$ (the discrepancy is mostly due to the lesser confidence about the implausibility of better algorithms in $\Bbb Z_p^*$).