Discrete logarithms for finite groups (Q2390938)

Let \(G\) be an arbitrary finite group, \({ \alpha}=( \alpha_{1}, \dots , \alpha_{t})\) an ordered \(t\)-tuple of elements of \(G\) such that \(G= \langle \alpha_{1}, \dots , \alpha_{t} \rangle\) and \[ S_{k}( \alpha)= \{ \prod_{i=1}^{k}( \alpha_{1}^{x_{i,1}} \cdots \alpha_{t}^{x_{i,t}}) \mid x_{i,j} \in { \mathbb Z}\}. \] Since \(G= \langle \alpha_{1}, \dots , \alpha_{t} \rangle\), there is a smallest positive integer \(k_{0}\) such that for each \(k \geq k_{0}\), \(G \subset S_{k}( \alpha)\). The integer \(k_{0}\) is called the \textit{depth} of \(G\) relative to \( \alpha\) and if \(k \geq k_{0}\), it is said that \(S_{k}( \alpha)\) \textit{covers} \(G\). Given an element \(y \in G\), the \textit{generalized discrete logarithm problem} (GDLP) for \(y\) with respect to \( \alpha\) is defined as follows: find a positive integers \(k\) and a \(kt\)-tuple of non-negative integers \(x=(x_{1,1}, \dots ,x_{1,t}, \dots , x_{k,1}, \dots ,x_{k,t})\) such that \[ y= \prod_{i=1}^{k}( \alpha_{1}^{x_{i,1}} \cdots \alpha_{t}^{x_{i,t}}). \tag{1} \] If \(k\) is the smallest positive integer for which \(y \in S_{k}( \alpha)\), the lexicographically smallest \(kt\)-tuple \((x_{1,1}, \dots ,x_{1,t}, \dots ,x_{k,1}, \dots ,x_{k,t})\) among all the \(kt\)-tuples of non-negative integers satisfying equation (1) is called the \textit{discrete logarithm of \(y\) with respect to} \( \alpha\). Moreover, the problem of determining the discrete logarithm of \(y \in G\) with respect to \( \alpha\) is referred to as the \textit{discrete logarithm problem} (DLP) \textit{with respect to} \( \alpha\). The paper concerns group-theoretic and cryptographic properties of the above defined generalized discrete logarithm problem. The authors investigate several questions related to properties which contribute to cryptographic security, such as distributional, coverage and complexity properties. They show that the distribution of elements in a certain multiset tends to uniform. In particular, the authors consider the family of finite non-abelian groups \(PSL_{2}({ \mathbb F}_{p})\), \(p\) a prime, as possible candidates in the design of new cryptographic primitives, based on the generalized discrete logarithm.