The Elliptic Curve Discrete Logarithm Problem

Problem 6.4 (Elliptic Curve Discrete Log Problem)   Suppose $E$ is an elliptic curve over $\mathbb{Z}/p\mathbb{Z}{}$ and  $P\in E(\mathbb{Z}/p\mathbb{Z}{})$ . Given a multiple $Q$ of $P$ , the elliptic curve discrete log problem is to find $n\in\mathbb{Z}$ such that $nP=Q$ .

For example, let $E$ be the elliptic curve given by $y^2 = x^3 + x+1$ over the field $\mathbb {Z}/7\mathbb {Z}{}$ . We have

$$E(\mathbb{Z}/7\mathbb{Z}{}) = \{\O, (2, 2), (0,1), (0,6), (2,5) \}.$$

If $P=(2,2)$ and $Q=(0,6)$ , then $3P=Q$ , so $n=3$ is a solution to the discrete logarithm problem.

If $E(\mathbb{Z}/p\mathbb{Z}{})$ has order $p$ or $p\pm 1$ or is a product of reasonably small primes, then there are some methods for attacking the discrete log problem on $E$ , which are beyond the scope of this book. It is thus important to be able to compute $\char93 E(\mathbb{Z}/p\mathbb{Z}{})$ efficiently, in order to verify that the elliptic curve one wishes to use for a cryptosystem doesn't have any obvious vulnerabilities. The naive algorithm to compute $\char93 E(\mathbb{Z}/p\mathbb{Z}{})$ is to try each value of $x\in\mathbb{Z}/p\mathbb{Z}{}$ and count how often $x^3+ax+b$ is a perfect square mod $p$ , but this is of no use when $p$ is large enough to be useful for cryptography. Fortunately, there is an algorithm due to Schoof, Elkies, and Atkin for computing $\char93 E(\mathbb{Z}/p\mathbb{Z}{})$ efficiently (polynomial time in the number of digits of $p$ ), but this algorithm is beyond the scope of this book.

In Section 3.1.1 we discussed the discrete log problem in $(\mathbb{Z}/p\mathbb{Z}{})^*$ . There are general attacks called ``index calculus attacks'' on the discrete log problem in $(\mathbb{Z}/p\mathbb{Z}{})^*$ that are slow, but still faster than the known algorithms for solving the discrete log in a ``general'' group (one with no extra structure). For most elliptic curves, there is no known analogue of index calculus attacks on the discrete log problem. At present it appears that given $p$ the discrete log problem in $E(\mathbb{Z}/p\mathbb{Z}{})$ is much harder than the discrete log problem in the multiplicative group $(\mathbb{Z}/p\mathbb{Z}{})^*$ . This suggests that by using an elliptic curve-based cryptosystem instead of one based on $(\mathbb{Z}/p\mathbb{Z}{})^*$ one gets equivalent security with much smaller numbers, which is one reason why building cryptosystems using elliptic curves is attractive to some cryptographers. For example, Certicom, a company that strongly supports elliptic curve cryptography, claims:

``[Elliptic curve crypto] devices require less storage, less power, less memory, and less bandwidth than other systems. This allows you to implement cryptography in platforms that are constrained, such as wireless devices, handheld computers, smart cards, and thin-clients. It also provides a big win in situations where efficiency is important.''

For an up-to-date list of elliptic curve discrete log challenge problems that Certicom sponsors, see [#!certicom:challenge!#]. For example, in April 2004 a specific cryptosystem was cracked that was based on an elliptic curve over $\mathbb{Z}/p\mathbb{Z}{}$ , where $p$ has $109$ bits. The first unsolved challenge problem involves an elliptic curve over $\mathbb{Z}/p\mathbb{Z}{}$ , where $p$ has $131$ bits, and the next challenge after that is one in which $p$ has $163$ bits. Certicom claims at [#!certicom:challenge!#] that the $163$ -bit challenge problem is computationally infeasible.