Quiz Entry - updated: 2026.07.14
What is the Elliptic Curve Discrete Logarithm Problem (ECDLP), and why is it harder than the classical DLP?
Given points P and Q = kP on a curve, finding k is the ECDLP — it's believed to be harder than the classical discrete log because no subexponential algorithm is known for ECC.
* Computing $Q = kP$ is easy; recovering $k$ from $P$ and $Q$ is the ECDLP — the one-way gap that all EC cryptography rests on. *
The problem:
- Given: Points $P$ and $Q = k \cdot P$ on an elliptic curve
- Find: The scalar $k$
- Forward (computing $Q = k \cdot P$): Easy — use double-and-add
- Reverse (finding $k$ from $P$ and $Q$): Hard — this is the ECDLP
Why harder than classical DLP:
- For $\mathbb{Z}_p^*$, subexponential algorithms exist (Number Field Sieve) → need 3072-bit $p$
- For elliptic curves, the best known attack is Pollard's rho: $O(\sqrt{n})$ where $n$ = group order
- This is fully exponential — no shortcut like NFS exists
- Result: 256-bit ECC ≈ 128-bit security (compared to 3072-bit RSA for the same)
Security comparison:
| Security Level | RSA/DH key | ECC key | Symmetric key |
|---|---|---|---|
| 80 bits | 1024 bits | 160 bits | — |
| 128 bits | 3072 bits | 256 bits | AES-128 |
| 192 bits | 7680 bits | 384 bits | AES-192 |
| 256 bits | 15360 bits | 512 bits | AES-256 |
Go deeper:
Pollard's rho algorithm for logarithms — Wikipedia — the $O(\sqrt{n})$ generic attack that sets ECC's security level.- Elliptic-curve cryptography — Wikipedia — why no index-calculus shortcut is known on well-chosen curves.