A DIGITAL SIGNATURE ALGORITHM ON THE ALGEBRA OF 3×3 MATRICES, WHICH USES TWO HIDDEN GROUPS
D.V. Zakharov · Voprosy kiberbezopasnosti · 2025
Purpose of work is increasing the performance of algebraic digital signature algorithms based on the computational difficulty of solving large systems of power equations. Research methods: application of the algebra of matrices of dimension 3×3 defined over a finite field GF(p) as an algebraic support. Selection of triangular matrices as the algebra elements of prime order p. Application of an automorphic mapping of a non-commutative finite algebra to generate the required-order matrices having a general form. Results of the study: for the first time, the algebra of matrices of dimension 3×3 was used as an algebraic carrier of diital sinature algorithms, the security of which is based on the computational complexity of solving large systems of power equations. The randomization of the signature is provided by calculating it depending on two random elements selected from two hidden commutative groups, the elements of one of which are non-commutative with the elements of the other. Algorithms for calculating generators of hidden groups of orders p, p2 – 1 and p2 + p + 1 are proposed. For the first time, when calculating the elements of a public key from the elements of a secret key, an algebraic element of order two was used as a masking factor and the existence of a sufficiently large number of non-scalar matrices with order two was shown. An assessment of the security of the developed algorithm is given. Practical relevance: the scientific and practical significance of the results of the article consists in increasing the performance of post-quantum algebraic signature algorithms exploiting computational complexity of solving large systems of power equations.