On Schubert cells of projective geometry and pseudo- quadratic public keys of multivariate cryptography ⋆ Vasyl Ustimenko1,2,† and Oleksandr Pustovit2,*,† 1 Royal Holloway University of London, TW20 0EX Egham, United Kingdom 2 Institute of Telecommunications and Global Information Space, 13 Chokolivsky ave., 02000 Kyiv, Ukraine Abstract Jordan-Gauss graphs are bipartite graphs given by special quadratic equations over the commutative ring K with unity with partition sets K n and K m, n≥m such that the neighbour of each vertex is defined by the system of the linear equation given in its row-echelon form. Assume that K is a finite multivariate commutative ring and the cardinality of multiplicative group K* is >2. We use families of these graphs for the construction of new injective multivariate maps F of (K*) n onto Kn of unbounded degree of size O(n) with the trapdoor accelerators T, i.e. pieces of information which allows us to compute the reimage of the given value of F in polynomial time. The number of monomial terms of multivariate rule F written in its standard form (the density) is O(n2). Thus public user can encrypt his/her message in time O(n3) similar to the case of a quadratic map. This cryptosystem can be obfuscated via the use of a temporal analogue of selected Jordan-Gauss graphs. Previously known multivariate cryptosystems of unbounded degree have density O(n4) of F allowing us to use the inform in the case of finite field it can be used for the construction of new cryptosystems from known pairs (F, T). Keywords multivariate cryptography, Jordan-Gauss graphs, projective geometries, temporal graphs, largest Schubert cells, symbolic computations 1 1. Introduction 3]). The first 4 winners of this competition were announced in 1922, they were developed in terms of Lattice Theory. This paper presents the modification of the quadratic Noteworthy that the NIST tender was designed for the multivariate public key given in [1] and defined via special selection and investigation of public key algorithms and in walks on projective geometries over finite fields and their the area of multivariate cryptography only quadratic natural analogs defined over general commutative rings. multivariate maps were investigated. We have to admit that New graph-based multivariate rules are “pseudo quadratic”, general interest in various aspects of multivariate i.e., they are maps of unbounded degree of size O(n) but the cryptography was connected with the search for secure and number of monomial terms in all equations is O(n2). So, like effective procedures of digital signature where mentioned in the case of a quadratic map the computation of the value above ROUV cryptosystem was taken as a serious candidate of the map on the given tuple costs O(n3). to make the shortest signature. Multivariate cryptography is one of the five main Let us summarize the outcomes of the mentioned above directions of Post-Quantum Cryptography. NIST tender. The progress in the design of experimental quantum There are 5 categories that were considered by NIST in computers is speeding up lately. Expecting such development the PQC standardization (the submission date was 2017; in the National Institute of Standardisation Technologies of USA July 2022, the 4 winners and the 4 final candidates were announced in 2017 the tender on the standardisation best proposed for the 4th round—this is the current official status. known quantum-resistant algorithms of asymmetrical However, the current 8 final winners and candidates only cryptography. The first round was finished in March 2019, and belong to the following 4 different mathematical problems essential parts of the presented algorithms were rejected. At the (not the 5 announced at the beginning): same time, the development of new algorithms with a postquantum perspective was continued. A similar process  Lattice-based took place during the 2, 3, and 4th rounds.  Hash-based The last algebraic public key “Unbalanced Oil and Vinegar  Code-based on Rainbow like digital signatures” (ROUV) constructed in  Supersingular elliptic curve isogeny based. terms of multivariate cryptography was rejected in 2021 (see [2, The standards are partially published in 2024. CPITS-II 2024: Workshop on Cybersecurity Providing in Information 0000-0002-2138-2357 (V. Ustimenko); and Telecommunication Systems II, October 26, 2024, Kyiv, Ukraine 0000-0002-3232-1787 (O. Pustovit) ∗ Corresponding author. © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). † These authors contributed equally. vasyl.ustymenko@rhul.ac.uk (V. Ustimenko); sanyk_set@ukr.net (O. Pustovt) CEUR Workshop ceur-ws.org ISSN 1613-0073 198 Proceedings It’s interesting that the new obfuscation “TUOV: Triangular the ciphertext c=F(p). He sends c to Alice via the open Unbalanced Oil and Vinegar” was presented to NIST by channel. Her knowledge of T allows Alice to restore p as F- principal submitter Jintaj Ding [4]. 1 (c). The historical development of Classical Multivariate In both schemes, correspondents would like to use F as Cryptography which studies quadratic and cubic one way function for which reimages of b or p are endomorphisms of Fq[x1, x2,…, xn] can be found in [5] and impossible to compute in polynomial time without the [6]. Current research in Postquantum Cryptography can be knowledge of T. found in [5, 7–23]. The search for multivariate one way functions is Section 2 contains some definitions of Multivariate motivated by the following gap between linearity and Cryptography over a general commutative ring. nonlinearity. In Section 3 we introduce the concept of linguistic We know that the system of linear equations written over graphs and Jordan-Gauss graphs defined over commutative the field F can be solved in time O(n3) via the Jordan-Gauss ring K together with the examples of such graphs which elimination method. The complexity of solving a nonlinear appear as bipartite-induced subgraphs of the Incidence system of constant degree d, d>1 is subexponential (see [24, Graph of Projective Geometry or its analogue defined over 25]). Despite the convenience of the Groebner-Shirshov basis K. method [26] for the implementation the complexity of this Equations of some graphs are given explicitly. We algorithm is equivalent to the old Gauss elimination method define the temporal analogue of linguistic graphs. for the solution of the system of nonlinear equations. There is Section 4 is dedicated to the constructions of a standard way to transform of nonlinear system of equation multivariate rules with trapdoor accelerators in terms of of degree d, d>2 to an equivalent quadratic system via the linguistic graphs. In the case of Cellular Schubert graphs or introduction of additional variables and substitutions (see their temporal analogue we evaluate the density of [5]). constructed multivariate rules. So if we have a nonlinear map F of bounded degree d in In Section 5 we describe the Eulerian subgroup of “general position” which has a trapdoor accelerator T then transformations of Affene Cremona semigroup of all the corresponding cryptosystem is secure. This status endomorphisms of K[x1, x2,…, xn]. Eulerian transformation insures the fact that F is given as one way function i.e. maps each variable x_i into a monomial term. reimage of F is impossible to compute in a polynomial time The new cryptosystem is described in Section 6. This without knowledge of the secret T. map is formed as the composition of Eulerian The map F is not in a “general position” if some transformation J, transformation F defined in terms of additional specific information is known. For instance, if F special Jordan-Gauss graphs in Section 4, and element L is the bijective cubic map and F-1 is also cubic. The public from AGLn(K). The complexity of the decryption procedure user can generate O(n3) pairs of kind plaintext is estimated there. p/corresponding ciphertext c and approximate inverse map Section 7 contains concluding remarks. in time O(n10). Known computer tests and cryptanalytic methods 2. On the tasks of multivariate ensure that map F is “in general position”. Noteworthy that the existence of one way function is not proven yet even cryptography over arbitrary under the main complexity conjecture that P≠NP. finite commutative ring It is well known that the investigation of nonlinear This paper is dedicated to the construction of public maps F systems of equations over the commutative ring K with zero of multivariate cryptography transforming the tuple (x1, x2, divisors is essentially a harder case in comparison to the ..., xn) from Kn to (f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., fk(x1, x2, case of a field. ..., xn)) from Kk where K is a finite commutative ring with Multivariate cryptography over rings with zero divisors unity and polynomials fiϵK[x1, x2, ..., xn] are written in their is a brand new direction of research. Another idea is the standard forms, i.e. lists of their monomial terms ordered construction of functions F of unbounded degree of size O(n) lexicographically. with the trapdoor accelerators. As we already mentioned We say that piece of information T is a trapdoor there is a reduction of arbitrary system of nonlinear accelerator of F if T is the piece of information such that its equations to the system of quadratic equations. This method knowledge allows us to compute the reimage of F for given leads to the nonlinear increase of a number of variables. The value b from Kk in a polynomial time O(nα). change of practically used hundreds of variables for several Classical multivariate cryptography uses surjective map thousands of them makes it impossible to use the Groebner F defined over finite field K=Fq with the trapdoor accelerator basis technique as a cryptanalytical instrument. The T. Correspondents Alice and Bob use the following scheme. adversary has the luck of computational resources to break Map F is announced publicly. Alice has the knowledge the cryptosystem. of T. Alice and Bob have some digest (hash value) b=(b1, b2, We will combine both ideas for the construction of new ..., bk)ϵKk of the document. To sign the document Alice multivariate public keys for the task of information solves the system of equations fi(x)=bi, i=1, 2, ..., k. She gets exchange within the following general scheme. a solution x1=d1, x2=d2, ..., xn=dn and sends the tuple d=(d1, d2, Let K be a commutative ring with nontrivial ..., dn). Public user Bob verifies that F(d)=b. multiplicative group K*. If k=n then the pair (F, T) can be used as the encryption We consider the multivariate map F of Kn into Kn given scheme. Bob writes his plaintext p=(p1, p2, ..., pn) and forms by the rule xi→fi(x1, x2, ..., xn) such that its restriction on 199 (K*)n is injective. We say that T is a multiplicative trapdoor We identify the binary relation I with the corresponding of F if the knowledge of T allows us to solve the system of multipartite graph. equations F(x)=b for bϵF((K*)n). Let i,jГ(F) be the bipartite graph of the restriction of I on Assume that the density of F is O(nd) where d is some the disjoint union of Grassmanians Гi(F) and Гj(F). constant. Then the public rule x→F(x) can be used as an The Borel subgroup B of algebraic group PGLn(K) encryption scheme with the space of plaintexts (K*)n and the consists of triangular matrices A=(ai,j): such that ai,j=0 if ij). graphs and their temporal analogs The transitive group of transformation (U(J), OJ) is a The missing definitions of graph-theoretical concepts and regular representation of abstract group U(J), i.e. stabilisator incidence systems theory which appear in this paper can be of each representative of the orbit is the unity subgroup. found in each of the books [27–30]. Thus there are natural one-to-one correspondence between All graphs we consider are simple graphs, i.e. undirected elements U(J) and OJ and we can identify these sets. without loops and multiple edges. Let V(G) and E(G) denote Elements of orbits U(J) and U(J’) are not incident unless the set of vertexes and the set of edges of G respectively. the condition When it is convenient, we shall identify G with the J⸦J’ or J’⸦J and |J|≠|J’| (2) corresponding anti-reflexive binary relation on V(G), i.e. holds, i.e. elements J and J’ are incident as elements of Weyl E(G) is a subset of Cartesian product V(G)∙V(G) and write v geometry An. G u for the adjacent vertexes u and v (or neighbours). We For the description of the incidence condition of refer to |{x ϵ V(G)|xGv}| as the degree of the vertex v. The elements MϵU(J) we introduce subset ∆(J)={(i,j)|(iϵiϵJ)&(j incidence structure is the set V with partition sets P (points) &N-J)&(i>j)}. and L (lines) and symmetric binary relation I such that the We define the projection of triangular matrix M=(m(i,j)) incidence of two elements implies that one of them is a point on the subset A of {(i, j): i>j} as function f from A to such that and another one is a line. We shall identify I with the simple f(i,j)=m(i,j) for (i,j)ϵA. graph of this incidence relation or bipartite graph. Each unit triangular matrix M from U(J) is uniquely We define linguistic graphs of type (𝑠, 𝑟, 𝑚) where 𝑠>0, determined by its projection on ∆(J). 𝑟>0, 𝑚>0 over the commutative ring 𝐾 with unity as Let M and M’ be elements of U(J) and U(J’) where J and bipartite graphs with the partition sets 𝑃=𝐾s+m and J’ are incident elements of Weyl geometry. Then M and M’ 𝐿=𝐾r+m such that the point (𝑥1, 𝑥2, …, 𝑥s, 𝑥s+1, 𝑥s+2, …, 𝑥s+m) are incident elements of projective geometry if and only if from 𝑃 is incident to the line [𝑦1, 𝑦2, …, 𝑦r, 𝑦r+1, 𝑦r+2, …, 𝑦r+m] (M-M’) ∆(J)∩∆(J’)=(MM-M’M) 1∆(J)∩∆(J’) (3) from 𝐿 if and only if the following equations are satisfied: It is easy to see that the bipartite graph FG(J, J’) with 𝑎j𝑥s+j-𝑏j𝑦s+j=𝑓j(𝑥1, 𝑥2, …, 𝑥s+j-1, 𝑦1, 𝑦2, …, 𝑦t+j-1) (1) partition sets U(J) and U(J’) where J and J’ are incident where 𝑎j and 𝑏j are elements of the multiplicative group of elements of Weyl geometry and incidents of points and lines 𝐾 and 𝑓j are polynomials from 𝐾[𝑥1, 𝑥2, …, 𝑥s+j-1, 𝑦1, 𝑦2, …, are defined by the condition (2) is a Jordan-Gauss graph. 𝑦r+j-1] (see [31]). Noteworthy that the coefficients of monomial terms in We say that a linguistic graph is a Jordan-Gauss graph the system of equations (2) are +1 and -1. So we can if polynomials 𝑓j have degree 2 and consist of monomial introduce KG(J, J) over arbitrary commutative ring K with unity via the direct change of F for K. We can consider terms of kind 𝑥i𝑦k for 𝑗=1, 2, …, 𝑚. unimportant subgroup UK(J) of the group of unitriangular The neighbourhood of each vertex of a general Jordan- matrices U(n+1, K) over K and define the incidence of Gauss graph is given by the system of linear equations in its elements UK(J) and UK(J’) by the condition 2 in the case row-echelon form. when J and J’ satisfy (1). Examples of families of Jordan-Gauss graphs can be In fact, we can define PGn(K) in the case of general obtained as induced subgraphs of the incidence graphs of commutative ring with unity as disjoint union of partition geometries of Chevalley groups (see [32]) defined over sets of bipartite graphs KG(J, J’), type function t(x) of xϵUK(J) various fields (see [23], [33] and further references). equals |J| for the incidence xϵUK(J) and y ϵUK(J’) the Let us consider the case of Coxeter-Dynkin diagram 𝐴n, condition (1) is necessary, if (1) holds then (2) is required i.e. projective geometry PGn(F) of dimension n over the field additionally. F. This incidence system is a totality PGn(F) of proper This approach of construction of incidence systems over nontrivial subspaces of the vector space Fn+1. commutative ring K with unity can be used in the case of The dimension t(W) of subspace defines the type of W. other Dynkin-Coxeter diagrams, i.e. 𝐵n, 𝐶n, 𝐷n, 𝐸6, 𝐸7, 𝐸8, 𝐹4, So the set Pn(F) is a disjoint union of Grassmanians Гi(F)={W: t(W)=i}, i=1,2, ..., n-1. Two elements 1W and 2W are incident 𝐺2 (see [28], [32]). (1W I 2W) if they have different types and 1W<2W or 2W<1W. Each Grassmanian Гm(K) is the union of affine spaces UK(J) where |J|=m. These spaces are known as large 200 Schubert cells, small Schubert cells can be defined in the values of “time-dependent” coefficients of monomial terms case of field K (see [34], [35]) The variety Гm(K) contains the of equations. unique largest Schubert cell which is the cell of maximal In another example, the graph s, s+1𝐶s+r(𝐾) can be interpreted dimension. It is easy to see that the largest Schubert cell of as a bipartite graph consisting of points of the form (𝑥1, 𝑥2, …, Гm(K) is UK(J) for J={n+1, n, ..., n+1-m}. 𝑥s, 𝑥1,1, 𝑥1,2, …, 𝑥s,r) and lines [𝑦1, 𝑦2, …, 𝑦r, 𝑦1,1, 𝑦1,2, …, 𝑦s,r], with We refer to the disjoint union SPGn(K) of largest the incidence condition given by the equations: Schubert cells as Schubert with the restriction of incidence 𝑥i,j-𝑦i,j=𝑥iyj, 𝑖=1,2, …, s, 𝑗=1,2, …, r. relation I of PGn(K) on this subset as Schubert system over This is symbolically equivalent to the graph s, s+1𝐶s+r+1(𝐾), K. It is easy to see that for the incidence of elements x and y defined over the same commutative ring 𝐾 and with an from distinct Schubert cells the condition (3) is sufficient. incidence relation given by the system of equations: Let Г(K) be a Jordan-Gauss graph of type (𝑠, 𝑟, 𝑚) where 𝑎 i,j𝑥i,j-𝑏i,jyi,j=di,j𝑥iyj, where elements 𝑎i,j and bi,j belong to 𝑠>0, 𝑟>0, 𝑚>0 over the commutative ring 𝐾 with unity with 𝐾* and di,j are elements from 𝐾∖{0}. the incidence given by conditions (1). These two families of graphs give us extremal cases: the We refer to the list 𝑆 of all nonzero monomial terms of incidence of points and hyperplanes from 1, n𝐶n(𝐾) is the case 𝑓j taken with coefficient 1, together with the parameters 𝑠, of the single equation, while the case of subspaces of 𝑟, m as the symbolic type of the Jordan-Gauss graph Г(𝐾). It dimension s and s+1 of s, s+1𝐶s+r+1(𝐾) is the case when is convenient that the symbolic type of a Jordan-Gauss polynomials of the right-hand side have a single monomial. graph Г (𝐾) over 𝐾 is independent of the choice of 𝐾. We say that two Jordan-Gauss graphs defined over 4. Jordan-Gauss graphs and the commutative rings 𝐾 and 𝐾’ are symbolically equivalent if they have the same symbolic type. maps with the trapdoor We define a temporal (depending on time) Jordan-Gauss accelerator graph Г(𝐾) t of symbolic type 𝑆 as the family of equivalent Let us consider basic operators on the set of vertexes of the Jordan-Gauss graphs Г(𝐾) t, 𝑡=1, 2, … defined by equations linguistic graph of type (s, r, m). (1) with the same constant symbolic type 𝑆 depending on We refer to ρ((x))=(x1, x2, …, xs) for (x)=(x1, x2, …, xs+m) time 𝑡 coefficients 𝑎i=ai(t), 𝑏i=bi(t) and nonzero monomial and ρ([y])=(y1, y2, …, yr) for [y]=[y1, y2, …, yr+m] as the colour terms of 𝑓j of the form j𝑎(𝑖, 𝑘)𝑥i 𝑦k, 𝑥i 𝑦k ∈𝑆, j𝑎(𝑖, 𝑘)=ja(i, of the point and the colour of the line respectively. k)(t)≠0. Some examples of temporal Jordan-Gauss graphs For each bϵ Kr and p=(p1, p2, …, ps+m) there is the unique can be found in [36]. In contrast to the definition of time- neighbour of the point [l]=Nb(p) with the colour b. Similarly, dependent graphs of [37] we introduce Jordan-Gauss for each c ϵ Ks and line l=[l1, l2, …, lr+m] there is the unique temporal graphs via time-dependent equations. neighbour of the line (p)= Nc([l]) with the colour c. We refer So we can introduce temporal analogue PGn(K)t of to operator of taking the neighbour of the vertex PGn(K) and temporal analogue SPGn(K)t of SPGn(K) via the accordingly chosen colour as neighbourhood operator. option to change the coefficients of monomial terms of each On the sets P and L of points and lines of the linguistic nontrivial induced subgraph GK(J, J’), j𝐶n(K). graph we define colour jump operators J=Jb(p)=(b1, b2, …, bs, Let i, j𝐶n(𝐾) be the bipartite-induced subgraph of SPGn(K) p1, p2, …, ps+m), where (b1, b2, …, bs)ϵKs and J=Jb([l])=[b1, b2, …, of all elements of type i or type j. We refer to this graph as br, l1, l2, …, lr+m], where (b1, b2, …, br)ϵKr. a cellular Schubert graph and use the term temporal For the point (p) and odd parameter l sequence of the Schubert Graph for SPGn (K). colours a(1)ϵKs, b(1) ϵKr, a(2)ϵKr , b(2) ϵKs, ...., a(l)ϵKs, b(l) ϵKr, We refer to PGn(K)t and SPGn(K)t as temporal projective a(1+1) ϵKr which allows us to define the map H: Km+s→Km+r geometry over K and say that SPGn(K)t is temporal Schubert moving arbitrary point (v) to the line h=h(a(1), b(1), a(2), Geometry with the diagram An over the commutative ring b(2), ..., a(l), b(l), a(l+1))(v)=vl+1 defined via the following K. Temporal geometries of Chevalley groups and sequence of vertexes. corresponding Schubert geometries in the cases of various v1=Ja(1)(v), u1=Nb(1)(v1), Coxeter-Dynkin diagrams are defined in [36]. v2=Ja(2)(v1), u2=Nb(2)(v2), Let us consider some illustration examples. ..., The graph 1, n𝐶n(𝐾) is a bipartite graph of points (𝑥1, 𝑥2, vl=Ja(l)(vl-1), ul=Nb(l)(vl), vl+1=Ja(l+1)(ul). We refer to map H …, 𝑥n) and lines [𝑦1, 𝑦2, …, 𝑦 n] with incidences given by as the transition of (v) in the direction (a(1), b(1), a(2), b(2), equations: 𝑥n-𝑦n=𝑥1𝑦1+𝑥2𝑦2+⋯+𝑥n-1𝑦n-1. ..., a(l), b(l), a(l+1)). This is symbolically equivalent to the 1,n𝐶n(𝐾’) Jordan- We can define the transition H(a(1), b(1), a(2), b(2), ..., Gauss graph over the ring 𝐾’ with unity, having partition a(l), b(l), a(l+1)) in the case of even l in which v→h(v) will sets isomorphic to (𝐾’)n and with incidences given by be a transformation acting on Ks+m=P. equations of the form: 𝑎𝑥n-𝑏𝑦n=𝑎1𝑥1𝑦1+𝑎2𝑥2𝑦2+⋯+𝑎n-1𝑦n-1, For eachlinguistic graph Г(К) we consider Г'=Г(K[z1, z2, where 𝑎 and 𝑏 are elements of the multiplicative group of ..., zm+s]) given by the same equation but with the partition 𝐾’ and 𝑎i≠0, 𝑖=1, 2, …, 𝑛-1. sets K[z1, z2, ..., zm+s])m+s and K[z1, z2,..., zm+s])m+r. Graph 1, n𝐶n(𝐾)t has the same points and lines with 1, We take an odd parameter l, l>2, special point z=(z1, z2, ..., zm+s) and apply the transition H(a(1), b(1), a(2), b(2), ..., n 𝐶n(K) but the incidence is given by equations a(l), a(l+1)) to the vertex z of the graph Г’ such that 𝑎(t)𝑥n−𝑏(t)𝑦n=𝑎1(t)x1𝑦1+𝑎2𝑥(t)x2𝑦2+⋯+𝑎n-1(t)xn-1yn-1. coordinates of a(i), b(i) are elements of K[[z1, z2,..., zs]. The We say that i, j𝐶n(𝐾)t convert in fixed time moment t=t* image of z will be the tuple u=(a(l+1)1(z1, z2,..., zs), a(l+1)2(z1, to static Jordan-Gauss graph i ,j𝐶n(𝐾)t |t=t* via selection of z2,..., zs),..., a(l+1 )r(z1, z2,..., zs), f1(z1, z2,..., zm+s), f2(z1, z2,..., zm+s), 201 …, fm(z1, z2,..., zm+s)). Let F=F(a(1), b(1), a(2), b(2), ..., a(l), Semigroup nCS(K) is defined as an endomorphism group of a(l+1)) be a polynomial map of Km+s to Km+r sending (z1, z2, ..., polynomial ring K[x1, x2, ..., xn] over the commutative ring zm+s) to (u1, u2, ..., um+s])=u. K. It is an important object of Algebraic Geometry (see [38] We take two affine transformations L1 and L2 and about mathematics of Luigi Cremona—a prominent figure consider the composition G=L1FL2 sending (z1, z2, ..., zm+s) to in Algebraic Geometry in XIX). (g1(z1, z2, ..., zm+s), g2(z1, z2, ..., zm+s), …, gm+r(z1, z2,..., zm+s)). Element of the semigroup σ can be given via its values Additionally, we consider the above-presented on variables, i.e. as the rule xi→fi(x1, x2, …, xn), i=1, 2, …, n. construction in the case of even parameter l Then a(l+1) is This rule induces the map σ’: (a1, a2,.., an)→(f1(a1, a2, ..., an), an element of K[x1, x2, ..., xs]s, ul+1 and vl+1 are points. We f2(x1, x2, …, xn), …, fn(x1, x2, …, xn)) on the free module Kn. have to take L1 and L2 from AGLm+s(K) and construct the Automorphisms of K[x1, x2, ..., xn] form affine Cremona transformation G=L1FL2 of the affine space Km+s. GroupnCG(K) (see [39]). Proposition 1 [23]. Let us assume that the surjective In the case when K is a finite field or arithmetic ring Zm map (z1, z2, ..., zs) to (a(l+1)1, a(l+1)2, ..., a(l+1)t) where t=r or of residues modulo m elements of affine Cremona Groups t=s has a trapdoor accelerator T. or Semigroups are used in algorithms of multivariate Then the knowledge on Г(К) and tuples a(1), b(1), a(2), cryptography. Results about subsemigroups S of nCS(K) (or b(2). ..., a(l), b(l), transformations L1, L2, and T is a trapdoor subgroups of nCG(K) such that computation of the accelerator of the standard form of G mapping Km+s on Km+t. superposition of arbitrary n elements can be completed for Justification of Proposition 1’. polynomial time can be used as so-called platforms of Let us assume that Г(К) is temporal graph and its static Noncommutative Cryptography. graphs Гі in time i=1, 2, ..., l are known as well as a(1), b(1), One class of such objects is formed by stable a(2), b(2), ..., a(l), b(l), a(l+1), T and L1, L2 of the Proposition subsemigroups of degree k, i.e. subsemigroup S such that the 1. Let us consider the equation G(z)=b for the given value of maximal degree of its representative is bounded by the the tuple b. constant k. We will talk about the Multiple Composition We compute (L2)-1 (b)=c and introduce intermediate Computability (MCC) property. In the case of k=1 one can vector p=(p1, p2, ..., ps, ps+1, ps+2, ..., ps+m) of variables pi and take AGLn(K), stable subsemigroups of degree k in nCG(K) consider the equation H(p)=c where H=H(a(1), b(1), a(2), exist for each k, k=2, 3, ... Affine Cremona semigroup nCS(K) b(2), ..., a(l), a(l+1))=(a(l+1)1, a(l+1)2, ...a(l+1)t, h1, h2,..., hm), does not pose MCC. If one takes n quadratic elements where hiϵK[x1, x2,..., xs+m]. randomly their product with a probability close to 1 will We use our knowledge of the trapdoor accelerator T to have degree 2n. So the computation is not feasible. get solution p1=d1, p2=d2, ..., ps=ds. Let d=(d1, d2,...,ds). It gives EXAMPLE: Let us consider the totality nES(K) of us the opportunities to compute a*(1)=a(1)(d1, d2, ..., ds), endomorphisms of K[x1, x2, ..., xn] of kind b*(1)=b(1)(d1, d2, ..., ds), a*(2)=a(2)(d1, d2, ..., ds), b*(2)=b(2)(d1, x1→ϻ1x1 a(1,1) x2 a(1,2) … xn a(1,n), d2, ..., ds), ..., a*(l)=a(l)(d1, d2, ..., ds), b*(l)=b(l)(d1, d2, ..., ds), x2→ϻ2x1 a(2,1) x2 a(2,2) … xn a(2,n), (4) a*(1)=a(1)(d1, d2, ..., ds). … So, we compute H(b*(l), a*(l), b*(l-1), a*(l-1), b*(1), a*(1), xm→ϻnx1 a(n,1) x2 a(n,2) … xn a(n,n) d)= (w1, w2, ..., ws, ws+1, ws+2, ..., ws+m)=w. where ϻi are regular elements of finite commutative ring K Thus we got a solution for H(p)=c. We compute the with unity. solution z* of G(z)=c as z*=(L1)-1(w)). It is easy to see that the complexity of the computation If l is even or r=1 then the reimage reimage z* is of the product of two elements of kind (4) is O(n3). So, the uniquely defined. semigroup of Eulerian transformations nES(K) poses the We define a density of multivariate polynomial f(z1, z2, ..., property MCC. Semigroups with this property can serve as zn) written in its standard form as a number of monomial terms. “platforms” of protocols of Noncommutative Cryptography. The density den(b) of the tuple b=(f1, f2, ..., fk) from K[z1, The following examples of special elements of nES(K) z2, ..., zn]k is the maximal density of fi. The density of the map can be found in [40]. F: xi→fi, i=1,2, ..., k coincides with the density of the corresponding tuple of polynomials fi. 5.2. On some bijective transformation of Proposition 2 [23]. Let us assume that condition of the (K*)n Proposition 1 hold and Г(К) coincides with the Jordan-Gauss Let π and δ be two permutations on the set {1, 2, ..., n}. Let K graph i,j𝐶n(K), den(a(i))=O(nd), den(b(i))=O(ne), d>1, i-j=O(nk.), be a commutative ring with unity which has nontrivial 0≤k≤1 for i=1,2, ..., l. Then the density of the map F(a(1), b(1), multiplicative group K* of order d=|K*|>1 and n≥1. We a(2), b(2), ..., a(l), b(l), a(l+1)) is O(nd+e+k). define transformation AJG(π, δ) of the variety (K*)n, where Remark. Proposition 1 and Proposition 2 hold also for A is a triangular matrix with positive integer entries the temporal linguistic graphs and temporal cellular 0≤a(i,j)≤d, i≥d defined by the following closed formula. Schubert graphs. yπ(1)=ϻ1xδ(1)a(1,1) yπ(2)= ϻ2xδ(1)a(2,1) xδ(2)a(2,2) 5. On some subgroups of affine … Cremona Semigroup yπ(n)= ϻnxδ(1)a(n,1) xδ(2)a(n,2) …xδ(n)a(n,n) where (a(1,1),d)=1, (a(2,2),d)=1,…,(a(n,n),d)=1. 5.1. Some definitions We refer to AJG(π, δ) as Jordan transformations Gauss Let us consider the following important object of multiplicative transformation, or simply JG element. It is an Noncommutative Cryptography. Affine Cremona invertible element of nES(K) with the inverse of kind BJG(δ, 202 π) such that a(i,i)b(i,i)=1 (mod d). Notice that in the case b(i)=(ih1(z1, z2, …, zs), ih2(z1, z2, …, zs), …, ihs(z1, z2, …, zs)) K=Zm straightforward process of computation the inverse of for i=2, 4, …, l. JG element is connected with the factorization problem of Alice selects a(l+1) as a tuple of kind integer m. If n=1 and m is a product of two large primes p (λ1z1e(1,1), λ2z1e(2,1)z2e(2,2), ..., and q the complexity of the problem is used in the RSA λsz1e(s,1)z2e(s,2) … zs(s,s)) where (e(1, 1), d)=1, e(2, 2), d)=1, …, public key algorithm. The idea to use the composition of JG (e(s, s), d)=1. elements or their generalisations with injective maps of Kn Alice computes F(z1, z2, …, zn)=(F(a(1), b(1), a(2), b(2), into Kn was used in [41] (K=Zm) and [42] (K=Fq.). ..., a(l), b(l), a(l+1)) (z1, z2, …, zn)=(u1, u2, …, un)=u. We say that τ is a tame Eulerian element over the She takes element L from AGLn(K) and computes commutative ring K if it is a composition of several Jordan L(u)=(w1, w2, …, wn). So Alice computes the composition Gauss multiplicative maps over a commutative ring or field G=J1J2FL:(x1, x2, …, xn)→(w1(x1, x2, …, xn), w2(x1, x2, …, xn), …, respectively. It is clear that τ sends variable xi to a certain wn(x1, x2, …, xn)). monomial term. The decomposition of τ into a product of She sends standard forms of multivariate polynomials Jordan Gauss transformation allows us to find the solution wi to Bob. Alice keeps J1, J2, L and a(1), b(1), a(2), b(2), ..., of equations τ(x) = b for x from (Z*m)n or (F*q)m. So tame a(l), b(l), a(l+1) as her private secret. Eulerian transformations over Zm or Fq are special elements Encryption. of nEG(Zm) or nEG(Fq) respectively. Bob generates his message p=(p1, p2, ..., pn) from the We refer to elements of nES(K) as multiplicative space of plaintexts (K*)n. He creates the ciphertext G(p1, p2, Cremona elements. Assume that the order of K is constant. ..., pn)=c and sends it to Alice. As it follows from the definition the computation of the The process of generating G insures that the density of value of element from nES(K) on the given element of Kn is the map is O(n). Each monomial can be computed in time estimated by O(n2). The product of two multiplicative O(n). Thus the complexity of the encryption procedure is Cremona elements can be computed in time O(n3). O(n3). We are not discussing here the complexity of computing We have a nonlinear map of an unbounded degree such the inverse for general element gϵ nEG(K) on the Turing that the computation of its value has the same complexity machine or Quantum computer and the problem of finding as the computation of an image of a quadratic map. the inverse for tame Eulerian elements. Decryption. Alice receives the message c from Bob. Firstly she 6. Multivariate cryptosystem computes b=L-1(c). Secondly Alice creates the intermediate tuple (z1, z2, ..., zn) to study equation F(z1, z2, ..., zn)=b. Let K be a finite commutative ring with unity and nontrivial She writes the equation multiplicative group K* of order d>1. Alice selects graph λ1z1e(1,1)=b1, i, j 𝐶2m(𝐾), i>j, i=m+α, j=m-β where α>0 and β ≥0 are λ2z1e(2,1)z2e(2,2)=b2, constants ≥0. We assume that parameters α and β are (5) … essentially smaller than n. She computes parameter λsz1e(s,1) z2e(s,2) …zse(s,s)=bs n=(m+α)(m-α+1) and s=(m+α-1)(α+ β), r=(m-β)(α+β) and Alice gets the solution z1=d1, z2=d2, ..., zs=ds. forms the transformation J1 and J2 from nEG(K) of kind She computes the parameters a*(i)=a(i)(d1, d2, ..., ds) and y1=μ1x1a(1,1) b*(i)=b(i)(d1, d2, ..., ds) for i=1, 2,..., l. y2=μ2x1a(2,1) x2a(2,2) Alice takes point (b) and computes recurrently … ul=Jb*(l)(b), wl= Na*(l)(ul), yn=μnx1a(n,1) x2a(n,2) … xna(n,n) ul-1=Jb*(l-1)(wl), wl-1=Na*(l-1)(ul-1), where (a(1,1), d)=1, (a(2, 2), d)=1, …, (a(n, n), d)=1, …, z1=μ’1y1b(1,1) y2b(1,2) … ynb(1,n) u1=Jb*(1)(w2), w1=Na*(1)(u1), She computes z*=(z*1, z*2,..., z*s, z*s+1,..., z*n) as Jd(w1) for z2=μ’1y2b(2,2) y2b(2,3) … ynb(2,n) d=(d1, d2,…, ds). … We can see that z* is the solution of the system (3). zn=μ’nynb(n,n) Alice computes the plaintext p as (J2)-1(Jl)-1(z*). Alice computes the inverses of J1 and J2 in the group where (b(n,n), d)=1, (b(n-1, 2), d)=1, …, (b(1, n), d)=1. n EG(K) as well as the inverse of the map z1→λ1z1e(1,1), She computes the composition of J1 and J2 and obtains z2→λ2z1e(2,1)z2e(2,2), ..., zs→ λsz1e(s,1)z2e(s,2) … zse(s,s) in the group the vector (z1, z2, ..., zs, zs+1, …, zn) and treats this tuple as a s EG(K) in advance. So the complexity of her decryption point of graph i, j𝐶2m(𝐾). procedure can be estimated as O(n2). She selects even parameter l, l>5 of size O(1) together Obfuscation. with sparse tuples a(1), b(1), a(2), b(2), …, a(l), b(l), a(l+1) of Instead of graphs i,j𝐶2m(𝐾) Alice takes temporal analogue density O(1) of Proposition 2. i,j 𝐶2m(𝐾) t of them. She forms static graphs i,j𝐶2m(𝐾)t|t=t* for So, a(i)=(il1(z1, z2, …, zs), il2(z1, z2, …, zs), …, ils(z1, z2, …, zs)) t*=1, 2, ..., l. for i=1, 3, 5, …, l-1, l+1, a(i)=(il1(z1, z2, …, zs), il2(z1, z2, …, zs), …, ilr(z1, z2, …, zs)) for So she computes each N_b(i) in static graph i,j𝐶2m(𝐾)t|t=i i=2, 4,…, l, during the algorithm execution. b(i)=(ih1(z1, z2, …, zs), ih2(z1, z2, …, zs), …, ihr(z1, z2, …, zs)) Illustrating example. for i=1, 3, …, l-1, Let us consider the case (α=1, β=0).Then graph m+1,m C2m(K) known as Double Schubert Graph which has 203 points (x)=(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m) and [y]=[y1, y2, ..., (case of general linear group). Some other maps with ym, y1,1, y1,2, ..., ym,m] and incidence given by equations xi,j- trapdoor accelerators are described in [23] the cases of yi,j=xiyj. We assume that indexes of kind (i,j) are ordered diagrams Bn, Cn, and Dn. lexicographically. The first graph-based bijective quadratic public key Alice takes endomorphism J1 and J2 of K[x1, x2, ..., ,..., xm, where constructed in [6]. It uses special cellular Schubert x1,1, x1,2, ..., xm,m]. graphs of Projective Geometry over the finite field of J1J2(x)=(a1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), a2(x1, x2, ..., xm, characteristics 2. The cryptanalysis for this public key is x1,1, x1,2, ..., xm,m), …, unknown. am(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), The obfuscation of this cryptosystem is presented in [1]. a1,1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), Recent development in this direction is reflected in [33] a1,2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), where multivariate rules given by quadratic surjective maps …, and temporal analogues of cellular Schubert graphs can be am,m(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m))=(z1, z2, …, zm, z1,1, z1,2, used. …, zm,m)=(z) where expressions a1, a2, …, am, a1,1, a1,2, …, am,m Another bijective quadratic cryptosystem which is also are monomial terms with the coefficients from K*. constructed in terms of Jordan-Gauss graphs is given in [43]. Alice takes graph m+1,mC2m(K[z1, z2, …, zm, z1,1, z1,2, …, Multivariate cryptosystems with rules of unbounded zm,m]). She selects colours a(1), b(1), a(2), b(2), ..., a(l), b(l), degree are quite rare. We refer to cryptosystems [42] and a(l+1) where a(i) and b(i) are elements of K[z1, z2, ..., zm, z1,1, [41] defined in terms of extremal Jordan-Gauss graphs over z1,2, …, zm,m]m. Element a(l+1) will be chosen as (λ1z1e(1,1), Fq and Zq. λ2z1e(2,1)z2e(2,2), ..., λsz1e(s,1)z2e(s,2) … zse(s,s)). She computes the These multivariate maps have O(n4) monomial maps. destination point of transition H(a(1), b(1), a(2), b(2), ..., a(l), Cryptanalysis for them is still unknown. Presented in this b(l), a(l+1)) of the point (z) in the graph m+1,mC2m(K[z1, z2, …, paper cryptosystem is given by multivariate rule with O(n2) zm, z1,1, z1,2, …, zm,m]). Alice specialise zi as ai(x) and zi,j as monomial terms. Thus it can be implemented with hundreds ai,j(x). of variables, The reduction of the degree of equations to 2 So she computes the composition of J=J1J2 moving (x) to or 3 leads to an essential increase of variables (more than (z) and F(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1) moving z to n2). It makes it unfeasible to use standard methods of u=(u1, u2, ..., um, u1,1, u1,2, ..., um,m). It is clear that the density symbolic computations for cryptanalytic purposes. of JF is O(1). Finally Alice selects L from AGLn(K), n=(m+1)m For the implementation of this public key, we select and computes (JF)L=G(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m) of kind cases K=Fq and K=Zq where q is a prime power ≥128. x1→g1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), x2→g2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), Acknowledgments ..., xm→gm(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), This research is partially supported by the British Academy x1,1→g1,1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), Fellowship for Researchers under Risk 2022 and partially x1,2→g1,2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), supported by the British Academy grant LTRSF\100333. ... xm,m→gm,m(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m). References For convenience Alice can rename variables from the [1] V. Ustimenko, Linear Codes of Schubert Type and list x1, x2, ..., xm, x1,1, x1,2, ..., xm,m as y1, y2, ..., ym, xm+1, xm+2, ..., Quadratic Public Keys of Multivariate Cryptography, xm(m+1). IACR e-print archive (2023). [2] W. Beullens, Improved Cryptanalysis of UOV and 7. Conclusions Rainbow, Advances in Cryptology – EUROCRYPT In this paper, we present the method of construction of 2021, LNCS 12696 (2021) 348–373. doi: 10.1007/978-3- sparce multivariate maps of unbounded degree O(n) with 030-77870-5_13. the trapdoor accelerators with the use of walks on algebraic [3] A. Canteaut, F.-X. Standaert, Eurocrypt 2021, LNCS graphs. It uses bipartite cellular Schubert graphs of 12696, 40th Annual International Conference on the projective geometries and their analogues defined over the Theory and Applications of Cryptographic general commutative ring K with the unity. These bipartite Techniques (2021). doi: 10.1007/978-3-030-77870-5. graphs can be changed for their temporal analogues defined [4] J. Ding, et al., TUOV: Triangular Unbalanced Oil and via the option of a momentum change of the coefficients of Vinegar. Algorithm Specifications and Supporting monomial terms in the equations defining the incidence of Documentation, ver. 1.0 (2023). URL: points and lines. https://csrc.nist.gov/csrc/media/Projects/pqc-dig- The partition sets of such graphs are affine spaces Kn sig/documents/round-1/spec-files/TUOV-spec- and Km. The special walk on the temporal graph over K [x1, web.pdf x2, ..., xn] can be used for the construction of a multivariate [5] J. Ding, A. Petzoldt, D. Schmidt, Multivariate Public map G from Kn to Kn. The information on the temporal Key Cryptosystems, Second Edition. Advances in graph and the walk can serve as corresponding trapdoor Information Security, Springer (2020). accelerator T of G, i.e. the knowledge of T allows us to [6] V. Ustimenko, On Schubert cells in Grassmanians and compute the reimages of G. We presented some of these New Algorithms of Multivariate Cryptography, procedures as Algorithm 1 and 4 in the case of graphs Proceedings of the Institut of Mathematics, 23(2) s,k Cn(K) in terms of Chevalley group over the diagram An (2015) 137–148. 204 [7] J. Ding, A. Petzoldt, Current State of Multivariate Symposium on Symbolic and Algebraic Computation Cryptography, in IEEE Security & Privacy, 15(4) (1989) 121–128. doi: 10.1145/74540.74556. (2017) 28–36. doi: 10.1109/MSP.2017.3151328. [26] B. Buchberger, Groebner basis: An Algorithmic [8] D. Smith-Tone, 2F—A New Method for Constructing Method in Polynomial Ideal Theory, in: Recent Trends Efficient Multivariate Encryption Schemes, in: in Multidimensional Systems Theory (1985) 184–232. Proceedings of PQCrypto 2022: The 13th International [27] N. Biggs, Algebraic graphs theory, Second Edition, Conference on Post-Quantum Cryptography, virtual, Cambridge University Press (1993). DC, US (2022). [28] A. Brower, A. Cohen, A. Nuemaier, Distance regular [9] D. Smith-Tone, New Practical Multivariate Signatures graphs, Springer (1989). from a Nonlinear Modifier, IACR e-print archive [29] B. Bollob´as’, Extremal Graph Theory, Academic (2021). Press (1978). [10] D. Smith-Tone, C. Tone, A Nonlinear Multivariate [30] F. Buekenhout, Handbook on Incidence Geometry, Cryptosystem Based on a Random Linear Code (2019). North Holland (1995). [11] J. Dey, R. Dutta, Progress in Multivariate [31] V. Ustimenko, Maximality of Affine Group, Hidden Cryptography: Systematic Review, Challenges, and Graph Cryptosystem and Graph’s Stream Ciphers, Research Directions, ACM Computing Survey, 55(12) Journal of Algebra and Discrete Mathematics, 1 (2005) (2023) 1–34. doi: 10.1145/3571071. 51–65. [12] F. Cabarcas, D. Cabarcas, J. Baena, Efficient Public- [32] R. W. Carter, Simple Groups of Lie Type, Wiley (1972). Key Operation in Multivariate Schemes, Advances in [33] V. Ustimenko, On Schubert cells of Projective Mathematics of Communications 13(2) (2019). Geometry and Quadratic Public Keys of Multivariate [13] R. Cartor, D. Smith-Tone, EFLASH: A New Cryptography, IACR e-print archive (2024). Multivariate Encryption Scheme, International [34] I. Gelfand, R. MacPherson, Geometry in Grassmanians Conference on Selected Areas in Cryptography (2018) and Generalization of the Dilogarithm, Adv. in Math. 281–299. 44 (1982) 279–312. [14] A. Casanova, et al., Gemss: A Great Multivariate Short [35] I. Gelfand, V. Serganova, Combinatorial Geometries Signature, Submission to NIST (2017) 209–229. and Torus Strata on Homogeneous Compact [15] J. Chen, et al., A New Encryption Scheme For Manifolds, Soviet Math. Surv. 42 (1987) 133–168. Multivariate Quadratic Systems, Theoretical Comput. [36] V. Ustimenko, On Small World non Sunada Twins and Sci. 809 (2020) 372–383. Cellular Voronoi Diagams, Algebra and Discrete [16] M.-S. Chen, et al., SOFIA: MQ-based Signatures in the Mathematics, 30(1) (2020) 118–142. QROM, IACR International Workshop on Public Key [37] T. Adamo, G. Ghiani, E. Guerriero, On Path Ranking Cryptography, LNCS 10770 (2018) 3–33. in Time-Dependent Graphs, Computers & Operations [17] D. H. Duong, et al., An Efficient Multivariate Research, 135 (2021) 105–446. Threshold Ring Signature Scheme, Computer [38] M. Noether, Luigi Cremona, Mathematische Annalen, Standards & Interfaces 74 (2021). 59 (1904) 1–19. [18] J.-C. Faugère, et al., A New Perturbation for [39] V. L. Popov, Roots of the Affine Cremona group, multivariate public key schemes such as HFE and Contemporary Mathematics, 369 (2005) 12–13. UOV, Cryptology ePrint Archive (2022). [40] V. Ustimenko, On Eulerian Semigroups of [19] M. J. Saarinen, Daniel Tony-Smith, Post Quantum Multivariate Transformations and their Cryptography, in: 15th International Workshop, Cryptographic applications, European J. Math. 9(93) PQCrypto 2024, Part 1 (2024). (2023). [20] M. J. Saarinen, DTony-Smith (eds.), Post Quantum [41] V. A. Ustimenko, On New Multivariate Cryptosystems Cryptography, 15th International Workshop, based on Hidden Eulerian Equations, Dopovidi of PQCrypto 2024, Part 2 (2024). National Academy of Science of Ukraine, 5 (2017). [21] T. Takagi, et al., International Symposium on [42] V. Ustimenko, On New Multivariate Cryptosystems Mathematics, Quantum Theory, and Cryptography, based on Hidden Eulerian Equations over Finite Proceedings of MQC 2019, Open Access (2021). Fields, IACR e-print archive (2017). [22] K. Arai, Advances in Information and [43] V. Ustimenko, A. Wróblewska, On Extremal Algebraic Communication, Future of Information and Graphs, Quadratic Multivariate Public Keys and Communication Conference (FICC), 1–3 (2024). Temporal Rules, FedCSIS (2023) 1173–1178. [23] V. Ustimenko. Graphs in terms of Algebraic Geometry, Symbolic Computations and Secure Communications in Post-Quantum world, UMCS Editorial House (2022). [24] B. Sturmfels. Solving Systems of Polynomial Equations. Providence, RI: American Mathematical Soc. (2002). [25] J. F. Canny, E. Kaltofen, L. Yagati, Solving Systems of Nonlinear Polynomial Equations Faster, ISSAC '89: Proceedings of the ACM-SIGSAM 1989 International 205