ALGEBRAIC SIGNATURE ALGORITHMS WITH TWO HIDDEN GROUPS
Nikolay Andreevich Moldovyan, Alexei Petrenko · Voprosy kiberbezopasnosti · 2025
Purpose of work is improving the performance of post-quantum algebraic signature algorithms based on the computational difficulty of solving large systems of power equations. Research methods: the use of two hidden commutative groups, the elements of one of which are non-commutative with the other, to ensure sufficient completeness of signature randomization in algebraic signature schemes, the security of which is based on the computational difficulty of solving large systems of power equations in the ground finite field GF(p). Calculation of the fitting signature in the form of a vector S depending on mutually non-commutative non-scalar vectors selected from hidden groups and a random scalar vector. The use of finite non-commutative associative algebras (FNAA) with a well-studied structure as an algebraic carrier of signature algorithms with a verification equation with multiple occurrences of the vector S. Defining the FNAAs by the sparse basic vector multiplication tables. Results of the study: three types of post-quantum algebraic signature schemes are proposed, differing in techniques for ensuring high security to the forging signature attacks using vector S as a fitting parameter of the attacks. The first type uses the technique of exponentiating the product, which includes vector S, to a large degree, the second type uses the exponentiation operation to a power equal to the value of the hash function calculated from S, and the third type uses the combination of the first two techniques. Algorithmic implementations of signature schemes of each type are carried out and the correctness of the developed algorithms is shown. Security to direct attack, to attack based on known signatures, and to signature forgery was assessed. A comparison of the proposed signature algorithms with known analogues is presented. The multiplication by a scalar vector when calculating vector S and setting the FNAAs by the sparse basis vector multiplication tables are used as techniques for improving the performance of algebraic signature algorithms. Practical relevance: the significance of the results of the article consists in testing a method for enhancing signature randomization, including calculating the signature fitting element S depending on the product of two non-commutative vectors, while developing algebraic algorithms of three different types, which are of interest as a prototype of a practical post-quantum signature standard. The results were obtained with the financial support of the project «Technologies for countering previously unknown quantum cyber threats», implemented within the framework of the state program of the «Sirius» Federal Territory «Scientific and technological development of the «Sirius» Federal Territory (Agreement No. 23-03 dated September 27, 2024).