New Forms of Defining the Hidden Discrete Logarithm Problem
Abstract
There are introduced novel variants of defining the discrete logarithm problem in a hidden group, which represents interest for constructing post-quantum cryptographic protocols and algorithms. This problem is formulated over finite associative algebras with non-commutative 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. Earlier it has been shown that 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 investigations of the congruent logarithm problem as primitive of the post-quantum cryptoschemes should be carried out in direction of finding new its carriers. The present paper introduces novel associative algebras possessing significantly different properties than quaternion algebra, in particular they contain no global unit. This difference had demanded a new definition of the discrete logarithm problem in a hidden group, which is different from the congruent logarithm. There are proposed several variants of such definition, in which it is used the notion of the local unite. There are considered right, left, and bi-side local unites. 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.
Published
How to Cite
Section
Copyright (c) 2019 Александр Андреевич Молдовян, Николай Андреевич Молдовян
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).