Discrete Logarithm Assumption

The so-called Discrete Logarithm Problem (DLP), also called the Discrete Logarithm Assumption, is one of the most fundamental assumptions in cryptography.

Definition: Let $G$ be a finite cyclic group of order $r$ and let $g$ be a generator of $G$. We know that there is an exponential map $g^{(·)} : Z_r → G ; x → g^x$ that maps the residue classes from modulo $r$ arithmetic onto the group in a $1 : 1$ correspondence. The Discrete Logarithm Problem is the task of finding an inverse to this map, that is, to find a solution $x ∈ Z_r$ to the following equation for some given $h, g ∈ G$:

$$h = g^x$$

There are groups in which the DLP is assumed to be infeasible to solve, and there are groups in which it isn’t. We call the former group DL-secure groups.

Rephrasing the previous definition, it is believed that, in DL-secure groups, there is a number $n$ such that it is infeasible to compute some number $x$ that solves the equation $h = g^x$ for a given $h$ and $g$, assuming that the order of the group $n$ is large enough. The number $n$ here corresponds to a chosen security parameter.