New forms of defining the hidden discrete logarithm problem

Novel variants of defining the discrete logarithm problem in a hidden group, which represents interest for constructing post-quantum cryptographic protocols and algorithms, are proposed. This problem is formulated over finite associative algebras with noncommutative multiplication operation. In the known variant this problem, called congruent logarithm, is formulated as superposition of exponentiation operation and automorphic mapping of the algebra that is a finite non-commutative ring. As it has been shown before, congruent logarithm problem defined in the finite quaternion algebra can be reduced to discrete logarithm in the finite field that is an extension of the field over which the quaternion algebra is defined. Therefore further reseaches of the congruent logarithm problem as primitive of the post-quantum cryptoschemes should be carried out in direction of finding new carriers. This paper presents novel associative algebras possessing significantly different properties than quaternion algebra, in particular they contain no global unit. This difference demanded a new definition of the discrete logarithm problem in a hidden group, which is different from the congruent logarithm. Several variants of such definition, in which the notion of the local unite is used, are proposed. Right, left, and bi-side local unites are considered. Two general methods for constructing the finite associative algebras with non-commutative multiplication operation are proposed. The first method relates to defining the algebras having dimension value equal to a natural number $m>1$, and the second one relates to defining the algebras having arbitrary even dimensions. For the first time, the digital signature algorithms based on computational difficulty of the discrete logarithm problem in a hidden group have been proposed.