=Paper=
{{Paper
|id=Vol-3896/paper11
|storemode=property
|title=Jordan-Gauss graphs and quadratic public keys of Multivariate Cryptography
|pdfUrl=https://ceur-ws.org/Vol-3896/paper11.pdf
|volume=Vol-3896
|authors=Vasyl Ustimenko,Oleksandr Pustovit
|dblpUrl=https://dblp.org/rec/conf/ittap/UstimenkoP24
}}
==Jordan-Gauss graphs and quadratic public keys of Multivariate Cryptography==
<pdf width="1500px">https://ceur-ws.org/Vol-3896/paper11.pdf</pdf>
<pre>
                                Jordan-Gauss graphs and quadratic public
                                keys of Multivariate Cryptography
                                Vasyl Ustimenko1,2,†, Oleksandr Pustovit2,∗,†
                                1
                                 Royal Holloway University of London, United Kingdom, Egham Hill, Egham TW20 0EX, United Kingdom
                                2
                                 Institute of telecommunications and global information space, NAS of Ukraine, Chokolivsky Boulevard 13, Kyiv,
                                02000, 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 such that the neighbour of each vertex is defined by
                                                the system of linear equation given in its row-echelon form. We use families of this graphs for the
                                                construction of new quadratic surjective multivariate maps F of affine spaces over K with the
                                                trapdoor accelerator T which is a piece of information which allows to compute the reimage of F in
                                                polynomial time.
                                                In particular for each quadratic automorphism F of K[x1, x2,..., xn] with the trapdoor accelerator T we
                                                construct the quadratic surjective map F’ of Kt, t=n 2+n onto K t-s, s≥0 with the trapdoor accelerator T’,
                                                T’>T.
                                                So we can introduce enveloping trapdoor accelerator for Matsumoto-Imai cryptosystem over finite
                                                fields of characteristic 2, for the Oil and Vinegar public keys over Fq or quadratic multivariate public
                                                keys defined over Jordan-Gauss graphs D(n, K),where K is arbitrary finite commutative ring with the
                                                nontrivial multiplicative group

                                                Keywords
                                                Multivariate Cryptography, Jordan – Gauss graphs, Projective Geometries, Largest Schubert Cells,
                                                Symbolic Computations 1



                                1. Introduction
                                This paper presents the generalisations of the quadratic multivariate public key given in [23]
                                and defined via special walks on projective geometries over finite fields and their natural
                                analogues defined over general commutative rings. 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 standardisation best known quantum resistant algorithms of
                                asymmetrical cryptography. The first round was finished in March 2019, essential part of

                                1
                                  ITTAP’2024: 4th International Workshop on Information Technologies: Theoretical and Applied Problems, October 23-
                                25, 2024, Ternopil, Ukraine, Opole, Poland
                                ∗
                                  Corresponding author.
                                †
                                   These authors contributed equally.
                                   Vasyl.Ustymenko@rhul.ac.uk (V. Ustimenko); sanyk_set@ukr.net (O. Pustovt)
                                    0000-0002-2138-2357 (V. Ustimenko); 0000-0002-3232-1787 (O. Pustovit)
                                             Copyright © 2024 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).




CEUR
                  ceur-ws.org
Workshop      ISSN 1613-0073
Proceedings
presented algorithms were rejected. In the same time the development of new algorithms with
postquantum perspective was continued. 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 was announced in 2022, they are developed
in terms of Lattice Theory.
    Noteworthy that 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 to 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 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):- lattice-based,- hash-based,- code-based, - supersingular elliptic curve isogeny
based.
    The standards are partially published in 2024.
    Its interesting that new obfuscation ‘’TUOV: Triangular Unbalanced Oil and Vinegar’’ were
presented                             to                        NIST                            (see
https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/TUOV-
spec-web.pdf) by principal submitter Jintaj Ding.
    Further development of Classical Multivariate Cryptography which study quadratic and
cubic endomorphisms of Fq[x1, x2,…, xn] is reflected in [14]. Current research in Postquantum
Cryptography can be found in [4], [5], [6], [7], [8], [9], [10], [11], [12]. [13], [15], [16], [17], [27],
[28], [29], [30]
    We use the concept of quadratic accelerator of the endomorphism σ of K[x1, x2,…, xn] which
is the piece of information T such that its knowledge allows us to compute the reimage of (σ, Kn)
in time O(n 2). Symbol K stands here for an arbitrary commutative ring with unity. Our
suggestion is to use for public key the pairs (σ, T) such that σ has a polynomial density, i. e.
number of monomial terms of σ(xi), i=1,2,…,n. Some examples of such public keys the reader can
find in [1], [22]
    For each pair (K, n), n>1 we present quadratic automorphism σ of K[x1, x2,…, xn] with the
trapdoor accelerator T defined via totality of special bipartite Jordan-Gauss graphs with the
partition sets isomorphic to Kn. We discuss the possible use of these transformation in the case
of finite fields and arithmetical rings Zq where q is a prime power.
    In this paper we suggest new quadratic multivariate public rules defined in terms of
Projective Geometry. Recall that multivariate public rule G has to be given in its standard form
xi →gi(x1, x2, … , xn), where polynomials gi are given via the lists of monomial terms in the
lexicographical order.
    We consider the bipartite induced subgraphs J(F) of projective geometry over the field F
which partition sets are the largest Schubert cells. The incidence of points and lines of these
graphs is given by the system of quadratic equations such that the neighbourhood of each
vertex is a solution set of the system of linear equation written in its row-echelon form.
Straightforward change of the finite field F for the general commutative ring with unity gives
the definition of cellular Schubert graph J(K) (see [23]). We use graphs J(K[x1, x2,…., xn])) for the
construction of trapdoor accelerators, which are surjective multivariate maps F of Kn onto Kn’
written in their standard form together with the piece of information T such that the knowledge
of this information allows to compute the reimage for the given value of F.
    The first cryptosystem based on such trapdoor accelerator where proposed in 2015 (see [31]),
cryptanalysis for the system is still unknown. The obfuscations of these cryptosystems was
suggested in [32]. They were seriously generalized in [23] where walks on general cellular
Schubert graphs were used.
    In this article we suggest a wide class of generalization of previously proposed trapdoor
accelerators based on Jordan-Gauss graphs. The main idea is to use algebraic temporal graphs.
Such graphs are given via the system of algebraic equations which depends on the time of the
computation.
    In the Section 2 we define cellular Schubert graphs. These Jordan-Gauss graphs will be used
in the constructions of quadratic multivariate transformations of the affine spaces together with
the corresponding trapdoor accelerators for the computation of reimages of these maps (se
Section 4).
    Section 3 is dedicated to constructions of trapdoor accelerators for the polynomial maps
defined in terms of temporal linguistic graphs, i. e. special sequences of linguistic graphs. In
general case the degree of constructed maps can be essentially higher than 2.
    Section 5 presents some methods of constructions of new trapdoor accelerators in terms of
known ones. In Section 6 we discuss the possible impact of proposed algorithms.

2. Schubert cellular graphs over the fields
    commutative ring
The missing definitions of graph-theoretical concepts which appear in this paper can be found
in [17], [18] or [19]. 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 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 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. The pair x,y, xϵP, yϵL such that x I y is called a flag of incidence structure I. Projective
geometry n-1PG(Fq) of dimension n-1 over the finite field Fq, where q is a prime power, is a totality
of proper subspaces of the vector space V=(Fq) n of nonzero dimension.
    This is the incidence system with type function t(W)=dim(W), W ϵ n-1 PG(Fq) and incidence
relation I defined by the condition W1IW2 if and only if one of these subspaces is embedded in
another one. We can select standard base e1, e2,…, en of V and identify n-1PG(Fq) with the totality of
linear codes in (Fq)n.The geometry n-1ℾ(q)= n-1PG(Fq) is a partition of subsets n-1ℾ(q) i consisting of
elements of selected type i, i=1,2, …, n-1. We assume that each element of V is presented in the
chosen base as column vector (x1, x1, … , xn). Let U stands for the unipotent subgroup of
automorphism group PGLn(Fq) consisting of lower unitriangular matrices. 5
     Let us consider orbits of the natural action of U on the projective geometry n-1PG(Fq). They
are known as large Schubert cells. Each of orbits on the set ℾm(Fq) contains exactly one
symplectic element spanned by elements ei(1), ei(2), ..., ei(m). So the number of orbits of (U, ℾm(Fq))
equals to binomial coefficient Cmn (n,m). Noteworthy that the cardinality of n-1 ℾm(Fq) is
expressed by Gaussian binomial coefficient. Unipotent subgroup U is generated by elementary
transvections xi,j(t), i<j, tϵFq. If we select i and j then elements of kind xi,j(t) form root subgroup
Ui,j, corresponding to the positive root ei-ej of root system An-1.
     Let J be a proper subset of {1, 2, …, n}=N, JS be Schubert cell containing symplectic subspace
