On the Jordan-Gauss graphs and new multivariate public keys⋆ Vasyl Ustymenko1,2,∗,†, Tymoteusz Chojecki3,† and Aneta Wróblewska3,† 1 Royal Holloway, University of London, Egham Hill, TW20 0EX Egham, United Kingdom 2 Institute of Telecommunication and Global Information Space, 25 Chokolivskiy blv., 03186 Kyiv, Ukraine 3 Maria Curie-Skłodowska University, 5 Pl. M. Curie-Skłodowskiej, 20-031 Lublin, Poland Abstract We suggest two families of multivariate public keys defined over arbitrary finite commutative ring K with unity. The first one has a quadratic multivariate public rule, this family is an obfuscation of previously defined cryptosystem defined in terms of well-known algebraic graphs D(n, K) with the partition sets isomorphic to Kn. Another family of cryptosystems uses the combination of Eulerian transformation of K[x1, x2, ..., xn] sending each variable xi to a monomial term with the quadratic encryption map of the first cryptosystem. The resulting map has an unbounded degree and the density O(n4) like the cubic multivariate map. The space of plaintexts of the second cryptosystem is the variety (K*)n and the space of ciphertexts is the affine space Kn. Keywords multivariate cryptography over commutative rings, graph-based symbolic computations, quadratic public keys, multivariate public keys of unbounded degree1 1. Introduction Noteworthy that the NIST tender was designed for the selection and investigation of public key algorithms and This paper presents the generalization of the quadratic in the area of Multivariate Cryptography only quadratic multivariate public key given in [1] with the use of multivariate maps were investigated. So, a large class of quantum computing. protocol-supported asymmetric algorithms of El Gamal The progress in the design of experimental quantum type was eliminated. We were working on the design of computers is speeding up lately. Expecting such the new algorithms from this class during our project. We development the National Institute of Standardisation have to admit that general interest in various aspects of Technologies of USA announced in 2017 the tender on Multivariate Cryptography was connected with the standardization best known quantum-resistant search for secure and effective procedures of digital algorithms of asymmetrical cryptography. The first signature where mentioned above ROUV cryptosystem round was finished in March 2019, and essential parts of was taken as a serious candidate to make the shortest the presented algorithms were rejected. At the same signature. time, the development of new algorithms with a Let us summarize the outcomes of the mentioned postquantum perspective was continued. A similar above NIST tender. process took place during the 2nd, 3rd, and 4th rounds. Five categories were considered by NIST in the PQC The last algebraic public key “Unbalanced Oil and standardization (the submission date was 2017; in July Vinegar Rainbow like digital signatures” (ROUV) 2022, the four winners and the four final candidates were constructed in terms of Multivariate Cryptography was proposed for the 4th round—this is the current official rejected in 2021 (see [2, 3]). Certain hopes of algebraists status. However, the current 8 final winners and are connected with so-called Noncommutative candidates only belong to the following four different Cryptography which is based on problems connected mathematical problems (not the five announced at the with the studies of algebraic objects such as groups, beginning): semigroups, noncommutative rings, and algebras. Presented on Mist tender single algorithms from this  Lattice-based class based on braids group was broken. The first four  Hash-based winners of this competition were announced in 1922,  Code-based they are developed in terms of Lattice Theory.  Supersingular elliptic curve isogeny based. CQPC-2024: Classic, Quantum, and Post-Quantum Cryptography, August 0000-0002-2138-2357 (V. Ustymenko); 0000-0002-3294-2794 6, 2024, Kyiv, Ukraine (T. Chojecki); 0000-0001-9724-4586 (A. Wróblewska) ∗ Corresponding author. © 2024 Copyright for this paper by its authors. Use permitted under † These authors contributed equally. Creative Commons License Attribution 4.0 International (CC BY 4.0). vasyl.ustymenko@rhul.ac.uk (V. Ustymenko); tymoteusz.chojecki@umcs.pl (T. Chojecki); aneta.wroblewska@poczta.umcs.lublin.pl (A. Wróblewska) CEUR Workshop ceur-ws.org ISSN 1613-0073 54 Proceedings The standards are to be published in 2024. But already at Let K be a finite commutative ring. We refer to an the end of round 3, the last candidate (“Rainbow”) from incidence structure with a point set P = Ps,m = Ks+m and a the multivariate cryptography (MVC) category was out. line set L = Lr,m = Kr+m as linguistic incidence structure Im Its interesting obfuscation “TUOV: Triangular if point x = (x1, x2 ,…, xs, xs+1, xs+2, …, xs+m) is incident to Unbalanced Oil and Vinegar” was presented to NIST line y = [y1, y2, …, yr, yr+1, yr+2, …, yr+s] if and only if the [39] by principal submitter Jintaj Ding. following relations hold Further development of Classical Multivariate a1xs+1-b1yr+1 = f1 (x1, x2, …, xs, y1, y2, …, yr) Cryptography which studies quadratic and cubic a2xs+2-b2yr+2 = f2 (x1, x2, …, xs, xs+1 xs+1, y1, y2, …, yr, yr+1) endomorphisms of Fq[x1, x2, …, xn] see [6–18]. Current … research in Postquantum Cryptography can be found in amxs+m-bmyr+m = fm (x1, x2, …, xs, xs+1, …, xs+m-1, y1, y2, …, [35–38]. yr, yr+1, …, yr+m-1) We use the concept of quadratic accelerator of the where aj, and bj, j = 1, 2, …, m are not zero divisors, endomorphism σ of K[x1, x2, …, xn] which is the piece of and fj are multivariate polynomials with coefficients information T such that its knowledge allows us to from K (see [22, 23]). Brackets and parenthesis allow us compute the reimage of (σ, Kn) in time O(n2). Symbol K to distinguish points from lines. stands here for an arbitrary commutative ring with unity. The color ρ(x) = ρ((x)) (ρ(y) = ρ([y])) of point (x) (line Our suggestion is to use for public key the pairs (σ, T) such [y]) is defined as the projection of an element (x) that σ has a polynomial density, i. e. number of monomial (respectively [y]) from a free module on its initial s terms of σ(xi), i = 1, 2, …, n. Some examples of such public (relatively r) coordinates. As it follows from the keys the reader can find in [4, 5]. definition of linguistic incidence structure for each For each pair (K, n), n > 1 we present quadratic vertex of the incidence graph there exists a unique automorphism σ of K[x1, x2,…, xn] with the trapdoor neighbor of a chosen color. accelerator T defined via totality of special bipartite We refer to ρ((x)) = (x1, x2, …, xs) for (x) = (x1, x2, …, Jordan-Gauss graphs with the partition sets isomorphic to xs+m) and ρ([y]) = (y1, y2, …, yr) for [y] = [y1, y2, …, yr+m] as Kn. We discuss the possible use of these transformations the color of the point and the color of the line in the case of finite fields and arithmetical rings Zq where respectively. For each b ϵ Kr and p = (p1, p2, …, ps+m) there q is a prime power. Additionally, we create a public key as is a unique neighbor of the point [l] = Nb(p) with the a composition of quadratic σ with the Eulerian color b. Similarly for each c ϵ Ks and line l = [l1, l2, …, lr+m], transformation sending each x1 to a monomial term. The there is a unique neighbor of the line (p) = Nc([l]) with public map has an unbounded degree and density O(n4). the color c. The triples of parameters s, r, and m define So the complexity of encryption is as in the case of the type of linguistic graph. classical cubic maps. We consider also linguistic incidence structures defined by the infinite number of equations. 2. On Jordan-Gauss graphs and Linguistic graphs are defined up to isomorphism. multivariate keys We refer to written above equations as canonical equations of linguistic graphs. We consider also The missing definitions of graph-theoretical concepts linguistic incidence structures defined by the infinite which appear in this paper can be found in [19–21]. All number of equations. Linguistic graphs are defined up to graphs we consider are simple graphs, i.e. undirected isomorphism. We refer to written above equations as without loops and multiple edges. Let V(G) and E(G) canonical equations of linguistic graphs. denote the set of vertices and the set of edges of G We say that linguistic graph is a Jordan-Gauss type respectively. When it is convenient we shall identify G if the map [(x), [y]] → (f1 (x1, x2, …, xs, y1, y2, …, yr), f2 (x1, with the corresponding anti-reflexive binary relation on x2, …, xs, xs+1, y1, y2, …, yr, yr+1), …, fm-1 (x1, x2, …, xs, xs+1, …, V(G), i.e. E(G) is a subset of V(G)◦V(G) and write v G u xs+m-1, y1, y2, …, yr, yr+1, …, yr+m-1)) where (x)ϵKs+m, [y]ϵKr+m for the adjacent vertices u and v (or neighbors). is a bilinear map into K1. So all fi are special quadratic We refer to |{x ϵ V(G)|xGv}| as the degree of the maps. In the case of Jordan-Gauss graphs, the vertex v. neighborhood of each vertex is given by the system of The incidence structure is the set V with partition linear equations written in its row—echelon form. sets P (points) and L (lines) and symmetric binary Let Im be a linguistic graph defined over the relation I such that the incidence of two elements commutative ring K. For each bϵ Kr and p = (p1, p2, …, ps+m) implies that one of them is a point and another one is a there is the unique neighbor of the point [l] = Nb(p) with line. We shall identify I with the simple graph of this the color b. Similarly, for each c ϵ Ks and line l = [l1, l2, …, incidence relation or bipartite graph. The pair x, y, x ϵ P, lr+m] there is the unique neighbor of the line (p) = Nc([l]) y ϵ L such that x I y is called a flag of incidence structure with the color c. We refer to the operator of taking the I. 55 neighbor of vertex accordingly chosen color as y2, ..., ys), …, ys → hs(y1, y2, ..., ys), is bijective on Ks [24]. neighborhood operator. Defined above transformations form a semigroup I(K)SP On the sets P and L of points and lines of the linguistic of multivariate transformation. Some basic properties of graph we define jump operators 1J = 1Jb(p) = (b1, b2, …, bs, this semigroup are discussed in [24]. p1, p2, …, ps+m), where (b1, b2, …, bs) ϵ Ks and Of course, we can use lines instead of points and define 2 J = 2Jb([l]) = [b1, b2, …, br, l1, l2, …, lr+m], where (b1, b2, …, another semigroup I(K)SL formed by transformation of kind br) ϵ Kr. We refer to tuple (s, r, m) as the type of the I(K), c Pass, cϵ K[x1, x2, …, xs] (2t+1)r+2 ts acting on the variety Km+r. linguistic graph I. Remark. We may omit some operators of kind Jc(i) We say that point (p) is a line [l] adjacent in the making the color c(i) to be the same as c(i – 1). linguistic graph I if 1Jb(p)I 2Jc[l] for some colors b ϵKs and We can treat the sequence c from K[x1, x2, …, xs]l as c ϵKr. Let ψ stand for the adjacency relation of the the tuple of its coordinates ci from K[x1,x2,…, xs] and linguistic graph. We say that the linguistic graph has define the degree of c as polynomials ci(x1, x2,…, xs). degree d, d≥2 if the maximal degree of nonlinear In [25] special Jordan-Gauss graph JG(r, s, m, Fq), multivariate polynomials fi, i = 1, 2, …, m is d. q = 2t, t>1 was used for the construction of the public Noteworthy, that the path v0, v1, …, vk in the key. This linguistic graph of type (r, s, m) is obtained linguistic graph Im_ is determined by starting vertex v0 from the projective geometry PGn(Fq), i.e. the totality of and colours of vertexes v1, v2, …, vk such that nonzero proper subspaces of (Fq)n+1. The corresponding ρ(vi) ≠ ρ(vi+2) for i = 0, 1, …, k-2. bipartite graph is obtained as an induced subgraph of Let us consider the sequence of colours c(1), c(2), c(3), bipartite incidence graph with the partition sets which c(4), c(5) where c(1) and c(4), c(5) are from Ks and c(2), are largest Schubert cells, i.e. largest orbits of UTn(Fq) c(4) are elements of Kr. acting on l dimensional subspaces and subspaces of Let v0 = (x) be a general point of the graph I then for dimension t, l ≠ t. the vertices v1 = 1Jc(1)(v0), v2 = Nc(2)(v1), v3 = 2Jc(3),(v2), Cubic public keys defined in [26U, Ch, K] used v4 = Nc(4)(v3), v5 = 1Jc(5)(v4) the relations v0ψv3, v2 ψv5 Jordan-Gauss graphs A(n, Fq) [27] and D(n, Fq) [28]. holds. These two families of graphs were used in [1] for the We consider the tuple of colors c(1), c(2)…., c(t), t = 1 construction of a quadratic public key. This paper also mod 4 such that c(i)ϵKs for i = 0,1 mod 4 and c(i) ϵKr for contains the construction of trapdoor accelerator T of i = 2,3 mod 4. quadratic endomorphism σ of K[x1, x2, …, xn] acting We refer to the sequence of vertexes v1 = 1J(v0), bijectively on Kn and defined in terms of graph D(n, K) v2 = Nc(2)(v1), v3 = 2Jc(3), v4 = Nc(4)(v3), v5 = 1J(v4), v6 = Nc(6)(v5), where K is an arbitrary commutative ring with unity v7 = 2Jc(7)(v6), v8 = Nc(8)(v7), …, vt-1 = Nc(t-1)(vt-2), vt = 1J(vt-1) as [23]. walk on the adjacency graph with the starting point (x) and The description of the generalization of this the colour trace c(1), c(2), …, c(t). construction is given below. For each positive integer l, we can consider graph Affine root system Ầ1 (A1 with wave see [29]) is the Im(K) together with lIm = Im(K[y1, y2, …, yl]) defined by the totality of vectors in the two-dimensional Euclidean space same polynomials fi, i = 1, 2, …, m with coefficients from R2 with the standard basis e1 = (1, 0) and e2 = (0, 1) containing K. vectors (1, 0), (0, 1), (i, i), (i, i + 1), (i + 1, i), i ≥ 1. All multiples Assume that l = m+s. We can consider the walk on of (1, 1) are known as imaginary roots, other roots that have the adjacency graph ψ(K[y1, y2, …, yl]) of length 4t+1 no multiples are known as real roots. with starting point (y1, y2, …, ys, ys+1, ys+2, …, ym+s) and We modify Ầ1 by adding copies (i, i)’ for each imaginary colours c(1), c(2), …, c(t) such that c(i)ϵK[y1, y2, …, ys]s for root (i, i), i >1. So we obtain a set Root consisting of roots i = 0,1 mod 4 and c(i)ϵK[y1, y2, …, ys]r for i = 2,3 mod 4. of Ầ1 and elements (i, i)’, i>1. Assume that c(t) = (h1(y1, y2, ..., ys), h2(y1, y2, …, ys), Let R1 = Root—{(0,1)} and R2 = Root—\{(1,0))\} and K be …, hs(y1, y2, …, ys)). a commutative ring with unity. We consider sets Li = KRi, Then v1 = (h1, h2, …, hs, g1, g2, …, gm). Let us consider i = 1, 2 of all functions f from Ri, i = 0,1 to K such that the polynomial map I(K),c Pass, cϵ K[x1, x2, …, xs] (2t+1)s+2rt only for finite elements x from Ri the value f(x) differs of K s+m to itself which sends (y1, y2, …, ys, ys+1, …, ys+m) from zero. to vt, i. e. the map We write an element X = (x) from P = L1 as the tuple y1 → h1(y1, y2, ..., ys), y2 → h2(y1, y2, ..., ys), …, ys → (x) = (x1,0, x1,1, x1,2, x2,1, x2,2, x’2, 2, …, xi, i+1, xi+1,i, xi+1,i+1, x’i+1, → hs(y1, y2,...,ys), i+1, ...) where xα is the value of X on the root α from Ầ1 ys+1 → g1(y1, y2, ..., ys, ys+1, ys+2, ..., ys+m), ys+2 → and x’i,i is the value of X on (i, i)’, i>1. → g2(y1, y2, ..., ys, ys+1, ys+2, ..., ys+m), …, ys+m → → gm(y1, Similarly we write an element Y = [y] from L = L2 as y2, ..., ys, ys+1, ys+2, ..., ys+m). the tuple It is easy to see that this transformation is bijective [y] = [y0,1, y1,1, y1,2, y2,1, y2,2 y’2,2, …, yi,i+1, yi+1,i, yi+1,i+1, if and only if the map y1 → h1(y1, y2, ..., ys), y2 → h2(y1, y’i+1, i+1, …] where yα is the value of Y on the root α from 56 Ầ1 and y’i,i is the value of Y on (i, i)’, i>1. We introduce Let G be a t-regular simple graph and v be the vertex the incidence structure (P, L, I) as the following bipartite from V(G). We say that k is the local depth of the vertex graph on P U L. v if the induced graph of all vertices at distance ≤k is a A point (x) of this incidence structure I is incident tree and the graph on vertices at the distance k+1 has a with a line [y], i.e. (x)I[l], if their coordinates obey the cycle. following relations: The depth of G is the maximal local depth. xi, i, – y i, I = x1,0 yi-1,i, Computer simulation supports the conjecture that x’i,i – y’i,i=xi, i-1y0,1, the depths of graphs D(k, K) and DT (k, K) are the same. (1) x i,i+1 – yi, i+1 = xi,iy0,1, It is known that the depth of D(k, K) is at least [(k+3)/2]. xi+1,i – yi+1,I = x1,0y’i,i. Let us renominate the coordinates of points and line (These four relations are well defined for i>1, of DT (k, K) with one variable index i according to the x1,1 = x’1,1, y1,1 = y’1,1). lexicographical order on roots of Ầ1. So we have point We start the description of the connectivity (x1, x2, ..., xk-m) and line [y1, y2, ..., yk-m] of linguistic graph. invariants of D(k, K). We take the “symbolic” line [y1, y2, ..., yk-m] of this To facilitate notation in the future results on graph and consider the infinite graph DT (k, K[y1, y2,..., “connectivity invariants” of D(n, K), it will be convenient yk-m]). We use the presented above technique to for us to define x-1,0 = y0,-1 = y1,0 = = x0,1 = 0, x0,0 = y0,0 = -1, associate with this graph the polynomial x’0,0 = y’0,0 = -1, x1,1 = x’1,1, y1,1 = y’1,1 and to assume that transformations acting on K, but slightly modify the our equations are defined for i≥0. procedure. Graphs CD(k, K) with k≥6 were introduced in [23], as Let ℾ(n, K), n=k-m be one of the graphs DT (k, K). The induced subgraphs of D(k, K) with vertices u satisfying graph ℾ(n, K) has so-called linguistic coloring ρ of the special equations a2(u) = 0, a3(u) = 0, …, at(u) = 0, set of vertices. We assume that ρ(x1, x2, …, xn) = x1 for the t = [(k+2)/4], where u = (uα, u1,1, u1,2, u2,1, …, ur,r, u’r,r, ur,r+1, vertex x (point or line) given by the tuple with ur+1, r, …), 2≤r≤t, α ϵ {(1, 0), (0,1)} is a vertex of D(k, K) and coordinates x1, x2,…, xn. We refer to x1 from K as the color ar = ar(u) = Σi=0,r (ui,iu’r-i,r-i -ui, i+1 ur-i,r-1-1) for every r from of vertex x. the interval [2,t]. Recall that Na and Ja are operators of taking the We set a = a(u) = (a2, a3, …, at) and assume that D(k, neighbor with color a and jump operator changing the K) = CD(k, K) if k = 2, 3, 4, 5. As it was proven in [23] original color of point or line for new color a from K. graphs D(n, K) are edge transitive. So their connected Let [y1, y2, …, yn] be the line y of ℾ(n, K[y1, y2, …, yn]) components are isomorphic graphs. and (ᾳ(1), ᾳ(2), …, ᾳ(t)) and (β(1), β(2), …, β(t)) are the Let vCD(k, K) be a solution set of the system of sequences of colours from K[y1] of the length at least 2. equations a(u) = (v2, v3, …, vt) = v for certain vϵ Kt-1. It is We consider the sequence 0v = y, 1v = Jᾳ(1)(0v), proven that each vCD(k, K) is the disjoint union of some = 2v = Nβ(1)(1v), 3v = Nᾳ(2)(2v), 4v = Nβ(2)(3v), 5v = Nᾳ(3)(4v), …, connected components of graph D(n, K). 2t- 2 v=Nβ(t-1)(2t-3v), 2t-1v=Nᾳ(t)(2t-2v), 2tv=Jβ(t)(2t-1v). If K is a commutative ring with unity of odd Assume that v = 2tv = [v1, v2, …, vn] where vi are from characteristic then vCD(k, K) is the actual connected K[y1, y2, …, yn]. We consider polynomial transformation component of the graph (see [30]). g(ᾳ(1), ᾳ(2), …, ᾳ(t), β(1), β(2), …, β(t)), t ≥2 of affine space If K is a finite field of even characteristics of order ≥ 8 Kn of kind y1 → y1+β(t), y2 → v2(y1, y2), y3 → v3(y1, y2, then vCD(k, K) is the actual connected component of the y3), …, yn → vn(y1, y2, …, yn). graph (see [31]). It is easy to see that g(ᾳ(1), ᾳ(2), …, ᾳ(t), β(1), β(2), …, Let us consider the following graphs DT(k, K) β(t))•g(γ(1), γ(2), …, γ(s), σ(1), σ(2), …, σ(t)) = g(ᾳ(1), ᾳ(2), associated with D(n, K) and subset T = {j(1), j(2), j(s)} of …, ᾳ(t), γ(1)(β(t)), γ(2)(β(t)), …, γ(s)(β(t)), β(1), β(2), …, β(s), {2, 3, …, [(k+2)/2]} via the following procedure. σ(1)(β(t)), σ(2)(β(t)), …, σ(s)(β(t)). Delete coordinates of points and lines indexed by The following statements are formulated in [1] in roots (i(l), i(l))’, l = 1, 2, ..., s together with corresponding the case of graph D(k, K) but they hold for arbitrary equations of kind x’i(l),i(l) -y’i(l), i(l) = ..., = 1, 2, ..., s. graph DT (k, K). Substitute equations xi(l)+1,i(l) – yi(l)+1,i(l)=x1.0y’i(l), i(l) by xi(l)+1,i(l) Proposition 1. Transformations of kind g = g(ᾳ(1), – yi(l)+1,i(l)=x1.0yi(l), i(l). the last action is just a deletion of the ᾳ(2), …, ᾳ(t), β(1), β(2), …, β(t)), t ≥2 generate a semigroup prime symbol on the righthand side of the equation. S(ℾ(n, K)) of transformations of Kn. Proposition. Graphs DT(k, K) are Jordan-Gauss graphs Lemma 1. The degree of transformation g of the of type (1, 1, n-m-1) where m is a cardinality of T. Proposition 1 is at least [deg(ᾳ(1))+deg(ᾳ(1)- Polynomials ai(v) where 11. y*n). So Alice gets the intermediate tuple [y1, y2, …, Then transformation h = h(ᾳ(1), ᾳ(2), …, ᾳ(t), β(1), β(2), yn] = y*1, y*2 ,..., y*n] = y*. …, β*(t)) for which deg ᾳ(i) = 0, i = 1, 2, …, t, β(i) = y1+c(i), She computes the plaintext [p] as (L1)-1(y*). c(i)ϵK, i = 1, 2, … t-1 and β*(t) = (y1)2 is a bijective quadratic transformation of the vector space (Fq)n, the 3. Special endomorphisms of K[x1, polynomial degree of its inverse transformation is at least x2 …, xn] and cryptosystems of 2r-1. We use the modifications of transformation post quantum cryptography Theorem 1 for the construction of quadratic public keys. 3.1. Some definitions Algorithm 1. Alice selects commutative ring K with unity and K* of order >2 together with parameters k, m. Affine Cremona Semigroup nCS(K) is defined as an She selects T = {j(1), j(2),…, j(m)} and works with the endomorphism group of polynomial ring K[x1, x2, ..., xn] graph DT(k, K). Let us assume that j(1)>3. over the commutative ring K. It is an important Cremona Alice selects two transformations L1 and L2 from the object of Algebraic Geometry (see Max Noether paper group AGLn(K). She takes t = O(n), 22 and selects Jordan-Gauss We can use the following method of generating multiplicative transformations J1, J2, ..., Jd,. She computes invertible elements. their inverses (Jj)-1 and the composition J = J1J2, ..., Jd Let π and δ be two permutations on the set {1, 2, ..., Alice takes parameters m and k such that n = m-k. n}. Let us consider a transformation of (K*)n, d = |K*|. She selects graph DT(m, K) such that T contains k (the most important cases are K = Zm or K = Fq). We elements. define transformation AJG(π, δ), where A is a triangular Alice chooses affine and transformations L1 and L2 matrix with positive integer entries 0≤a(i,j)≤d, i≥j from defined by the following closed formula. AGLn(K). She forms ᾳ(1), ᾳ(2), …, ᾳ(t), β(1), β(2), …, yπ(1) = ϻ1xδ(1)a(1,1) β(t-1), β*(t) of Algotithm 1 of section 2. Alice uses the yπ(2) = ϻ2 xδ(1)a(2,1) xδ(2)a(2,2) transformation G = L1H(ᾳ(1), ᾳ(2), …, ᾳ(t), β(1), β(2), …, … β(t-1), β*(t)) L2. yπ(n) = ϻn xδ(1)a(n,1) xδ(2)a(n,2) …xδ(n)a(n,n) She computes the standard form F of JG which has linear where (a(1,1),d)=1, (a(2,2),d)=1, …, (a(n,n),d)= =1. degree O(n) and density O(n4). We refer to AJG(π, δ) as Jordan—Gauss multiplicative Alice sends F to public user Bob. transformation or simply JG element. It is an invertible Correspondents Alice and Bob use the variety (K*)n element of nES(K) with the inverse of kind BJG(δ, π) such as the space of plaintexts and a free module (K)n as the that a(i,i)b(i,i)=1 (mod d). Notice that in the case K= Zm space of ciphertexts. straightforward process of computation of the inverse of Bob writes the plaintexts p = (p1, p2, ..., pn) in the the JG element is connected with the factorization alphabet K*. He sends the ciphertexts c = F(p) to Al ice. problem of integer m. Alice computes u = G-1 (c) according to her private decryption procedure of Algorithm 1. Noteworthy that 3.2. Some algorithms u is an element of (K*)n. Alice computes consequtively So Alice can generate the element J as a product of d u = Jd(u), several Jordan Gauss transformations. The simplest case d-1 u = Jd-1(du), ..., 1u = J1(2u) = p. in the spirit of LU factorization is the composition of lower and upper triangular transformations. The cryptosystem is the following procedure. 4. Conclusions Alice can select several Jordan-Gauss Multivariate Cryptography in a wide sense is about transformations J1, J2, …, Jd, d>1 from mEG(K) and constructions and investigations of Public Keys in the compute their product J. One of the options is to send J form of nonlinear Multivariate rules defined over some to public user Bob. It looks like the security of such a finite commutative ring K. cryptosystem depends on the choice of commutative This rule F has to be written as transformation ring K (see [34]). xi → fi, i = 1, 2, ..., n, fi ϵ K[x1, x2, ..., xn] over the We suggest the following use J as a public rule. commutative ring K. Bijective F can be used for the Public user works with the space of plaintexts (K*)m. encryption of tuples (plaintexts) from the affine space The idea to use polynomial map F of bounded degree Kn. Multivariate rules can serve as instruments for the with the trapdoor accelerator T is used in [dop], [arch] creation of digital signatures. In the case of bijective for the construction of multivariate public key in the transformation, the decryption process can be thought case of special rings K = Fq and K = Zq. These schemes of as an application of inverse rule G. The degree of G use cubic endomorphism F of K[x1, x2, ..., xn] with the can be defined as the maximum of degrees of trapdoor accelerator T defined in terms of graphs D(n, K) polynomials G(xi), i = 1, 2, ..., n. For the usage of given (or their homomorphic images A(n, K)). We suggest the publicly, F as an efficient and secure instrument its following modification of these algorithms. degree of has to be bounded by some constant c (traditionally c = 2) but the polynomial degree of the inverse G has to be high. The key owner (Alice) is supposed to have some additional piece S of private information about pair (F, G) to decrypt ciphertext obtained from the public user 59 (Bob). Recall that the family Fn, n = 2, 3, ... from K[x1, x2,..., We believe that studies of multivariate public rules of xn] has trapdoor accelerator nS if the knowledge of the polynomial degree in variable n and the polynomial piece of information nS allows to compute reimage x of density are also interesting areas of research. y = Fn(x) from Kn in time O(n2). Of course, the concept of So we present a new cryptosystem from this area trapdoor accelerator is just an instrument to search for obtained via the composition of the Eulerian map of practical trapdoor functions. As you know the existence unbounded degree O(n) with the constructed quadratic of theoretical trapdoor functions is just a conjecture. It endomorphism of K[x1, x2, ..., xn] with the trapdoor is closely connected to the Main Conjecture of accelerator. Cryptography about the fact that P ≠ NP. Without the knowledge of Sn one has to solve a Funding nonlinear system of equations which generally is an NP- hard problem. The finding of the inverse for Fn is an NP- This research is supported by the British Academy hard problem if these maps are in the so-called “general Fellowship for Researchers under Risk 2022 and by the position”. In the case of specific maps additional British Academy Award LTRSF\100333 and UMCS Mini- argumentation of the complexity to find inverses Gn can Grants. be useful. We present such heuristic arguments in the case of References DT(n, K) based encryption defined for arbitrary [1] V. Ustimenko, A. Wróblewska, On Extremal commutative ring K with unity with at least 3 elements Algebraic Graphs, Quadratic Multivariate Public and presented in the previous section. Subset T can be Keys and Temporal Rules, FedCSIS (2023) 1173– viewed as part of the corresponding trapdoor accelerator 1178. n S. [2] W. Beullens, Improved Cryptanalysis of UOV and Graphs DT(n, K) have partition sets Kn (set of points Rainbow, Advances in Cryptology – EUROCRYPT and set of lines), and the incidence relation between 2021. LNCS 12696 (2021) 348–373. doi: points and lines is given by the system of linear 10.1007/978-3-030-77870-5_13 equations over K. [3] A. Canteaut, F.-X. Standaert, Eurocrypt 2021, 40th To define the trapdoor accelerator for standard Annual International Conference on the Theory forms Fn, n = 2, 3, ... we use special walks on graphs DT(n, and Applications of Cryptographic Techniques, K) and DT(n, K[x1, x2, ..., xn]). The constructed map Fn acts LNCS 12696 (2021). doi: 10.1007/978-3-030-77870- on the selected partition set Kn. In the case of trivial 5. affine transformations L1 and L2 the relation Fn(x) = y for [4] V. Ustimenko, On New Multivariate x = (x1, x2, ..., xn) and y = (y1, y2, ..., yn) vertices x and y are Cryptosystems Based on Hidden Eulerian joint in the graph DT(n, K) by the path of length >cn, Equations Over Finite Fields, where c is positive constant. archive.2017/093(PDF). Finding the path will give us the trapdoor [5] V. Ustimenko. On New Multivariate accelerator for the computation of preimages. This can Cryptosystems Based on Hidden Eulerian be done by the Dijkstra algorithm of complexity O(v Equations, Reports of the National Academy of ln(v)) where v is the order of graphs. It could not be done Sciences of Ukraine 5 (2017). doi: in polynomial time because v = 2|K|n and |K|≥3. 10.15407/dopovidi2017. 05.017. Noteworthy that the usage of nontrivial L1 and L2 will [6] J. Ding, A. Petzoldt, Current State of Multivariate complicate the cryptanalysis. Cryptography, IEEE Security & Privacy 15(4) Noteworthy that any nonlinear system of (2017) 28–36. doi: 10.1109/MSP.2017.3151328. multivariate equations of of constant degree d over a [7] D. Smith-Tone, 2F—A New Method for finite field can be rewritten as a quadratic system with Constructing Efficient Multivariate Encryption extra variables. Schemes, Proceedings of PQCrypto 2022, LNCS Studies of quadratic multivariate public rules over 13512 (2022). doi: 10.1007/978-3-031-17234-2_10. finite rings with zero divisors is an interesting task for [8] D. Smith-Tone, New Practical Multivariate cryptanalysts. Arithmetical rings modulo 2s is an Signatures from a Nonlinear Modifier, PQCrypto important practical task because several natural 2021, LNCS 12841 (2021). doi: 10.1007/978-3-030- alphabets for the presentation of files in informatics 81293-5_5. have size which is the power of 2. We are looking for the [9] D. Smith-Tone, C. Tone, A Nonlinear Multivariate K-theory of multivariate cryptography and presenting Cryptosystem Based on a Random Linear Code, the public rule defined over a general finite commutative URL: https://eprint.iacr.org/2019/1355.pdf ring with unity. [10] J. Dey, R. Dutta, Progress in Multivariate Cryptography: Systematic Review, Challenges, 60 and Research Directions, ACM Computing Survey [26] V. Ustimenko, T. Chojecki, M. Klisowski, On 55(12) (2023) 1–34. doi: 10.1145/3571071. Extremal Algebraic Graphs and Implementations [11] F. Cabarcas, D. Cabarcas, J. Baena, Efficient Public- of New Cubic Multivariate Public Keys, FedCSIS 35 Key Operation in Multivariate Schemes, Advances (2023) 1179–1184. doi: 10.15439/2023 F7763. in Mathematics of Communications 13(2) (2019). [27] V. Ustimenko, On Extremal Graph Theory and [12] R. Cartor, D. Smith-Tone, EFLASH: A New Symbolic Computations, Dopovidi National Multivariate Encryption Scheme, International Academy of Sci. 2 (2013) 42–49. Conference on Selected Areas in Cryptography, [28] F. Lazebnik, V. Ustimenko, A. J. Woldar, A New LNCS 11349 (2019) 281–299. doi: 10.1007/978-3- Series of Dense Graphs of High Girth, Bulletin of 030-10970-7_13 the AMS 32(1) (1995), 73–79. [13] A. Casanova, et al., Gemss: A Great Multivariate [29] N. Bourbaki, Lie Groups and Lie Algebras, Short Signature, Submission to NIST (2017) 209– Springer (1998). 229. [30] V. Ustimenko, Algebraic Groups and Small World [14] J. Chen, et al., A New Encryption Scheme for Graphs of High Girth, Albanian J. Math. 3(1) (209) Multivariate Quadratic Systems, Theoretical 26–33. Comput. Sci. 809 (2020) 372–383. doi: [31] F. Lazebnik, R. Viglione, On the Connectivity of 10.1016/j.tcs.2019.12.032. Certain Graphs of High Girth, Discrete Math. 277 [15] M.-S. Chen, et al., SOFIA: MQ-based Signatures in (2004) 309–319. the QROM, IACR Inter-National Workshop on [32] M. Noether, {\em Luigi Cremona}, Mathematische Public Key Cryptography. Springer (2018) 3–33. Annalen 59 (1904) 1–19. doi: 10.1007/978-3-319-76581-5_1. [33] V. L. Popov, Roots of the affine Cremona Group, [16] J. Ding, A. Petzoldt, D. S. Schmidt, Multivariate Affine Algebraic Geometry, Seville, Contemporary Public Key Cryptosystems, Second Edition, Mathematics 369 (2005) 12–13. Advances in Information Security, Springer, [34] V. Ustimenko, On Eulerian Semigroups of (2020). Multivariate Transformations and Their [17] D. H. Duong, et al., An Efficient Multi-Variate Cryptographic Applications, European J. Math. Threshold Ring Signature Scheme, Comput. Stand. 9(93) (2023). Interfaces 74 (2021). doi: 10.1016/J.CSI.2020. [35] M.-J. Saarinen, D. Smith-Tony, Post Quantum 103489. Cryptography, 15th International Workshop, [18] J.-C. Faugère, et al., A New Perturbation for PQCrypto 2024, Part 1 (2024). Multivariate Public Key Schemes Such as HFE and [36] M.-J. Saarinen, D. Smith-Tony, Post Quantum UOV, Cryptology ePrint Archive (2022). Cryptography, 15th International Workshop, [19] N. Biggs, Algebraic Graphs Theory, Second PQCrypto 2024, Part 2 (2024). Edition, Cambridge University Press (1993). [37] T. Takagi, et al., International Symposium on [20] A. Brower, A. Cohen, A. Nuemaier, Distance Mathematics, Quantum Theory, and Regular Graphs, Springer (1989). Cryptography, Proceedings of MQC 2019, Open [21] B. Bollob´as, Extremal Graph Theory, Academic Access (2021). Press (1978). [38] K. Arai, Advances in Information and [22] V. Ustimenko, Maximality of Affine Group, Communication, Proceedings of the 2024 Future of Hidden Graph Cryptosystem and Graph’s Stream Information and Communication Conference Ciphers, J Algebra Discrecadete Math. 1 (2005) 51– (FICC) 1–3, LNNS 919–921 (2024). doi: 65 10.1007/978-3-030-98012-2. [23] V. A. Ustimenko, Linguistic Dynamical Systems, [39] J. Ding, et al., TUOV: Triangular Unbalanced Oil Graphs of Large Girth and Cryptography, J. Math. and Vinegar. Algorithm Specifications and Sci. 140(3) (2007) 412–434. Supporting Documentation, ver. 1.0 (2023). [24] V. Ustimenko, Graphs in Terms of Algebraic https://csrc.nist.gov/csrc/media/Projects/pqc-dig- Geometry, Symbolic Compu-tations and Secure sig/documents/round-1/spec-files/TUOV-spec- Communications in Post-Quantum World, UMCS web.pdf Editorial House (2022). [25] V. Ustimenko, 2023, Schubert cells and quadratic public keys of Multivariate Cryptography, in: 3rd International Workshop on Information Technologies: Theoretical and Applied Problems, vol. 3628 (2023) 598–604. 61