On Multivariate Algorithms of Digital Signatures Based on Maps of Unbounded Degree Acting on Secure El Gamal Type Mode

Abstract

Multivariate cryptography studies applications of endomorphisms of K[x1 x2, ..., xn] where K is a finite commutative ring given in the standard form xi →f1 (x1, x2,..., xn), i=1, 2,..., n. The importance of this direction for the constructions of multivariate digital signatures systems is well known. Close attention of researchers directed towards studies of perspectives of efficient quadratic unbalanced rainbow oil and vinegar system (RUOV) presented for NIST postquantum certification. Various cryptanalytic studies of these signature systems were completed. During Third Round of NIST standardisation projects ROUV digital signature system were rejected. Recently some options to seriously modify theses algorithms as well as all multivariate signature systems which alow to avoid already known attacks were suggested. One of the modifications is to use protocol of noncommutative multivariate cryptography based on platform of endomorphisms of degree 2 and 3. The secure protocol allows safe transfer of quadratic multivariate map from one correspondent to another. So the quadratic map developed for digital signature scheme can be used in a private mode. This scheme requires periodic usage of the protocol with the change of generators and the modification of quadratic multivariate maps. Other modification suggests combination of multivariate map of unbounded degree of size O(n) and density of each fi of size O(1). The resulting map F in its standard form is given as the public rule. We suggest the usage of the last algorithm on the secure El Gamal mode. It means that correspondents use protocols of Noncommutative Cryptography with two multivariate platforms to elaborate safely a collision endomorphism G: xi → gi of linear unbounded degree such that densities of each gi are of size O(n2). One of correspondents generates mentioned above F and sends F+G to his/her partner.

The security of the protocol and entire digital signature scheme rests on the complexity of NP hard word problem of finding decomposition of given endomorphism G of K[x1,x2,...,xn] into composition of given generators 1G, 2G, ...tG, t>1 of the semigroup of End(K[x1,x2,...,xn]). Differently from the usage of quadratic map on El Gamal mode the case of unbounded degree allows single usage of the protocol because the task to approximate F via interception of hashed messages and corresponding signatures is unfeasible in this case.