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 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/TUOVspec-web.pdf) by principal submitter Jintaj Ding.

Further development of Classical Multivariate Cryptography which study quadratic and cubic endomorphisms of F q [x 1 , x 2 ,…, x n ] 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[x 1 , x 2 ,…, x n ] which is the piece of information T such that its knowledge allows us to compute the reimage of (σ, K n ) 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 σ(x i ), 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[x 1 , x 2 ,…, x n ] with the trapdoor accelerator T defined via totality of special bipartite Jordan-Gauss graphs with the partition sets isomorphic to K n . We discuss the possible use of these transformation in the case of finite fields and arithmetical rings Z q 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 x i →g i (x 1 , x 2 , … , x n ), where polynomials g i 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[x 1 , x 2 ,…., x n ])) for the construction of trapdoor accelerators, which are surjective multivariate maps F of K n onto K n' 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.

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-1 PG(F q ) of dimension n-1 over the finite field F q , where q is a prime power, is a totality of proper subspaces of the vector space V=(F q ) n of nonzero dimension. This is the incidence system with type function t(W)=dim(W), W ϵ n-1 PG(F q ) and incidence relation I defined by the condition W 1 IW 2 if and only if one of these subspaces is embedded in another one. We can select standard base e 1 , e 2 ,…, e n of V and identify n-1 PG(F q ) with the totality of linear codes in (F q ) n .The geometry n-1 ℾ(q)= n-1 PG(F q ) 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 (x 1 , x 1 , … , x n ). Let U stands for the unipotent subgroup of automorphism group PGL n (F q ) consisting of lower unitriangular matrices. 5 Let us consider orbits of the natural action of U on the projective geometry n-1 PG(F q ). They are known as large Schubert cells. Each of orbits on the set ℾ m (F q ) contains exactly one symplectic element spanned by elements e i( 1) , e i(2) , ..., e i(m) . So the number of orbits of (U, ℾ m (F q )) equals to binomial coefficient C m n (n,m). Noteworthy that the cardinality of n-1 ℾ m (F q ) is expressed by Gaussian binomial coefficient. Unipotent subgroup U is generated by elementary transvections x i,j (t), i<j, tϵF q . If we select i and j then elements of kind x i,j (t) form root subgroup U i,j , corresponding to the positive root e i -e j of root system A n-1 .

Let J be a proper subset of {1, 2, …, n}=N, J S be Schubert cell containing symplectic subspace W J spanned by e j ϵ J, ∆(J)= { (i,j) | iϵ J, jϵN-J, i<j }. Then a subgroup U(J) generated by root subgroups U i,j , (i, j) ϵ ∆(J) of order q k , k= |∆(J)| acts regularly on J S. It means that we can identify J S and U(J).Noteworthy that each ℾ m (F q ) has a unique largest Schubert cell of size q m(n-m) , it is J S for J={n, n-1, n-2, … , n-m+1}. We denote this cell as m LS(q). We consider the bipartite graph m,k I n (F q ) of the restriction of I onto disjoint union m LS(F q ) and k LS(F q ). It is bipartite graph with bidegrees q r and q s 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,k I n (F q ) as Cellular Schubert graph and denote it as m,k CS n (F q ) 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=U n (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 A n-1 . We identify element M from U n (K) with the function f: ∆→ K such that f(i,j)=m i,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=(m i,j ) from U such that (i, j) ϵ{∆-∆(J)} implies that m i,j =0. We define incidence system n-1 PG(K) as a totality of pairs (J, M), M ϵU(J) with type function t(J, M)=|J| and incidence relation given by conditions ( 1 J, 1 M) I ( 2 J, 2 M) if and only if one of subsets 1 J and 2 J is embedded in another one and 1 1 M. We refer to this incidence system as projective geometry scheme over commutative ring K. If K=F is the field then n-1 PG(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].

M-2 M) | ∆( 1 J )∩∆( 2 J) = 1 M • 2 M-2 M •

We introduce ℾ m (K), m LS(K) and graphs m,k CS n (K) for m=1, 2, …, n-1 via simple substitution of

K instead F q .

We refer to disjoint union of m LS(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 A n-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.

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=P s,m =K m+s and a line set L=L r,m =K m+r as linguistic incidence structure I m (K) where a j and b j , 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))=(x 1 , x 2 , …, x s ) for (x)=(x 1 , x 2 , …, x s+m ) and ρ([y])=(y 1 , y 2 , …, y r ) for [y]=[y 1 , y 2 , … , y r+m ] as the colour of the point and the colour of the line respectively.