WJ spanned by ej ϵ J, ∆(J)= { (i,j) | iϵ J, jϵN-J, i<j }. Then a subgroup U(J) generated by root
subgroups Ui,j, (i, j) ϵ ∆(J) of order qk, k= |∆(J)| acts regularly on JS. It means that we can identify
J
  S and U(J).Noteworthy that each ℾm(Fq) has a unique largest Schubert cell of size q m(n-m), it is JS
for J={n, n-1, n-2, … , n-m+1}. We denote this cell as mLS(q). We consider the bipartite graph
m,k
   In(Fq) of the restriction of I onto disjoint union mLS(Fq) and kLS(Fq). It is bipartite graph with
bidegrees qr and qs where r=|∆({n, n-1, n-2, …, n-m+1})- ∆({n, n-1, n-2, … , n-m+1}) ∩∆({n, n-1, n-2,
… , n-k+1}) | and s=|∆({n, n-1, n-2, … , n-k+1}) - ∆({n, n-1, n-2, …, n-m+1})∩ ∆({n, n-1, n-2, …, n-
k+1})|. We refer to the graph of binary relation m,kIn(Fq) as Cellular Schubert graph and denote it
as m,kCSn(Fq) graph. In particular case n=2m+1, k=m these graphs are known as Double Schubert
graphs [ 33].
     Let K be a commutative ring. We consider group U=Un(K) of lower unitriangular n times n
matrices with the entries from K. Let ∆ be the totality of all entries of (i, j), 1 ≤ i<j ≤ n, i. e. totality
of positive roots from An-1. We identify element M from Un(K) with the function f: ∆→ K such
that f(i,j)=mi,j. The restriction M|D of M on subset D of ∆ is simply f|D. For each proper nonempty
subset J of {1, 2, …, n } we define U(J) as totality of matrices M=(mi,j) from U such that (i, j) ϵ{∆-
∆(J)} implies that mi,j=0. We define incidence system n-1PG(K) as a totality of pairs (J, M), M
ϵU(J) with type function t(J, M)=|J| and incidence relation given by conditions (1J, 1M) I (2J, 2M) if
and only if one of subsets 1J and 2J is embedded in another one and 1M-2M) | ∆(1J )∩∆(2J) =1M ∙
2
  M-2M ∙ 1M. We refer to this incidence system as projective geometry scheme over commutative
ring K. If K=F is the field then n-1PG(F) coincides with n-1-dimensional projective geometry over
F, i. e. totality of proper nonzero subspaces of the vector space F n(see [21] and further references)
where the reader can find similar interpretations of Lie geometries and their Schubert cells,
their generalisations via pairs of type (irreducible root system, commutative ring K). The
concept of large and small Schubert cell in the classical case of field is presented in [34], [35].
     We introduce ℾm(K), mLS(K) and graphs m,k CS n(K) for m=1, 2, …, n-1 via simple substitution of
K instead Fq.
     We refer to disjoint union of mLS(K), m=1, 2, …, n-1 with the restriction of incidence relation I
and type function t on this set as Schubert geometry scheme of type An-1 over commutative ring
K. We refer to elements of this incidence system as linear codes of Schubert type. We can define
Schubert schemes over other Dynkin-Coxeter diagrams.
3. Linguistic graphs of type (r, s, p) and symbolic
    computations
Let K be a commutative ring. We refer to an incidence structure with a point set P=Ps,m=Km+s and
a line set L=Lr,m=Km+r as linguistic incidence structure I m(K) of type (r, s, m) if point x=(x1, x2,…,
xs, xs+1, xs+2,…, xs+m) is incident to line y=[y1, y2, …, yr, yr+1, yr+2, …, yr+m] if and only if the following
relations hold

   a1xs+1+b1yr+1=f1(x1, x2 ,..., xs, y1, y2,… , yr)

   a2xs+2+b2yr+2=f2(x1, x2, ..., xs, xs+1, y1, y2, … , yr, yr+1)

                                   ...

   amxs+m+bmyr+m=fm(x1, x2, …, xs, xs+1, …, xs+m, y1, y2, … , yr, yr+1, …, yr+m)

     where aj and bj, j=1,2, …, m are not zero divisors, and fj are multivariate polynomials with
coefficients from K. Brackets and parenthesis allow us to distinguish points from lines (see [20],
[21] and further references).
     The colour ρ(x)=ρ((x)) (ρ(y)=ρ([y])) of point (x) (line [y]) is defined as projection of an
element (x) (respectively [y]) from a free module on its initial s (relatively r) coordinates. As it
follows from the definition of linguistic incidence structure for each vertex of incidence graph
there exists the unique neighbour of a chosen colour.
     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 vertex
accordingly chosen colour as neighbourhood operator.
     On the sets P and L of points and lines of linguistic graph we define jump operators
1
 J=1Jb(p)=(b1, b2, …, bs, p1+s, p2+s, …, ps+m), where (b1, b2, …, bs)ϵKs and 2J=2Jb([l])=[b1, b2, …, br, l1+r,
l2+r, …, lr+m], where (b1, b2, …, br)ϵKr. We refer to tuple (s, r, m) as type of the linguistic graph I. If
(p1, p2, ...., ps+m) and [l1, l2, ..., lr+m] are point and line of some linguistic graph I(K) of the type (s, r,
m) over K then the values of jump operators do not depend on the choice of linguistic graph I(K).
     We refer to a linguistic graph Im(K) where K is a commutative ring with the unity as Jordan-
Gauss graph if each monomial term of fi, i=1, 2,...., m is of kind axiyj, a≠0.
     Let Li=L(fi) be the list of nonzero monomial terms of fi with coefficients equals 1.
     We refer to the triple (s, r, m) and lists Li, i=1, 2,...,m as linguistic symbolic scheme S =S(Im(K))
and say that linguistic graph Im(K) with parameters ai, bi, i=1,2,....m and polynomials fi, i=1,2,...,
m is the interpretation of S. Noteworthy that linguistic scheme does not depend on the
commutative ring K. We refer to linguistic graphs 1Im(K) and 2Im(K’) as symbolically equivalent if
S(1Im(K)) =S(2Im(K’)).
     Note that commutative rings K and K’ can be different.
    Let K be a subring of K’. We say that the interpretation of S has type (K’, K) if point sets and
line set are affine spaces over K’ but coefficients ai, bi, i=1,2,....m are elements of the
multiplicative group K* and coefficients of the polynomials fi , i=1,2,..., m are elements of K.
    We will use the case when K’=K[z1, z2, ..., zm+s] for arbitrary chosen K to define the map
from Ks+m to itself.
    Assume that graph Im(K) has parameters ai , bi and symbolic scheme S is defined by
polynomials fi. Let Im(K[ z1, z2, ..., zl]) be the interpretation of S of type (K[z1,z2,..., zl], K) given by
same parameters ai, bi and monomial terms of fi.
    Algorithm 1 (construction of endomorphisms of K[z1, z2,…, zs, zs+1,zs+2,…, zs+m] via the
sequence of linguistic graphs of type (s, r, m)).
    We select the linguistic graph Im(K) of type (s, r, m) with symbolic scheme S and graphs 1Im(K)
of type (r, s, m), 2Im(K) of type (s, r, m),..., graph 2t+1Im of type r, s, m with the symbolic schemes iS,
i=1, 2,..., 2t+1.
    We consider the graphs Im(K[z1, z2, ..., zs+m]) together with
    j
     Im(K[z1, z2,..., zm+s]) , j ≥ 1 and select the polynomial tuples
     0
      H=(0h1(z1, z2,..., zs), 0h2(z1, z2, ..., zs), ..., 0hs(z1, z2, ..., zs)),
    0
      G=( 0g1(z1, z2, ..., zs), 0g2(z1, z2, ..., zs),..., 0gr(z1, z2, ..., zs)),
       1
        H=(1h1(z1, z2,..., zs), 1h2(z1, z2, ..., zs), ..., 1hr(z1, z2, ..., zs)),
    1
      G= ( 1g1(z1, z2, ..., zs), 1g2(z1, z2, ..., zs),..., 1gs(z1, z2, ..., zs)),
    2
      H=(2h1(z1, z2,..., zs),2h2(z1, z2, ..., zs), ..., 2hs(z1, z2, ..., zs)),
    2
      G= ( 2g1(z1, z2, ..., zs), 2g2(z1, z2, ..., zs),..., 2gr(z1, z2, ..., zs)),
    ...,
    2t+1
         H=(2h1(z1, z2,..., zs),2h2(z1, z2, ..., zs), ..., 2hr(z1, z2, ..., zs)),
    2t+1
         G= ( 2tg1(z1, z2, ..., zs), 2tg2(z1, z2, ..., zs),..., 2tgs(z1, z2, ..., zs)),
       H=H2t+2=(h1(z1, z2,..., zs), h2(z1, z2, ..., zs), ..., hs(z1, z2, ..., zs)).
    Let Nb be the neighbourhood operator of Im(K[z1, z2,..., zm+s]) and jNb be the neighbourhood
