Computational Complexity

The discrete logarithm problem (DLP) in a finite group is the basis for many protocols in cryptography. The best general algorithms which solve this problem have a time complexity of $O(\sqrt {N} \; log \;N)$ and a space complexity of $O( \sqrt N)$, where N is the order of the group. (If N is unknown, a simple modification would achieve a time complexity of $O(\sqrt N(log \; N)^2))$. These algorithms require the inversion of some group elements or rely on finding collisions and the existence of inverses, and thus do not adapt to work in the general semigroup setting. For semigroups, probabilistic algorithms with similar time complexity have been proposed. The main result of this article is a deterministic algorithm for solving the DLP in a semigroup. Specifically, let x be an element in a semigroup having finite order $N_x$. The article provides an algorithm, which, given any element $y ∈ ⟨x⟩$, provides all natural numbers m with $x^m = y$, and has time complexity $O(\sqrt N_x(log \; N_x)^2)$ steps. The article also gives an analysis of the success rates of the existing probabilistic algorithms, which were so far only conjectured or stated loosely.

Keywords: discrete logarithm problem; semigroups; complexity of algorithms

Introduction

Let G be a group and assume $x, y ∈ G$ are two elements of the group. We refer to x as the base element. The discrete logarithm problem (DLP) asks for the computation of an integer $m∈Z$ (assuming such integers exist) such that $x^m=y$. The DLP plays an important role in a multitude of algebraic and number theoretic cryptographic systems. Its use was introduced in the Diffie–Hellman protocol for public key exchange and has since seen a tremendous amount of development, generalizations, and extensions. Many modern-day systems for public key exchange use the DLP in a suitable group. The most commonly used groups have been the multiplicative group of finite fields and the group of points on an elliptic curve. The DLP in Jacobians of hyperelliptic curves and more general abelian varieties has also been studied extensively.

In this article, we compute complexities using group multiplications as one fundamental step. Thus, an exponentiation $x^e$ is performed in O(loge) steps. We will use the fact that for two lists of length n in which a match exists, a match can be found in $O(n \; log \; n)$ steps using standard sorting and searching algorithms. For a general finite group of order N , there exist algorithms that solve the DLP in $O(\sqrt N log \; N)$ steps. Such algorithms are said to produce a square root attack. The most well-known examples are Shank's baby step-giant step algorithm and the Pollard-Rho algorithm. Note that Shank's algorithm is a deterministic algorithm having time complexity $O(\sqrt N \; log \;N)$ and space complexity $O(\sqrt N)$. In contrast, Pollard's algorithm is a probabilistic algorithm having time complexity $O(\sqrt N \; log \;N)$ group multiplications and space complexity $O(1)$. If N is unknown, a simple modification of these algorithms would achieve a time complexity of $O(\sqrt N(log \; N)^2)$.

Elliptic curve groups have been widely implemented in practice since for a carefully selected elliptic curve group, the best known classical algorithm for solving DLP has running time $O(\sqrt N log \; N)$, where N is the group order. This is in contrast to many other finite groups such as the multiplicative group of a finite field and the group of invertible matrices over a finite field where algorithms with subexponential running time are known.

In cryptography the Diffie–Hellman protocol using a finite group has been generalized to situations where the underlying problem is a DLP in a semigroup or even to situations where a semigroup acts on a set. The interested reader will find more material in a recent survey by Goel et al.

It is naturally interesting to ask whether the DLP also has a square root attack in more generalized structures such as semigroups. Here, we define a semigroup as any set of elements with an associative binary operation. Since the best algorithms for the DLP all make use of the existence of inverses, it is unclear whether they can be generalized to a semigroup. However, when a special type of semigroup element, called a torsion element, is used as the base, it turns out that the DLP is reducible in polynomial time to the DLP in a finite group. A torsion element is one whose powers eventually repeat to form a cycle, and will be defined more precisely in Section 2. This section also elaborates more on why the standard collision-based algorithms are not directly adaptable to the semigroup case. A semigroup in which every element is torsion is called a torsion semigroup.

The DLP in semigroups with a torsion base element, in a classical setting, was first discussed by Monico in 2002, and later in a article by Banin and Tsaban in 2016. While the discussion in the present article is entirely on classical algorithms, it is also worth mentioning the paper, where the authors independently provide a quantum algorithm that solves the DLP in a torsion semigroup.

Both the algorithm of Monico and the one of Banin and Tsaban are probabilistic and might fail with low probability. Furthermore, some of their methods are heuristic, dependent on an oracle or some additional assumption, and their success rates and expected number of steps are either conjectured or stated loosely. It is therefore of interest to come up with an algorithm which deterministically computes the discrete logarithm in a semigroup. In this regard, we like to make some analogy to the problem of determining if an integer is a prime number, a problem of great importance in cryptography. Nowadays, in practice the algorithm of Miller  and Rabin has been implemented for many years. Still it was a great result when Agrawal et al. came up with a deterministic polynomial time algorithm to achieve this goal.

A key step in finding the discrete logarithm in a semigroup is computing the cycle length of an element. Both the algorithms rely on computing some multiple of the cycle length, and then removing "extra" factors by taking greatest common divisors (gcd's) until the cycle length is obtained. Once the cycle length value is obtained, the discrete logarithm may easily be computed with a few more simple steps. While Monico does not provide further elaboration on how this is done, the paper by Banin and Tsaban bridges this knowledge gap by showing how the problem is reduced to a DLP in a group once the cycle length and start values are known. Denote by $N_x$ the order of x (formally defined in Definition 4). The complexity of the algorithm is $O(\sqrt N_x (log N_x)^2 log \; log \;N_x)$, and that of the one is $O(\sqrt N_x (log \; N_x)^2)$. While both of the existing methods seem to succeed with high probability for practical values, we show that the process of taking successive gcd's/factors is unnecessary, and that one can deterministically find the cycle length. The main contribution of this article will be a deterministic algorithm for computing the discrete logarithm of an element y in some semigroup S with respect to some torsion base element $x∈S$. The time complexity of our algorithm is $O(\sqrt N_x(log N_x)^2)$.

The article is structured as follows: After providing preliminaries and basic definitions in Section 2, we will analyse in Section 3 the success rates and expected number of steps involved in the probabilistic algorithms for cycle length by Banin and Tsaban (Algorithm 1) and Monico (Algorithm 3.1).

In Section 4, which is the main section of this article, we provide a deterministic algorithm to calculate the cycle length $L_x$ of a torsion element x of a semigroup and thus to also solve the DLP, without the use of an oracle. This algorithm has complexity $O(\sqrt N_x ⋅ (log N_x)^2)$. For completeness, we will also demonstrate the use of Pohlig–Hellman algorithm for a semigroup.

Source: Simran Tinani and Joachim Rosenthal, https://www.degruyter.com/document/doi/10.1515/jmc-2021-0022/html?lang=en
This work is licensed under a Creative Commons Attribution 4.0 License.