Paper 2026/942 Original: eprint.iacr.org/2026/942 ↗

On the Investigation of Variants for Discrete Logarithm Problems in Abelian Groups: An Algebraic Structure Approach

Abstract

In this work, we investigate variants of the discrete logarithm problem (DLP) based on different algebraic group properties. We demonstrate that within abelian groups—particularly cyclic groups—the problems $\text{DLP}^2$ and, more generally, $\text{DLP}^n$ are polynomially reducible to solving multiple instances of the classical DLP. This result confirms that multi-generator variants in abelian settings inherit the vulnerabilities of the conventional DLP and therefore provide no additional resistance against quantum attacks such as Shor’s algorithm. Motivated by this limitation, we propose that $\text{DLP}^n$ should instead be formulated in non-abelian groups. Specifically, let $G$ be a non-abelian group. Given generators $g_1, g_2, \dots , g_n \in G$ of cyclic subgroups $H_1, H_2, \dots, H_n$ of $G$, respectively, and an element $A \in G$, the problem is to find $(\alpha_1, \alpha_2, \dots , \alpha_n)$ such that $A = \prod_{i=1}^n g_i^{\alpha_i}$, where $0 \leq \alpha_i <|H_i|$. This formulation leverages the non-commutative structure of $G$, which may obstruct reductions that trivialize multi-generator variants in abelian groups. Our findings strongly motivate the exploration of quantum-resistant cryptographic primitives in non-commutative algebraic structures, as these settings may evade known quantum attacks and provide new hardness assumptions for post-quantum security.