operator of jIm(K[z1, z2,..., zm+s]), j=1, 2,..., 2t+1.
    Let us take a special point (z1, z2 , ..., zs, zs+1, zs+2,..., zm+s)=(z) and compute
    1
      Jb(0) ((z)) = 0(z) in the graph Im(K[z1, z2, ..., zs+m]) with b(0)= 0H,
      Nc(0) (0(z))= 0([u]) in Im(K[z1, z2, ..., zs+m]) with c(0)= 0G,
    1
      Jb(1) (0([u]))=1([z]) in the graph 1Im(K[z1, z2,..., zm+s]) with b(1)= 1H,
    1
      Nc(1) (1([z]))= 1(u)        in the graph 1Im(K[z1, z2,..., zm+s]) with c(1)= 1G,
    1
      Jb(2) ( 1(u))=2(z)       in the graph 2Im(K[z1, z2,..., zm+s]) with b(2)= 2H,
    2
      Nc(2) ( (z))= (u)
               2     2
                              in the graph 2Im(K[z1, z2,..., zm+s]) with c(2)2= 2G,
    …..
    1
      Jb(2t+1) (2t([u]))=2t+1([z]) in the graph 2t+1Im(K[z1, z2,..., zm+s]) with b(2t+1)= 2t+1H,
    1
      Nc(2t+1) (2t+1([z]))= 2t+1(u) in the graph 2t+1Im(K[z1, z2,..., zm+s]) with c(2t+1)= 2t+1G.

    Finally we compute u as 2Jb (2t+1(u)) with b=H.
    Assume that u=(h1(z1, z2,..., zs), h2(z1, z2,...,zs),..., hs(z1, z2,...., zs), gs+1(z1, z2,..., zs, zs+1, zs+2,..., zs+m),
gs+2(z1, z2,..., zs, zs+1, zs+2,..., zs+m), ..., gs+m(z1, z2,..., zs, zs+1, zs+2,..., zs+m)).
            We consider the polynomial map F of Ks+m to itself given by the following rule.
      z1 →h1(z1, z2,..., zs),
    z2 → h2(z1, z2,..., zs),
    ...,
    zs→ hs(z1, z2,...., zs),

   zs+1 → gs+1(z1, z2,..., zs, zs+1, zs+2,..., zs+m),
   zs+2 → gs+2(z1, z2,..., zs, zs+1, zs+2,..., zs+m),
   ...,
   zs+m → gs+m(x1, x2,..., xs, xs+1, xs+2,..., x s+m).

    We refer to linguistic graphs 1Im(K) and 2Im(K) of types (s, r, m) and (r, s, m) as graphs of
adjacent types. Let
    I*m(K) stands for the dual graph to Im(K) obtained via the replacement of partition sets P and
L.
    So graphs Im(K) and I*m(K) are isomorphic graphs of adjacent types.
    The transformation F is defined via the sequence of linguistic graphs of consecutively
adjacent types Im(K)=0Im(K), 1Im(K), 2Im(K), ...,2t+1Im(K) and listed above sequences of tuples iH,
i=0, 1, ..., 2t+2 and iG, i=0, 1, 2, ..., 2t+1 with coordinates from K[z1, z2, ..., zs] of length s or r.
    Proposition 1 [22] . Let z1 →h1(z1, z2,..., zs), z2 → h2(z1, z2,..., zs),..., zs→ hs(z1, z2,...., zs) be a
bijective map B from Ks onto Ks. Then transformation F=F(jIm(K), jG, iH), j=0, 1, …, 2m+1, i=0, 1, …,
2m+2 is a bijective map of Ks+m to itself.
    Proposition 2 [ 22]. Let the conditions of the Proposition 1 holds and the polynomial map B
has a trapdoor accelerator. Then the standard form G of L1FL2 where L1 and L2 are affine
transformations from AGLn(K), n=s+m has a trapdoor accelerator.
    Proof. We justify the Proposition 2 via the construction of trapdoor accelerator for G.
    Assume that condition of Proposition 1 holds. We assume that Alice and Bob share the
standard form of G. Alice poses the trapdoor accelerator T of B and the knowledge on graphs
Im(K) and tuples jG and iH.
    Alice will work with the intermediate vector u = (u1, u2,..., us+m). She selects affine
transformation L1 from AGLs+m(K) of kind
     z1 →L1(z1, z2,..., zm+s) =u1,
     z2 →L2(z1, z2,..., zm+s) =u2,
    …,
    zs+m →Ls+m(z1, z2,..., zm+s)=um+s,

     Alice computes (w1(z1, z2, ...., zm+s), w2(z1, z2, ...., zm+s),…, wm+s(z1, z2, ...., zm+s)) =w via the
substitution of written above expressions for ui into F(u1, u2, …um+s). She selects another affine
transformation L2 from AGLm+s(K) and compute L2(w)=(g1(z1, z2,..., zm+s), g2(z1, z2,..., zm+s), ..., gm+s(z1,
z2,..., zm+s)). Alice announces publicly the standard form of the map G: zi →gi, i=1, 2,..., m+s.
     The trapdoor accelerator T for G consists of graphs Im(K) of type (s, r, m) , linguistic graphs
j
 Im(K), tuples iH , i=0, 1,..., 2t+2 and iG, i=0, 1,..., 2t+1 with coordinates from K[z1, z2,..., zs] and affine
transformations Li, i=1, 2.
     Assume that Alice gets the value c =(c1 , c2 , ..., cm+s ) of G(p1 , p2 , ..., pm+s ). She computes (L2)-
1
  (c)=1c=(1c1 , 1c2 , ..., 1cm+s). Alice works with the equations

   h1(u1, u2,..., us)= 1c1,
   h2(u1, u2,..., us)= 2c1,
   …,
      hs(u1, u2,..., us)= sc1,
      She is getting the solution ui=ti, i=1, 2,...,s from Ks. Let (11, t2, …, ts)=(t).

  She computes tuples 2t+1G(t1, t2,..., ts)=a(2t+1), H2t+1(t1, t2,..., ts)=b(2t+1), 2tG(t1, t2,..., ts)=a(2t),
H (t1, t2,..., ts)=b(2t), ..., G0(t1, t2,..., ts)=a(0), H0(t1, t2,..., ts)=b(0).
 2t



    Alice works with the sequence of graphs jIm(K), ,j=2t+1, 2t,..., 1, 0.
    She computes 2Ja(2t+1)(c )=2t+1c and treat it as vertex of the graph 2t+1Im(K) Then Alice computes
the neighbours Nb(2t+1)(2t+1c)=2t+1b of this vertex in 2t+1Im(K) and treat it as a vertex of graph 2t
Im(K). So, she computes the 2Ja(2t)(2t+1b)=2tc. Then Alice computes the neighbour Nb(2t)(2tc)=2tb in
the graph 2t Im(K). She continue this process.
    Finally Alice gets Ja(1)( 2b)=1c and Nb(1)(1c)=1b together with Ja(0)(1b)=0c and Nb(0)( 0c)=0b.
    So she gets (u*) as 1J(t)( 0b)=(t1, t2, ..., ts, us+1, us+2,..., us+m).
    Alice computes the plaintext (p) as (L1)-1(u*).
    Remark. We can substitute elements L1 and L2 by surjective affine map L’1 of affine space
Kn’ onto Kn, n’>n and surjective map L’2 of affine space Km onto Km’, m≥m’ and get surjective map
L’1 F L’2 of affine space Kn’ onto Km’.

   1) Algorithm 2.
     Let us assume that s>r. We select the linguistic graph Im(K) of type (s, r, m) with symbolic
