Elliptic curve cryptography is much more secure for the same parameters because attacks that work on the DLP do not work on the ECDLP. Why do the attacks fail in the latter case?


"Attacks that work on the DLP do not work on ECDLP" is a rather vague statement, as ECDLP is just a particular case of DLP, on elliptic curves. I suppose that you refer to DLP over $\mathbb{F}_q$ for some $q = p^k$, $p$ being a prime.

The intuitive reason why the DLP is harder to solve over (well-chosen) elliptic curves is that they are our best construction of a generic-like group, id est a group with seemingly no more structure than the group law. It is known that over a generic group of order $q$, the best algorithm to solve DLP takes $O(\sqrt{q})$ steps.

However, fields do obviously have way more structure than generic groups, and this structure can be exploited. More precisely, there is a family of algorithms, called Index Calculus, tailored to exploit this structure. Note that for some elliptic curves, DLP can be solved via index calculus, hence ECDLP requires "well-chosen" elliptic curves.

Index calculus algorithms work by creating a large base of the relation between the discrete logarithm of small prime values. This system of equations is then solved to get the discrete logarithm of each element of the factor base. Let $(g,h)$ be the DL instance. Next, the algorithm tries to write $g^sh$ as a product of powers of the factor base, for some $s$. Once it finds such an $s$, finding the discrete log of $h$ in base $g$ is easy.

The core notion to answer your question is the need for a base of small prime values: although well defined for a field, "prime" cannot be defined for generic groups, or for elliptic curves. Hence, the index calculus cannot be used on well-chosen elliptic curves. Still, some elliptic curves are affected by the index calculus when there is some map which moves the DLP problem from the curve to some field.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.