The Discrete Logarithm Problem

The DLP in $\mathbb{F}_{p}^{*}$

As discussed in the previous sections, the first published public-key system by Diffie and Hellman is based on the discrete logarithm problem in the multiplicative group $\mathbb{F}_{p}^{*}$ of a finite field, with $p$ prime. According to the primitive root theorem :Primitive_Root_Theorem , there exists a primitive element $a \in \mathrm{F}_{p}^{*}$ that generates the whole group, i.e.,

$$F_{p}^{*}=\langle a\rangle=\left\{1, a, a^{2}, \ldots, a^{p-2}\right\}.$$

Discrete logarithm problem (DLP) in $\mathbb{F}_{p}^{*}$

Definition:

Let $a$ be a primitive element (i.e., a generator) of the cyclic group $\mathbb{F}_{p}^{*}$ and $b \in \mathbb{F}_{p}^{*}$. The DLP is the problem of finding an exponent $x$ such that

$$a^{x} \equiv b \quad mod \space p$$

$x$ is said to be the discrete logarithm of $b$ to the base $a$. However, if there exists a solution for $x$, then there’s an infinite number of solutions to this problem. Due to Fermat’s little theorem :Fermats_Little_Theorem , it holds that

$$a^{p-1} \equiv 1 \quad mod \space p,$$

and hence

$$a^{x+k(p-1)}=a^{x} \cdot\left(a^{p-1}\right)^{k} \equiv b \cdot 1^{k} \equiv b \quad mod \space p.$$

Thus, we conclude that if $x$ is a solution to the problem $a^{x} \equiv b \quad mod \space p$, then $x+k(p-1)$ is also a solution for every $k \in \mathbb{Z}$.

Computing the DLP in $\mathbb{F}_{p}^{*}$ is a very hard computational problem if $p$ is sufficiently large. Since $a^{x} \equiv b \quad mod \space p$ can be computed efficiently if $x$ is known, this serves as a one-way function. However, there are several well-known attacks against the DLP, which we introduce in this section.

The generalized discrete logarithm problem

So far, we just considered the DLP in the multiplicative group $\mathrm{F}_{p}^{*}$. However, the DLP isn’t restricted to only this group, but rather can generally be defined over any cyclic group.

Generalized DLP

Definition:

Let $G$ be a cyclic group with group operation *, a primitive element $a \in G$ and any given $b \in G$. Then, the discrete logarithm problem for $G$ is to find an integer $x$ that satisfies

$$a^{x}=\{a * a * \ldots * a\}_{x \text { times }}=b .$$

Every group $G$ has its own discrete logarithm problem, whereas the difficulty of the DLP depends on the structure of $G$. We consider the DLP for the following three cyclic groups: the additive group $\left(\mathbb{Z}_{n},+\right)$, the multiplicative group $\left(\mathbb{F}_{p}^{*}, \cdot\right)$, and the elliptic curve $\left(E\left(\mathbb{F}_{p}\right),+\right)$.

1. For $\left(\mathbb{Z}_{n},+\right)$, the DLP is to find an integer $x$ for two given $a, b \in \mathbb{Z}_{n}$ such that $x \cdot a=b \quad mod \space n$. This problem can be solved very easily since it works by using the Euclidean algorithm that takes $\mathcal{O}(\log (n))$ steps and hence works in polynomial time.

2. For $\left(\mathbb{F}_{p}^{*}, \cdot\right)$, the DLP is according to this definition. The solution is hard. For example, there exists the index calculus method that works in sub-exponential time. The best-known algorithm is the generalized number field sieve, which also has a sub-exponential running time.

3. For $\left(E\left(F_{P}\right),+\right)$, the DLP (known as ECDLP) is to find an integer $x$ for two given points $P, Q \in\left(E\left(F_{p}\right),+\right)$ such that $x P=Q .$ However, the problem is very hard to solve since the fastest known algorithm takes $\mathcal{O}(\sqrt{p})$ steps and hence needs fully exponential time.

In conclusion, the ECDLP is harder than the DLP in $\left(\mathbb{F}_{P}^{*}, \cdot\right)$, provided that the orders of the groups are about the same.