scheme S and graphs 1Im(K) of type (r, s, m), 2Im(K) of type (s, r, m),..., graph 2tIm of type r, s, m
with the symbolic schemes iS, i=1, 2,..., 2t. Similarly to algorithm 1 we consider the graphs
Im(K[z1, z2, ..., zs+m]) together with
   j
    Im(K[z1, z2,..., zm+s]) , j ≥ 1 and select the polynomial tuples
    0
     H=(0h1(z1, z2,..., zs), 0h2(z1, z2, ..., zs), ..., 0hs(z1, z2, ..., zs)),
   0
     G=( 0g1(z1, z2, ..., zs), 0g2(z1, z2, ..., zs),..., 0gr(z1, z2, ..., zs)),
      1
       H=(1h1(z1, z2,..., zs), 1h2(z1, z2, ..., zs), ..., 1hr(z1, z2, ..., zs)),
   1
     G= ( 1g1(z1, z2, ..., zs), 1g2(z1, z2, ..., zs),..., 1gs(z1, z2, ..., zs)),
   2
     H=(2h1(z1, z2,..., zs),2h2(z1, z2, ..., zs), ..., 2hs(z1, z2, ..., zs)),
   2
     G= ( 2g1(z1, z2, ..., zs), 2g2(z1, z2, ..., zs),..., 2gr(z1, z2, ..., zs)),
   ...,
   2t
      H=(2h1(z1, z2,..., zs),2h2(z1, z2, ..., zs), ..., 2hs(z1, z2, ..., zs)),
   2t
      G= ( 2tg1(z1, z2, ..., zs), 2tg2(z1, z2, ..., zs),..., 2tgr(z1, z2, ..., zs)),
   H=H2t+1=(h1(z1, z2,..., zs), h2(z1, z2, ..., zs), ..., hr(z1, z2, ..., zs)).

      As in the algorithm 1 we take a special point (z1, z2 , ..., zs, zs+1, zs+2,..., zm+s)=(z) and compute
      1
       Jb(0) ((z)) = 0(z) in the graph Im(K[z1, z2, ..., zs+m]) with b(0)= 0H,
       Nc(0) (0(z))= 0([u]) in Im(K[z1, z2, ..., zs+m]) with c(0)= 0G,
      1
       Jb(1) (0([u]))=1([z]) in the graph 1Im(K[z1, z2,..., zm+s]) with b(1)= 1H,
      1
       Nc(1) (1([z]))= 1(u)       in the graph 1Im(K[z1, z2,..., zm+s]) with c(1)= 1G,
      1
       Jb(2) ( 1(u))=2(z)      in the graph 2Im(K[z1, z2,..., zm+s]) with b(2)= 2H,
      2
       Nc(2) ( (z))= (u)
                2     2
                               in the graph 2Im(K[z1, z2,..., zm+s]) with c(2)2= 2G,
      …..
      1
       Jb(2t) (2t-1([u]))=2t([z]) in the graph 2tIm(K[z1, z2,..., zm+s]) with b(2t)= 2tH,
    1
     Nc(2t) (2t([z]))= 2t(u)       in the graph 2tIm(K[z1, z2,..., zm+s]) with c(2t)= 2tG.

    Finally we compute u as 2Jb (2t(u)) with b=H.
    Assume that u=(h1(z1, z2,..., zs), h2(z1, z2,...,zs),..., hr(z1, z2,...., zs), gs+1(z1, z2,..., zs, zs+1, zs+2,..., zs+m),
gs+2(z1, z2,..., zs, zs+1, zs+2,..., zs+m), ..., gs+m(z1, z2,..., zs, zs+1, zs+2,..., zs+m)).

    We consider the polynomial map F of Ks+m to Kr+m itself given by the following rule
    (z1, z2,..., zs, zs+1, zs+2,..., zs+m)→(h1(z1, z2,..., zs), h2(z1, z2,..., zs),..., hs(z1, z2,...., zr), gs+1(z1, z2,..., zs,
zs+1, zs+2,..., zs+m),
     gs+2(z1, z2,..., zs, zs+1, zs+2,..., zs+m), ..., gs+m(x1, x2,..., xs, xs+1, xs+2,..., x s+m).
    The transformation F is defined via the sequence of linguistic graphs
    of consecutively adjacent types Im(K)=0Im(K), 1Im(K), 2Im(K), ...,2tIm(K) and listed above
sequences of tuples iH, i=0, 1, ..., 2t+1 and iG, i=0, 1, 2, ..., 2t with coordinates from K[z1, z2, ..., zs]
of length s or r.
    Proposition 3 [22]. Let ( z1 , z2, …, zs)→( h1(z1, z2,..., zs), h2(z1, z2,..., zs),..., hr(z1, z2,...., zs) be a
surjective map B from Ks onto Kr. Then transformation F=F(jIm(K), jG, iH), j=0, 1, …, 2m+1, i=0, 1,
…, 2m+2 is a surjective map of Ks+m to Kr+m .
    Proposition 4 [22]. Let the conditions of the Proposition 1.1 holds and the polynomial map
B has a trapdoor accelerator.
    Assume that L’1 and L’2 are surjective affine maps of affine space Kn’ onto Kn, n’>n and
affine space Km onto Km’, m≥m’ respectively . Then polynomial surjective map L’1 F L’2 of affine
space Kn’ onto Km’ also has a trapdoor accelerator.
    Below we present a modification of Algorithm 1.

    Let Im(K) be a linguistic graph of type (s, r, m). We
    define its digraph cover D(Im(K)) as the following directed graph.
    The set of vertexes of D(Im(K)) is subdivided into two blocks.
    3The first one PLm(K) is the totality of ordered flags of kind ((p) , [l]) of the incidence
structure Im(K) where (p)=(p1, p2,..., ps, ps+1,..., ps+2,..., ps+m), [l]=[l1, l2,..., lr, lr+1, lr+2,..., lr+m] such that
(p)I[l] and the totality
    LPm (K) of ordered flags of kind [[l], p] and binary relation ψ which is defined via the
conditions
     ((p), [l])ψ[[l’], (p’)] if [l]=[l’] and (p)≠(p’), [[l],(p)]ψ((p’), [l])) if
    (p)=(p’), [l] ≠[l’].

    We refer to pair of tuples <(p1, p2,..., ps), [l1, l2, ..., lr]> of ((p), [l]) from PLm(K) as the colour of
the flag. We say that (p1,p2,…,ps) and [l1,l2,…,ls] are internal and external colours of the flag ((p),
[l]). The information on the flag can be given by the tuple (p1, p2, ..., ps, ps+1 , ps+2,..., ps+m, l1, l2, ..., lr).
Dual presentation of ((p), [l]) is (p1, p2,…, ps, l1, lr+2,…, lr+m, l1, l2,…, lr)* given via the coordinates of
line.
    Similarly we say that [l1, l2,...,lr] and (p1,p2,…,ps) are internal and external colours of [[l],(p)].
The information on this flag can be given by the tuple [l1,l2,..., lr, lr+1, lr+2,..., lr+m, p1, p2,..., ps] or dual
presentation [l1,l2,..., lr, ps+1, ps+2,..., ps+m, p1, p2,..., ps]*.
    We introduce operator of change the colour 1JCa, a=(p’1, p’2,..., p’s, l’1, l’2,..., l’r) [(p), [l])]= (p1’,
p’2, ..., p’s, ps+1, ps+2,..., ps+m, l’1, l’2,..., l’r) acting on PLm(K) and operator 2JCa , a=(l1’, l’2,...., l’r, p’1,
p’2,..., p’s), 2JCa([[l],(p)]) [l’1, l’2,..., l’r, lr+1 ,lr+2, ..., lr+m, p’1, p’2 ,...p’s] acting on the set LPm(K).

    Algorithm 3.

    Alice takes the sequence of graphs D(Im(K)), D( lIm(K)), l=1,2,…,t. She will work with the
multivariate ring K’=K[z1, z2,…, zs, zs+1, zs+2,…, zs+m, z1s+m+1, zs+m+2, …, zs+m+r ] and graphs
D(Im(K’)),D( lIm (K’)).
    Alice selects the tuple 0H=(h1, h2,…, hs, g1, g2,…, gr) , H’=(h’1, h’2,…, h’s, g’1, g’2,…, g’r) and
i
 H=(ih1, ih2,…, ihs, ig1, ig2,…, igr) from (K’)s+r . She takes the flag (z)=( z1, z2,…, zs, zs+1, zs+2,…, zs+m,
zs+m+1, zs+m+2, …, zs+m+r ) of Im(K’).
    Assume that for ((p),[ l]) from j PL(Im(K’)), j=1.2,…,t-1 symbol ((p),[ l])*
    means ([l], (p)) from j+1PL(Im(K’)). If ((p),[ l]) is a flag from tPL(Im(K’)) then ((p),[ l])* is ([l], (p))
from t-1PL(Im(K’)).
    Alice uses operator 1Ja, a= 0H and computes 1z =1Ja(z)=( h1, h2,…, hs, z s+1, zs+2,…, zs+m, g1, g2,…
gr) in the graph D(Im(K)). She computes (1u)=(1z)*= [ g1, g2,… gr, z’ s+1, z’s+2,…, zs’+m, h1, h2,…, hs] of
the graph 1Im (K’) where [ g1, g2,… gr, z’ s+1, z’s+2,…, zs’+m] is the neighbour of ( h1, h2,…, hs, z s+1,)
zs+2,…, zs+m) in Im(K’).
    2Next Alice uses 1Ja(1), a(1)= 1H and computes 1Ja(1)(1u)= 2z in the graph 1Im (K’) and
