The Elliptic Curve Discrete Logarithm Problem

Learn about the elliptic curve discrete logarithm problem and elliptic curve Diffie-Hellman problem, which are briefly explained in this lesson.


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

E(Fp)={(x,y)Fp×Fp:y2=x3+Ax+B}{O}.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 EE be an elliptic curve over the finite field Fp,PE(Fp)\mathbb{F}_{p}, P \in E\left(\mathbb{F}_{p}\right), a primitive element, and QE(Fp)Q \in E\left(\mathbb{F}_{p}\right) such that QP.Q \in\langle P\rangle . The ECDLP is to find an integer kk, where 1kE(Fp)1 \leq k \leq\left|E\left(\mathbb{F}_{p}\right)\right|, such that

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

So, given an integer kk and a point PP, the scalar multiplication kPk P is done by repeated addition, i.e., QQ is obtained by adding the point PP for kk 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.

Get hands-on with 1200+ tech skills courses.