ELEMENTS OF HIGH ORDER FOR CRYPTOSYSTEMS WITH NON-ABELIAN PLATFORM GROUPS - POPOVYCH, BOGDAN; POPOVYCH, ROMAN (Herald of Khmelnytskyi National University. Technical sciences, 2023)
The security of a number of well-known cryptographic primitives (Diffie-Hellman protocol, El-Gamal public key cryptosystem, El-Gamal digital signature) is based on the computational complexity of the discrete logarithm problem in a finite cyclic group. In the case of both abelian and non-abelian groups, this complexity is ensured by construction of elements of high (ideally, maximum possible) order from the group. Actually, such elements are used in the implementation of corresponding asymmetric cryptosystems. However, for the case of a non-abelian group, it is not known how to explicitly obtain such elements. Therefore, it is customary to take random elements, that does not guarantee the system's resistance to hacking.The paper shows how to explicitly construct two high order elements that do not commute for the case of non-abelian group of square matrices with nonzero determinant over an arbitrary finite field. To obtain such two elements, known results on the construction of high order elements in finite fields of general form were used. The key idea is to form a matrix whose determinant is equal to high order element in the finite field. Then the order of this element is a lower bound for the order of the matrix. As one of the options, it is proposed to form such a matrix as a product of lower triangular and upper triangular matrices. Post-quantum asymmetric cryptosystems that use high order elements from the specified group are considered. It is shown how, using the constructed elements, to implement the cryptosystem that is analogous to the El-Gamal cryptosystem in the non-commutative case. A simple computational example is given that illustrates the implementation of this cryptosystem in the case of 2×2 matrices with elements from a finite field with 256 elements. Cryptosystems in the field of multivariate cryptography are also considered, for the construction of which high order elements from the specified group of matrices are required. Obtained results can be used in the construction of various post-quantum primitives.
Keywords: cryptographic information protection; finite field; general linear group; order of element; post-quantum cryptosystem