( u)=( 2z)* from 2Im (K’).
  2

    She continue this procedure and constructs (iu), i=3.4,…, t. Alice takes (tu) from tIm (K’)
    and uses 2Jb, b= H’ for the computation of u=1J(tu) of kind ( h’1, h’2,…, h’s, v1, v2, …, vm, g’1,
g’2,…, g’r) or (g’1, g’2,…, g’r, v1, v2, …, vm, h’1, h’2, …, h’s) dependently on t mod 2.
    She uses the following map G= G=G(jIm(K), iH, H’), i=0,1,…,t as the output of the algorithm.
    z1→h’1(z1, z2,…, zs, zs+m+1, zs+m+2, …, zs+m+r),
    z2→h’2(z1, z2,…, zs, zs+m+1, zs+m+2, …, zs+m+r),
    …
    zs→h’s(z1, z2,…, zs, zs+m+1, zs+m+2, …, zs+m+r),
    zs+1→v1(z1, z2,…, zs, zs+1, zs+2,…, zs+m, zs+m+1, zs+m+2, …, zs+m+r),
    zs+2→ v2(z1, z2,…, zs, zs+1, zs+2,…, zs+m, zs+m+1, zs+m+2, …, zs+m+r),
    …,
    zs+m→vm(z1, z2,…, zs, zs+1, zs+2,…, zs+m, zs+m+1, zs+m+2, …, zs+m+r),
    z1+s+m→g’1(z1, z2,…, zs zs+m+1, zs+m+2, …, zs+m+r),
    z2+s+m→g’2(z1, z2,…, zs, zs+m+1, zs+m+2, …, zs+m+r),
    …
    zr+s+m→g’r(z1, z2,…, zs,, zs+m+1, zs+m+2, …, zs+m+r).

    Proposition 5 [22]. Let z1 →h’1(z1, z2,..., zs zs+m+1, zs+m+2, …, zs+m+r), z2 → h’2(z1, z2,..., zs , zs+m+1,
zs+m+2, …, zs+m+r),..., zs→ h’s,(z1, z2mzs, zs+m+1, zs+m+2, …, zs+m+r), z1+s+m→g’1(z1, z2,…, zs zs+m+1, zs+m+2, …,
zs+m+r), z2+s+m→g’2(z1, z2,…, zs zs+m+1, zs+m+2, …, zs+m+r), …, ), zr+s+m→g’r(z1, z2,…, zs , zs+m+1, zs+m+2, …,
zs+m+r)
    be a bijective map B from Ks+r onto Ks+r. Then transformation G=G(jIm(K), iH, H’), j=0, 1, …, t is
a bijective map of Ks+r+m to itself.
   Proposition 6 [22]. Let the conditions of the Proposition 3 holds and the polynomial map B
has a trapdoor accelerator. Then the standard form F of L1GL2 where L1 and L2 are affine
transformations from AGLn(K), n=s+r+m has a trapdoor accelerator.
   The justification of this statement can be obtained via the modification of the procedure in
the proof of Proposition 2.

4. On the examples of Schubert cellular graphs, their
     symplectic quotients and cryptographic algorithms
Let us consider graphs m,m-1CS m+k-1(F) over the field F which are induced subgraphs of projective
geometry PGm+k-1(F) with vertices from the largest Schubert cells on the totalities of
m=dimensional and m-1 dimensional subspaces of the vector space Fm+k. They can be defined as
totalities of points (x)=(x1, x2,…,xk, x1,1, x1,2,….,x k,m-1 ) and lines [y]=[y1, y2,…,ym-1, x1,1, x1,2,….,x k,m-1]
from F k(m-1)+kand F k(m-1)+m-1 where indexes of coordinates of kind i,j for` i=1,2,…,k and j=1,2,…,
m-1 are 1ordered lexicographically and the point (x) is incident to the line [y] if and only if the
conditions for each pair i,j.
    Thesymbolic type S of this graph is the triple (k, m-1, k(m-1)) and the list of Li,j={xi yj} ordered
lexicographically. Let K be commutative ring with the unity then graph m,m-1CS m+k-1(K) is defined
via the change of F for K.
    Let Ik(m-1)(K) be the Jordan-Gauss graph over K symbolically equivalent to m,m-1CS m+k-1(K) then
corresponding equations are ai,jxi,j- bijyi,j= ci,jxiyj where ai,j and bij are elements of multiplicative
group K* and ci,j are elements from K-{0}.
    We can see that arbitrary nonempty subset M of {(11),(1,2),…, (m-1, m-1)} is define the
symplectic quotient IM of Ik(m-1)(K).
    Other special case of cellular Schubert graph is m,1CSm(F) of type (m-1, m-1, 1) when we have
points and lines of kind (x1, x2,…, xm) and [y1, y2, …., ym] and equation xm-ym=x1y1 +x2y2+…
+xm-1ym-1. Symbolically equivalent to m,1CSm(F) will be Jordan-Gauss graph of type (m-1, m-1, 1)
with the incidence given by an equation of kind axm-bym=c1x1y1 +c2x2y2+…+cm-1xm-1ym-1 with a and
b from the multiplicative group K* and ci from K-{0}.
    Let us consider special homomorphisms of linguistic graphs and corresponding semigroups.
Let I(K) be linguistic graph over commutative ring K defined in section and M = {m(1), m(2),…,
m(d)} be a subset of {1, 2, …, m} (set of indexes for equations). Assume that equations indexed by
elements from M of the following kind

    am(1)+s xm(1) -bm(1)ym(1)+r=fm(1)(x1, x2 , …, xs ,y1, y2, … , yr)

    am(2)xm(2)+s -bm(2)ym(2)+r= fm(2)(x1, x2, … ,xs,xm(1)+s,y1, y2, … , yr,, ym(1)+r)
    )…
    am(d)xm(d)+s -bm(d)ym(d)+r =fm(d) (x1, x2, … , xs,, ,xm(1)+s, xm(2)+s,… , xm (d-1)+s, y1, y2, … , yr,, ym(1)+r, ym(2)+r,,… , ym (d-1)+r)
define other linguistic incidence structure IM..
    Then the natural projections δ1,: (x)→(x1, x2, … , xs,, xm(1)+s, xm(2)+s,… , xm(d)+s) and δ2: [y]→[y1, y2, … ,
yr, ym(1)+r,ym(2)+r,… , y m(d)+r] of free modules define the natural homomorphism δ of incidence
structure I onto I’=IM.. We will use the same symbol ρ for the colouring of linguistic graph IM..
    It is clear, that δ is colour preserving homomorphism of incidence structures (bipartite
graphs). We refer to δ as symplectic homomorphism and graph IM as symplectic quotient of
linguistic graph I. In the case of linguistic graphs defined by infinite number of equations we
may consider symplectic quotients defined by infinite subset M (see [22] where symplectic
homomorphism was used for the cryptosystem construction).
    As it follows from the definition the symplectic quotient of Jordan-Gauss graph is also
Jordan-Gauss graph.
    For each linguistic graph I and M={1, 2,…,d}, d<m there is the symplectic quotient IM.
    Let us consider graphs m,m-1CS m+k-1(F) over the field F which are induced subgraphs of
projective geometry PGm+k-1(F) with vertices from the largest Schubert cells on the totalities of
m=dimensional and m-1 dimensional subspaces of the vector space Fm+k. They can be defined as
totalities of points (x)=(x1, x2,…,xk, x1,1, x1,2,….,x k,m-1 ) and lines [y]=[y1, y2,…,ym-1, x1,1, x1,2,….,x k,m-1]
from F k(m-1)+kand F k(m-1)+m-1 where indexes of coordinates of kind i,j for` i=1,2,…,k and j=1,2,…,
m-1 are 1ordered lexicographically and the point (x) is incident to the line [y] if and only if the
conditions for each pair i,j. The symbolic type S of this graph is the triple (k, m-1, k(m-1)) and the
list of Li,j={xi yj} ordered lexicographically. Let K be commutative ring with the unity then graph
m,m-1
     CS m+k-1(K) is defined via the change of F for K.
    Let Ik(m-1)(K) be the Jordan-Gauss graph over K symbolically equivalent to m,m-1CS m+k-1(K) then
corresponding equations are ai,jxi,j- bijyi,j= ci,jxiyj where ai,j and bij are elements of multiplicative
group K* and ci,j are elements from K-{0}.
    We can see that arbitrary nonempty subset M of {(11),(1,2),…, (m-1, m-1)} is define the
symplectic quotient IM of Ik(m-1)(K).
    Let us consider trapdoor accelerators defined in terms of cellular Schubert graphs.
    We introduce the degree of the tuple from K[z1, z2, ...., zp], p>1 as maximal degree of its
coordinates as multivariate polynomials.
    Proposition 7 [22]. Let the condition of Proposition 1 holds, graph jIm(K), j=0,1, …, 2t +1 are
symbolically equivalent to l,kCSn(K) or its dual graph and deg(jH)+deg(jG)≤2, j=1,2,…, 2t+1,
deg(H)=2. Then transformation G=F(jIm(K)j, jG, iH), j=0, 1, …, 2t+1, i=0, 1, …, 2m+2 is a bijective
quadratic map of Ks+m to itself.
    So under the conditions of Proposition 7 the construction of Proposition 2 is a bijective
quadratic transformations with the trapdoor accelerator.
    Proposition 8 [22]. Let the condition of Proposition 3 holds, graph jIm(K), j=0,1, …, 2t are
symbolically equivalent to l,kCSn(K) or its dual graph and deg(jH)+deg(jG)≤2, j=1,2,…, 2t,
deg(H’)=2. Then transformation G=F(jIm(K), jG, iH), j=0, 1, …, 2t, i=0, 1, …, 2m+1 is a surjective
quadratic map of Ks+m to Kr+m itself.
    So under the conditions of Proposition 8 the construction of Proposition 4 is a surjective
quadratic transformations with the trapdoor accelerator.
    Proposition 9 [22]. Let the condition of Proposition 7 holds, graph jIm(K), j=0,1, …, t are
