The paper is dedicated to Multivariate Cryptography over general commutative ring K and protocols of symbolic computations for safe delivery of multivariate maps. We consider the iterative algorithm of generation of multivariate maps of prescribed degree or density with the trapdoor accelerator, i.e. piece of information which allows to compute the reimage of the map in polynomial time. The concept of JordanGauss temporal graphs is used for the obfuscation of known graph based public keys and constructions of new cryptosystems. We suggest use of the platforms of Noncommutative Cryptography defined in terms of Multivariate Cryptography over K for the conversion of Multivariate Public Keys into El Gamal type Cryptosystems. Some new platforms are introduced.
K[x1, x2, ..., xn] which sends each variable xi, i = 1, 2, ..., n to a monomial term. Some other protocols of Noncommutative Cryptography with the platform nES(K) are given in [1].
For each positive integer d, d≥2 we present the multivariate map of degree d with the trapdoor
accelerator. In fact we present the iterative process of expansion of initial map F0 which can be a
bijective multivariate nonlinear map of degree at most d on Kn with the trapdoor accelerator T or
an element of general affine group AGLn(K). The input parameters are positive integers m(
Similarly we can take polynomial surjective map F0 of Kn onto Kr of degree at most d with the
trapdoor accelerator T and get the sequence of surjective polynomial multivariate maps of
Kn+m(
So we can use known construction of multivariate cryptography over the general maps with trapdoor accelerators or linear maps on affine spaces for the construction of new maps together with the polynomial algorithm to compute reimage.
We define the density of the multivariate polynomial in n variables as the number of its monomial terms. The density of multivariate map F: (x1, x2, ..., xn) → (f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., f2(x1, x2, ..., xn), ..., fm(x1, x2, ..., xn)) is the maximal value of densities of fi for i = 1, 2, ..., m.
We also will work with the multivariate maps in n variable of unbounded degree and prescribed density O(nλ). Let K* stands for the multiplicative group of K. Assume that K* is nontrivial. We say that multivariate map F of Kn to itself has multiplicative trapdoor accelerator T if the restriction of F onto (K*)n is injective map and the knowledge of T allows to compute the reimage of the element from F((K*)n) in a polynomial time.
For each nonnegative rational number λ we present the explicit constructions of multivariate
maps of density λ with unbounded degree and multiplicative trapdoor accelerator. Additionally we
present the iterative process of the expansion of the selected initial map F0 which is a multivariate
nonlinear map of density O(
The step i, i = 1, 2, ..., k of the algorithm produces the multivariate map Gi of polynomial density
on the Kn+m(
We can use multivariate maps of unbounded degree and prescribed polynomial density with the multiplicative trapdoor accelerator instead of maps of bounded degree in the presented above scheme of access control. We can use the same protocol of Noncommutative Cryptography and the same platform nES(K) of Eulerian transformations. The modification of the deformation rule will be presented.
Let us consider the case of finite commutative ring K of the cardinality O(
It is better then in the case of quadratic map on the space Kn. If density is O(n) we say that we have pseudo quadratic map.
We hope that defined in the paper wide variety of the quadratic or cubic maps with the trapdoor accelerators and the varieties of pseudo-linear, sub quadratic and pseudo quadratic maps with the multiplicative trapdoor accelerators can be effectively used in the presented above scheme of the access control of Information System.
These varieties are defined via the symbolic computations in terms of algebraic graphs defined by the systems of nonlinear algebraic equations over the finite commutative ring K with unity or temporal analogue of these graphs for which generic equations are changeable with the change of time. The sequences of pseudorandom or genuinely random graphs can be used for the change of coefficients in time dependent algebraic equations.
For the design of maps we use Jordan-Gauss graphs which are bipartite graph with partition sets Kn and Km given via quadratic equations such that the neighbourhood of the vertex is the solution set of linear system of equations written in its row-echelon form.
Subsection 2.1 of Section 2 contains basic definitions of affine Cremona semigroup and group of endomorphism of multivariate ring K[x1, x2, ..., xn], endomorphisms with the trapdoor accelerators. It contains the discussion of the area of Multivariate Cryptography over the general finite commutative ring.
In the subsection 2. 2 we define linguistic graphs over the general commutative ring and their temporal analogue. Algorithm 1.2 allows us to construct the variety of elements of Cremona semigroup with the trapdoor accelerator defined in terms of selected linguistic graph or its temporal analogue. Simple conditions insure that the constructive map is bijective transformation of Kn. The method allows us to construct surjective maps of Kn onto Km, n>m≥2 with the trapdoor accelerator. For practical implementation of the algorithm we need select special classes of linguistic graphs which allow us to control the degrees and densities of the outputs. We define the special class of Jordan-Gauss graphs and consider flexible families of generalised Double Schubert graphs DSs,r(K) and truncated Double Schubert graphs QDSs,r(K) which are convenient instruments for generating of families of multivariate maps of prescribed degree on the affine space Kn.
Assume that (F, T) stands for pair multivariate function F of degree d, d≥2 on K n and its trapdoor accelerator. We suggest the method of construction of new pair (F’, T’) of degree d on Kn’, n’>n from the known (F, T). It can be used iteratively. Many constructions of pairs (F, T) over fields can be found in the recent papers on Classical Multivariate Cryptography [2–13].
In Section 3 we introduce semigroup of nES(K) of Eulerian endomorphisms of K[x1, x2, ..., xn] and consider iterative method of construction of multivariate maps of prescribed density O(nd) with the trapdoor accelerators or multiplicative trapdoor accelerators. These maps are constructed in terms of temporal truncated Schubert graphs.
In Section 4 we consider twisted Diffie-Hellman protocol implemented with the platform nES(K) of Eulerian transformations. We introduce several deformation rules convenient for the safe delivery of multivariate maps of prescribed degree or density from one correspondent to his/her partner. We discuss the use of stable subsemigroups of Cremona semigroup nCS(K) as a platform for the protocol. Stability means that the maximal degree of endomorphisms from the semigroup is a constant d.
Section 5 contains conclusive remarks. We have to note that last talk at Eurocrypt conferences was delivered in 2021. It is paper [14] dedicated to cryptanalytic studies. Some studies on Multivariate Cryptography were presented during PQCrypt workshops [15–18].
Let K be a finite commutative ring. It is possible to say that Multivariate Cryptography in a wide sense is about the use of polynomial maps F of affine spaces Kn to itself for cryptographical purposes.
In classical case K=Fq the map F is an element of affine Cremona semigroup nCS(K) of endomorphisms of multivariate ring K[x1, x2, ..., xn]. Endomorphism F can be given by its values F(x1) = f1, F(x2)=f2, ..., F(xn)=fn on the variables xi, i = 1, 2,..., n.
We can assume that polynomials fi are given in their standard form i.e. sum of monomial terms ordered in lexicographical order.
Endomorphism F induces the map F’: x1 → f1(x1, x2, ..., xn), x2 → f1(x1, x2, ..., xn), ..., xn → fn(x1, x2, ..., xn) of the affine space Kn into itself.
We define degree deg(F) as maximal value of deg (fi). The density den fi(x1, x2, ..., xn) is its number of monomial terms. We define density den(F) of F as maximal value of den (fi), i = 1, 2, ..., n and identify endomorphism F with the tuple (f1(x1, x2, ..., xn), f2(x1, x2, ..., xn), ..., fm(x1, x2, ..., xn)).
The image Im F’ is isomorphic to Km for some m, n≥m. We can treat F’ as surjective map of Kn onto Km.
We say that piece of information T is trapdoor accelerator of surjective nonlinear polynomial map F’ of K n onto Km, n≥m if the knowledge of T allows to compute a reimage of given element bϵKm in a polynomial time.
New multivariate cryptosystem “TUOV: Triangular Unbalanced Oil and Vinegar” was officially submitted to NIST recently see https://csrc.nist.gov/csrc/media/Projects/pqc-digsig/documents /round-1/spec-files/TUOV-spec-web.pdf). It is based on the quadratic map defined over finite fields with the trapdoor accelerator.
He hopes that this is the example of one way function, i.e. the reimage of this quadratic map is not possible to compute in a polynomial time without the knowledge of given trapdoor accelerator.
As you know the existence of one way function is not proven. Anyway there is a chance of NIST certification of TOUV as first representative from the class of Multivariate Public Keys.
As you know Multivariate cryptography uses the gap between linearity and nonlinearity. We know that the system of linear equations written over the field F can be solved in time O(n3) via Jordan-Gauss elimination method.
The complexity of solving a nonlinear system of constant degree d, d>1 is subexponential.
Despite the convenience of Groebner basis method for the implementation the complexity of this algorithm is equivalent to old Gauss elimination method for solution of the system of nonlinear equation.
Recall that the standard way to transform of nonlinear system of equation of degree d, d>2 to an equivalent quadratic system via introduction of additional variables and substitutions is well known [19].
So if we have a nonlinear map F of bounded degree d in “general position” which has a trapdoor accelerator T then corresponding cryptosystem is secure. This status is insure the fact that F is given as one way function i.e. reimage of F is impossible to compute in a polynomial time without knowledge of the secret T.
The map F is not in “general position” if some additional specific information is known. For instance, if F is bijective cubic map and F-1 is also cubic. Then public user can generate O(n3) pairs of kind plaintext p/corresponding ciphertext c and approximate inverse map in time O(n10).
Known computer tests and cryptanalytic methods are attempts to justify that map F is “in general position”. Noteworthy that the existence of one way function is not proven yet even under the main complexity conjecture that P≠NP.
Note that the investigation of nonlinear systems of equations over the commutative ring K with zero divisors is essentially harder case in comparison the case of a field.
Multivariate Cryptography over rings with zero divisors can be an interesting direction of cryptographic research.
Below we present the method of construction of nonlinear representatives of affine Cremona semigroup End K[x1, x2,..., xn] where K is a finite commutative ring.
The incidence structure is the set V with the 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 which is of
course a 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 with the unity. 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)
(
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 the incidence graph there exists a 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 a 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 a unique neighbour of the line (p) = Nc([l]) with the colour c. The triples of parameters s, r, m defines type of linguistic graph.
Let Ja(v) stands for the operator of change colour of vertex v (point or line) for a = (a1, a2, ..., at) where t=s or t=r.
We consider also linguistic incidence structures defined by infinite number of equations. Let I(K) and I’(K’) be two linguistic graphs of the same type (s, r, m) with governing polynomials fi and f’i written in their standard forms. We refer to them as symbolically equivalent structures if monomial terms of fi and f’i for each i are the same up to their nonzero coefficients.
We refer to family I(K)t, t = 1, 2, ... of symbolically equivalent linguistic graphs as temporal linguistic graph.
Algorithm 1.2. (Generation of multivariate map F with the trapdoor accelerator [22])
Let us consider linguistic graph mIs,r(K) given by equations (
Let us conduct the following symbolic computation. We consider the special point z = (z) = (z1,
z2, ..., zs, zs+1, zs+2, ..., zs+m) which coordinates are variables, positive integer l and colours a(
So, we compute recurrently v1 = Ja(
Note that fi, i = 1, 2, ..., s are elements of K[z1, z2, ..., zs] but fiϵK[z1, z2, ..., zs, z1+s, z2+s, ..., zm+s].
Assume that map L1 is an element of AGLs+m(K) and L2 is taken from AGLr+m(K) in the case of odd l and L2 ϵAGLs+m(K) if l is even. The bijective polynomial maps L1 and L2 have degree 1. Then we can compute the standard form of the map G=L1FL2.
Proposition 1. 2. [22] Assume that constant l is odd the tuple c defines surjective multivariate
map C from Ks to K r with trapdoor accelerator T and parameters a(i), b(i) and c have degrees of size
O(
Remark 1.2. If K = Fq we can take the pair C, T defined by J. Ding and his team and get a new surjective map G from larger vector space with the trapdoor accelerator.
Proposition 2.2. [22] Assume that l is even or r = s and the tuple c defines bijective multivariate map
C from Ks to Ks with trapdoor accelerator T. Assume that a(i), b(i), c are of size O(
Remark 2.2. Under the condition of Proposition 2 in the case of even l it could be that r>s. Procedure 1.2 (reimage computation).
Alice gets the image e = (e1, e2, ..., et, et+1, et+2, ..., et+m), t = r or t = s of the map G. She creates intermediate vector (z1, z2, .., zs, zs+1, zs+2, ..., zs+m). Alice computes (L2)-1(e) = (d1, d2, ..., dt, dt+1, dt+2, ..., ds+m) = d. She investigates the system of equations c1(z1, z2, ..., zs) = d1, c2(z1, z2, ..., zs) = d2, …, ct(z1, z2, ..., zs) = dt. The knowledge of T allows her to take some solution z1 = α1, z2 = α2, ..., zs = αs. Alice calculates values β(i) = b(i)(α1, α2, ..., αs), γ(i) = a(i)(α1, α2, ..., αs), i = 1, 2, ..., l.
She computes Jβ(l)(d) = vl, Na(l)(vl) = ul, Jβ(l-1)(ul) = vl-1, Na(l-1)(vl-1) = ul-1, …, Jβ(
Alice computes the reimage as (L1)-1(u).
Remark. 3.2. We can define F = F(a(
To control the degrees and densities of F = F(a1, a2, ..., al, b1, b2, ..., bl, c) we need a special class of linguistic graphs over K.
Jordan-Gauss graphs are linguistic graphs given by special quadratic equations over the commutative ring K with unity such that the neighbour of each vertex is defined by the system of linear equation given in its row-echelon form [23–25].
Generalised Double Schubert graph DSs,r(K) (see [22] and [26] and further references) is a
bipartite graph with the points of kind (x) = (x1, x2, ..., xs, x11, x12, ..., xsr) and lines [y] = [y1, y2, ..., yr,
y11, y12, …yst] such that point (x) is incident to [y] if and if the conditions
xij-yij = xiyj
(
Temporal graph DSs,r(K)t is given by equations
i,jα(t)xij-i,jβ(t)yij = i,jγ(t)xiyj (2′) where i,jα(t) and i,jβ(t) are elements of multiplicative group K* and i,jγ(t) are elements of K-{0}.
To form momentum graphs D1 = DSs,r(K)t/t = 1, D2 = DSs,r(K)t/t = 2, ... we can use pseudorandom or random sequences of elements from K* or K-{0} respectively. For the constructions genuinely random sequences Quantum Computer can be used.
Remark 4.2. Graph DSs,r(K), K = Fq is formed by spaces of dimension s and s+1 from two corresponding largest Schubert cells of projective geometry PGs+r(Fq).
In fact many other temporal Jordan-Gauss graphs and their configurations the reader can find in [27]. These constructions are defined in terms of theory of Lie Geometries and their generatisations [28–30].
Proposition 3.2. [22] Let us consider map introduced above map G = L1F(a(
In the case of d = 2, 3 we can use this construction to obfuscate selected multivariate
cryptosystem C, T. In particular we can take as C, T already mentioned quadratic cryptosystem
TUOV (Triangular Unbalanced Oil and Vinegar cryptosystem). We can also introduce enveloping
trapdoor accelerator for Matsumoto-Imai cryptosystem over finite fields of characteristic 2, for the
Oil and Vinegar public keys over Fq. Another quadratic multivariate public keys defined over
Jordan-Gauss graphs D(n, K), where K is arbitrary finite commutative ring with the nontrivial
multiplicative group. It gives us the option to use Proposition 3.2 in the case of arbitrary
commutative ring K [24, 31]. We can obfuscate presented above constructions of multivariate maps
of degree d with the trapdoor accelerator T below via deleting of some coordinates of points and
lines with double indexes together with corresponding equations. It will give us examples of
multivariate maps of prescribed degree with the trapdoor accelerator on arbitrary free module Kn.
Instead of generalised Schubert graph DSs,r(K) with points of kind (x) = (x1, x2, ..., xs, x11, x12, ..., xsr)
and lines [y] = [y1, y2, ..., yr, y11, y12, …, yst] we consider homomorphic image QDSs,r(K) where Q is
selected proper subset of Cartesian product of {1,2, …, s} = N and [1, 2, …, r} = M. We assume that
r = O(s), the projection (i, j) → i maps Q onto N and the projection (i, j) → j maps Q onto M. Let
Q = {α(
Let D1 = DSs,r(K)t/t = 1,D2 = DSs,r(K)t/t = 2, ... stands for the momentum graphs of QDSs,r(K)t .
Proposition 3’.2. [22] Let us consider map introduced above map G = L1F(a(
Corollary. Formulated above proposition allows us to construct multivariate bijective map G of prescribed degree d, d≥2 with the trapdoor accelerator on arbitrary affine space Kn.
We can use the construction of Proposition 3’ iteratively.
Example 1.2. Let us select finite commutative ring K and positive numbers s, m(
1 step. We use Proposition 3’.2 in the case of selected d, temporal Jordan-Gauss graph of type s,
r, s+m(
2 step and iteration. We use Proposition 3’.2 in the case of Jordan graph of type s+m(
We use the tuple c = g(
Procedure 2.2 (reimage computation for (Gk, Tk)).
Assume that Gj = jL1Fj jL2, j = 1,2, ..., k and Fj=F(a(1, j), a(2, j), ..., a(l(j), j), b(1, j), b(2, j), ..., b(l(j),j),
g(j-1), jD1, jD2, ..., jDl(j)) acting on the affine space jW of dimension s+m(
Alice obtained the ciphertext 0c = (0c1, 0c2, ..., 0cn(k)). She computes kL2-1(0c) = kc and takes its projection kc’ on the first n(k-1) coordinates.
Alice computes k-1L2-1(kc’) = k-1c and takes its projection k-1c’ on first n(k-2) coordinates. She
continue this procedure and gets the tuple 1c = (b1, b2, ..., bs, bs+1, bs+2, ..., bs+m(
Alice forms the intermediate tuple (z1, z2, ..., zs) and investigates the system of linear equations
c1(z1, z2, ..., zs) = b1, c2(z1, z2, ..., zs) = b2, ..., cs(z1, z2, ..., zs) = bs. She gets the solution z1 = α1, z2 = α2, …,
zs = αs. Alice computes tuples a*(i, 1) = a(
The tuple (1L1)-1(e(
Alice considers the equation 2L1F2(z1, z2, ..., zs, zs+1, ..., zs+m(
Alice computes the specializations a*(
She computes the point d(l(
The tuple (2L1)-1(e(
Alice continue this recurrent process and gets the solution γ(k) of the equation Gk(z1, z2, zs,
zs+1, ..., zs+m(
Example 2.2. Let us select finite commutative ring K and positive numbers s, r, s≥r, m(
1 step. We use Proposition 3’ in the case of selected d, temporal Jordan-Gauss graph of type s, r,
m(
Let the standard form the map G1 from Ks+m(
2 step and iteration. We use Proposition 3’ in the case of Jordan graph of type s+m(
We use the tuple c = g(
The procedure of reimage computation of Gk is similar to the case of Example 1.2.
Remark 4. 2. (nonlinear disturbance). In both examples instead of linear map C any nonlinear surjective map H of degree at most d with the trapdoor accelerator can be used. In particular one can use quadratic transformations of arbitrary free module Kn presented in [24] and [31]. In the case of Example 2. In case of finite field many classical broken or unbroken multivariate cryptosystem can be used (see [32] and further references).
Let Assume that commutative ring K contains nontrivial multiplicative group K*. Let us consider
the totality nES(K) of endomorphisms of K[z1, z2,..., zn] of kind
z1 → q1z1 a(
It is easy to see that the complexity of the composition of two elements of kind (
The semigroup nES(K) acts naturally on (K*)n and contains large subgroup nEG(K) of bijective transformations of the variety [1].
Recall that we define density den (f) of element f from K[z1, z2, ..., zn] written in its standard form as its number of monomial terms. The density of the tuple H(z1, z2, ..., zn) is defined as maximum of den(hi), i = 1,2, ..., m.
The following statements are proven in [22].
Proposition 1. 3. Let us consider map introduced above map F = F(a(
Remark 1.3. Parameter d can be selected as a rational number.
Corollary 1.3. Let s = r or l is even, r = O(s), m = O(sμ), 1≤μ≤2, H be an element of s+mES(K) and LϵAGLs+m (K) and F satisfies conditions of Proposition 1.3. Then the density of standard form of G = HFL is O(sd+μ) = O((s+m)d/μ+1).
Remark 2.3. We can select L of density O(
Corollary 2.3. Assume that conditions of Corollary 1.3 holds and C = EN, where EϵsEG(K), NϵsCG(K). Then G induces an injective map of (K*)s+m into (K)s+m.
Let Ms(K) = GLs(K)∩sES(K) be the monomial group of linear transformations.
Corollary 3.3. Assume that conditions of Proposition 1.3 hold and HϵMs+m (K) and CϵsCG(K). Then G is a bijective map of Ks+m onto itself.
Formulated above statements allow us to construct element G of nCG(K) of unbounded degree and prescribed density d, d≥O(n) with the trapdoor accelerator.
We define multiplicative trapdoor accelerator (F, T) of F which is the map of density d such that its restriction F’ on (K*)n is injective map and the knowledge of T allows to compute the reimage of F’ in a polynomial time.
Remark 3.3. We can construct multiplicative accelerators (F, T) where FϵnCS(K) has unbounded degree and prescribed density O(nd ), d≥0.
Algorithm 1.3. Public key with the multivariate map G with the multiplicative trapdoor accelerator.
Alice select even parameter l of size O(
She selects parameters n and k = O(n) together with the subset Q = {α(
Alice forms the tuples ai, bi, i = 1, 2, ... l of with coordinates of kind q1z1 a(
The procedure 1 for this step is given below. She takes N of density O(
She select parameters i,jα(t)ϵK*, i,jβ(t) and i,jγ(t) where t = 1, 2, ..., l, (i, j)ϵQ for construction of momentum Jordan-Gauss graphs D1, D2, ..., Dl of the temporary graph QDSs,k(K)t.
Alice will use Dj(K[z1, z2, ..., zs, zα(
She uses symbolic computation in the graph QDSn,k(R)t to construct the transformation F = F(a(
The standard form of G will be used as an encryption tool in the case of the space of plaintexts (K*)n+m.
Alice generates the map via special walks on the graph. The degree of the map G is O(n+m). The density of the map is O(n+m) λ+d/μ.
Thus the complexity of encryption of computation of the image of (p1, p2, ..., pn+m)ϵ(K*)m+n is O(n+m)λ+d/μ+1.
Decryption procedure.
Public user Bob writes his plaintext p = (p1, p2, ..., pm+n) and sends the ciphertext s = G(p) to Alice. Alice decrypts via the following procedure.
She computes L-1(s) = (d1, d2, ..., dn, dα(
E(z1, z2,..., zn) = e1, E(z1, z2,..., zn) = e2, ..., E(z1, z2,..., zn) = en, Alice uses E’ and gets the solution z1 = t1, z2 = t2, ..., zn = tn.
She computes a(i)(t1, t2, ..., tn) = a*i, i = 1, 2, ..., l, b(i)(t1, t2, ..., tn) = b*i, i = 1, 2, ..., l and writes the
system of linear equations F = F(a*(
This system is already written in row-echelon form.
So Alice gets the solution zα(
She forms t = (t1, t2, ..., tn, tα(
Procedure 1.3. Let K be a finite commutative ring with unity and nontrivial multiplicative group K* of order d>1. Assume that parameter n is selected and we have the task of generating two elements E and E’ of nEG(K) such that EE’ and E’E act on (K*)n as identity transformations.
We form the transformation J1 and J2 from nEG(K) of kind
y1 = μ1x1a(
Similarly, she constructs lower triangular and upper triangular bijective transformations JG1 and JG2 from (m+nES(K), (K*)m+n).
So Alice computes H = GJ1 GJ2 and H’ = GJ’2 GJ’1.
In case d = 0 and λ = 0 when the density of a(i), b(i), and L are O(
In the case of d/μ+λ<1 we get sub quadratic cryptosystem. It has complexity better than O(n+m)3.
If d/μ+λ = 1 we obtain a pseudo quadratic cryptosystem.
More general methods of generation of invertible elements of nES(K) can be found in [1].
The family of pseudo quadratic transformations with the trapdoor accelerators based on the modification DSn,k(K) in terms of generalisations of projective geometries was presented in [33].
Corollary 4.3. Let K be a commutative ring with nontrivial multiplicative group K*. Then for each natural n, n>2 we can construct a multivariate map of the prescribed density with the multiplicative trapdoor accelerator.
Recall that G = EQQL induces an injective map of (K*)n+m into Kn+m.
The standard form of G has the trapdoor accelerator Q, E, L, H, N, ai, bi, i = 1, 2, ..., l, T’. We assume that equations of DS(n, K) are known publicly.
Remark 4.3. Note that the map with the trapdoor accelerator of polynomial density O(nd) where d, d ≥2 is a natural number can be obtained as the product of J1 and J2 of Procedure 1 and selected multivariate map F of degree d with the trapdoor accelerator T.
In [34] the first implementation of the scheme of the previous Remark 4.3 was presented in the case of F induced by the special walk on the Jordan-Gauss graphs D(n, K) and A(n, K) for the case when K = Fq, of characteristic 2. Recall that in [24] the special walks of odd length in the JordanGauss graphs D(n, K) of type 1, 1, n-1 were used for the generation of quadratic multivariate map F with the trapdoor accelerator.
In [35] the scheme of remark 4.3 was suggested for the graph-based encryption with D(n, K) and A(n, K) in the case of arithmetical rings Zm.
The point (p) = (p1, p2, …, pn) of the graph D(n, K) is incident with the line [l] = [l1, l2, …, ln], if the following relations between their coordinates hold: l2-p2 = l1p1, l3-p3 = l2p1, l4-p4 = l1p2, li-pi = l1pi-2, li+1-pi+1 = li-1p1, li+2-pi+2 = lip1, li+3-pi+3=l1pi+1 where i≥5.
So the encryption scheme is the following. Let us take graph D(n, K[x1, x2, …, xn]), sequence of
colors d(
Then we have to take sequence x = (x1, x2, …, xn) (point from D(n, K[x1, x2, …, xn])), v1 = Nd(
Let F be the map x1 → v1(x1, x2, …, xn ), x2 → v2(x1, x2, …, xn), …, xn → vn(x1, x2, …, xn). Then deg F = 3.
We consider the map of kind G = J1J2L1FL2 where L1 and L2 are elements of AGLn(K).
In the case of linguistic graph A(n, K) we simply change the incidence condition between points and lines: l2-p2 = l1p1, l3-p3 = p1l2,l4-p4 = l1p3, l5-p5 = p1l4, … ln-pn = l1pn-1 (for even n) or ln-pn = p1ln-1 (for odd n).
Recently we implement the generating process described above map G in the case when K is arithmetic ring Zq, q=232.
Let us denote G as G(n, k, K) in the case when the length of the sequence of colours d(
We have written a program for generating elements and for encrypting a text using the generated public key. The program is written in C++. We use an average PC with processor Pentium 3.00 GHz, 2GB memory RAM, and system Windows 7. We have implemented three cases: 1. L1 and L2 are identities. 2. L1 and L2 are maps of kind z1 → z1+a2z2+a3z3+ … +atzt, z2 → z2, z3 → z3, …, zn → zn, ai ≠ 0, i = 1, 2, …, n (linear time of computing for L1 and L2). 3. L1 = Ax+b, L2 = A1x+b1; matrices A, A1 and vectors b, b1 have mostly nonzero elements. Tables confirm that in Cases 2 and 3 we have multivariate transformations of density O(n3) and global O(n4). So, the encryption process for this map of unbounded degree takes O(n5).
Similarly to Example 1 we can use Proposition 4 iteratively.
Example 1.3. Alice selects finite commutative ring K and positive number s and prescribed degree d.
Step 1. Alice selects even parameter l = l(
She takes parameter k = O(s) together with the subset Q = {α(
deg (a(i)) = α(i), deg b(i) = β(i) and α(i)+β(i) = d(
Alice forms the tuples ai, bi, i = 1, 2, .... l of with coordinates of kind q1z1 a(
She selects the pair of E, E’ϵsEG(K) such that (EE’, (K*)s) and (E’E, (K*)s) are identity
permutations. She takes N of density O(
Alice will use 1Dj(K[z1, z2, ..., zs, zα(
She uses symbolic computation in the graph QDSs,k(R) t to construct the transformation
F = F1 = F(a(
Step 2 and the iteration.
Alice selects parameter k(
Alice will use 2Dj(K[z1, z2, ..., zs+m(
J = 1, 2, ..., l(
She selects tuples a(
She selects L = L2 from AGLs+m(
G2=H2F2L2.
The density of the standard form of the map G2 will be determined as O((s+m(
Alice takes parameters d(
Alice will work with graph Q(
Alice forms tuples a(
She selects the pair of H3, H3’ϵs+m(
The density of the standard form of the map G3 will be determined as O((s+m(
Alice continues the iterative process. She creates G4, G5, ..., Gr of the densities of kind O(n(i)) β(i), i = 4, 5, ..., r where n(i) is the dimension of the space of ciphertexts and β(i) = d(i)/μ(i) with the multiplicative trapdoor accelerators Ti, i =4, 5, ..., r respectively.
So the final map Gr of Ks+m(
Recall that d(i)≥d(i-1)/μ(i-1) for i = 2, 3, ..., r. In the case when these inequalities become
equalities d(r)/μ (r) = d(
Alice can select d(
Note that Alice can take Gr L where L has degree 1 and density O(n) and use the standard form of transformation of density O(nd+1) with the multiplicative trapdoor accelerator.
Procedure 1.3. (reimage computation for (Gr, Tr)). Assume that Gj = HjFjLj, j = 1, 2, ..., r and
Fj = F(a(1, j), a(2, j), ..., a(l(j), j), b(1, j), b(2, j), ..., b(l(j),j), g(j-1), jD1, jD2, ..., jDl(j)) acting on the affine
space jW of dimension s+m(
Alice obtained the ciphertext 0c = (0c1, 0c2, ..., 0cn(r)). She computes Lr-1(0c) = rc and takes its projection rc’ on the first n(r-1) coordinates.
Alice computes Lr-1-1(rc’) = r-1c and takes its projection r-1c’ on the first n(r-2) coordinates. She
continue this procedure and gets the tuples 1c = (b1, b2, ..., bs, bs+1, bs+2, ..., bs+m(
Alice forms the intermediate tuple (z1, z2, ..., zs) and investigates the system of linear equations c1(z1, z2, ..., zs) = b1,c2(z1, z2, ..., zs) = b2, ..., cs(z1, z2, ..., zs) = bs. She gets the solution z1 = α1, z2 = α2, …, zs = αs. In fact (α1, α2, …, αs) = E’(N-1(b1, b2, …, bs)).
Alice computes tuples a*(i, 1) = a(
Alice takes graph 1Dl(
Alice treats the tuple d’(l(
The tuple (H1)’(e(
Alice considers the equation H2F2(z1, z2, ..., zs, zs+1, ..., zs+m(
The first s+m(
Alice computes the specializations a*(
She computes the point d(l(
The tuple (H2)’(e(
Remark 5.3. (nonlinear disturbance). In this iterative algorithm instead of the combination EN on Ks one can take any pseudolinear map Z with the multiplicative trapdoor accelerator at most d with the trapdoor accelerator can be used.
The following protocol is one of the classical instruments of Noncommutative Cryptography.
Twisted Diffie-Hellman protocol.
Similarly, let S be an abstract group which has some invertible elements.
Alice and Bob pose common element gϵS and the pair of invertible elements h, h -1 from this semigroup.
Alice selects natural numbers k(A) and r(A), and she forms h-r(A)gk(A)hr(A) = gA.
Bob chooses k(B) and r(B), and he forms h-r(B)gk(B)hr(B) = gB.
They exchange gA, gB and compute the collision element X as Ag = h-r(A)gBk(A)hr(A) (Alice) and Bg = h-r(B)gAk(B)hr(B) (Bob) respectively.
The security of this scheme is based on the complexity of the Power Conjugacy Problem, the adversary has to solve the equation h-xgyhx = b, where b coincides with gB or gA. The complexity of this problem essentially depends on the choice of highly noncommutative platform S.
In the case of platform S = nES(K) where K = Fq or K = Zq this problem is intractable even with the use of a quantum computer.
The computational complexity of this protocol is O(n3).
If we assume that the degree of transformations h and g from nES(K) is O(
Other platforms defined in terms of multivariate cryptography and corresponding protocols readers can be found in [22, 36–41].
Foundations of Noncommutative Cryptography, description of algorithms and cryptanalytic results reader can find in [42–62].
Let F be the map from (K*)n in Kn of density O(nd), 0≤d≤1 such that its restriction on (K*) n is injective. Assume that T is a multiplicative trapdoor accelerator of F and Alice has the pair (F, T).
Below please find examples of the deformation.
Example 1.4. (the case of maps of unbounded degree).
Alice and Bob conduct Twisted Diffie-Hellman protocol based on the platform nES(K). Assume
that the collision map C is given by formula (
Let jg(C) be an element of nES(K) generated as a product of characters of the wj(C). We form jh(C) sending xi to jg(C )(xi)a(i, j) where a(i, j) are publicly known elements of K-{0}.
Let G(C) be the sum 1h(C )+2h(C)+... rh(C).
Alice can send the tuple (F(x1)+G(C) (x1), F(x2)+G(C)(x2), ...
F(xn)+G(C)(xn)) to Bob. He is able to restore the map F.
This “steganographic” way of safe delivery of the multivariate map is secure even in the case r is a linear expression from n of size O(n).
Example 2.4. (the case of nonlinear transformation of constant degree d).
Alice takes the collision element C and nonempty subsets of {1, 2, ..., n} of kind {i(
She form gi as the linear combination of monomial terms (qi(
Remark 1.4. Assuming that the map F of degree O(n) is not given publicly, Alice and Bob use it in a protocol-based secure way.
An adversary may intercept a polynomial number of pairs of kind plaintext/ciphertext but even this information can be insufficient for restoration of F without the knowledge of the symbolic type of Z, i.e. lists of nontrivial monomial terms of F(xi) with coefficients 1.
Remark 2.4. It is known that a polynomial system of equations of degree d(n) can be rewritten as a system of quadratic equations via the method of introducing extra variables. If the degree is unbounded then the growth of the number of variables does not allow for investigating the resulting quadratic system. In case when the system is not given publicly the method of degree reduction can not be used.
The technique of Jordan-Gauss graphs and their temporal analog defined over arbitrary commutative ring K can be used for the construction of bijective multivariate map F of prescribed degree d on free module Kn with the trapdoor accelerator T which allows computing the reimage of the given value in a polynomial time. In the case of d = 2 and 3 such maps can be used for the construction of public keys.
If d is a constant larger than 3 we can construct sparse maps of density O(n) with the trapdoor accelerator T. So the value of the function can be computed in time O(n2). For each constant d, we can construct the map of degree d, density O(n), and trapdoor accelerator which allows the computation of the reimage in time O(n2). Recall that we define the density of F as the maximal density of polynomials F(xi) for i = 1, 2, ..., n.
It is known that there is a special way to increase the number of variables and rewrite the nonlinear system F(x)=b as equivalent to it quadratic system in many variables. One can select “sufficiently large” d such that the corresponding quadratic system is unfeasible for cryptanalytic investigation.
We define sup(t) of the monomial term t = t(x1, x2, ..., xn) as the number of variables xi in positive power in the expression of t. The support of the multivariate map F is defined as the maximal value of sup(F) supports its monomial terms. We can construct multivariate maps on Kn with the prescribed density O(nα), 0≤α≤1, and prescribed support O(nβ) with the trapdoor accelerator. We construct multivariate map F of unbounded degree with the support n and prescribed density O(nβ) and multiplicative trapdoor accelerator.
Mentioned above pairs of kind (F, T) can be investigated as potential public key constructions of multivariate Cryptography. Alternatively, Alice can use her pair (F, T) in a different way. She and her trusted partner Bob can use twisted Diffie-Hellman protocol with the platform nES(K), and deform the output E via its transformation to polynomial transformation D(E) of Kn. Alice sends F+D(E) to Bob. The security of this asymmetric algorithm described in Section 1 rests on the security of the selected protocol.
Note that the mentioned above pairs (F, T) can be used as stream ciphers when the knowledge of T is shared between Alice and Bob.
This research is partially supported by the British Academy Fellowship for Researchers under Risk 2022.
While preparing this work, the authors used the AI program Strike Plagiarism to search for
possible plagiarism. After using this tool, the authors reviewed and edited the content as needed
and took full responsibility for the publication’s content.
[23] V. Ustimenko, O. Pustovit, Jordan-Gauss graphs and quadratic public keys of multivariate
cryptography, in: ITTAP 2024, 4th International Workshop on Information Technologies:
Theoretical and Applied Problems, vol. 3896, 2024.
[24] V. Ustimenko, T. Chojecki, A. Wróblewska, On the Jordan-Gauss graphs andmultivariate
public keys, in: IACR Cryptol. ePrint Arch., 2024/1793.
[25] T. Chojecki, et al., On affine forestry over integral domains and families of deep Jordan-Gauss
graphs, Eur. J. Math. 11(
Discret. Math. 30(
Information Security, Springer, 2020. doi:10.1007/978-1-0716-0987-3 [33] V. Ustimenko, O. Pustovit, On Schubert cells of projective geometry and pseudo-quadratic public keys of multivariate cryptography, in: Cybersecurity Providing in Information and Telecommunication Systems II, vol. 3826, 2024, 198–205. [34] V. Ustimenko. O. Pustovit, On the implementations of new multivariate public keys based on transformations of linear degree, in: Proceedings of the Conference on Mathematical Foundations of Informatics MFOI 2919. [35] V. Ustimenko, On new multivariate cryptosystems based on hidden Eulerian equations,
Dopovidi of National Academy of Science of Ukraine N5, 2017.
[36] V. Ustimenko, A. Wroblewska, On the key exchange with nonlinear polynomial maps of stable
degree, Annalles UMCS Informatica AI XI, 2 (2011) 81–93.
[37] V. Ustimenko, On short digital signatures with Eulerian transformations, IACR e-print archive,
2024/001.
[38] V. Ustimenko, On the restoration of historical matsumoto-imai cryptosystem and other
schemes in terms of noncommutative cryptography, in: Future Technologies Conference (FTC)
2024, vol. 2, FTC 2024, Lecture Notes in Networks and Systems, vol. 1155.
doi:10.1007/978-3031-73122-8_7
[39] V. Ustimenko, M. Klisowski, On noncommutative cryptography with cubical multivariate
maps of predictable density, in: Intelligent Computing, CompCom 2019, Advances in
Intelligent Systems and Computing, vol. 998, 2019, 654–674.
[40] V. Ustimenko, M. Klisowski, On new protocols of noncommutative cryptography in terms of
homomorphism of stable multivariate transformation groups, Algebra Discrete Math. 35(