The discrete logarithm problem

We know that most public cryptosystems are based on hard computational problems. One of them is the discrete logarithm problem. Let's find out about it.

The general statement

Suppose we have some finite cyclic group $G$, written multiplicatively. Let's recall that a cyclic group means that there is an element $g$ called a generator, such that every element $h$ of the group is some power of $g$: $h = g^{x}$. So, a cyclic group of order $n$ (containing $n$ elements) looks like

$G = \{g, g^{2}, g^{3}, \ldots, g^{n-1}, g^{n} =e\}$When we work with real numbers, the power to which we have to raise a real number $b$ to produce a real number $t$, is called the logarithm of $t$ to base $b$ and denoted as $\log_{b}t$. We can also refer to it as a discrete logarithm of $h$ (to base $g$) and write this as $x = \log_{g}h$.

You can notice that, if $g^{x} = h$ in $G$, then also $g^{x + n} =g^{x} \cdot g^{n} = h$. So, if we want the discrete logarithm of $h$ (to base $g$) to be unique, we should refine the definition a bit:

Definition. Let $G$ be a cyclic group with a generator $g$. The discrete logarithm of $h \in G$ to base $g$ is the least non-negative integer $x$ such that

$h = g^{x}$The question is: can we efficiently find this discrete logarithm $x$, knowing $g$ and $h$?

The word "efficiently" is crucial here. No doubt we can begin to patiently check all possible powers, computing $g^{z}$ for $z = 0, 1, 2, 3 \ldots$ and comparing the result to $x$. Sooner or later, we'll encounter our $x$ (remember that $g$ is a generator). But it can be later rather than sooner. For a huge group $G$ and an unlucky choice of $h$, thousands of years may pass before we'll find $x$ through this trial-and-error process.

Do we know an efficient algorithm for the problem of finding the discrete logarithm (which is called the discrete logarithm problem, or simply DLP)? It depends on the group $G$.

When DLP is easy

The first example of a finite cyclic group is $(\mathbb{Z}_{m}, +)$ — integers modulo $m$ with respect to addition. We can write its elements as $\overline{0}, \overline{1}, \ldots, \overline{m - 1}$ or as $0 \bmod m, 1 \bmod m, \ldots, (m-1) \bmod m$Since in this topic we will often switch between different values of $m$, we will prefer the second form of notation, although it may seem cumbersome.

For every $m$, $g = 1 \bmod m$ is a generator in $\mathbb{Z}_{m}$ — every other element $h \bmod m$ of this group can be presented as a sum of $h$ instances of $g$.

For example, if $m = 100$ and $h = 19$, we immediately notice that $h = 19g = \underbrace{g + g + \ldots + g}_{19 \text{ times}}$ and can conclude that $\log_{g}h = 19$.

Of course, finding a logarithm in $\mathbb{Z}_{100}$ is especially easy with $g = 1 \bmod 100$. But even if we chose another generator for $(\mathbb{Z}_{100}, +)$, say, $g = 3 \bmod 100$ or $g = 69 \bmod 100$, the discrete logarithm problem wouldn't become much harder. In fact, for any $m, g, h$, finding $\log_{g}h$ in $(\mathbb{Z}_{m}, +)$ requires just solving a congruence

$h \equiv xg \pmod m$It can can be done efficiently using extended Euclid's algorithm.

When DLP is hard

We considered $(\mathbb{Z}_{100}, +)$ as an example above. Now let's look at another cyclic group of the same order:

$(\mathbb{Z}^{*}_{101}, \cdot)$It is the group of non-zero integers modulo 101 with respect to multiplication, and it's also cyclic. The last claim is certainly not obvious and follows from the theory of finite fields. In fact, for any prime number $p$ $(\mathbb{Z}^{*}_{p}, \cdot)$is a cyclic group of order $p-1$, that is, all its $p-1$ elements are powers of some $g$. For $p = 101$ you can take, for instance, $g = 3 \bmod 101$ as a generator (but there are other elements that can play this role).

Now, what is $log_{3}h$ for some $h \in \mathbb{Z}^{*}_{101}$ — say, $h = 19$? It's an integer $x$ such that

$19 \equiv 3^{x} \pmod {101}$For $\mathbb{Z}^{*}_{101}$, you can just check all possible $x$'s using your computer (you have to try only $x$'s from 1 to 100). But what about finding a discrete logarithm in $\mathbb{Z}^{*}_{p}$ if $p$ is really huge? It turns out there is no efficient (that is, requiring a reasonable amount of time) algorithm to solve such congruences. To be more precise, nobody has invented this algorithm, as well as nobody has proved it doesn't exist. But nonetheless, the lack of known efficient algorithms for DLP in $\mathbb{Z}^{*}_{p}$ gives an opportunity to build some cryptographic protocols.

To be more concrete about inefficiency of the currently known algorithms, we can say that for now, discrete logarithm computation in $\mathbb{Z}^{*}_{p}$ for 795-bit $p$ (not so long a number, in fact — roughly 240 decimal digits) is considered a record.

There are other groups where the discrete logarithm problem is hard, and some cryptographic protocols initially developed for $\mathbb{Z}^{*}_{p}$ can be modified to work with such groups. An especially interesting example — or, rather, a range of examples — is provided by so-called elliptic curves (google these words if you're not afraid to see how abstract algebra meets geometry!)

An important point is that in a group $G$ with known generator $g$, we can quickly find $h = g^{x}$ if we know $x$. But the recovery of $x$ from known $g$ and $h$ becomes — in a suitable $G$ — a hard problem. The cases when a problem has an efficient algorithm, but the inverse problem has none, are loved by cryptographers. An honest user of a cryptosystem has to solve an easy problem, while the adversary has to crack the hard inverse.

Conclusion

• The discrete logarithm problem (DLP) in a finite group with the generator $g$ consists in finding the least non-negative integer $x$, such that $g^{x}$ is equal to a given $h$.

• There are some groups, for which we can solve DLP efficiently.

• But in the general case, and, in particular, in $\mathbb{Z}^{*}_{p}$ for a prime $p$, DLP is considered a hard problem, for which no one knows an effective algorithm.

• It is not proven yet that the effective algorithm can't exist. But all efforts to find such an algorithm haven't been fruitful so far.

• It's easy to raise an element of a cyclic group to some known power, but it's hard to find the discrete logarithm. This allows to build some cryptographic protocols.