symbolically equivalent to l,kCSn(K) or its dual graph and deg(jh1, jh2, ,,,, jhs)+deg( jg1, jg2, ,,,, jgr)≤2,
j=0,1,2,…, t, and deg (H’)=2. Then the transformation G=G(jIm(K)j, iH, H’), j=0, 1, …, t is a bijective
quadratic map of Ks+r+m to itself.
    So under the conditions of Proposition 9 the construction of Proposition 6 is a bijective
quadratic transformations with the trapdoor accelerator.
    Remark. We can substitute graphs jIm(K) of the propositions 7, 8 and 9 for the nontrivial
symplectic quotients of these Jordan-Gauss graphs.
5. On the extensions of known trapdoor accelerators
Let us discuss Algorithm 1 in the case when the conditions of Proposition 2 and Proposition 7
hold. So graph jIm(K), j=0,1, …, 2t +1 are symbolically equivalent to l,kCSn(K) or its dual graph and
deg(jH)+deg(jG)≤2, j=1,2,…, 2t+1, and deg(H)=2 and the transformation B has a trapdoor
accelerator T. We suggest the following two options for the construction of the pair (B, T).

    1.We take the triangular transformation Q:x1→a1x1+b1, x2→a2x2+f2(x1), x3→a3x3+f3(x1, x2),…,
xs→ asxs+fs(x1, x2,…,xs-1) where ai, i=1, 2,…, s are elements from K* and deg fi=2, i=2,3,…,s together
with two elements D1wn and D2 from AGLs(K) and define B as D1QD2.
    So the standard form of B and the decomposition of B into D1QD2 will be used as a trapdoor
accelerator.
    2. In [1] authors constructed multivariate quadratic cryptosystem based on Jordan-Gauss
graphs D(s, K), s>4 of type (1, 1, s). Corresponding trapdoor accelerator is a standard form of
automorphism of K[z1, z2,…, zs] and trapdoor accelerator which provides1 the knowledge on the
graph D(s,K) and the tuple of ring elements of length O(n2). We may assume that the knowledge
on the graph is publicly known.
    3. We can use the procedure of Algorithm 1 under the conditions of Proposition 2 and
Proposition 7 in the case of graph s,kCSs, k<s for the construction of B. Alice can select the tuples
0
 H, 0 G, 1 H, 1G,…, 2t+1H, 2t+1G and can choose 2t+1H which defines the transformation from AGLk-
s(K). This way she obtains the quadric bijective transformation F and construct B as the map
D1FD2 , D1 , D2 ϵAGLs(K) on the affine space Ks.
    In the case of finite fields of characteristic 2 Alice can use quadratic automorphism of Fq[z1,
z2,…, zs] from Matsumoto-Imai Cryptosystem. In the case of general finite field Fq she can use
bijective encryption map of Oil and Vinegar public key or use other transformations with the
trapdoor accelerators from known suggested multivariate schemes.
    Remark. The simplest choice of linear transformation B is not appropriate for the
construction of multivariate public key. Accordingly [22] the choice of B as the element from
AGLs(K) insures the fact that the inverse map for F is also quadratic transformation. So the
linearization attack will allow to construct inverse transformation in a polynomial time.
    Example 1.
    Let us assume that the graph Im(K) of the Algorithm 1 is r,r-1CSk+r-1 and the conditions of
Proposition 7 hold.
    The type of this Jordan-Gauss graph is (k, r-1, m) where m=k(r-1). Let us assume that k=O(n)
and r=O(n). So m=O(n2),
    The interpretation of each graph from the sequence requires 2k(r-1) elements of K* and (r-1)
elements from K-{0}.
    So Alice has to select the parameter t and form the tuple from (K*)2(2t+2)k(r-1) and the tuple from
(K-{0})(2t+2)k(r-1) .
    Let us assume A that k≥ r-1. She has to form the colours of the point and line as the tuples of
length k and r-1 with coordinates from K[z1, z2 ,…., zk] of degree 2, 1 and 0. In the entscase of the
colour of the point of degree 2 Alice has to choose ((k(k-1)/2+k+1)k coefficients from K.
Roughly the number of parameters is (1/2)k3. In the case of degree 1 or 0 the numbers will be
(k+1)k and k respectively.
    In the case of line we get (k(k-1)/2+k+1)(r-1), (k+1)(r-1) and r. Assume that the parameter t has
size O(n).
    The construction of the chain 0H, 0G, 1H, 1G,… requires O)(n4) parameters. The trapdoor
accelerator T can be thought as the sequence of O(n4) elements of the commutative ring. Alice
has to keep it safely as her private key.
    Recall that the dimension of the space of plaintexts is d=k+k(r-1). It means that the trapdoor
accelerator is a tuple of length O(d2).
    The symbolic type of the graph can be given publicly.
    The cost of the computation of the neighbor of vertex in the graph is O(d). The computation
of the walk with jumps of length O(n) costs O(d3/2) and application of the element from AGLd(K)
costs O(d2).
    Thus the complexity of private decryption procedure is O(d2).

   The obfuscation of the algorithm.


   a) Let us take permutations 0π, 1π, 2π, , …, 2π
    on the set {1, 2,…,k} and 0µ, 1µ, 2µ, …, 2t+1µ on the set {1, 2,…, m-1} and change the incidence
equations of lIm(K), l=1, 2, …, 2t+1for lai,jxi,j -lbi,jyi,j = lci,jxi’ yj’ where ‘i=1π(i), j’=lµ(j) and get the new
graphs lI’m(K).
   It is easy to see that graphs lI’m(K) and lIm(K) have different symbolic type but they are
isomorphic incidence structures.
   We can change graphs lIm(K) for l’Im(K) and construct the new quadratic transformation F’
with the trapdoor accelerator.
   b) We can select a nontrivial subset M of the Cartesian product of {1, 2,…,k} and {1,2….,m-1}
and consider a symplectic quotient IM(K) instead of Im(K) in the Proposition 5 The degree of a
new transformation F’ will be the same. The information on the choice of a subset M can be
treated as part of the trapdoor accelerator. So the graph IM(K) will be unknown to public.

    Example 2.
    Let us assume that the graph Im(K) of the Algorithm 2 is r,r-1CSk+r-1 and the conditions of
Proposition 6 hold. We assume that k ≥r-1.
    In this case Alice also has a wide choice of options to create appropriate transformation B‘
from Ks to Kr.
    For instance she can use bijective transformations B on Ks in the presented above schemes 1
and 2. Alice takes affine map D from AGLs(K) and surjective affine map D3 from Ks onto Kr and
forms B’=BD3.
    In the case of finite fields K=Fq we can use for the construction of B recently developed
scheme TUOV.
    In the case of the field of characteristic 2 Alice can use B of kind (z1, z2,…., zk)→(l1(z1, z2,…,
zk)2+b1, l2(z1, z2,…, zk)2+b2,…, lr-1(z1, z2,…, zk)2+br-1) where (z1, z2,…., zk)→(l1(z1, z2,…, zk), l2(z1, z2,…,
zk),…, lr-1(z1, z2,…, zk)) is a linear map of rank r-1.
    She can use (z1, z2,…., zk)→(l1(z12, z22,…., zk2)+b1, l2(z12, z22,…, zk2) +b2,…, lr-1(z12, z22,…, zk2)+br-1)
alternatively.
   Alice will use the same graph Im(K)= r, r-1CSk+r-1 of the Algorithm 1 but under the conditions
of Proposition 6.
   She will select that k=O(n) and r=O(n). So m=O(n2). Recall that the interpretation, of each
graph from the sequence requires 2k(r-1) elements of K* and k(r-1) elements from K-{0}.
   Alice selects symbolically equivalent to r, r-1CSk+r-1 graphs jIm(K), m=k(r-1), j=0,1, …, 2t and
symbolic colours

    0
     H=(0h1(z1, z2,..., zk), 0h2(z1, z2, ..., zk), ..., 0hs(z1, z2, ..., zk)), 0G=( 0g1(z1, z2, ..., zk), 0g2(z1, z2, ..., zk),...,
0
 gr-1(z1, z2, ..., zk)),
       1
        H=(1h1(z1, z2,..., zk), 1h2(z1, z2, ..., zk), ..., 1hr-1(z1, z2, ..., zk)), 1G= ( 1g1(z1, z2, ..., zk), 1g2(z1, z2, ...,
zk),..., 1gk(z1, z2, ..., zk)),
    2
     H=(2h1(z1, z2,..., zk),2h2(z1, z2, ..., zk), ..., 2hk(z1, z2, ..., zk)),2G= ( 2g1(z1, z2, ..., zk), 2g2(z1, z2, ..., zk),...,
2
 gr-1(z1, z2, ..., zk)),
    ...,
    2t
      H=(2h1(z1, z2,..., zk),2h2(z1, z2, ..., zk), ..., 2hk(z1, z2, ..., zk)),2tG= ( 2tg1(z1, z2, ..., zk), 2tg2(z1, z2, ...,
zk),..., 2tgr-1(z1, z2, ..., zk)),

   Alice chooses the tuple H==(h1(z1, z2,..., zk),h2(z1, z2, ..., zk), ..., hr-1(z1, z2, ..., zk)). Recall that
