We suggest two families of multivariate public keys defined over arbitrary finite commutative ring K with unity. The first one has a quadratic multivariate public rule, this family is an obfuscation of previously defined cryptosystem defined in terms of well-known algebraic graphs D(n, K) with the partition sets isomorphic to Kn. Another family of cryptosystems uses the combination of Eulerian transformation of K[x1, x2, ..., xn] sending each variable xi to a monomial term with the quadratic encryption map of the first cryptosystem. The resulting map has an unbounded degree and the density O(n4) like the cubic multivariate map. The space of plaintexts of the second cryptosystem is the variety (K*)n and the space of ciphertexts is the affine space Kn.
This paper presents the generalization of the quadratic multivariate public key given in [1] with the use of quantum computing.
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 standardization best known quantum-resistant algorithms of asymmetrical cryptography. The first round was finished in March 2019, and essential parts of the presented algorithms were rejected. At the same time, the development of new algorithms with a postquantum perspective was continued. A similar process took place during the 2nd, 3rd, and 4th rounds.
The last algebraic public key “Unbalanced Oil and Vinegar Rainbow like digital signatures” (ROUV) constructed in terms of Multivariate Cryptography was rejected in 2021 (see [2, 3]). Certain hopes of algebraists are connected with so-called Noncommutative Cryptography which is based on problems connected with the studies of algebraic objects such as groups, semigroups, noncommutative rings, and algebras. Presented on Mist tender single algorithms from this class based on braids group was broken. The first four winners of this competition were announced in 1922, they are developed in terms of Lattice Theory.
Noteworthy that the NIST tender was designed for the selection and investigation of public key algorithms and in the area of Multivariate Cryptography only quadratic multivariate maps were investigated. So, a large class of protocol-supported asymmetric algorithms of El Gamal type was eliminated. We were working on the design of the new algorithms from this class during our project. We have to admit that general interest in various aspects of Multivariate Cryptography was connected with the search for secure and effective procedures of digital signature where mentioned above ROUV cryptosystem was taken as a serious candidate to make the shortest signature.
Let us summarize the outcomes of the mentioned above NIST tender.
Five categories were considered by NIST in the PQC standardization (the submission date was 2017; in July 2022, the four winners and the four 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 four different mathematical problems (not the five announced at the beginning):
0000-0002-2138-2357 (V. Ustymenko); 0000-0002-3294-2794 (T. Chojecki); 0000-0001-9724-4586 (A. Wróblewska) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The standards are to be published in 2024. But already at the end of round 3, the last candidate (“Rainbow”) from the multivariate cryptography (MVC) category was out.
Its interesting obfuscation “TUOV: Triangular Unbalanced Oil and Vinegar” was presented to NIST [39] by principal submitter Jintaj Ding.
Further development of Classical Multivariate Cryptography which studies quadratic and cubic endomorphisms of Fq[x1, x2, …, xn] see [6–18]. Current research in Postquantum Cryptography can be found in [35–38].
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(n2). 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 [4, 5].
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 transformations in the case of finite fields and arithmetical rings Zq where q is a prime power. Additionally, we create a public key as a composition of quadratic σ with the Eulerian transformation sending each x1 to a monomial term. The public map has an unbounded degree and density O(n4). So the complexity of encryption is as in the case of classical cubic maps.
The missing definitions of graph-theoretical concepts which appear in this paper can be found in [19–21]. 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 vertices 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 vertices u and v (or neighbors).
We refer to |{x ϵ V(G)|xGv}| as the degree of the vertex v.
The incidence structure is the set V with partition sets P (points) and L (lines) and symmetric binary relation I such that the incidence of two elements implies that one of them is a point and another one is a line. We shall identify I with the simple graph of this incidence relation or bipartite graph. The pair x, y, x ϵ P, y ϵ L such that x I y is called a flag of incidence structure I.
Let K be a finite commutative ring. We refer to an incidence structure with a point set P = Ps,m = Ks+m and a line set L = Lr,m = Kr+m as linguistic incidence structure Im 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+s] 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 xs+1, y1, y2, …, yr, yr+1) … amxs+m-bmyr+m = fm (x1, x2, …, xs, xs+1, …, xs+m-1, y1, y2, …, yr, yr+1, …, yr+m-1)
where aj, and bj, j = 1, 2, …, m are not zero divisors, and fj are multivariate polynomials with coefficients from K (see [22, 23]). Brackets and parenthesis allow us to distinguish points from lines.
The color ρ(x) = ρ((x)) (ρ(y) = ρ([y])) of point (x) (line [y]) is defined as the 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 the incidence graph there exists a unique neighbor of a chosen color.
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 color of the point and the color of the line respectively. For each b ϵ Kr and p = (p1, p2, …, ps+m) there is a unique neighbor of the point [l] = Nb(p) with the color b. Similarly for each c ϵ Ks and line l = [l1, l2, …, lr+m], there is a unique neighbor of the line (p) = Nc([l]) with the color c. The triples of parameters s, r, and m define the type of linguistic graph.
We consider also linguistic incidence structures defined by the infinite number of equations.
Linguistic graphs are defined up to isomorphism. We refer to written above equations as canonical equations of linguistic graphs. We consider also linguistic incidence structures defined by the infinite number of equations. Linguistic graphs are defined up to isomorphism. We refer to written above equations as canonical equations of linguistic graphs.
We say that linguistic graph is a Jordan-Gauss type if the map [(x), [y]] → (f1 (x1, x2, …, xs, y1, y2, …, yr), f2 (x1, x2, …, xs, xs+1, y1, y2, …, yr, yr+1), …, fm-1 (x1, x2, …, xs, xs+1, …, xs+m-1, y1, y2, …, yr, yr+1, …, yr+m-1)) where (x)ϵKs+m, [y]ϵKr+m is a bilinear map into K1. So all fi are special quadratic maps. In the case of Jordan-Gauss graphs, the neighborhood of each vertex is given by the system of linear equations written in its row—echelon form.
Let Im be a linguistic graph defined over the commutative ring K. For each bϵ Kr and p = (p1, p2, …, ps+m) there is the unique neighbor of the point [l] = Nb(p) with the color b. Similarly, for each c ϵ Ks and line l = [l1, l2, …, lr+m] there is the unique neighbor of the line (p) = Nc([l]) with the color c. We refer to the operator of taking the neighbor of vertex accordingly chosen color as neighborhood operator.
On the sets P and L of points and lines of the linguistic graph we define jump operators 1J = 1Jb(p) = (b1, b2, …, bs, p1, p2, …, ps+m), where (b1, b2, …, bs) ϵ Ks and 2J = 2Jb([l]) = [b1, b2, …, br, l1, l2, …, lr+m], where (b1, b2, …, br) ϵ Kr. We refer to tuple (s, r, m) as the type of the linguistic graph I.
We say that point (p) is a line [l] adjacent in the linguistic graph I if 1Jb(p)I 2Jc[l] for some colors b ϵKs and c ϵKr. Let ψ stand for the adjacency relation of the linguistic graph. We say that the linguistic graph has degree d, d≥2 if the maximal degree of nonlinear multivariate polynomials fi, i = 1, 2, …, m is d.
Noteworthy, that the path v0, v1, …, vk in the linguistic graph Im_ is determined by starting vertex v0 and colours of vertexes v1, v2, …, vk such that ρ(vi) ≠ ρ(vi+2) for i = 0, 1, …, k-2.
Let us consider the sequence of colours c(
Let v0 = (x) be a general point of the graph I then for
the vertices v1 = 1Jc(
We consider the tuple of colors c(
We refer to the sequence of vertexes v1 = 1J(v0),
v2 = Nc(
For each positive integer l, we can consider graph Im(K) together with lIm = Im(K[y1, y2, …, yl]) defined by the same polynomials fi, i = 1, 2, …, m with coefficients from K.
Assume that l = m+s. We can consider the walk on
the adjacency graph ψ(K[y1, y2, …, yl]) of length 4t+1
with starting point (y1, y2, …, ys, ys+1, ys+2, …, ym+s) and
colours c(
Assume that c(t) = (h1(y1, y2, ..., ys), h2(y1, y2, …, ys), …, hs(y1, y2, …, ys)).
Then v1 = (h1, h2, …, hs, g1, g2, …, gm). Let us consider the polynomial map I(K),c Pass, cϵ K[x1, x2, …, xs] (2t+1)s+2rt of K s+m to itself which sends (y1, y2, …, ys, ys+1, …, ys+m) to vt, i. e. the map
y1 → h1(y1, y2, ..., ys), y2 → h2(y1, y2, ..., ys), …, ys → → hs(y1, y2,...,ys),
ys+1 → g1(y1, y2, ..., ys, ys+1, ys+2, ..., ys+m), ys+2 → → g2(y1, y2, ..., ys, ys+1, ys+2, ..., ys+m), …, ys+m → → gm(y1, y2, ..., ys, ys+1, ys+2, ..., ys+m).
It is easy to see that this transformation is bijective if and only if the map y1 → h1(y1, y2, ..., ys), y2 → h2(y1, y2, ..., ys), …, ys → hs(y1, y2, ..., ys), is bijective on Ks [24]. Defined above transformations form a semigroup I(K)SP of multivariate transformation. Some basic properties of this semigroup are discussed in [24].
Of course, we can use lines instead of points and define another semigroup I(K)SL formed by transformation of kind I(K), cPass, cϵ K[x1, x2, …, xs] (2t+1)r+2 ts acting on the variety Km+r.
Remark. We may omit some operators of kind Jc(i) making the color c(i) to be the same as c(i – 1).
We can treat the sequence c from K[x1, x2, …, xs]l as the tuple of its coordinates ci from K[x1,x2,…, xs] and define the degree of c as polynomials ci(x1, x2,…, xs).
In [25] special Jordan-Gauss graph JG(r, s, m, Fq), q = 2t, t>1 was used for the construction of the public key. This linguistic graph of type (r, s, m) is obtained from the projective geometry PGn(Fq), i.e. the totality of nonzero proper subspaces of (Fq)n+1. The corresponding bipartite graph is obtained as an induced subgraph of bipartite incidence graph with the partition sets which are largest Schubert cells, i.e. largest orbits of UTn(Fq) acting on l dimensional subspaces and subspaces of dimension t, l ≠ t.
Cubic public keys defined in [26U, Ch, K] used Jordan-Gauss graphs A(n, Fq) [27] and D(n, Fq) [28]. These two families of graphs were used in [1] for the construction of a quadratic public key. This paper also contains the construction of trapdoor accelerator T of quadratic endomorphism σ of K[x1, x2, …, xn] acting bijectively on Kn and defined in terms of graph D(n, K) where K is an arbitrary commutative ring with unity [23].
The description of the generalization of this construction is given below.
Affine root system Ầ1 (A1 with wave see [29]) is the
totality of vectors in the two-dimensional Euclidean space
R2 with the standard basis e1 = (
We modify Ầ1 by adding copies (i, i)’ for each imaginary root (i, i), i >1. So we obtain a set Root consisting of roots of Ầ1 and elements (i, i)’, i>1.
Let R1 = Root—{(
We write an element X = (x) from P = L1 as the tuple (x) = (x1,0, x1,1, x1,2, x2,1, x2,2, x’2, 2, …, xi, i+1, xi+1,i, xi+1,i+1, x’i+1, i+1, ...) where xα is the value of X on the root α from Ầ1 and x’i,i is the value of X on (i, i)’, i>1.
Similarly we write an element Y = [y] from L = L2 as the tuple
[y] = [y0,1, y1,1, y1,2, y2,1, y2,2 y’2,2, …, yi,i+1, yi+1,i, yi+1,i+1, y’i+1, i+1, …] where yα is the value of Y on the root α from Ầ1 and y’i,i is the value of Y on (i, i)’, i>1. We introduce the incidence structure (P, L, I) as the following bipartite graph on P U L.
A point (x) of this incidence structure I is incident
with a line [y], i.e. (x)I[l], if their coordinates obey the
following relations:
xi, i, – y i, I = x1,0 yi-1,i,
x’i,i – y’i,i=xi, i-1y0,1, (
(These four relations are well defined for i>1, x1,1 = x’1,1, y1,1 = y’1,1).
We start the description of the connectivity invariants of D(k, K).
To facilitate notation in the future results on “connectivity invariants” of D(n, K), it will be convenient for us to define x-1,0 = y0,-1 = y1,0 = = x0,1 = 0, x0,0 = y0,0 = -1, x’0,0 = y’0,0 = -1, x1,1 = x’1,1, y1,1 = y’1,1 and to assume that our equations are defined for i≥0.
Graphs CD(k, K) with k≥6 were introduced in [23], as
induced subgraphs of D(k, K) with vertices u satisfying
special equations a2(u) = 0, a3(u) = 0, …, at(u) = 0,
t = [(k+2)/4], where u = (uα, u1,1, u1,2, u2,1, …, ur,r, u’r,r, ur,r+1,
ur+1, r, …), 2≤r≤t, α ϵ {(
We set a = a(u) = (a2, a3, …, at) and assume that D(k, K) = CD(k, K) if k = 2, 3, 4, 5. As it was proven in [23] graphs D(n, K) are edge transitive. So their connected components are isomorphic graphs.
Let vCD(k, K) be a solution set of the system of equations a(u) = (v2, v3, …, vt) = v for certain vϵ Kt-1. It is proven that each vCD(k, K) is the disjoint union of some connected components of graph D(n, K).
If K is a commutative ring with unity of odd characteristic then vCD(k, K) is the actual connected component of the graph (see [30]).
If K is a finite field of even characteristics of order ≥ 8 then vCD(k, K) is the actual connected component of the graph (see [31]).
Let us consider the following graphs DT(k, K)
associated with D(n, K) and subset T = {j(
Delete coordinates of points and lines indexed by roots (i(l), i(l))’, l = 1, 2, ..., s together with corresponding equations of kind x’i(l),i(l) -y’i(l), i(l) = ..., = 1, 2, ..., s.
Substitute equations xi(l)+1,i(l) – yi(l)+1,i(l)=x1.0y’i(l), i(l) by xi(l)+1,i(l) – yi(l)+1,i(l)=x1.0yi(l), i(l). the last action is just a deletion of the prime symbol on the righthand side of the equation.
Proposition. Graphs DT(k, K) are Jordan-Gauss graphs of type (1, 1, n-m-1) where m is a cardinality of T.
Polynomials ai(v) where 1<i<j(
Let G be a t-regular simple graph and v be the vertex from V(G). We say that k is the local depth of the vertex v if the induced graph of all vertices at distance ≤k is a tree and the graph on vertices at the distance k+1 has a cycle.
The depth of G is the maximal local depth.
Computer simulation supports the conjecture that the depths of graphs D(k, K) and DT (k, K) are the same. It is known that the depth of D(k, K) is at least [(k+3)/2].
Let us renominate the coordinates of points and line of DT (k, K) with one variable index i according to the lexicographical order on roots of Ầ1. So we have point (x1, x2, ..., xk-m) and line [y1, y2, ..., yk-m] of linguistic graph.
We take the “symbolic” line [y1, y2, ..., yk-m] of this graph and consider the infinite graph DT (k, K[y1, y2,..., yk-m]). We use the presented above technique to associate with this graph the polynomial transformations acting on K, but slightly modify the procedure.
Let ℾ(n, K), n=k-m be one of the graphs DT (k, K). The graph ℾ(n, K) has so-called linguistic coloring ρ of the set of vertices. We assume that ρ(x1, x2, …, xn) = x1 for the vertex x (point or line) given by the tuple with coordinates x1, x2,…, xn. We refer to x1 from K as the color of vertex x.
Recall that Na and Ja are operators of taking the neighbor with color a and jump operator changing the original color of point or line for new color a from K.
Let [y1, y2, …, yn] be the line y of ℾ(n, K[y1, y2, …, yn])
and (ᾳ(
Assume that v = 2tv = [v1, v2, …, vn] where vi are from
K[y1, y2, …, yn]. We consider polynomial transformation
g(ᾳ(
It is easy to see that g(ᾳ(
The following statements are formulated in [1] in the case of graph D(k, K) but they hold for arbitrary graph DT (k, K).
Proposition 1. Transformations of kind g = g(ᾳ(
Lemma 1. The degree of transformation g of the
Proposition 1 is at least
[deg(ᾳ(
Proposition 2. Transformations of kind ng = g(ᾳ(
Remark 1. The inverse element of ng = g(ᾳ(
Remark 2. In the case of two quadratic transformations of Kn of “general position,” their composition will have degree 4.
We associate with the sequence ᾳ(
Theorem 1. Let K be the finite field Fq, q = 2r, r>1.
Then transformation h = h(ᾳ(
We use the modifications of transformation Theorem 1 for the construction of quadratic public keys.
Algorithm 1. Alice selects commutative ring K with
unity and K* of order >2 together with parameters k, m.
She selects T = {j(
Alice selects two transformations L1 and L2 from the
group AGLn(K). She takes t = O(n), 2<t <[(n+3)/2] and
selects the parameters α1, α2 = α1+d(
where dϵK*, d’ϵK*, r = 2 if the order of K* is odd, r = 1 if K* has even order, and elements λi, λ, μi, and μ can be arbitrary elements from K.
She has to select β* as a nontrivial multivariate polynomial of degree 2.
Alice uses the transformation h = H(ᾳ(
Alice sends the multivariate polynomials gi to Bob via the open channel. He will use it to encrypt the plaintext from Kn.
Private Decryption Procedure. Let us assume that Alice gets the ciphertext c from Bob.
At the beginning, Alice forms an intermediate tuple L1(p) = [y1, y2, ..., yn] and treats its coordinates as variables yi.
She computes the vector b = (L2)-1(c ) = (b1, b2, ..., bn).
She forms the tuple (ᾳ(t), b2, b3, …, bn) = u and
computes invariants ai(u) for i = 2, 3, …, i(
She solves d((d’y1+t(
She computes β*(t-1) = y*1+c(t-1), β*(t-2) = =
y*1+c(t2), …, β*(
Alice computes Nβ*(t-1)(u) = 1u, Nα(t-2)(1u) = 2u , Nβ*(t-2)( 2u) = 3u,
Nα(t-3)(3u)=4u, …, Nβ*(
She computes the plaintext [p] as (L1)-1(y*).
x2 …, xn] and cryptosystems of post quantum cryptography
Affine Cremona Semigroup nCS(K) is defined as an endomorphism group of polynomial ring K[x1, x2, ..., xn] over the commutative ring K. It is an important Cremona object of Algebraic Geometry (see Max Noether paper [32] about Mathematics of Luigi Cremona who was the prominent figure in Algebraic Geometry in the XIX century, [33] and further references on papers which use the term affine Cremona group). Element of the semigroup σ can be given via its values on variables, i.e. as the rule xi → fi(x1, x2, …, xn), i = 1, 2,…, n. This rule induces the map σ’: (a1, a2, ..., an) → (f1(a1, a2,.., an), f2(x1, x2, …, xn), …, fn(x1, x2, …, xn)) on the free module Kn. Automorphisms of K[x1, x2, ..., xn] form affine Cremona Group nCG(K).
Let nES(K) stands for the semigroup of all
endomorphisms of K[x1, x2, …, xn] of kind
x1 → ϻ1x1 a(
We consider the natural action of Eulerian semigroup nES(K) on the set nE(K) = (K*)n. Let nEG(K) stand for the Eulerian group of invertible transformations from nES(K). They act as bijective maps on the variety (K*) n.
We can use the following method of generating invertible elements.
Let π and δ be two permutations on the set {1, 2, ..., n}. Let us consider a transformation of (K*)n, d = |K*|. (the most important cases are K = Zm or K = Fq). We define transformation AJG(π, δ), where A is a triangular matrix with positive integer entries 0≤a(i,j)≤d, i≥j defined by the following closed formula.
yπ(
So Alice can generate the element J as a product of several Jordan Gauss transformations. The simplest case in the spirit of LU factorization is the composition of lower and upper triangular transformations.
The cryptosystem is the following procedure.
Alice can select several Jordan-Gauss transformations J1, J2, …, Jd, d>1 from mEG(K) and compute their product J. One of the options is to send J to public user Bob. It looks like the security of such a cryptosystem depends on the choice of commutative ring K (see [34]).
We suggest the following use J as a public rule. Public user works with the space of plaintexts (K*)m.
The idea to use polynomial map F of bounded degree with the trapdoor accelerator T is used in [dop], [arch] for the construction of multivariate public key in the case of special rings K = Fq and K = Zq. These schemes use cubic endomorphism F of K[x1, x2, ..., xn] with the trapdoor accelerator T defined in terms of graphs D(n, K) (or their homomorphic images A(n, K)). We suggest the following modification of these algorithms.
Alice selects the finite commutative ring K with unity.
She selects parameter n to work with the
endomorphisms of K[x1, x2, ..., xn]. Alice takes positive
integer d = O(
Alice takes parameters m and k such that n = m-k. She selects graph DT(m, K) such that T contains k elements.
Alice chooses affine and transformations L1 and L2 from
AGLn(K). She forms ᾳ(
She computes the standard form F of JG which has linear degree O(n) and density O(n4).
Alice sends F to public user Bob.
Correspondents Alice and Bob use the variety (K*)n as the space of plaintexts and a free module (K)n as the space of ciphertexts.
Bob writes the plaintexts p = (p1, p2, ..., pn) in the alphabet K*. He sends the ciphertexts c = F(p) to Al ice.
Alice computes u = G-1 (c) according to her private decryption procedure of Algorithm 1. Noteworthy that u is an element of (K*)n.
Alice computes consequtively du = Jd(u), d-1u = Jd-1(du), ..., 1u = J1(2u) = p.
Multivariate Cryptography in a wide sense is about constructions and investigations of Public Keys in the form of nonlinear Multivariate rules defined over some finite commutative ring K.
This rule F has to be written as transformation xi → fi, i = 1, 2, ..., n, fi ϵ K[x1, x2, ..., xn] over the commutative ring K. Bijective F can be used for the encryption of tuples (plaintexts) from the affine space Kn. Multivariate rules can serve as instruments for the creation of digital signatures. In the case of bijective transformation, the decryption process can be thought of as an application of inverse rule G. The degree of G can be defined as the maximum of degrees of polynomials G(xi), i = 1, 2, ..., n. For the usage of given publicly, F as an efficient and secure instrument its degree of has to be bounded by some constant c (traditionally c = 2) but the polynomial degree of the inverse G has to be high.
The key owner (Alice) is supposed to have some additional piece S of private information about pair (F, G) to decrypt ciphertext obtained from the public user (Bob). Recall that the family Fn, n = 2, 3, ... from K[x1, x2,..., xn] has trapdoor accelerator nS if the knowledge of the piece of information nS allows to compute reimage x of y = Fn(x) from Kn in time O(n2). Of course, the concept of trapdoor accelerator is just an instrument to search for practical trapdoor functions. As you know the existence of theoretical trapdoor functions is just a conjecture. It is closely connected to the Main Conjecture of Cryptography about the fact that P ≠ NP.
Without the knowledge of Sn one has to solve a nonlinear system of equations which generally is an NPhard problem. The finding of the inverse for Fn is an NPhard problem if these maps are in the so-called “general position”. In the case of specific maps additional argumentation of the complexity to find inverses Gn can be useful.
We present such heuristic arguments in the case of DT(n, K) based encryption defined for arbitrary commutative ring K with unity with at least 3 elements and presented in the previous section. Subset T can be viewed as part of the corresponding trapdoor accelerator nS.
Graphs DT(n, K) have partition sets Kn (set of points and set of lines), and the incidence relation between points and lines is given by the system of linear equations over K.
To define the trapdoor accelerator for standard forms Fn, n = 2, 3, ... we use special walks on graphs DT(n, K) and DT(n, K[x1, x2, ..., xn]). The constructed map Fn acts on the selected partition set Kn. In the case of trivial affine transformations L1 and L2 the relation Fn(x) = y for x = (x1, x2, ..., xn) and y = (y1, y2, ..., yn) vertices x and y are joint in the graph DT(n, K) by the path of length >cn, where c is positive constant.
Finding the path will give us the trapdoor accelerator for the computation of preimages. This can be done by the Dijkstra algorithm of complexity O(v ln(v)) where v is the order of graphs. It could not be done in polynomial time because v = 2|K|n and |K|≥3. Noteworthy that the usage of nontrivial L1 and L2 will complicate the cryptanalysis.
Noteworthy that any nonlinear system of multivariate equations of of constant degree d over a finite field can be rewritten as a quadratic system with extra variables.
Studies of quadratic multivariate public rules over finite rings with zero divisors is an interesting task for cryptanalysts. Arithmetical rings modulo 2s is an important practical task because several natural alphabets for the presentation of files in informatics have size which is the power of 2. We are looking for the K-theory of multivariate cryptography and presenting the public rule defined over a general finite commutative ring with unity.
We believe that studies of multivariate public rules of polynomial degree in variable n and the polynomial density are also interesting areas of research.
So we present a new cryptosystem from this area obtained via the composition of the Eulerian map of unbounded degree O(n) with the constructed quadratic endomorphism of K[x1, x2, ..., xn] with the trapdoor accelerator.
This research is supported by the British Academy Fellowship for Researchers under Risk 2022 and by the British Academy Award LTRSF\100333 and UMCS MiniGrants.