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).
This paper presents the modification of the quadratic multivariate public key given in [1] and defined via special walks on projective geometries over finite fields and their natural analogs defined over general commutative rings. New graph-based multivariate rules are “pseudo quadratic”, i.e., they are maps of unbounded degree of size O(n) but the number of monomial terms in all equations is O(n2). So, like in the case of a quadratic map the computation of the value of the map on the given tuple costs O(n3).
Multivariate cryptography is one of the five main directions of Post-Quantum Cryptography.
The progress in the design of experimental quantum computers is speeding up lately. Expecting such development the National Institute of Standardisation Technologies of USA announced in 2017 the tender on the standardisation best known quantum-resistant algorithms of asymmetrical cryptography. The first round was finished in March 2019, and essential parts of the presented algorithms were rejected. At the same time, the development of new algorithms with a postquantum perspective was continued. A similar process took place during the 2, 3, and 4th rounds.
The last algebraic public key “Unbalanced Oil and Vinegar on Rainbow like digital signatures” (ROUV) constructed in terms of multivariate cryptography was rejected in 2021 (see [2, 3]). The first 4 winners of this competition were announced in 1922, they were developed in terms of Lattice Theory.
Noteworthy that the NIST tender was designed for the selection and investigation of public key algorithms and in the area of multivariate cryptography only quadratic multivariate maps were investigated. We have to admit that general interest in various aspects of multivariate cryptography was connected with the search for secure and effective procedures of digital signature where mentioned above ROUV cryptosystem was taken as a serious candidate to make the shortest signature.
Let us summarize the outcomes of the mentioned above NIST tender.
There are 5 categories that were considered by NIST in the PQC standardization (the submission date was 2017; in July 2022, the 4 winners and the 4 final candidates were proposed for the 4th round—this is the current official status. However, the current 8 final winners and candidates only belong to the following 4 different mathematical problems (not the 5 announced at the beginning):
The standards are partially published in 2024.
0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3232-1787 (O. Pustovit) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). It’s interesting that the new obfuscation “TUOV: Triangular Unbalanced Oil and Vinegar” was presented to NIST by principal submitter Jintaj Ding [4].
The historical development of Classical Multivariate
Cryptography which studies quadratic and cubic
endomorphisms of Fq[x1, x2,…, xn] can be found in [5] and
[6]. Current research in Postquantum Cryptography can be
found in [
Section 2 contains some definitions of Multivariate Cryptography over a general commutative ring.
In Section 3 we introduce the concept of linguistic graphs and Jordan-Gauss graphs defined over commutative ring K together with the examples of such graphs which appear as bipartite-induced subgraphs of the Incidence Graph of Projective Geometry or its analogue defined over K.
Equations of some graphs are given explicitly. We define the temporal analogue of linguistic graphs.
Section 4 is dedicated to the constructions of multivariate rules with trapdoor accelerators in terms of linguistic graphs. In the case of Cellular Schubert graphs or their temporal analogue we evaluate the density of constructed multivariate rules.
In Section 5 we describe the Eulerian subgroup of transformations of Affene Cremona semigroup of all endomorphisms of K[x1, x2,…, xn]. Eulerian transformation maps each variable x_i into a monomial term.
The new cryptosystem is described in Section 6. This map is formed as the composition of Eulerian transformation J, transformation F defined in terms of special Jordan-Gauss graphs in Section 4, and element L from AGLn(K). The complexity of the decryption procedure is estimated there.
Section 7 contains concluding remarks.
This paper is dedicated to the construction of public maps F of multivariate cryptography transforming the tuple (x1, x2, ..., xn) from Kn to (f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., fk(x1, x2, ..., xn)) from Kk where K is a finite commutative ring with unity and polynomials fiϵK[x1, x2, ..., xn] are written in their standard forms, i.e. lists of their monomial terms ordered lexicographically.
We say that piece of information T is a trapdoor accelerator of F if T is the piece of information such that its knowledge allows us to compute the reimage of F for given value b from Kk in a polynomial time O(nα).
Classical multivariate cryptography uses surjective map F defined over finite field K=Fq with the trapdoor accelerator T. Correspondents Alice and Bob use the following scheme.
Map F is announced publicly. Alice has the knowledge of T. Alice and Bob have some digest (hash value) b=(b1, b2, ..., bk)ϵKk of the document. To sign the document Alice solves the system of equations fi(x)=bi, i=1, 2, ..., k. She gets a solution x1=d1, x2=d2, ..., xn=dn and sends the tuple d=(d1, d2, ..., dn). Public user Bob verifies that F(d)=b.
If k=n then the pair (F, T) can be used as the encryption scheme. Bob writes his plaintext p=(p1, p2, ..., pn) and forms the ciphertext c=F(p). He sends c to Alice via the open channel. Her knowledge of T allows Alice to restore p as F1(c).
In both schemes, correspondents would like to use F as one way function for which reimages of b or p are impossible to compute in polynomial time without the knowledge of T.
The search for multivariate one way functions is motivated by the following gap between linearity and nonlinearity.
We know that the system of linear equations written over
the field F can be solved in time O(n3) via the Jordan-Gauss
elimination method. The complexity of solving a nonlinear
system of constant degree d, d>1 is subexponential (see [
So if we have a nonlinear map F of bounded degree d in “general position” which has a trapdoor accelerator T then the corresponding cryptosystem is secure. This status insures the fact that F is given as one way function i.e. reimage of F is impossible to compute in a polynomial time without knowledge of the secret T.
The map F is not in a “general position” if some additional specific information is known. For instance, if F is the bijective cubic map and F-1 is also cubic. The public user can generate O(n3) pairs of kind plaintext p/corresponding ciphertext c and approximate inverse map in time O(n10).
Known computer tests and cryptanalytic methods ensure that map F is “in general position”. Noteworthy that the existence of one way function is not proven yet even under the main complexity conjecture that P≠NP.
It is well known that the investigation of nonlinear systems of equations over the commutative ring K with zero divisors is essentially a harder case in comparison to the case of a field.
Multivariate cryptography over rings with zero divisors is a brand new direction of research. Another idea is the construction of functions F of unbounded degree of size O(n) with the trapdoor accelerators. As we already mentioned there is a reduction of arbitrary system of nonlinear equations to the system of quadratic equations. This method leads to the nonlinear increase of a number of variables. The change of practically used hundreds of variables for several thousands of them makes it impossible to use the Groebner basis technique as a cryptanalytical instrument. The adversary has the luck of computational resources to break the cryptosystem.
We will combine both ideas for the construction of new multivariate public keys for the task of information exchange within the following general scheme.
Let K be a commutative ring with nontrivial multiplicative group K*.
We consider the multivariate map F of Kn into Kn given by the rule xi→fi(x1, x2, ..., xn) such that its restriction on (K*)n is injective. We say that T is a multiplicative trapdoor of F if the knowledge of T allows us to solve the system of equations F(x)=b for bϵF((K*)n).
Assume that the density of F is O(nd) where d is some constant. Then the public rule x→F(x) can be used as an encryption scheme with the space of plaintexts (K*)n and the space of ciphertexts (Kn).
Assume that Alice has a pair (F, T) and public user Bob has the standard form of F.
Then he writes his plaintext p=(p1, p2, ...., pn) and sends the ciphertext c=F(p) to Alice. She uses the information piece T and computes the plaintext.
The missing definitions of graph-theoretical concepts and
incidence systems theory which appear in this paper can be
found in each of the books [
All graphs we consider are simple graphs, i.e. undirected without loops and multiple edges. Let V(G) and E(G) denote the set of vertexes and the set of edges of G respectively. When it is convenient, we shall identify G with the corresponding anti-reflexive binary relation on V(G), i.e. E(G) is a subset of Cartesian product V(G)∙V(G) and write v G u for the adjacent vertexes u and v (or neighbours). We refer to |{x ϵ V(G)|xGv}| as the degree of the vertex v. The incidence structure is the set V with partition sets P (points) and L (lines) and symmetric binary relation I such that the incidence of two elements implies that one of them is a point and another one is a line. We shall identify I with the simple graph of this incidence relation or bipartite graph.
We define linguistic graphs of type ( , , ) where >0,
>0, >0 over the commutative ring with unity as
bipartite graphs with the partition sets = s+m and
= r+m such that the point ( 1, 2, …, s, s+1, s+2, …, s+m)
from is incident to the line [ 1, 2, …, r, r+1, r+2, …, r+m]
from if and only if the following equations are satisfied:
j s+j- j s+j= j( 1, 2, …, s+j-1, 1, 2, …, t+j-1) (1)
where j and j are elements of the multiplicative group of
and j are polynomials from [ 1, 2, …, s+j-1, 1, 2, …,
r+j-1] (see [
We say that a linguistic graph is a Jordan-Gauss graph if polynomials j have degree 2 and consist of monomial terms of kind i k for =1, 2, …, .
The neighbourhood of each vertex of a general JordanGauss graph is given by the system of linear equations in its row-echelon form.
Examples of families of Jordan-Gauss graphs can be
obtained as induced subgraphs of the incidence graphs of
geometries of Chevalley groups (see [
Let us consider the case of Coxeter-Dynkin diagram n, i.e. projective geometry PGn(F) of dimension n over the field F. This incidence system is a totality PGn(F) of proper nontrivial subspaces of the vector space Fn+1.
The dimension t(W) of subspace defines the type of W. 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 (1W I 2W) if they have different types and 1W<2W or 2W<1W.
We identify the binary relation I with the corresponding multipartite graph.
Let i,jГ(F) be the bipartite graph of the restriction of I on the disjoint union of Grassmanians Гi(F) and Гj(F).
The Borel subgroup B of algebraic group PGLn(K) consists of triangular matrices A=(ai,j): such that ai,j=0 if i<j with determinant 1.
Let us consider the orbits of group B acting on PGn(F). For the description of orbits, we select the standard basis e1, e2, ..., en, en+1 of the vector space Fn+1.
Then each orbit OJ from Гm(F) contains the unique symplectic subspace of kind ej(1), ej(2), ..., ej(m) where J={i(1), i(2), ...,i(m)} is a subset of {1, 2, ..., n, n+1}. There is a subgroup U(J) of unitriangular elements from GLn+1(F) which consists of matrices E+(ai,j ) such that ai,j≠0 if (iϵiϵJ)&(j &N-J)&(i>j).
The transitive group of transformation (U(J), OJ) is a regular representation of abstract group U(J), i.e. stabilisator of each representative of the orbit is the unity subgroup. Thus there are natural one-to-one correspondence between elements U(J) and OJ and we can identify these sets.
Elements of orbits U(J) and U(J’) are not incident unless the condition
J⸦J’ or J’⸦J and |J|≠|J’| (2) holds, i.e. elements J and J’ are incident as elements of Weyl geometry An.
For the description of the incidence condition of elements MϵU(J) we introduce subset ∆(J)={(i,j)|(iϵiϵJ)&(j &N-J)&(i>j)}.
We define the projection of triangular matrix M=(m(i,j)) on the subset A of {(i, j): i>j} as function f from A to such that f(i,j)=m(i,j) for (i,j)ϵA.
Each unit triangular matrix M from U(J) is uniquely determined by its projection on ∆(J).
Let M and M’ be elements of U(J) and U(J’) where J and J’ are incident elements of Weyl geometry. Then M and M’ are incident elements of projective geometry if and only if (M-M’) ∆(J)∩∆(J’)=(MM-M’M) 1∆(J)∩∆(J’) (3)
It is easy to see that the bipartite graph FG(J, J’) with partition sets U(J) and U(J’) where J and J’ are incident elements of Weyl geometry and incidents of points and lines are defined by the condition (2) is a Jordan-Gauss graph.
Noteworthy that the coefficients of monomial terms in the system of equations (2) are +1 and -1. So we can introduce KG(J, J) over arbitrary commutative ring K with unity via the direct change of F for K. We can consider unimportant subgroup UK(J) of the group of unitriangular matrices U(n+1, K) over K and define the incidence of elements UK(J) and UK(J’) by the condition 2 in the case when J and J’ satisfy (1).
In fact, we can define PGn(K) in the case of general commutative ring with unity as disjoint union of partition sets of bipartite graphs KG(J, J’), type function t(x) of xϵUK(J) equals |J| for the incidence xϵUK(J) and y ϵUK(J’) the condition (1) is necessary, if (1) holds then (2) is required additionally.
This approach of construction of incidence systems over
commutative ring K with unity can be used in the case of
other Dynkin-Coxeter diagrams, i.e. n, n, n, 6, 7, 8, 4,
2 (see [
Each Grassmanian Гm(K) is the union of affine spaces
UK(J) where |J|=m. These spaces are known as large
Schubert cells, small Schubert cells can be defined in the
case of field K (see [
We refer to the disjoint union SPGn(K) of largest Schubert cells as Schubert with the restriction of incidence relation I of PGn(K) on this subset as Schubert system over K. It is easy to see that for the incidence of elements x and y from distinct Schubert cells the condition (3) is sufficient.
Let Г(K) be a Jordan-Gauss graph of type ( , , ) where >0, >0, >0 over the commutative ring with unity with the incidence given by conditions (1).
We refer to the list of all nonzero monomial terms of j taken with coefficient 1, together with the parameters , , m as the symbolic type of the Jordan-Gauss graph Г( ). It is convenient that the symbolic type of a Jordan-Gauss graph Г ( ) over is independent of the choice of . We say that two Jordan-Gauss graphs defined over commutative rings and ’ are symbolically equivalent if they have the same symbolic type.
We define a temporal (depending on time) Jordan-Gauss
graph Г( ) t of symbolic type as the family of equivalent
Jordan-Gauss graphs Г( ) t, =1, 2, … defined by equations
(1) with the same constant symbolic type depending on
time coefficients i=ai(t), i=bi(t) and nonzero monomial
terms of j of the form j ( , ) i k, i k ∈ , j ( , )=ja(i,
k)(t)≠0. Some examples of temporal Jordan-Gauss graphs
can be found in [
So we can introduce temporal analogue PGn(K)t of PGn(K) and temporal analogue SPGn(K)t of SPGn(K) via the option to change the coefficients of monomial terms of each nontrivial induced subgraph GK(J, J’), j n(K).
Let i, j n( ) be the bipartite-induced subgraph of SPGn(K) of all elements of type i or type j. We refer to this graph as a cellular Schubert graph and use the term temporal Schubert Graph for SPGn (K).
We refer to PGn(K)t and SPGn(K)t as temporal projective
geometry over K and say that SPGn(K)t is temporal Schubert
Geometry with the diagram An over the commutative ring
K. Temporal geometries of Chevalley groups and
corresponding Schubert geometries in the cases of various
Coxeter-Dynkin diagrams are defined in [
Let us consider some illustration examples.
The graph 1, n n( ) is a bipartite graph of points ( 1, 2, …, n) and lines [ 1, 2, …, n] with incidences given by equations: n- n= 1 1+ 2 2+⋯+ n-1 n-1.
This is symbolically equivalent to the 1,n n( ’) JordanGauss graph over the ring ’ with unity, having partition sets isomorphic to ( ’)n and with incidences given by equations of the form: n- n= 1 1 1+ 2 2 2+⋯+ n-1 n-1, where and are elements of the multiplicative group of ’ and i≠0, =1, 2, …, -1.
Graph 1, n n( )t has the same points and lines with 1, n n(K) but the incidence is given by equations (t) n− (t) n= 1(t)x1 1+ 2 (t)x2 2+⋯+ n-1(t)xn-1yn-1.
We say that i, j n( )t convert in fixed time moment t=t* to static Jordan-Gauss graph i ,j n( )t |t=t* via selection of values of “time-dependent” coefficients of monomial terms of equations.
In another example, the graph s, s+1 s+r( ) can be interpreted as a bipartite graph consisting of points of the form ( 1, 2, …, s, 1,1, 1,2, …, s,r) and lines [ 1, 2, …, r, 1,1, 1,2, …, s,r], with the incidence condition given by the equations: i,j- i,j= iyj, =1,2, …, s, =1,2, …, r.
This is symbolically equivalent to the graph s, s+1 s+r+1( ), defined over the same commutative ring and with an incidence relation given by the system of equations: i,j i,j- i,jyi,j=di,j iyj, where elements i,j and bi,j belong to * and di,j are elements from ∖{0}.
These two families of graphs give us extremal cases: the incidence of points and hyperplanes from 1, n n( ) is the case of the single equation, while the case of subspaces of dimension s and s+1 of s, s+1 s+r+1( ) is the case when polynomials of the right-hand side have a single monomial.
Let us consider basic operators on the set of vertexes of the linguistic graph of type (s, r, m).
We refer to ρ((x))=(x1, x2, …, xs) for (x)=(x1, x2, …, xs+m) and ρ([y])=(y1, y2, …, yr) for [y]=[y1, y2, …, yr+m] as the colour of the point and the colour of the line respectively.
For each bϵ Kr and p=(p1, p2, …, ps+m) there is the unique neighbour of the point [l]=Nb(p) with the colour b. Similarly, for each c ϵ Ks and line l=[l1, l2, …, lr+m] there is the unique neighbour of the line (p)= Nc([l]) with the colour c. We refer to operator of taking the neighbour of the vertex accordingly chosen colour as neighbourhood operator.
On the sets P and L of points and lines of the linguistic graph we define colour jump operators J=Jb(p)=(b1, b2, …, bs, p1, p2, …, ps+m), where (b1, b2, …, bs)ϵKs and J=Jb([l])=[b1, b2, …, br, l1, l2, …, lr+m], where (b1, b2, …, br)ϵKr.
For the point (p) and odd parameter l sequence of the colours a(1)ϵKs, b(1) ϵKr, a(2)ϵKr , b(2) ϵKs, ...., a(l)ϵKs, b(l) ϵKr, a(1+1) ϵKr which allows us to define the map H: Km+s→Km+r moving arbitrary point (v) to the line h=h(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1))(v)=vl+1 defined via the following sequence of vertexes.
v1=Ja(1)(v), u1=Nb(1)(v1), v2=Ja(2)(v1), u2=Nb(2)(v2), ..., vl=Ja(l)(vl-1), ul=Nb(l)(vl), vl+1=Ja(l+1)(ul). We refer to map H as the transition of (v) in the direction (a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1)).
We can define the transition H(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1)) in the case of even l in which v→h(v) will be a transformation acting on Ks+m=P.
For eachlinguistic graph Г(К) we consider Г'=Г(K[z1, z2, ..., zm+s]) given by the same equation but with the partition sets K[z1, z2, ..., zm+s])m+s and K[z1, z2,..., zm+s])m+r.
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), ..., a(l), a(l+1)) to the vertex z of the graph Г’ such that coordinates of a(i), b(i) are elements of K[[z1, z2,..., zs]. The image of z will be the tuple u=(a(l+1)1(z1, z2,..., zs), a(l+1)2(z1, z2,..., zs),..., a(l+1 )r(z1, z2,..., zs), f1(z1, z2,..., zm+s), f2(z1, z2,..., zm+s), …, fm(z1, z2,..., zm+s)). Let F=F(a(1), b(1), a(2), b(2), ..., a(l), a(l+1)) be a polynomial map of Km+s to Km+r sending (z1, z2, ..., zm+s) to (u1, u2, ..., um+s])=u.
We take two affine transformations L1 and L2 and consider the composition G=L1FL2 sending (z1, z2, ..., zm+s) to (g1(z1, z2, ..., zm+s), g2(z1, z2, ..., zm+s), …, gm+r(z1, z2,..., zm+s)).
Additionally, we consider the above-presented construction in the case of even parameter l Then a(l+1) is an element of K[x1, x2, ..., xs]s, ul+1 and vl+1 are points. We have to take L1 and L2 from AGLm+s(K) and construct the transformation G=L1FL2 of the affine space Km+s.
Proposition 1 [
Then the knowledge on Г(К) and tuples a(1), b(1), a(2), b(2). ..., a(l), b(l), transformations L1, L2, and T is a trapdoor accelerator of the standard form of G mapping Km+s on Km+t.
Justification of Proposition 1’.
Let us assume that Г(К) is temporal graph and its static graphs Гі in time i=1, 2, ..., l are known as well as a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1), T and L1, L2 of the Proposition 1. Let us consider the equation G(z)=b for the given value of the tuple b.
We compute (L2)-1 (b)=c and introduce intermediate vector p=(p1, p2, ..., ps, ps+1, ps+2, ..., ps+m) of variables pi and consider the equation H(p)=c where H=H(a(1), b(1), a(2), b(2), ..., a(l), a(l+1))=(a(l+1)1, a(l+1)2, ...a(l+1)t, h1, h2,..., hm), where hiϵK[x1, x2,..., xs+m].
We use our knowledge of the trapdoor accelerator T to get solution p1=d1, p2=d2, ..., ps=ds. Let d=(d1, d2,...,ds). It gives us the opportunities to compute a*(1)=a(1)(d1, d2, ..., ds), b*(1)=b(1)(d1, d2, ..., ds), a*(2)=a(2)(d1, d2, ..., ds), b*(2)=b(2)(d1, d2, ..., ds), ..., a*(l)=a(l)(d1, d2, ..., ds), b*(l)=b(l)(d1, d2, ..., ds), 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), d)= (w1, w2, ..., ws, ws+1, ws+2, ..., ws+m)=w.
Thus we got a solution for H(p)=c. We compute the solution z* of G(z)=c as z*=(L1)-1(w)).
If l is even or r=1 then the reimage reimage z* is uniquely defined.
We define a density of multivariate polynomial f(z1, z2, ..., zn) written in its standard form as a number of monomial terms.
The density den(b) of the tuple b=(f1, f2, ..., fk) from K[z1, z2, ..., zn]k is the maximal density of fi. The density of the map F: xi→fi, i=1,2, ..., k coincides with the density of the corresponding tuple of polynomials fi.
Proposition 2 [
Remark. Proposition 1 and Proposition 2 hold also for the temporal linguistic graphs and temporal cellular Schubert graphs.
Let us consider the following important object of Noncommutative Cryptography. Affine Cremona
Semigroup nCS(K) is defined as an endomorphism group of
polynomial ring K[x1, x2, ..., xn] over the commutative ring
K. It is an important object of Algebraic Geometry (see [
Element of the semigroup σ can be given via its values
on variables, i.e. as the rule xi→fi(x1, x2, …, xn), i=1, 2, …, n.
This rule induces the map σ’: (a1, a2,.., an)→(f1(a1, a2, ..., an),
f2(x1, x2, …, xn), …, fn(x1, x2, …, xn)) on the free module Kn.
Automorphisms of K[x1, x2, ..., xn] form affine Cremona
GroupnCG(K) (see [
In the case when K is a finite field or arithmetic ring Zm of residues modulo m elements of affine Cremona Groups or Semigroups are used in algorithms of multivariate cryptography. Results about subsemigroups S of nCS(K) (or subgroups of nCG(K) such that computation of the superposition of arbitrary n elements can be completed for polynomial time can be used as so-called platforms of Noncommutative Cryptography.
One class of such objects is formed by stable subsemigroups of degree k, i.e. subsemigroup S such that the maximal degree of its representative is bounded by the constant k. We will talk about the Multiple Composition Computability (MCC) property. In the case of k=1 one can take AGLn(K), stable subsemigroups of degree k in nCG(K) exist for each k, k=2, 3, ... Affine Cremona semigroup nCS(K) does not pose MCC. If one takes n quadratic elements randomly their product with a probability close to 1 will have degree 2n. So the computation is not feasible.
EXAMPLE: Let us consider the totality nES(K) of endomorphisms of K[x1, x2, ..., xn] of kind x1→ϻ1x1 a(1,1) x2 a(1,2) … xn a(1,n), x2→ϻ2x1 a(2,1) x2 a(2,2) … xn a(2,n), (4) … xm→ϻnx1 a(n,1) x2 a(n,2) … xn a(n,n) where ϻi are regular elements of finite commutative ring K with unity.
It is easy to see that the complexity of the computation of the product of two elements of kind (4) is O(n3). So, the semigroup of Eulerian transformations nES(K) poses the property MCC. Semigroups with this property can serve as “platforms” of protocols of Noncommutative Cryptography.
The following examples of special elements of nES(K)
can be found in [
(K*)n Let π and δ be two permutations on the set {1, 2, ..., n}. Let K be a commutative ring with unity which has nontrivial multiplicative group K* of order d=|K*|>1 and n≥1. We define transformation AJG(π, δ) of the variety (K*)n, where A is a triangular matrix with positive integer entries 0≤a(i,j)≤d, i≥d defined by the following closed formula. yπ(1)=ϻ1xδ(1)a(1,1) yπ(2)= ϻ2xδ(1)a(2,1) xδ(2)a(2,2) … 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.
We refer to AJG(π, δ) as Jordan transformations Gauss
multiplicative transformation, or simply JG element. It is an
invertible element of nES(K) with the inverse of kind BJG(δ,
π) such that a(i,i)b(i,i)=1 (mod d). Notice that in the case
K=Zm straightforward process of computation the inverse of
JG element is connected with the factorization problem of
integer m. If n=1 and m is a product of two large primes p
and q the complexity of the problem is used in the RSA
public key algorithm. The idea to use the composition of JG
elements or their generalisations with injective maps of Kn
into Kn was used in [
We say that τ is a tame Eulerian element over the commutative ring K if it is a composition of several Jordan Gauss multiplicative maps over a commutative ring or field respectively. It is clear that τ sends variable xi to a certain monomial term. The decomposition of τ into a product of Jordan Gauss transformation allows us to find the solution of equations τ(x) = b for x from (Z*m)n or (F*q)m. So tame Eulerian transformations over Zm or Fq are special elements of nEG(Zm) or nEG(Fq) respectively.
We refer to elements of nES(K) as multiplicative Cremona elements. Assume that the order of K is constant. As it follows from the definition the computation of the value of element from nES(K) on the given element of Kn is estimated by O(n2). The product of two multiplicative Cremona elements can be computed in time O(n3).
We are not discussing here the complexity of computing the inverse for general element gϵ nEG(K) on the Turing machine or Quantum computer and the problem of finding the inverse for tame Eulerian elements.
Let K be a finite commutative ring with unity and nontrivial multiplicative group K* of order d>1. Alice selects graph i, j 2m( ), i>j, i=m+α, j=m-β where α>0 and β ≥0 are constants ≥0. We assume that parameters α and β are essentially smaller than n. She computes parameter n=(m+α)(m-α+1) and s=(m+α-1)(α+ β), r=(m-β)(α+β) and forms the transformation J1 and J2 from nEG(K) of kind y1=μ1x1a(1,1) y2=μ2x1a(2,1) x2a(2,2) … yn=μnx1a(n,1) x2a(n,2) … xna(n,n) 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) z2=μ’1y2b(2,2) y2b(2,3) … ynb(2,n) … zn=μ’nynb(n,n) where (b(n,n), d)=1, (b(n-1, 2), d)=1, …, (b(1, n), d)=1.
She computes the composition of J1 and J2 and obtains the vector (z1, z2, ..., zs, zs+1, …, zn) and treats this tuple as a point of graph i, j 2m( ).
She selects even parameter l, l>5 of size O(1) together with sparse tuples a(1), b(1), a(2), b(2), …, a(l), b(l), a(l+1) of density O(1) of Proposition 2.
So, a(i)=(il1(z1, z2, …, zs), il2(z1, z2, …, zs), …, ils(z1, z2, …, zs)) for i=1, 3, 5, …, l-1, l+1,
a(i)=(il1(z1, z2, …, zs), il2(z1, z2, …, zs), …, ilr(z1, z2, …, zs)) for i=2, 4,…, l,
b(i)=(ih1(z1, z2, …, zs), ih2(z1, z2, …, zs), …, ihr(z1, z2, …, zs)) for i=1, 3, …, l-1,
b(i)=(ih1(z1, z2, …, zs), ih2(z1, z2, …, zs), …, ihs(z1, z2, …, zs)) for i=2, 4, …, l.
Alice selects a(l+1) as a tuple of kind (λ1z1e(1,1), λ2z1e(2,1)z2e(2,2), ..., λsz1e(s,1)z2e(s,2) … zs(s,s)) where (e(1, 1), d)=1, e(2, 2), d)=1, …, (e(s, s), d)=1.
Alice computes F(z1, z2, …, zn)=(F(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1)) (z1, z2, …, zn)=(u1, u2, …, un)=u.
She takes element L from AGLn(K) and computes L(u)=(w1, w2, …, wn). So Alice computes the composition G=J1J2FL:(x1, x2, …, xn)→(w1(x1, x2, …, xn), w2(x1, x2, …, xn), …, wn(x1, x2, …, xn)).
She sends standard forms of multivariate polynomials wi to Bob. Alice keeps J1, J2, L and a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1) as her private secret.
Encryption.
Bob generates his message p=(p1, p2, ..., pn) from the space of plaintexts (K*)n. He creates the ciphertext G(p1, p2, ..., pn)=c and sends it to Alice.
The process of generating G insures that the density of the map is O(n). Each monomial can be computed in time O(n). Thus the complexity of the encryption procedure is O(n3).
We have a nonlinear map of an unbounded degree such that the computation of its value has the same complexity as the computation of an image of a quadratic map.
Decryption.
Alice receives the message c from Bob. Firstly she computes b=L-1(c). Secondly Alice creates the intermediate tuple (z1, z2, ..., zn) to study equation F(z1, z2, ..., zn)=b.
She writes the equation
λ1z1e(1,1)=b1, λ2z1e(2,1)z2e(2,2)=b2, (5) … λsz1e(s,1) z2e(s,2) …zse(s,s)=bs Alice gets the solution z1=d1, z2=d2, ..., zs=ds.
She computes the parameters a*(i)=a(i)(d1, d2, ..., ds) and b*(i)=b(i)(d1, d2, ..., ds) for i=1, 2,..., l.
Alice takes point (b) and computes recurrently ul=Jb*(l)(b), wl= Na*(l)(ul), ul-1=Jb*(l-1)(wl), wl-1=Na*(l-1)(ul-1), …, 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 d=(d1, d2,…, ds).
We can see that z* is the solution of the system (3). Alice computes the plaintext p as (J2)-1(Jl)-1(z*).
Alice computes the inverses of J1 and J2 in the group nEG(K) as well as the inverse of the map z1→λ1z1e(1,1), z2→λ2z1e(2,1)z2e(2,2), ..., zs→ λsz1e(s,1)z2e(s,2) … zse(s,s) in the group sEG(K) in advance. So the complexity of her decryption procedure can be estimated as O(n2).
Obfuscation.
Instead of graphs i,j 2m( ) Alice takes temporal analogue i,j 2m( ) t of them. She forms static graphs i,j 2m( )t|t=t* for t*=1, 2, ..., l.
So she computes each N_b(i) in static graph i,j 2m( )t|t=i during the algorithm execution.
Illustrating example.
Let us consider the case (α=1, β=0).Then graph m+1,mC2m(K) known as Double Schubert Graph which has points (x)=(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m) and [y]=[y1, y2, ..., ym, y1,1, y1,2, ..., ym,m] and incidence given by equations xi,jyi,j=xiyj. We assume that indexes of kind (i,j) are ordered lexicographically.
Alice takes endomorphism J1 and J2 of K[x1, x2, ..., ,..., xm, x1,1, x1,2, ..., xm,m].
J1J2(x)=(a1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), a2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), …, am(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), a1,1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), a1,2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), …, am,m(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m))=(z1, z2, …, zm, z1,1, z1,2, …, zm,m)=(z) where expressions a1, a2, …, am, a1,1, a1,2, …, am,m are monomial terms with the coefficients from K*.
Alice takes graph m+1,mC2m(K[z1, z2, …, zm, z1,1, z1,2, …, zm,m]). She selects colours a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1) where a(i) and b(i) are elements of K[z1, z2, ..., zm, z1,1, z1,2, …, zm,m]m. Element a(l+1) will be chosen as (λ1z1e(1,1), λ2z1e(2,1)z2e(2,2), ..., λsz1e(s,1)z2e(s,2) … zse(s,s)). She computes the destination point of transition H(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1)) of the point (z) in the graph m+1,mC2m(K[z1, z2, …, zm, z1,1, z1,2, …, zm,m]). Alice specialise zi as ai(x) and zi,j as ai,j(x).
So she computes the composition of J=J1J2 moving (x) to (z) and F(a(1), b(1), a(2), b(2), ..., a(l), b(l), a(l+1) moving z to u=(u1, u2, ..., um, u1,1, u1,2, ..., um,m). It is clear that the density of JF is O(1). Finally Alice selects L from AGLn(K), n=(m+1)m and computes (JF)L=G(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m) of kind x1→g1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), x2→g2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), ..., xm→gm(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), x1,1→g1,1(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), x1,2→g1,2(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m), ... xm,m→gm,m(x1, x2, ..., xm, x1,1, x1,2, ..., xm,m).
For convenience Alice can rename variables from the list x1, x2, ..., xm, x1,1, x1,2, ..., xm,m as y1, y2, ..., ym, xm+1, xm+2, ..., xm(m+1).
In this paper, we present the method of construction of sparce multivariate maps of unbounded degree O(n) with the trapdoor accelerators with the use of walks on algebraic graphs. It uses bipartite cellular Schubert graphs of projective geometries and their analogues defined over the general commutative ring K with the unity. These bipartite graphs can be changed for their temporal analogues defined via the option of a momentum change of the coefficients of monomial terms in the equations defining the incidence of points and lines.
The partition sets of such graphs are affine spaces Kn
and Km. The special walk on the temporal graph over K [x1,
x2, ..., xn] can be used for the construction of a multivariate
map G from Kn to Kn. The information on the temporal
graph and the walk can serve as corresponding trapdoor
accelerator T of G, i.e. the knowledge of T allows us to
compute the reimages of G. We presented some of these
procedures as Algorithm 1 and 4 in the case of graphs
s,kCn(K) in terms of Chevalley group over the diagram An
(case of general linear group). Some other maps with
trapdoor accelerators are described in [
The first graph-based bijective quadratic public key where constructed in [6]. It uses special cellular Schubert graphs of Projective Geometry over the finite field of characteristics 2. The cryptanalysis for this public key is unknown.
The obfuscation of this cryptosystem is presented in [1].
Recent development in this direction is reflected in [
Another bijective quadratic cryptosystem which is also
constructed in terms of Jordan-Gauss graphs is given in [
Multivariate cryptosystems with rules of unbounded
degree are quite rare. We refer to cryptosystems [
These multivariate maps have O(n4) monomial maps. Cryptanalysis for them is still unknown. Presented in this paper cryptosystem is given by multivariate rule with O(n2) monomial terms. Thus it can be implemented with hundreds of variables, The reduction of the degree of equations to 2 or 3 leads to an essential increase of variables (more than n2). It makes it unfeasible to use standard methods of symbolic computations for cryptanalytic purposes.
For the implementation of this public key, we select cases K=Fq and K=Zq where q is a prime power ≥128.
This research is partially supported by the British Academy Fellowship for Researchers under Risk 2022 and partially supported by the British Academy grant LTRSF\100333.