B(z)=H.

    She follows to Algorithm 2 and creates the polynomial map F of Ks+m to Kr+m-1 itself given by
the following rule
    (z1, z2,..., zk, zk+1, zk+2,..., zk+m)→(h1(z1, z2,..., zk), h2(z1, z2,..., zk),..., hr-1(z1, z2,...., zk), gr(z1, z2,..., zk,
zk+1, zk+2,..., zk+m),
     gr+1(z1, z2,..., zk, zk+1, zk+2,..., zk+m), ..., gr+m-1(x1, x2,..., xk, xs+1, xs+2,..., xk+m)).

   Alice forms L’1 and L’2 of the Proposition 2.1 which are surjective affine maps of affine
space Kn’ onto Kn, n’>n=k+m and the affine space Km+r-1 onto Km’, m+r-1≥m’ respectively. Then
she computes the standard form G of polynomial surjective map L’1 F L’2 of affine space Kn’ onto
Km’ and sends it to Bob.

    Assume that Alice and Bob gets the hash value (c1, c2, …., cm’).

   Alice creates the intermediate tuple of variables u=(u1, u2,…ur-1, ur, ur+1, …, ur+m-1) and writes
the system of linear equations L’2 (u)=c. So she gets the solution *u=(*u1, *u2,…, *ur-1 , *ur, *ur+1,
…, *ur+m-1) and considers the quadratic equations B(z1, z2,..., zk)=*u =(*u1, *u2,…, *ur-1). The
knowledge on the trapdoor accelerator of B allows Alice to get a solution z*=(*z1, *z2,…, *zk).

   So Alice computes 2tG= ( 2tg1(*z1, *z2, ..., *zk), 2tg2(*z1, *z2, ...,* zk),...,                         2t
                                                                                                              gr-1(*z1, *z2, ...,
*zk))=b(2t),
   2t
     H=(2h1(*z1, *z2,..., *zk),2h2(*z1, *z2, ..., *zk), ..., 2hk(*z1, *z2, ..., *zk))=a(2t),…,
   2
    G= ( 2g1(*z1,* z2, ..., *zk), 2g2(*z1, *z2, ..., *zk),..., 2gr-1(*z1,*z2, ..., *zk))=b(2),

    2
     H=(2h1(*z1, *z2,..., *zk),2h2(*z1,* z2, ..., *zk), ..., 2hk(*z1,* z2, ...,* zk))=a(2),
   1
    G= ( 1g1(*z1, *z2, ..., *zk), 1g2(*z1,*z2, ..., *zk),..., 1gk(*z1,* z2, ..., *zk))=b(1),

   1
    H=(1h1(*z1, *z2,..., *zk), 1h2(*z1, *z2, ..., *zk), ..., 1hr-1(*z1, *z2, ..., *zk))=a(1),
   -
   0
    G=( 0g1(*z1, *z2, ..., *zk), 0g2(*z1, *z2, ..., *zk),..., 0gr-1(*z1, *z2, ..., *zk))=b(0),

   0
    H=(0h1(*z1, *z2,..., *zk), 0h2(*z1, *z2, ..., *zk), ..., 0hk(*z1, *z2, ..., *zk)))=a(0).


   Alice considers the graph 2tIm(K) with the line *u and computes 2Jb(2t)(*u)=u2t. She
   takes the point Na(2t)(u2t)=v2t.
   Alice treats v2t as the line of the graph 2t-1Im(K) and computes 2Jb(2t-1)=u2t-1. Alice forms the
