Abstract:
In the field of post-quantum public-key cryptography, a direction of development of practical algebraic signature algorithms with a secret group is of particular interest, the security of which is based on the computational difficulty of solving large systems of power equations. As an algebraic carrier of such algorithms, finite non-commutative associative algebras (FNAA) are used. A specific point related to ensuring security against attacks based on known signatures when developing digital signature schemes of this type is the presence of the problem of improving the randomization mechanism of the fitting element of the digital signature, which is a vector S, repeatedly included in the verification equation as a multiplier. A well-known solution to this problem based on the use of two commutative secret groups, such that the elements of one of them are non-commutative with the elements of the other, when using the hash function value from S in the verification equation leads to an increase in the size of the digital signature, due to the need to specify two auxiliary fitting signature elements. The article proposes a new mechanism for signature randomization, which is distinguished by calculating the value of S depending on two vectors randomly selected from one commutative secret group. The proposed mechanism provides an acceptable security level against attacks based on known signatures and can be used as a basis for developing digital signature schemes with one verification equation and one auxiliary fitting signature element. A new algebraic algorithm has been developed that is of interest as a prototype of a practical post-quantum digital signature standard. Estimates of its parameters are given when using FNAA and the algebra of 3$\times$3 matrices defined over a finite field as an algebraic support.
Keywords:post-quantum cryptography, multivariate cryptography, digital signature algorithm, signature randomization, cryptoalgorithm on finite algebras, cryptoalgorithm on non-commutative algebras, secret group.
Fulltext:
PDF file (2068 kB)