For each bϵ K r and p=(p 1 , p 2 , …, p s+m ) there is the unique neighbour of the point [l]=N b (p) with the colour b. Similarly, for each c ϵ K s and line l=[l 1 , l 2 , …, l r+m ] there is the unique neighbour of the line (p)= N c ([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= 1 J b (p)=(b 1 , b 2 , …, b s , p 1+s , p 2+s , …, p s+m ), where (b 1 , b 2 , …, b s )ϵK s and 2 J= 2 J b ([l])=[b 1 , b 2 , …, b r , l 1+r , l 2+r , …, l r+m ], where (b 1 , b 2 , …, b r )ϵK r .

We refer to tuple (s, r, m) as type of the linguistic graph I. If (p 1 , p 2 , ...., p s+m ) and [l 1 , l 2 , ..., l r+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 I m (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 ax i y j , a≠0.

Let L i =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 L i , i=1, 2,...,m as linguistic symbolic scheme S =S(I m (K)) and say that linguistic graph I m (K) with parameters a i , b i , 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 1 I m (K) and 2 I m (K') as symbolically equivalent if

S( 1 I m (K)) =S( 2 I m (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 a i , b i , 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[z 1 , z 2 , ..., z m+s ] for arbitrary chosen K to define the map from K s+m to itself.

Assume that graph I m (K) has parameters a i , b i and symbolic scheme S is defined by polynomials fi. Let I m (K[ z 1 , z 2 , ..., z l ]) be the interpretation of S of type (K[z 1 ,z 2 ,..., z l ], K) given by same parameters a i , b i and monomial terms of fi.

Algorithm 1 (construction of endomorphisms of K[z 1 , z 2 ,…, z s , z s+1 ,z s+2 ,…, z s+m ] via the sequence of linguistic graphs of type (s, r, m)).

We select the linguistic graph I m (K) of type (s, r, m) with symbolic scheme S and graphs 1 I m (K) of type (r, s, m), 2 I m (K) of type (s, r, m),..., graph 2t+1 I m of type r, s, m with the symbolic schemes i S, i=1, 2,..., 2t+1.

We consider the graphs

I m (K[z 1 , z 2 , ..., z s+m ]) together with j I m (K[z 1 , z 2 ,..., z m+s ]) , j ≥ 1 and select the polynomial tuples 0 H=( 0 h 1 (z 1 , z 2 ,..., z s ), 0 h 2 (z 1 , z 2 , ..., z s ), ..., 0 h s (z 1 , z 2 , ..., z s )), 0 G=( 0 g 1 (z 1 , z 2 , ..., z s ), 0 g 2 (z 1 , z 2 , ..., z s ),..., 0 g r (z 1 , z 2 , ..., z s )), 1 H=( 1 h 1 (z 1 , z 2 ,..., z s ), 1 h 2 (z 1 , z 2 , ..., z s ), ..., 1 h r (z 1 , z 2 , ..., z s )), 1 G= ( 1 g 1 (z 1 , z 2 , ..., z s ), 1 g 2 (z 1 , z 2 , ..., z s ),..., 1 g s (z 1 , z 2 , ..., z s )), 2 H=( 2 h 1 (z 1 , z 2 ,..., z s ), 2 h 2 (z 1 , z 2 , ..., z s ), ..., 2 h s (z 1 , z 2 , ..., z s )), 2 G= ( 2 g 1 (z 1 , z 2 , ..., z s ), 2 g 2 (z 1 , z 2 , ..., z s ),..., 2 g r (z 1 , z 2 , ..., z s )), ..., 2t+1 H=( 2 h 1 (z 1 , z 2 ,..., z s ), 2 h 2 (z 1 , z 2 , ..., z s ), ..., 2 h r (z 1 , z 2 , ..., z s )), 2t+1 G= ( 2t g 1 (z 1 , z 2 , ..., z s ), 2t g 2 (z 1 , z 2 , ..., z s ),..., 2t g s (z 1 , z 2 , ..., z s )), H=H 2t+2 =(h 1 (z 1 , z 2 ,..., z s ), h 2 (z 1 , z 2 , ..., z s ), ..., h s (z 1 , z 2 , ..., z s )).

Let N b be the neighbourhood operator of I m (K[z 1 , z 2 ,..., z m+s ]) and j N b be the neighbourhood operator of j I m (K[z 1 , z 2 ,..., z m+s ]), j=1, 2,..., 2t+1.

Let us take a special point (z 1 , z 2 , ..., z s , z s+1 , z s+2 ,..., z m+s )=(z) and compute

1 J b(0) ((z)) = 0 (z) in the graph I m (K[z 1 , z 2 , ..., z s+m ]) with b(0)= 0 H, N c(0) ( 0 (z))= 0 ([u]) in I m (K[z 1 , z 2 , ..., z s+m ]) with c(0)= 0 G, 1 J b(1) ( 0 ([u]))= 1 ([z]) in the graph 1 I m (K[z 1 , z 2 ,..., z m+s ]) with b(1)= 1 H, 1 N c(1) ( 1 ([z]))= 1 (u) in the graph 1 I m (K[z 1 , z 2 ,..., z m+s ]) with c(1)= 1 G, 1 J b(2) ( 1 (u))= 2 (z) in the graph 2 I m (K[z 1 , z 2 ,..., z m+s ]) with b(2)= 2 H, 2 N c(2) ( 2 (z))= 2 (u) in the graph 2 I m (K[z 1 , z 2 ,..., z m+s ]) with c(2)2= 2 G, ….. 1 J b(2t+1) ( 2t ([u]))= 2t+1 ([z]) in the graph 2t+1 I m (K[z 1 , z 2 ,..., z m+s ]) with b(2t+1)= 2t+1 H, 1 N c(2t+1) ( 2t+1 ([z]))= 2t+1 (u) in the graph 2t+1 I m (K[z 1 , z 2 ,..., z m+s ]) with c(2t+1)= 2t+1 G. Finally we compute u as 2 J b ( 2t+1 (u)) with b=H. Assume that u=(h 1 (z 1 , z 2 ,..., z s ), h 2 (z 1 , z 2 ,...,z s ),..., h s (z 1 , z 2 ,...., z s ), g s+1 (z 1 , z 2 ,..., z s , z s+1 , z s+2 ,..., z s+m ), g s+2 (z 1 , z 2 ,..., z s , z s+1 , z s+2 ,..., z s+m ), ..., g s+m (z 1 , z 2 ,..., z s , z s+1 , z s+2 ,..., z s+m )).

We consider the polynomial map F of K s+m to itself given by the following rule.

z 1 →h 1 (z 1 , z 2 ,..., z s ), z 2 → h 2 (z 1 , z 2 ,..., z s ), ..., z s → h s (z 1 , z 2 ,...., z s ), z s+1 → g s+1 (z 1 , z 2 ,..., z s , z s+1 , z s+2 ,..., z s+m ), z s+2 → g s+2 (z 1 , z 2 ,..., z s , z s+1 , z s+2 ,..., z s+m ), ..., z s+m → g s+m (x 1 , x 2 ,..., x s , x s+1 , x s+2 ,..., x s+m ).

We refer to linguistic graphs 1 I m (K) and 2 I m (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 I m (K) obtained via the replacement of partition sets P and L.

So graphs I m (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 I m (K)= 0 I m (K), 1 I m (K), 2 I m (K), ..., 2t+1 I m (K) and listed above sequences of tuples i H, i=0, 1, ..., 2t+2 and i G, i=0, 1, 2, ..., 2t+1 with coordinates from K[z 1 , z 2 , ..., z s ] of length s or r.

Proposition 1 [22] .

Let z 1 →h 1 (z 1 , z 2 ,..., z s ), z 2 → h 2 (z 1 , z 2 ,..., z s ),..., z s → h s (z 1 , z 2 ,...., z s ) be a bijective map B from K s onto K s . Then transformation F=F( j I m (K), j G, i H), j=0, 1, …, 2m+1, i=0, 1, …, 2m+2 is a bijective map of K s+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 L 1 FL 2 where L 1 and L 2 are affine transformations from AGL n (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 I m (K) and tuples j G and i H.

Alice

(c)= 1 c=( 1 c 1 , 1 c 2 , ..., 1 c m+s ).

Alice works with the equations Finally Alice gets J a(1)

h 1 (u 1 , u 2 ,..., u s )= 1 c 1 , h 2 (u 1 , u 2 ,..., u s )= 2 c 1 , …, h s (u 1 , u 2 ,..., u s )= s c( 2 b)= 1 c and N b(1) ( 1 c)= 1 b together with J a(0) ( 1 b)= 0 c and N b(0) ( 0 c)= 0 b. So she gets (u*) as 1 J (t) ( 0 b)=(t 1 , t 2 , ..., t s , u s+1 , u s+2 ,..., u s+m ).

Alice computes the plaintext (p) as (L 1 ) -1 (u*).

Remark. We can substitute elements L 1 and L 2 by surjective affine map L' 1 of affine space K n' onto K n , n'>n and surjective map L' 2 of affine space K m onto K m' , m≥m' and get surjective map

L' 1 F L' 2 of affine space K n' onto K m' . 1) Algorithm 2.

Let us assume that s>r. We select the linguistic graph I m (K) of type (s, r, m) with symbolic scheme S and graphs 1 I m (K) of type (r, s, m), 2 I m (K) of type (s, r, m),..., graph 2t I m of type r, s, m with the symbolic schemes i S, i=1, 2,..., 2t. Similarly to algorithm 1 we consider the graphs

I m (K[z 1 , z 2 , ..., z s+m ]) together with j I m (K[z 1 , z 2 ,.

.., z m+s ]) , j ≥ 1 and select the polynomial tuples 0 H=( 0 h 1 (z 1 , z 2 ,..., z s ), 0 h 2 (z 1 , z 2 , ..., z s ), ..., 0 h s (z 1 , z 2 , ..., z s )), 0 G=( 0 g 1 (z 1 , z 2 , ..., z s ), 0 g 2 (z 1 , z 2 , ..., z s ),..., 0 g r (z 1 , z 2 , ..., z s )),

1 H=( 1 h 1 (z 1 , z 2 ,..., z s ), 1 h 2 (z 1 , z 2 , ..., z s ), ..., 1 h r (z 1 , z 2 , ..., z s )), 1 G= ( 1 g 1 (z 1 , z 2 , ..., z s ), 1 g 2 (z 1 , z 2 , ..., z s ),..., 1 g s (z 1 , z 2 , ..., z s )), 2 H=( 2 h 1 (z 1 , z 2 ,..., z s ), 2 h 2 (z 1 , z 2 , ..., z s ), ..., 2 h s (z 1 , z 2 , ..., z s )), 2 G= ( 2 g 1 (z 1 , z 2 , ..., z s ), 2 g 2 (z 1 , z 2 , ..., z s ),..., 2 g r (z 1 , z 2 , ..., z s )), ..., 2t H=( 2 h 1 (z 1 , z 2 ,..., z s ), 2 h 2 (z 1 , z 2 , ..., z s ), ..., 2 h s (z 1 , z 2 , ..., z s )), 2t G= ( 2t g 1 (z 1 , z 2 , ..., z s ), 2t g 2 (z 1 , z 2 , ..., z s ),..., 2t g r (z 1 , z 2 , ..., z s )), H=H 2t+1 =(h 1 (z 1 , z 2 ,..., z s ), h 2 (z 1 , z 2 , ..., z s ), ..., h r (z 1 , z 2 , ..., z s )).

As in the algorithm 1 we take a special point (z 1 , z 2 , ..., z s , z s+1 , z s+2 ,..., z m+s )=(z) and compute

1 J b(0) ((z)) = 0 (z) in the graph I m (K[z 1 , z 2 , ..., z s+m ]) with b(0)= 0 H, N c(0) ( 0 (z))= 0 ([u]) in I m (K[z 1 , z 2 , ..., z s+m ]) with c(0)= 0 G, 1 J b(1) ( 0 ([u]))= 1 ([z]) in the graph 1 I m (K[z 1 , z 2 ,..., z m+s ]) with b(1)= 1 H, 1 N c(1) ( 1 ([z]))= 1 (u) in the graph 1 I m (K[z 1 , z 2 ,..., z m+s ]) with c(1)= 1 G, 1 J b(2) ( 1 (u))= 2 (z) in the graph 2 I m (K[z 1 , z 2 ,..., z m+s ]) with b(2)= 2 H, 2 N c(2) ( 2 (z))= 2 (u) in the graph 2 I m (K[z 1 , z 2 ,..., z m+s ]) with c(2)2= 2 G, ….. 1 J b(2t) ( 2t-1 ([u]))= 2t ([z]) in the graph 2t I m (K[z 1 , z 2 ,..., z m+s ]) with b(2t)= 2t H, 1 N c(2t) ( 2t ([z]))= 2t (u) in the graph 2t I m (K[z 1 , z 2 ,..., z m+s ]) with c(2t)= 2t G.

Finally we compute u as

(K), j G, i H), j=0, 1, …, 2m+1, i=0, 1, …, 2m+2 is a surjective map of K s+m to K r+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 K n' onto K n , n'>n and affine space K m onto K m' , m≥m' respectively . Then polynomial surjective map L' 1 F L' 2 of affine space K n' onto K m' also has a trapdoor accelerator.

Below we present a modification of Algorithm 1.

Let I m (K) be a linguistic graph of type (s, r, m). We

(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 <(p 1 , p 2 ,..., p s ), [l 1 , l 2 , ..., l r ]> of ((p), [l]) from PL m (K) as the colour of the flag. We say that (p 1 ,p 2 ,…,p s ) and [l 1 ,l 2 ,…,l s ] are internal and external colours of the flag ((p), [l]). The information on the flag can be given by the tuple (p 1 , p 2 , ..., p s , p s+1 , p s+2 ,..., p s+m , l 1 , l 2 , ..., l r ).

Dual presentation of ((p), [l]) is(p 1 , p 2 ,…, p s , l 1 , l r+2 ,…, l r+m , l 1 , l 2 ,…, l r )*

Algorithm 3.

Alice takes the sequence of graphs D(I m (K)), D( l I m (K)), l=1,2,…,t. She will work with the multivariate ring K'=K[z 1 , z 2 ,…, z s , z s+1 , z s+2 ,…, z s+m , z 1s+m+1 , z s+m+2 , …, z s+m+r ] and graphs D(I m (K')),D( l I m (K')).

Alice selects the tuple 0 H=(h

1 , h 2 ,…, h s , g 1 , g 2 ,…, g r ) , H'=(h' 1 , h' 2 ,…, h' s , g' 1 , g' 2 ,…, g' r ) and i H=( i h 1 , i h 2 ,…, i h s , i g 1 , i g 2 ,…, i g r ) from (K') s+r . She takes the flag (z)=( z 1 , z 2 ,…, z s , z s+1 , z s+2 ,…, z s+m , z s+m+1 , z s+m+2 , …, z s+m+r ) of I m (K'). Assume that for ((p),[ l]) from j PL(I m (K')), j=1.2,…,t-1 symbol ((p),[ l])* means ([l], (p)) from j+1 PL(I m (K')). If ((p),[ l]) is a flag from t PL(I m (K')) then ((p),[ l])* is ([l], (p)) from t-1 PL(I m (K')).

Alice uses operator 1 J a , a= 0 H and computes

1 z = 1 J a (z)=( h 1 , h 2 ,…, h s , z s+1 , z s+2 ,…, z s+m , g 1 , g 2 ,… g r ) in the graph D(I m (K)). She computes ( 1 u)=( 1 z)*= [ g 1 , g 2 ,… g r , z' s+1 , z' s+2 ,…, z s'+m , h 1 , h 2 ,…, h s ] of the graph 1 I m (K') where [ g 1 , g 2 ,… g r , z' s+1 , z' s+2 ,…, z s'+m ] is the neighbour of ( h 1 , h 2 ,…, h s , z s+1 ,) z s+2 ,…, z s+m ) in I m (K').

2Next Alice uses 1 J a(1) , a(1)= 1 H and computes 1 J a(1) ( 1 u)= 2 z in the graph 1 I m (K') and

( 2 u)=( 2 z)* from 2 I m (K').

She continue this procedure and constructs ( i u), i=3.4,…, t. Alice takes ( t u) from t I m (K') and uses 2 J b , b= H' for the computation of

u= 1 J( t u) of kind ( h' 1 , h' 2 ,…, h' s , v 1 , v 2 , …, v m , g' 1 , g' 2 ,…, g' r ) or (g' 1 , g' 2 ,…, g' r , v 1 , v 2 , …, v m , h' 1 , h' 2 , …, h' s ) dependently on t mod 2.

She uses the following map G= G=G( j I m (K), i H, H'), i=0,1,…,t as the output of the algorithm. z 1 →h' Proposition 5 [22].

Let z 1 →h' 1 (z 1 , z 2 ,..., z s z s+m+1 , z s+m+2 , …, z s+m+r ), z 2 → h' 2 (z 1 , z 2 ,..., z s , z s+m+1 , z s+m+2 , …, z s+m+r ),..., z s → h' s, (z 1 , z 2 mz s, z s+m+1 , z s+m+2 , …, z s+m+r ), z 1+s+m →g' 1 (z 1 , z 2 ,…, z s z s+m+1 , z s+m+2 , …, z s+m+r), z 2+s+m →g' 2 (z 1 , z 2 ,…, z s z s+m+1 , z s+m+2 , …, z s+m+r), …, ), z r+s+m →g' r (z 1 , z 2 ,…, z s , z s+m+1 , z s+m+2 , …, z s+m+r)

be a bijective map B from K s+r onto K s+r . Then transformation G=G( j I m (K), i H, H'), j=0, 1, …, t is a bijective map of K s+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 L 1 GL 2 where L 1 and L 2 are affine transformations from AGL n (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.

On the examples of Schubert cellular graphs, their symplectic quotients and cryptographic algorithms

Let us consider graphs m,m-1 CS m+k-1 (F) over the field F which are induced subgraphs of projective geometry PG m+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 F m+k . They can be defined as totalities of points

(x)=(x 1 , x 2 ,…,x k , x 1,1 , x 1,2 ,….,x k,m-1 ) and lines [y]=[y 1 , y 2 ,…,y m-1 , x 1,1 , x 1,2 ,….,x k,m-1 ]

from F k(m-1)+k and 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 L i,j ={x i y j } 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 I k(m-1) (K) be the Jordan-Gauss graph over K symbolically equivalent to m,m-1 CS m+k-1 (K) then corresponding equations are a i,j x i,j -b ij y i,j = c i,j x i y j where a i,j and b ij are elements of multiplicative group K* and c i,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

I M of I k(m-1) (K).

Other special case of cellular Schubert graph is m,1 CS m (F) of type (m-1, m-1, 1) when we have points and lines of kind (x 1 , x 2 ,…, x m ) and [y 1 , y 2 , …., y m ] and equation x m -y m =x 1 y 1 +x 2 y 2 +… +x m-1 y m-1 . Symbolically equivalent to m,1 CS m (F) will be Jordan-Gauss graph of type (m-1, m-1, 1) with the incidence given by an equation of kind ax m -by m =c 1 x 1 y 1 +c 2 x 2 y 2 +…+c m-1 x m-1 y m-1 with a and b from the multiplicative group K* and c i 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 … , x s,, , x m(1)+s , x m(2)+s,… , x m (d-1)+s, y 1, y 2 , … , y r,, y m(1)+r , y m(2)+r , ,… , y m (d-1 It is clear, that δ is colour preserving homomorphism of incidence structures (bipartite graphs). We refer to δ as symplectic homomorphism and graph I M 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).

a m(1)+s x m(1) -b m(1) y m(1)+r =f m(1) (x 1 , x 2 , …, x s ,y 1, y 2 , … , y r ) a m(2) x m(2)+s -b m(2) y m(2)+r = f m(2) (x 1 , x 2 , … ,x s, x m(1)+s ,y 1, y 2 , … , y r,, y m(1)+r ) )… a m(d) x m(d)+s -b m(d) y m(d)+r =f m(d) (x 1 , x 2 ,

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 I M . Let us consider graphs m,m-1 CS m+k-1 (F) over the field F which are induced subgraphs of projective geometry PG m+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 F m+k . They can be defined as totalities of points

(x)=(x 1 , x 2 ,…,x k , x 1,1 , x 1,2 ,….,x k,m-1 ) and lines [y]=[y 1 , y 2 ,…,y m-1 , x 1,1 , x 1,2 ,….,x k,m-1 ]

from F k(m-1)+k and 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 L i,j ={x i y j } 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 I k(m-1) (K) be the Jordan-Gauss graph over K symbolically equivalent to m,m-1 CS m+k-1 (K) then corresponding equations are a i,j x i,j -b ij y i,j = c i,j x i y j where a i,j and b ij are elements of multiplicative group K* and c i,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

I M of I k(m-1) (K).

Let us consider trapdoor accelerators defined in terms of cellular Schubert graphs. We introduce the degree of the tuple from K[z 1 , z 2 , ...., z p ], p>1 as maximal degree of its coordinates as multivariate polynomials.

Proposition 7 [22]. Let the condition of Proposition 1 holds, graph j I m (K), j=0,1, …, 2t +1 are symbolically equivalent to l,k CS n (K) or its dual graph and deg( j H)+deg( j G)≤2, j=1,2,…, 2t+1, deg(H)=2. Then transformation G=F( j I m (K) j , j G, i H), j=0, 1, …, 2t+1, i=0, 1, …, 2m+2 is a bijective quadratic map of K s+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 j I m (K), j=0,1, …, 2t are symbolically equivalent to l,k CS n (K) or its dual graph and deg

( j H)+deg( j G)≤2, j=1,2,…, 2t, deg(H')=2. Then transformation G=F( j I m (K), j G, i H), j=0, 1, …, 2t, i=0, 1, …, 2m+1 is a surjective quadratic map of K s+m to K r+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 j I m (K), j=0,1, …, t are symbolically equivalent to l,k CS n (K) or its dual graph and deg( j h 1 , j h 2 , ,,,, j h s )+deg( j g 1 , j g 2 , ,,,, j g r )≤2, j=0,1,2,…, t, and deg (H')=2. Then the transformation G=G( j I m (K) j , i H, H'), j=0, 1, …, t is a bijective quadratic map of K s+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 j I m (K) of the propositions 7, 8 and 9 for the nontrivial symplectic quotients of these Jordan-Gauss graphs.

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 j I m (K), j=0,1, …, 2t +1 are symbolically equivalent to l,k CS n (K) or its dual graph and deg( j H)+deg( j G)≤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:x 1 →a 1 x 1 +b 1 , x 2 →a 2 x 2 +f 2 (x 1 ), x 3 →a 3 x 3 +f 3 (x 1 , x 2 ),…, x s → a s x s +f s (x 1 , x 2 ,…,x s-1 ) where a i , i=1, 2,…, s are elements from K* and deg fi=2, i=2,3,…,s together with two elements D 1wn and D 2 from AGL s (K) and define B as D 1 QD 2 .

So the standard form of B and the decomposition of B into D 1 QD 2 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[z 1 , z 2 ,…, z s ] and trapdoor accelerator which provides1 the knowledge on the graph D(s,K) and the tuple of ring elements of length O(n 2 ). 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,k CS s , k<s for the construction of B. Alice can select the tuples 0 H, 0 G, 1 H, 1 G,…, 2t+1 H, 2t+1 G and can choose 2t+1 H which defines the transformation from AGL k- s (K). This way she obtains the quadric bijective transformation F and construct B as the map D 1 FD 2 , D 1 , D 2 ϵAGL s (K) on the affine space K s .

In the case of finite fields of characteristic 2 Alice can use quadratic automorphism of F q [z 1 , z 2 ,…, z s ] from Matsumoto-Imai Cryptosystem. In the case of general finite field F q 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 AGL s (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 I m (K) of the Algorithm 1 is r,r-1 CS k+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(n 2 ),

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[z 1 , z 2 ,…., z k ] 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)k 3 . 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 0 H, 0 G, 1 H, 1 G,… requires O)(n 4 ) parameters. The trapdoor accelerator T can be thought as the sequence of O(n 4 ) 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(d 2 ).

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(d 3/2 ) and application of the element from AGL d (K) costs O(d 2 ).

Thus the complexity of private decryption procedure is O(d 2 ).

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 l I m (K), l=1, 2, …, 2t+1for l a i,j x i,jl b i,j y i,j = l c i,j x i' y j' where 'i= 1 π(i), j'= l µ(j) and get the new graphs l I' m (K).

It is easy to see that graphs l I' m (K) and l I m (K) have different symbolic type but they are isomorphic incidence structures.

We can change graphs l I m (K) for l' I m (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 I M (K) instead of I m (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 I M (K) will be unknown to public.

Example 2.

Let us assume that the graph I m (K) of the Algorithm 2 is r,r-1 CS k+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 K s to K r .

For instance she can use bijective transformations B on K s in the presented above schemes 1 and 2. Alice takes affine map D from AGL s (K) and surjective affine map D 3 from K s onto K r and forms B'=BD 3 .

In the case of finite fields K=F q 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

(z 1 , z 2 ,…., z k )→(l 1 (z 1 , z 2 ,…, z k ) 2 +b 1 , l 2 (z 1 , z 2 ,…, z k ) 2 +b 2 ,…, l r-1 (z 1 , z 2 ,…, z k ) 2 +b r-1 ) where (z 1 , z 2 ,…., z k )→(l 1 (z 1 , z 2 ,…, z k ), l 2 (z 1 , z 2 ,…, z k ),…, l r-1 (z 1 , z 2 ,…, z k )) is a linear map of rank r-1. She can use (z 1 , z 2 ,…., z k )→(l 1 (z 1 2 , z 2 2 ,…., z k 2 )+b 1 , l 2 (z 1 2 , z 2 2 ,…, z k 2 ) +b 2 ,…, l r-1 (z 1 2 , z 2 2 ,…, z k 2 )+b r-1 ) alternatively.

Alice will use the same graph I m (K)= r, r-1 CS k+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(n 2 ). 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-1 CS k+r-1 graphs j I m (K), m=k(r-1), j=0,1, …, 2t and symbolic colours 0

H=( 0 h 1 (z 1 , z 2 ,..., z k ), 0 h 2 (z 1 , z 2 , ..., z k ), ..., 0 h s (z 1 , z 2 , ..., z k )), 0 G=( 0 g 1 (z 1 , z 2 , ..., z k ), 0 g 2 (z 1 , z 2 , ..., z k ),..., 0 g r-1 (z 1 , z 2 , ..., z k )), 1 H=( 1 h 1 (z 1 , z 2 ,..., z k ), 1 h 2 (z 1 , z 2 , ..., z k ), ..., 1 h r-1 (z 1 , z 2 , ..., z k )), 1 G= ( 1 g 1 (z 1 , z 2 , ..., z k ), 1 g 2 (z 1 , z 2 , ..., z k ),..., 1 g k (z 1 , z 2 , ..., z k )), 2 H=( 2 h 1 (z 1 , z 2 ,..., z k ), 2 h 2 (z 1 , z 2 , ..., z k ), ..., 2 h k (z 1 , z 2 , ..., z k )), 2 G= ( 2 g 1 (z 1 , z 2 , ..., z k ), 2 g 2 (z 1 , z 2 , ..., z k ),..., 2 g r-1 (z 1 , z 2 , ..., z k )), ..., 2t H=( 2 h 1 (z 1 , z 2 ,..., z k ), 2 h 2 (z 1 , z 2 , ..., z k ), ..., 2 h k (z 1 , z 2 , ..., z k )), 2t G= ( 2t g 1 (z 1 , z 2 , ..., z k ), 2t g 2 (z 1 , z 2 , ..., z k ),..., 2t g r-1 (z 1 , z 2 , ..., z k )), Alice chooses the tuple H==(h 1 (z 1 , z 2 ,..., z k ),h 2 (z 1 , z 2 , ..., z k ), ..., h r-1 (z 1 , z 2 , ..., z k )). Recall that B(z)=H.

She follows to Algorithm 2 and creates the polynomial map F of K s+m to K r+m-1 itself given by the following rule (z Alice forms L' 1 and L' 2 of the Proposition 2.1 which are surjective affine maps of affine space K n' onto K n , n'>n=k+m and the affine space K m+r-1 onto K m' , m+r-1≥m' respectively. Then she computes the standard form G of polynomial surjective map L' 1 F L' 2 of affine space K n' onto K m' and sends it to Bob. She sends *y to Bob. He checks that G(*y)=c.

So Alice computes2t G= ( 2t g 1 (*z 1 , *z 2 , ..., *z k ), 2t g 2 (*z 1 , *z 2 , ...,* z k ),..., 2t g r-1 (*z 1 , *z 2 , ..., *z k ))=b(2t), 2t H=( 2 h 1 (*z 1 , *z 2 ,..., *z k ), 2 h 2 (*z 1 , *z 2 , ..., *z k ), ..., 2 h k (*z 1 , *z 2 , ..., *z k ))=a(2t),…, 2 G= ( 2 g 1 (*z 1 ,* z 2 , ..., *z k ), 2 g 2 (*z 1 , *z 2 , ..., *z k ),..., 2 g r-1 (*z 1 ,*z 2 , ..., *z k ))=b(2), 2 H=( 2 h 1 (*z 1 , *z 2 ,..., *z k ), 2 h 2 (*z 1 ,* z 2 , ..., *z k ), ..., 2 h k (*z 1 ,* z 2 , ...,* z k ))=a(2), 1 G= ( 1 g 1 (*z 1 , *z 2 , ..., *z k ), 1 g 2 (*z 1 ,*z 2 , ..., *z k ),..., 1 g k (*z 1 ,* z 2 , ..., *z k ))=b(1), 1 H=( 1 h 1 (*z 1 , *z 2 ,..., *z k ), 1 h 2 (*z 1 , *z 2 , ..., *z k ), ..., 1 h r-1 (*z 1 , *z 2 , ..., *z k ))=a(1), - 0 G=( 0 g 1 (*z 1 , *z 2 , ..., *z k ), 0 g 2 (*z 1 , *z 2 , ..., *z k ),..., 0 g r-1 (*z 1 , *z 2 , ..., *z k ))=b(0), 0 H=( 0 h 1 (*z 1 , *z 2 ,..., *z k ), 0 h 2 (*z 1 , *z 2 , ..., *z k ), ..., 0 h k (*z 1 , *z 2 , ..., *z k )))=a(0).

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 L 1 and L 2 of degree 1. Assume that she use only one cellular Schubert graphs s,k CS m (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,k CS m (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>d n 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 I m (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[x 1 , x 2 ,…, x n ] over the selected K. Examples of such platforms can be found in [33], [22].

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/TUOVspec-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[x 1 , x 2 ,…, x n ] (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.