vertex
    Na(2t-1)=v2t-1 of graph 2t-1Im(K).
   She treats v2t-1 as vertex of 2t-2Im(K) and computes 2Jb(2t-2)=u2t-2.
   Alice takes the neighbour Na(2t-2)(u2t-2)=v2t-2.
   She continues this process.

   Alice takes the vertex v1 of the graph 1Im (K). She treat it as the line of the graph 0Im(K).
   Alice computes 2Jb(0)((v1)=u0.
   She computes Na(0)(u0)=v0 .
   Finally Alice computes v=1Jz*(v0).

   So she gets v=(v1, v2,…., vk, vk+1, vk+2,…,vk+m).

   Alice writes the system of linear equations

   L’1(y1, y2, …., yn’)=v and gets the solution *y= (*y1, *y2, …., *yn’).

   She sends *y to Bob. He checks that G(*y)=c.



6. Conclusion

6.1. Some remarks
Below we present some heuristic arguments supporting the conjecture that the complexity to
find the reimage of quadratic map of algorithms 1 and 2 without the knowledge of described
trapdoor accelerator is nonpolynomial.
   Let us consider the case when Alice does not use endomorphisms L1 and L2 of degree 1.
   Assume that she use only one cellular Schubert graphs s,kCSm(K) with the operator of
changing colour and the operator to compute the neighbour of chosen vertex. We can consider
the graph ψ of the binary relation “ colours of vertexes x and y of different type can be changed
to make recoloured vertexes adjacent in s,kCSm(K). Then input x and output y vertexes of
algorithm 1 or 2 will be connected by the walk in ∙ψ. Dijkstra algorithm will allow us to find the
walk between x and y and recover the reimage of y in time vln (v) where v is the order of graph.
   Let d , d>3 be the order of finite commutative ring K and n be the maximal dimension of the
space of the partition sets of ψ. Then v>dn and the complexity of Dijkstra algorithm of finding
the path between the input and the output of the algorithm is exponential one. We can expect
that with the temporal graph defined via the sequence of Jordan-Gauss graphs j Im(K), j=0, 1, 2,…
the complexity of finding the path will be higher.
   Temporal Jordan-Gauss graphs can be used for the constructions of new platforms of
Noncommutative Cryptography (see [36], [37], [38], [39], [40], [41], [42] and new cryptanalytic
results [43],[ 44], [45], [46], [47], [48], [49]). These platforms are special semigroups or groups of
degree bounded by constant (2 or 3) of the Cremona semigroup of all endomorphisms of K[x1,
x2,…, xn] over the selected K. Examples of such platforms can be found in [33], [22].

6.2. The summary
Multivariate Cryptography (MC) is one of the five core directions of Postquantum
cryptography. It is specially important for creation of fast digital signatures procedures. Despite
the fact currently announced by National Standards of Information Technology (NIST, USA)
standards of postquantum cryptography are constructed in the terms of alternative to MC
approaches the intensive research on new multivariate cryptosystem is continue. When it
comes to digital signatures, NIST has developed two standards. The first is called Module-
Lattice-Based Digital Signature Algorithm (ML-DSA for short) and defines a general digital
signature algorithm.
    The second one is called Stateless Hash-Based Digital Signature Algorithm (SLH-DSA for
short). It is a digital signature algorithm based on the hash technique. Essentially shorter
signatures can be obtained with the multivariate cryptosystem ’’TUOV: Triangular Unbalanced
Oil      and       Vinegar’’      algorithm        were       presented      to      NIST       (see
https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/TUOV-
spec-web.pdf) by principal submitter Jintaj Ding.
    Our paper presents several new multivariate digital signatures. Some of them are the
generalisations of schemes [31] known since 2015 for which the cryptanalysis is still unknown.
Proposed methods allow us to construct obfuscations of arbitrary selected multivariate
cryptosystem such as mentioned above TUOV, old Matsumoto-Imai system, various variants of
Oil and Vinegar system and others. Additionally new method gives an option to create algebraic
cryptosystems over the finite commutative rings K different from finite fields such as
arithmetical or Boolean rings. We believe that Multivariate K-theory for which the main
instrument is an element of Cremona semigroup of endomorphisms of K[x1, x2,…, xn] (see [25],
[26]) has a capacity to provide efficient digital signatures. Suggested algorithms in case of finite
fields and arithmetical rings can be already used for the protection of Information systems.

Acknowledgements
This research is supported by British Academy Fellowship for Researchers under Risk 2022 and
by British Academy and partially supported by the British Academy award LTRSF\100333.
References
[1] Vasyl Ustimenko, Aneta Wróblewska, On extremal algebraic graphs, quadratic
     multivariate public keys and temporal rules, FedCSIS 2023: 1173-1178 (see also IACR,e-print
     archive 2023/738).
[2] Ward Beullens, Improved Cryptanalysis of UOV and Rainbow, In Eurocrypt 2021, Part 1, pp.
     348-373.
[3] Anne Canteaut, François-Xavier Standaert (Eds.), Eurocrypt 2021, LNCS 12696, 40th
     Annual In-ternational Conference on the Theory and Applications of Cryptographic
     Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I, Springer.
[4] Ding and A. Petzoldt, "Current State of Multivariate Cryptography," in IEEE Security &
     Privacy, vol. 15, no. 4, pp. 28-36, 2017, doi: 10.1109/MSP.2017.3151328.
[5] Smith-Tone, D. (2022), 2F - A New Method for Constructing Efficient Multivariate
     Encryption Schemes, Proceedings of PQCrypto 2022: The Thirteenth International
     Conference on Post-Quantum Cryptography, virtual, DC, US.
[6] Daniel Smith Tone, New Practical Multivariate Signatures from a Nonlinear Modifier, IACR
     e-print archive, 2021/419.
[7] Daniel Smith-Tone and Cristina Tone, A Nonlinear Multivariate Cryptosystem Based on a
     Random Linear Code, https://eprint.iacr.org/2019/1355.pdf
[8] Jayashree, Dey, Ratna Dutta, Progress in Multivariate Cryptography: Systematic Review,
     Challenges, and Research Directions, ACM Computing Survey, volume 55, issue 12,No.246,
     pp 1-34, https://doi.org/10.1145/3571071.
[9] Cabarcas Felipe, Cabarcas Daniel, and Baena John. 2019. Efficient public-key operation in
     multivariate schemes. Advances in Mathematics of Communications 13, 2 (2019), 343.
[10] Cartor Ryann and Smith-Tone Daniel. 2018. EFLASH: A new multivariate encryption
     scheme. In Proceedings of the International Conference on Selected Areas in
     Cryptography. Springer, 281–299.
[11] Casanova Antoine, Faugère Jean-Charles, Macario-Rat Gilles, Patarin Jacques, Perret
     Ludovic, and Ryckeghem Jocelyn. 2017. Gemss: A great multivariate short signature.
     Submission to NIST (2017).y. Springer, Singapore, 209–229.
[12] Chen Jiahui, Ning Jianting, Ling Jie, Lau Terry Shue Chien, and Wang Yacheng. 2020. A
     new encryption scheme for multivariate quadratic systems. Theoretical Computer Science
     809 (2020), 372–383.
[13] Chen Ming-Shing, Hülsing Andreas, Rijneveld Joost, Samardjiska Simona, and Schwabe
     Peter. 2018. SOFIA: MQ-based signatures in the QROM. In Proceedings of the IACR Inter-
     national Workshop on Public Key Cryptography. Springer, 3–33.
[14] Ding Jintai, Petzoldt Albrecht, and Schmidt Dieter S.. 2020. Multivariate Public Key Cryp-
     tosystems, Second Edition. Advances in Information Security. Springer.
[15] Dung H. Duong, Ha T. N. Tran, Willy Susilo, and Le Van Luyen. 2021. An efficient
     multivariate threshold ring signature scheme. Computer Standards & Interfaces 74.
[16] Jean-Charles Faugère, Gilles Macario-Rat, Jacques Patarin, and Ludovic Perret. 2022. A new
     perturbation for multivariate public key schemes such as HFE and UOV. Cryptology ePrint
     Archive (2022).
[17] N. Biggs, Algebraic graphs theory, Second Edition, Cambridge University Press, 1993.
[18] A. Brower, A. Cohen, A. Nuemaier, Distance regular graphs, Springer, Berlin, 1989.
[19] B. Bollob´as, Extremal Graph Theory, Academic Press, London, 1978
[20] V. Ustimenko, Maximality of affine group, hidden graph cryptosystem and graph's stream
     ciphers, Journal of Algebra and Discrete Mathematics, 2005, v.1, pp 51-65
[21] V. Ustimenko, On small world non Sunada twins and cellular Voronoi diagams, Algebra
     and Discrete Mathematics, vol. 30, N1 (2020), pp. 118-142.
[22] V. Ustimenko. 2022. Graphs in terms of Algebraic Geometry, symbolic computations and
     secure communications in Post-Quantum world, UMCS Editorial House, Lublin, 2022, 198.
[23] V. Ustimenko, 2023, Schubert cells and quadratic public keys of Multivariate Cryptography.
     CEUR Workshop Proceedings ITTAP , https://ceur-ws.org/Vol-3628/.
[24] N. Bourbaki, Lie Groups and Lie Algebras, Chapters 1 - 9, Springer, 1998-2008.
[25] M. Noether,{\em Luigi Cremona}, Mathematische Annalen, 59 (1904), pp. 1-19.
[26] V. L. Popov, Roots of the affine Cremona group, in: Affine Algebraic Geometry, Seville,
     Spain, June 1821, 2003, Contemporary Mathematics, Vol. 369, American Mathematical
     Society, Providence, RI, 2005, pp. 12-13.
[27] Markku Juhani Saarinen, Daniel Tony Smith (editors), Post Quantum Cryptography, 15th
     International Workshop, PQCrypto 2024,Oxford, UK, June 12-14, 2024, Proceedings, Part 1.
[28] Markku Juhani Saarinen, Daniel Tony Smith (editors), Post Quantum Cryptography, 15th
     International Workshop, PQCrypto 2024,Oxford, UK, June 12-14, 2024, Proceedings, Part 2.
[29] Tsuyoshi Takagi, Masato Wakayama, Keisuke Tanaka, Noboru Kunihiro, Kazufumi
     Kimoto, Yasuhiko Ikematsu (editors), International Symposium on Mathematics, Quantum
     Theory, and Cryptography, Proceedings of MQC 2019, Open Access, 2021
[30] Kohei Arai (editor), Advances in Information and Communication,Proceedings of the 2024
     Future of Information and Communication Conference (FICC), Volume 1-3, Lecture Notes
     in Networks and Systems,       (LNNS, volume 919 -921) , Springer, 2024.
[31] V. Ustimenko, On Schubert cells in Grassmanians and new algorithms of multivariate
     cryptography, Proceedings of the Institite of Mathematics, Minsk, 2015, Volume 23, N 2, pp.
     137-148 (Proceedings of international conference “Discrete Mathematics, algebra and their
     applications”, Minsk, Belarus, September 14-18, 2015, dedicated to the 100th anniversary of
     Dmitrii Alexeevich Suprunenko).
[32] V. Ustimenko, Linear codes of Schubert type and quadratic public keys of Multivariate
     Cryptography,
IACR e-print archive, 2023/175.
[33] v. ustimenko, On computations with double Schubert automaton and stable maps of
     multivariate cryptography, Interdisciplinary Studies of Complex SystemsNo. 19 (2021) 18–
     32.
[34] I. Gelfand, R. MacPherson,Geometry in Grassmanians and generalisation of the
     dilogarithm, Adv. in Math., 44 (1982), 279-312.
[35] I. Gelfand, V. Serganova, Combinatorial geometries and torus strata on homogeneous
     compact manifolds, Soviet Math. Surv. 42 (1987), 133-168.
 [36] D. N. Moldovyan and N.A. Moldovyan, A New Hard Problem over Non-commutative Finite
     Groups for Cryptographic Protocols, International Conference on Mathematical Methods,
     Models, and Architectures for Computer Network Security, MMM-ACNS 2010: Computer
     Network Security pp 183-194.
[37] L. Sakalauskas, P. Tvarijonas and A. Raulynaitis, Key Agreement Protocol (KAP) Using
     Conjugacy and Discrete Logarithm Problem in Group Representation Level,
     INFORMATICA, 2007, vol. 18, No 1, 115-124.
[38] V. Shpilrain, A. Ushakov, The conjugacy search problem in public key cryptography:
     unnecessary and insufficient, Applicable Algebra in Engineering, Communication and
     Computing, August 2006, Volume 17, Issue 3–4, pp 285–289.
[39] Delaram Kahrobaei and Bilal Khan, A non-commutative generalization of ElGamal key
     exchange using polycyclic groups, In IEEE GLOBECOM 2006 - 2006 Global
     Telecommunications Conference [4150920] DOI: 10.1109/GLOCOM.2006.
[40] Alexei Myasnikov; Vladimir Shpilrain and Alexander Ushakov (2008), Group-based
     Cryptography, Berlin: Birkhäuser Verlag.
[41] Zhenfu Cao (2012), New Directions of Modern Cryptography. Boca Raton: CRC Press,
     Taylor & Francis Group. ISBN 978-1-4665-0140-9.
[42] Benjamin Fine, et. al. "Aspects of Non abelian Group Based Cryptography: A Survey and
     Open Problems", arXiv:1103.4093.
[43] V. A. Roman'kov, A nonlinear decomposition attack, Groups Complex. Cryptol. 8, No. 2
     (2016), 197-207.27.
[44] V. Roman'kov, An improved version of the AAG cryptographic protocol, Groups, Complex.,
     Cryptol, 11, No. 1 (2019), 35-42.
[45] A. Ben-Zvi, A. Kalka and B. Tsaban, Cryptanalysis via algebraic span, In: Shacham H. and
     Boldyreva A. (eds.) Advances in Cryptology - CRYPTO 2018 - 38th Annual International
     Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I,
     Vol. 10991, 255{274, Springer, Cham (2018).
[46] B. Tsaban, Polynomial-time solutions of computational problems in noncommutative-
     algebraic cryptography, J. Cryptol. 28, No. 3 (2015), 601-622.
[47] V. Roman’kov, Cryptanalysis of a new version of the MOR scheme, arXiv:1911.00895
     [cs.CR].
[48] V. Roman’kov, Cryptanalysis of two schemes of Baba et al. by linear algebra methods. CoRR
     abs/1910.09480 (2019).
[49] Adi Ben-Zvi, Arkadius G. Kalka, Boaz Tsaban, Cryptanalysis via Algebraic Spans. CRYPTO
     (1) 2018: 255-274

</pre>