R. S. Fahrutdinov, Head of Laboratory, e-mail: fahr@cobra.ru, A. Yu. Mirin, Senior Researcher, e-mail: mirin@cobra.ru, D. N. Moldovyan, Researcher, e-mail: mdn.spectr@mail.ru, A. A. Kostina, Researcher, e-mail: anna-kostina1805@mail.ru, St. Petersburg Institute for Informatics and Automation of the Russian Academy of Sciences, St. Petersburg, 199178, Russian Federation

Public Key-Agreement Schemes Based on the Hidden Discrete Logarithm Problem

There is considered the problem of increasing the performance of the public key-agreement schemes based on the computational complexity of the hidden discrete logarithm problem defined in finite non-commutative associative algebras of various types. To increase the rate of cryptoschemes of the said type, it is proposed to use algebras as their algebraic support, in which the associative multiplication operation is specified using sparse multiplication tables of basis vectors. In framework of this method the rate increase is achieved by a significant reduction in the number of multiplications in the finite field, over which the algebra is specified, which are necessary to perform one multiplication operation in the algebra. The principal realizability of this method has
been demonstrated for cases of four-dimensional and six-dimensional algebras, for which the sparse tables are given that specify the associative multiplication operation and providing two-times reduction of the number of multiplications in the field. Another proposed way to increase the rate is to specify the procedure for generating permutable key elements in the form of a computational procedure performed according to specially derived mathematical formulas, free from the operation of exponentiation to a large-size integer power. The second method is based on the idea of defining a set of mutually permutable vectors of a finite non-commutative associative algebra, described by a fairly compact mathematical formula. Moreover, the latter defines a procedure for calculating a random vector from the indicated set of vectors, which has significantly lower computational complexity compared to the exponentiation operation used in well-known cryptoschemes of the considered type to generate random pairs of permutable vectors. The potential feasibility of the second method is demonstrated by the derivation of the indicated formula for a four-dimensional algebra given by sparse multiplication tables of basis vectors. Specific public key-agreement cryptoschemes have been developed that implement the developed methods for increasing performance, which are of interest for practical use as post-quantum public key-agreement schemes. To further increase the performance of cryptoschemes of the considered type, it is proposed to use the algebras set over finite extensions of a binary field.
Keywords: information protection, cryptography, public key-agreement, discrete logarithm problem, finite associative algebra, non-commutative algebra, global unit, local unit, left-sided unit

P. 577–585

Acknowledgements: This work was supported by the budget theme ¹ 0060-2019-0010.