The Elliptic Curve Discrete Logarithm Problem

Definition

The elliptic curve discrete logarithm problem (ECDLP) is the discrete logarithm problem over the elliptic curve

$$E\left(\mathbb{F}_{p}\right)=\left\{(x, y) \in \mathbb{F}_{p} \times \mathbb{F}_{p}: y^{2}=x^{3}+A x+B\right\} \cup\{\mathcal{O}\}.$$

Elliptic curve discrete logarithm problem (ECDLP)

Let $E$ be an elliptic curve over the finite field $\mathbb{F}_{p}, P \in E\left(\mathbb{F}_{p}\right)$, a primitive element, and $Q \in E\left(\mathbb{F}_{p}\right)$ such that $Q \in\langle P\rangle .$ The ECDLP is to find an integer $k$, where $1 \leq k \leq\left|E\left(\mathbb{F}_{p}\right)\right|$, such that

$$k P=\{P+P+\ldots+P\}_{k \space times }=Q .$$

So, given an integer $k$ and a point $P$, the scalar multiplication $k P$ is done by repeated addition, i.e., $Q$ is obtained by adding the point $P$ for $k$ times to itself.

The ECDLP is of fundamental importance for elliptic curve cryptography since all public-key ECC algorithms are based on the assumption that the ECDLP is very hard to compute. Since ECC schemes rely on scalar multiplication, the intractability of the ECDLP is crucial for any security of elliptic curve cryptosystems. The German Federal Office for Information Security (BSI) defines this aspect as follows:

Cryptographically strong elliptic curve groups

An elliptic curve group is called cryptographically strong if the underlying ECDLP is considered to be computationally intractable for the application in use.

The ECDLP is considered to be a very hard computational problem in general when appropriate curve parameters have been chosen. However, there are existing attacks that circumvent the hardness and hence weaken the elliptic curve. These attacks could be easily avoided if the domain parameters fulfill certain conditions. As a consequence, the strength of an elliptic curve depends on the choice of the elliptic curve domain parameters. In o rder to define cryptographically strong elliptic curve domain parameters in this section, we first outline the different well-known attacks on the ECDLP in this lesson.