Abstract—This research introduces two novel algebraic signature algorithms with a hidden group, which are based on the computational difficulty of finding a solution of a large system of quadratic multivariate equations. Like signature algorithms of multivariate cryptography, the developed ones represent interest as post-quantum cryptoschemes, the latter having a significant merit consisting of a 100 or more times smaller size of public key. The introduced algorithms represent interest as candidates for a practical post-quantum signature standard with small sizes for both the signature and the public key. Their security is estimated to be vulnerable to direct attacks using the known algorithms for solving the systems of many quadratic equations. The development of structural attacks exploiting properties of the used algebraic support is estimated as an independent research task composing the next stage of the analysis of the proposed signature algorithms on finite non-commutative associative algebras. Relatively the known algebraic signature algorithms with a hidden group, which are based on the computational difficulty of the so called hidden discrete logarithm problem, the developed signature algorithms differ in the use of the signature verification equations with multiple entry of signature. This feature defines a specific technique for the signature generation. The next peculiarity is the use of algebras of higher dimensions set over the finite fields of smaller orders.
 
Keywords—computer security, post-quantum cryptography, multivariate cryptography, digital signature, finite algebra, associativity, non-commutativity, hidden group


Copyright © 2023 by the authors. This is an open access article distributed under the Creative Commons Attribution License (CC BY-NC-ND 4.0), which permits use, distribution and reproduction in any medium, provided that the article is properly cited, the use is non-commercial and no modifications or adaptations are made.