Let us assume that one of two trusted parties (administrator) manages the in-formation system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user's access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly construct a cryptographically strong session key that can serve for the establishment of secure passwords in the form of tuples in certain alphabet during the certain time interval. Nowadays selected protocol has to be postquantum secure. We propose the implementation of this scheme in terms of Symbolic Computations. The key exchange protocol is one of the key exchange algorithms of Noncommutative Cryptography with the platform of multivariate transformation of the affine space over selected finite commutative ring. The session key is a multivariate map on the affine space. Platforms and multivariate maps are constructed with the use of algebraic constructions of expanding graphs of large girth.
over the finite commutative ring. Traditionally MC uses systems of equations of degree 2 or 3 defined over the finite field see [5]. Despite the fact that the last talk on Multivariate Cryptography on Eurocrypt conferences was in 2021 (see [6]) many new results in this area were obtained (see Proceedings of PQCrypts 2021-2024) and new cryptosystem [7] were submitted to NIST (USA).
Classical task of Multivariate Cryptography is the constructions of public keys in the form of multivariate maps of small degree over finite fields see ([22]-[38]). We consider more general task of construction of nonlinear multivariate map F on affine space Kn where K is a commutative ring with unity with the trapdoor accelerator T which is a piece of information such the knowledge of T allows us to compute the reimage of F in polynomial time (see [8] or [9] for some examples).
We assume that multivariate map F is given in its standard form of kind xi →fi(x1, x2, … , xn),
i=1, 2, … , n where polynomials fi are given in the form of the some of monomial terms listed in
the lexicographical order. We assume that monomial term M is written in the form a(x1)t(
We assume that Multivariate Cryptography in wide sense is about applications of the theory of nonlinear trapdoor accelerators to Symmetric and Asymmetric Cryptography. In the case when K is a finite commutative ring the pair (F, T) can be used as instrument of symmetric encryption. The space Kn can serve as space of ciphertexts. Usually the knowledge of T allows efficient computation of the value of F on the given tuple. Both correspondents have the knowledge on T. So they do not need to compute the standard form. Adversary can use various attacks to investigate the multivariate nature of encryption procedure for the construction of the procedure to compute the reimages of the map. Standard forms of F with trapdoor accelerator can be considered as potential multivariate maps which can serve as instruments for encryption or conducting digital signatures.
Multivariate maps are elements of Cremona semigroup nCS(K) of endomorphisms of K[x1, x2,…, xn] (see [39]). Such endomorphism F can be given by its values F(xi)= fi(x1, x2, …, xn) , i=1, 2, …, n on generic variables xi. We assume that polynomials fi are given via their standard form and define degree and density of the map F.
Trapdoor accelerators can be used for the generation of subsemigroup H of nCS(K) with the property P of computation of the product of n elements from H in a polynomial time. Its alternative approach to combinatorial method of generators and relations. Note that nCS(K) itself does not posses P itself because the product of n its general representatives of degree k , k≥2 will be of degree kn.
Subsemigroup H satisfying property P can be used as platforms of Noncommutative Cryptography [10] for the implementation of algebraic key exchange protocols of Postquantum Cryptography. Noncommutative Cryptography is an area of current intensive research (see [40]-[54]).
Some methods of construction of multivariate maps with the trapdoor accelerator in terms of Algebraic Graph Theory are presented in [8] (see also [9] and further references) together with some cryptographical applications.
The paper is dedicated to applications of graph based constructions of trapdoor accelerators to algorithm of the establishment of secure user’s access password to the resources of Information System with further options of the password changes. We suggest the following general scheme.
Assume that Administrator A and his/her trusted user have safely protected password t for mutual authentication, This is the string from Kn. Administrator A of the Information System (IS) possesses the map F in n-variables and its trapdoor accelerator T. He/she is going to give secure access to the resources of IS to trusted user U. So A and U executes selected protocol of Noncommutative Cryptography in terms of special subsemigroup S of the affine Cremona semigroup of all multivariate maps of Kn into itself. The output of the protocol X can be used by A and U for the mutual identification. U sends X(t) to A who compares it with own computation of X(t). Administrator creates the map F of the same degree deg (X) of the affine space of Kn Administrator sends F+X to U. User restores F. Now A is able to create pseudorandom or genuinely random password (p1, p2, ...., pn) =p as the condition to enter the system. Administrator solves the equation F(x)=b and sends the solution x=(d1, d2,..., dn)=d to the user together with the link for entering the password. User U gets the password as F(d1, d2,...., dn).
Administrator has the option to change the password several times working with the same map F with the trapdoor accelerator. He/she is able to change F via a new session of the protocol and delivery scheme. Some modifications of this procedure are discussed in the conclusion of the paper.
The security of this scheme rests on the security of selected Postquantum Protocol on Noncommutative Cryptography. We describe Twisted Diffie-Helman protocol which use the complexity of Conjugation Power Problem of the subsemigroup of nCS(K) satisfying property P. The general idea of this scheme is given in [11], some other protocols and platforms can be found in [8] or [9]. Some of them use the semigroup nES(K) of Eulerian transformations (see [12]).
This paper is dedicated to the implementation of the scheme with constructions of graph based
multivariate maps of prescribed degree and density with the trapdoor accelerators. We use the
platforms generated by the transformations of densities O(
The problem of safe key establishment and further key management is especially important currently when solution has to be secure in sense of Postquantum Cryptography. Research on this direction canbe found for instance in [13]-[15] where authors the postquantum technique different from Multivariate Cryptography. The description of one of the protocols of Noncommutative Cryptography and modifications of described above scheme of multivariate key establishment is given in the next section.
Assume that Alice and Bob are going to work with multivariate maps of the affine space Kn where K is finite commutative ring and elaborate the collision multivariate map. Assume that Alice decides to work with subsemigroup H of the Cremona semigroupnCS(K) of all multivariate maps of Kn to itself. Assume that all used elements are written in the form xi→fi(x1, x2,..., xn), fiϵK[x1, x2,…, xn] and each fi is written as the sum of monomial terms written lexicographically. Let noncommutative subsemigroup H contains invertible elements and satisfies to property P mentioned in previous section.
Assume that H consists of elements of density O(
Alice selects invertible element h and element g of H of densities O(
At the second stage of the algorithm Alice and Bob computes the collision map Y as hr(A)y(B)k(A)h-r(A) and hr(B)y(A)k(B)h-r(B) respectively.
Algorithm requires O(
The solution of Conjugacy Power Problem in polynomial time in the case of affine Cremona semigroup nCS(K) is currently unknown. This argument is in the favour of the post quantum security of protocol.
Assume that elements g and h of H as above are prescribed degree d, d=O(
The section 3-6 of this paper are dedicated to graph based explicit constructions of bijective multivariate map F on the affine space Kn of prescribed degree and density with the trapdoor accelerator. In the Appendix we describe the implementation of such algorithm in the selected cases.
We can use subsemigroups H and maps F with trapdoor accelerator to modify the key establishment scheme of previous section.
We assume that both parties has mutually known authentication passwords pA (administrator) and pB (trusted user). Tuples pA and pB are located in the safe data base of the system. 1 option. Authentication protocol with the multivariate platform satisfying the property P. So administrator Alice and IS user Bob have collision multivariate map G. Alice safely set the link to enter the system with the password of form G(t) where t is the concatenation of pB and pA. Bob enters the initial password G(t) and gets the access to the system. Alice can send a new access information r to Bob together with the link to access the system with the password G(r). The tuple r can be of pseudorandom or genuinely random nature .
Note that Bob can make request to change the password and send r toAlice. She sets the access password as G(r) and sends the link to Bob.
Alice or Bob can change the password several times. If they agree to make just single protocol adversary need to intercept quite many pairs (ri, G(ri)) and try to approximate map G. It is in fact difficult because Alice and Bob keep H(r ) safely. Only ri are delivered via the open channel. In the case of quadratic map Alice can change the access password O(nα), α<2.
The adversary can use specific features of the multivariate platform. Alice and Bob have to share some elements gi, i=1, 2,..., k from the platform. So adversary can try to investigate the platform generated by this elements. He/she can use specific features of the platform like a low degree and densities of elements. Sure that Alice and Bob can start new session of the protocol with other generators. 2 option. Alice can take arbitrary multivariate map F of degree at most d and sends F+G to Bob. This steganographic one time pad like action is safe. So Bob Restores F. He sends F(t) to Alice. She compares the received value with the her own computation of F(t) with the registered in system t. Alice takes the tuple r as above sends it to Bob and set the link with the entering condition in the form of the password F(r). The complexity to form the password for both parties after conducting single protocol is O(nd+1). To change F Alice and Bob need to start a new protocol. 3 option. Let us assume that Alice creates the bijective multivariate map F of degree d with the trapdoor accelerator T which allows her to compute the reimage in time O(nα) where α is smaller than d+1. She sends F+G to Bob. Bob sends F(t)=c. Alice compares F-1(c) with the registered t. Next Alice takes tuple r and computes F-1(r) =c and sends c to Bob. He restores r as F(c). In this case the knowledge of T allows Alice to compute c for O(nα). 4 option. Bob has (F, T) and sends F + G to Alice. Bob sends F(t). Alice compares it with her own independent computation of F(t). She sets r and forms the link with entering condition r, computes c=F(r) and sends it to Bob via open channel. So the public user can complete r as F-1(c ) the procedure for O(nα). In this case adversary has to intercept pairs (c, F-1) but he has to approximate F-1 to get the procedure to enter the system. This is essentially harder task than the approximation of F.
Missing definitions of Incidence Structures Theory or Graph Theory reader can find in [16], [17]. Let K be a commutative ring with unity. Recall that incidence structure is a triple (P, L, I) where P is the set of points, L is the set of lines and I is a bipartite graph with the partition sets P and L. We identify I with the corresponding binary relation on the disjoint union of P and L. Let P=Kn and L=Kn. We identify points with tuples of kind (x)=(x1, x2,…, xn) and lines with tuples [y] =[y1, y2,…, yn]. Brackets and parenthesis are convenient to distinguished type of the vertex of the graph. If (x) and [y] are incident (x)I[y] if and only if the following relations hold. a2x2-b2y2=f2(x1, y1), a3x3-b3y3=f3(x1, x2, y1, y2), …, anxn-bnyn=fn(x1, x2,…, xn-1, y1, y2, …, yn-1), where aj and bj , j = 2, 3, . . . , n-1 are not zero divisors, and fj ϵ K[x1. x2_, …. xj-1, y1, y2,…, yn-1], j=2, 3,…, n are multivariate polynomials with coefficients from K (see [8], [9] and further references). The color ρ(x) = ρ((x)) (and ρ(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 coordinate. As it follows from the definition of linguistic incidence structure, for each vertex of incidence graph there exists a unique neighbour of a chosen color.
We say that a linguistic graph is of Jordan-Gauss type if the map [(x), [y]] →(f2(x1, y1), f3(x1, x2, y1, y2), .. . . , fn(x1, x2, . . . , xn-1, y1, y2, . . . , yn-1)) is a bilinear map into Kn-1.
Thus, all fi are special quadratic maps. In the case of Jordan-Gauss graphs, the neighbourhood of each vertex is given by the system of linear equations written in its row-echelon form. Let In-1=In-1(K) be a linguistic graph defined over the commutative ring K. Foreach b ∈ K and (p) = (p1, p2, . . . , pn), there is the unique neighbour [l] = Nb(p) of the point with the color b. Similarly, for each c ∈ K and line l = [l1, l2, . . . , ln] there is the unique neighbour (p) = Nc([l]) of the line with the color c.
On the sets P and L of points and lines of the linguistic graph, we define jump operators J = Jb(p) = (b, p2, p3 , … , pn) and J = Jb([l]) = [b, l2, l3, . . . , ln] where b∈ K.
Let i(
In case when Weil group is infinite Dihedral group this graph is an infinite the corresponding qregular graphs, but projections of partition sets on first n coordinates defines interesting JordanGauss graphs Гn(Fq) with well defined projective limit.
Special modifications D(n, q) of Гn(Fq) in the case of Kac-Moody algebras with the Cartan matrix [−2 2 ]
2 −2 provides explicit construction of graphs of large girth of Extremal Graph Theory, they are used for the constructions of LDPC codes in satellite communications (see [19] and further references).
If we simply consider general commutative ring K we obtain Jordan - Gauss graphs In=D(n, K), n
≥2 of type (1, 1, n-1) which have triangular connectivity invariants as, s=1, 2, …, t, t= [(n+2)/4]-1
of the type i(
Graphs CD(n, q)=CD(n, Fq), q>2 were introduced in [2]. Results on the triangular invariants for graphs D(n, K) are observed in [3].
In fact graphs CD(n, q) are connected if q≠4. In the case of the field F4 this graph has exactly 4 connected components for each value of n, n>2 .
We present the description of graphs D(n, K) and their triangular connectivity invariants in the Section 3.
Below we introduce the algorithm of generating multivariate maps on the selected partition set of linguistic graph In-1(K) of type (1, 1, n-1) with the triangular connectivity invariants gs, s=1, 2, …, k.
Assume that R is the extension of commutative ring K. Then we can associate graph RIn-1(K) with
the graph In-1(K) such that partition sets of new graph are isomorphic to Rn but the incidence
relation is given by the same system of equations with the coefficients from K. Assume that gs,
s=1, 2, …, k as family of triangular connectivity invariants of the linguistic graph In-1(K) of type
i(
In particular we can take list of variables z1, z2, …, zn and take R=K[z1, z2, …, zn].
We take the special point v0=(z1, z2, …, zn) parameter k and the sequence of colours f1(z1, g1(z1,
z2,..., zi(s), g2(z1, z2,..., zi(
Assume that we have some bijective polynomial map h on the commutative ring K. We refer to this requirement on hk as reversibility condition. We consider the walk on vertices of RIn-1(K) with the starting point v0 and consecutive elements v1, v2, …, vk of colours h1, h2,…, hk with the last vertex vk with coordinates hk(z1, z2,…, zi(s)), u2(z1, z2, …, zn), u3(z1, z2, …, zn), …, un(z1, z2,…, zn).
The vertex vk is the point if k is even and vk is the line if k is odd. Finally we apply operator Jg, g=h(hk) to vk and get the vertex v= (h(hk(z1, z2,…, zi(s)), u2(z1, z2, …, zn), u3(z1, z2, …, zn), …, un(z1, z2,…, zn).
Proposition 3. 1. The reversibility condition implies that polynomial map F:z1→ h(hk(z1, z2,…, zi(s))), z2→ u2(z1, z2, …, zn), z3→ u3(z1, z2, …, zn),…, zn→ un(z1, z2, …, zn) is a bijective transformation. The information on the graph, its triangular invariants, the sequence of colours f1, f2,..., fk is a trapdoor accelerator.
The procedure of reimage computation is the following. Assume that the value of F on
some unknown tuple (z1, z2, …, zn) is (c1, c2, …, zn). We compute h-1(c1)=d and take the vertex vk=(d,
c2, c3,…, cn) and the equation fk(z1, g1(z1, z2,..., zi(
We take the sequence of colours h1, h2, ..., hk-1 and change hk for the constant γ. So we take the
walk as the sequence v0, v1,...., vk-1 and compute v’k=Nγ(vk-1), vk+1=Jh(v’k ) where h=hk. Recall that
the first coordinate of the vertex vk+1 is fk(z1, g1(z1, z2,..., zi(s)), g2(z1, z2,..., zi(
Proposition 3.2. The reversibility condition implies that polynomial map H:z1→ hk(z1, z2,…, zi(s)), z2→ w2(z1, z2, …, zn), z3→ w3(z1, z2, …, zn),…, zn→ wn(z1, z2, …, zn) is a bijective transformation. The information on the graph, its triangular invariants, sequence of colours f1, f2,..., fk and constant γ is a trapdoor accelerator.
The procedure of reimage computation is the following. Assume that the value of H on
some unknown tuple (z1, z2, …, zn) is (c )=(c1, c2, …, cn). We compute Jγ(c) =( γ, c2, c3,…, cn)=vk-1.
Recall that the first coordinate of vk+1 is fk(z1, g1(z1, z2,..., zi(s)), g2(z1, z2,..., zi(
We take the equation is fk(z1, d1, d2,..., ds). The reversibility condition allows us to solve it for z1. Let z1=α be the solution.
We compute fj(α, d1, d2,..., ds)=bj, j=1, 2,..., k-2 and take the path of vertexes of the graph with starting vertex vk-1 and consecutive colours bk-2, bk-3,..., b1 , α. The last vertex is (z1, z2,..., zn)=(α,α2, α3_...,αn)= H-1(c1, c2,..., cn).
Examples of hk satisfying the reversibility condition: (pr1(g1 , g2 , …, gs)+1)z1 +r2(g1 , g2 , …, gs) where r1, r2ϵZq[y1, y2, ..., ys] in the case K=Zq, q=pm; h(r1(g1 , g2 , …, gs))(z1)t+r2(g1 , g2 , …, gs), where r1, r2ϵFq[y1, y2,..., ys], h(y) has no linear terms in its decomposition in Fq[y] in the case of K=Fq, q=pm, (t, q)=1; αz1+ r(g1 , g2 , …, gs) where α ϵ K*, r ϵ K[y1,y2, ..., ys] in the case of general commutative ring with unity.
If linguistic graph coincides with D(n, K) or their modifications presented in [3] then their connectivity invariants can be used for the constructions of multivariate maps with prescribed degree and density.
J Jordan-Gauss graph D(n, K) of type 1, 1, n-1 is defined as incidence structure In-1 with the partition sets isomorphic to Kn .The point (p)=(x1, x2,…, xn) of this graph is incident with the line [y]=[y1, y2, …, yn], if the following relations between their coordinates hold: x2-y2=y1x1, x3-y3=y2x1, x4-y4=y1x2, xi-yi=y1xi-2, xi+1-yi+1=yi-1x1, xi+2-yi+2=yix1 ,xi+3-yi+3=y1xi+1 where i≥5 .
As it is easy to see the projective limit D(K) is well defined. In fact if K is an integral domain the biregular graph D(K) is the forest (see [3] and further references).
Recall that graphs D(n, Fq)=D(n, q) are the modifications of Гn(Fq) in the case of Kac-Moody algebras with the Dynkin diagram Ext A1 (A1 with wawe or extended Dynkin diagram of A1). It is convinient to use positive roots of this root system as indexes of points and lines. The real roots are k+1α1+kα2, kα1+(k+1)α2 where k≥0 α1, α2 are simple roots and and the imaginary roots are kα1+kα2 where k≥1. We identify roots with their coordinates in the lattice generated by simple roots (k+1, k), (k, k+1) and (k, k). The modification uses ‘’twins’’ of imaginary roots indexed as (k, k)’.
So graph D(K) can be defined as the incidence with lines [y]=[y01, y11, y12 , y21, y22, y'22 , …, y’ii, yi
i+1, yi+1,i , yi+1,i +1 … ], points (x)=( x10, x11, x12 , x21, x22, x'22 , …, x’ii, xi i+1, xi+1,i , xi+1,i +1 … ) and incidence
relation given by equations
xii-yii=x10 yi-1,i ;
x’ii –y’ii = xi,i-1 y01;
xi, i+1 – y i,i+1 =xii y01 ; (
This four relations are defined for i≥1, (x’11= x11, y’11= y11).
Note that tuples (x) and [y] have finite support, i. e. only finite number of their coordinates differ from zero. Coordinates x’ii and y’ii correspond to the root (i, i)’.
Further we interpret D(n, K) as homomorphic images of D(K) obtained via the projection of
points and lines into their first n coordinates. The incidence of points and lines of D(n, K) is
defined by the first n-1 equations of the system (
For the description of triangular connectivity invariants of D(n, K), it will be convenient for us
to define x-1,0 = y0,-1 = x1,0 = y0,1= 0, x0,0= y00= -1, x’0,0 = y’0,0 = -1, x1,1 = x’1,1, y1,1 = y’1,1 and to assume that
our equations (
Let u = (uα, u11, u12, u21, …, ur,r , u’r,r , ur r+1 ur,+1,r , ur+1,r+1 , …), 2 ≤r ≤t, α ϵ{ (
In introduced above set Δ of not simple roots (j, j), (j+1, j) , (j, j+1), (j+1, j+1)’ where j≥1 . We
assume that each equation of (
We assume that the elements of Δ are ordered accordingly to the list of coordinates of D(K) in
the presentation (
Assume that Δ’((i+1, i+1)’) be the list of roots of Δ’ with the order higher than (i+1,i+1)’. As it was proven in (i) deletion of coordinates with indexes from Δ’(i+1, i) and Δ’((i+1, i+1)’) defines the homomorphism Ψi and Ψ’i of graph D(K). The incidence of elements of the images are defined by equations indexed by elements Δ- Δ’(i+1, i) and Δ- Δ’((i+1, i+1)’) respectively. The image of Ψ1 is known as graph A( K). The projection of points and lines A(K) on its first n coordinates defines known graphs A(n, K). Graphs A(n, K) , n ≥4 differs from D(n,K). We introduce graphs iB(K) and iB’(K) as homomorphic images of Ψi and Ψ’i . We consider projections of points and lines of these graphs onto first n coordinates together with first n-1 equations. The images of these homomorphisms will be denoted as iB(n, K) and iB’(n, K) for n ≥ 4i and n ≥ 4i+2 respectively.We use roots in their definitions for the description of some triangular connectivity invariants.
Proposition 4. 1. Graphs iB(n, K) and iB’(n, K) has connectivity invariants
gs=as+1(u), s=1, 2, …, i-2 of type j(
We consider graphs iBS(n, K) and iB’S(n, K) obtained by deletion of coordinates (r, r)’ , (r, r)’ϵS from points and lines and replacement condition x r+1, r - y r+1,r = x10y’r,r by x r+1, r - y r+1,r = x10yr,r These graphs were introduced in [3] in different notations.
Assume that j(S)>2 then iBS(n, K) and iB’S(n, K) have triangular connectivity invariant gs=as+1(u), s=1, 2, …, j(S)-2. Note that partition sets of these graphs are isomorphic to Kn-s where s is the cardinality of S.
Let us consider the algorithms 1 and 2 in the cases of described graphs.
Assume that linguistic graph coincides with the Jordan-Gauss graphs presented in the Section 3 and multivariate maps F and H are defined via algorithms 1 and 2 respectively. Then the following propositions hold.
Proposition 4. 2. Let L be element of AGLn(K) of density O(
Proposition 4.3. Let L be element of AGLn(K), h1, h2,..., hk-1 are functions of density O(
Corollary. Let L1 be general element of AGLn(K). Then transformations LFL 1 and LHL 1 are pseudo quadratic. It means that for the standard forms of LFL1 and LHL1 the computation of their values on the given tuple costs O(n3).
In this section we propose the generalisation of implemented scheme of Algorithm 1.
Let In-1(K) be the linguistic graph of type (1, 1, n-1). Assume that gs, s=1, 2, …, k is the family of
its triangular connectivity invariants of type i(
We compute the symbolic expressions gs(z1, z2,…, zi(s)) for s=1, 2,…, k. We select element z=z(y1,
y2,…, yk+1) from K[y1, y2,…, yk+1] and compute the expression b(z1, z2, …, zi(k))=z(z1, g1(z1, z2, …, zi(
Proposition 4. 4. Let F be the map of Algorithm 1 with the described above data in the case of one of the graphs D(n, K), iBS(n, K) and iB‘S(n, K), iB(n, K), iB’(n, K) and bijective h from K[x] of degree s. Assume that degree of b(z1, z2, ...., zi(k)) is t. Then degree of F is max (2t+1, st) if l is odd and max(t+2, st) if l is even. Then degree of F is max (2t+1, s) if l is even and max(t+2, st) if l is odd.
In the cases of selected finite commutative rings of kind Fq or Zq we take element L of AGLn(K)
of the density O(
The implementation of Algorithm 1 in the case of graphs D(n, K) in the case of K=Fq, q=2s with h1=z1+β1, h2= z1+β2 , hi=h1-2+ βi, i ≥2 and h(x) =αx2+β, where β1 ϵ K, β2 ϵ K, β ϵ K, α ϵ K*, βi ϵ K* for i≥2 was described in the paper [20].
The description of the implementation of Algorithm 2 in the case of D(n, K), K=Fq, q=2s , even parameter k special colours h1=α1, h2=z1,0+b1, h3=α3, h4=z1,0+b2,...., hk-2=z1,0+bk-2, αk-1=γ, hk=αz1,0+ λ2a2(z1,0 , z1,1, ..., z’2, 2)+ λ3a3(z1,0, z1,1, ..., z’3,3 )+ .... +λtat(z1,0, z1,1, ...,z’t,t), t=[(n+2)/4], where αi , bi and λi are constants, is given in [21].
If we change K=Fq for K=Zq without the change of above written requirements on hi, i=1, 2,... we get the new case for the implementation. The results of corresponding computer simulations are below.
We have written a program for generating elements and for encrypting a text using above algorithm. The program is written in SAGE. We used an MacBook with a Intel Core 1,2 GHz processor, 8GB RAM, and the macOS Monterey operating system. We have implemented three cases: case 1. L1 and L2 are identities, case 2. L1 and L2 are maps of the kind z1,0 → z1,0 + a2z1,1 + a3z1,2 + · · · + atzt,t, z1,1 → z1,1, z1,2 → z1,2, . . . , zt,t → zt,t, with ai 0, i = 1, 2, . . . , n (linear time of computing for L1 and L2), case 3. L1 = Ax + b, L2 = A1x + b1; matrices A, A1 and vectors b, b1 mostly have nonzero elements.
In Tables 1, 2 and 3, we describe the numbers of monomials in case 1 for different sizes of the field. Tables 10,11,12 shows the generation time of the encryption.
In Tables 4, 5 and 6, we describe the numbers of monomials in case 2 for different sizes of the field. Tables 13,14,15 shows the generation time of the encryption.
In Tables 7, 8 and 9, we describe the numbers of monomials in case 3 for different sizes of the field. Tables 16,17,18 shows the generation time of the encryption.
Remark. After the change of the graph D(n, K) on iB(n, K), iBS(n, K), i>1, n≥4i or iB’(n, K), iB’S(n, K) with i>1, n ≥4n+2 the map H is also quadratic transformation. 64 1474 1914 1852 16 141 141 141 141 16 1076 1077 1078 1065 16 141 141 141 141 16 1021 1034 1075 1018 16 1078 1078 1078 1078 16 2416 2406 2419 2434
The expanding graphs of large girth D(n, q) and their generalisations D(n, K) defined over the commutative ring K turns out to be useful in the theory of LDPC codes, Message Authentication Codes, constructions of stream ciphers of symbolic nature, protocols of Noncommutative Cryptography , Multivariate Public Keys.
In this paper we present the applications of these graphs and their recent generalisations [3] to the design of the algorithms of key establishment.
This research is partially supported by British Academy Fellowship for Researchers under Risk 2022, British Academy/Cara/Leverhulme Research Support Grant LTRSF\100333 and UMCS Mini-Grant.
The author(s) have not employed any Generative AI tools. [19] M. Polak, V. Ustimenko, LDPC Codes Based on Algebraic Graphs, Annales UMCS Informatica
AI XII, 3 (2012) 107–119. [20] Ward Beullens, Improved Cryptanalysis of UOV and Rainbow, In Eurocrypt 2021, Part 1, pp. 348-373. A. Lubotzky, Expander Graphs in Pure and Applied Mathematics, Bulletin of the AMS,v.49, n.1, pp 113-14. [21] Lazebnik, F., Ustimenko, V., Woldar, A.J., A new series of dense graphs of high girth. Bulletin of the AMS, vol. 32, no. 1, pp. 73--79 (1995). [22] Smith-Tone, D.: 2F - A New Method for Constructing Efficient Multivariate Encryption Schemes. In: PQCrypto 2022: The Thirteenth International Conference on Post-Quantum Cryptography, virtual, DC, US (2022). [23] Smith-Tone, D.: New Practical Multivariate Signatures from a Nonlinear Modifier. IACR eprint archive, 2021/419. [24] Smith-Tone, D., Tone, C.: A Nonlinear Multivariate Cryptosystem Based on a Random Linear
Code. \url{https://eprint.iacr.org/2019/1355.pdf}, last accessed 2024/07/30. [25] Jayashree, D., Dutta, R.: Progress in Multivariate Cryptography: Systematic Review, Challenges, and Research Directions. ACM Computing Survey, vol. 55, issue 12, No. 246, pp. 1-34 (2023). \doi{10.1145/3571071} [26] Cabarcas, F., Cabarcas, D., Baena, J.: Efficient public-key operation in multivariate schemes.
Advances in Mathematics of Communications, vol. 13, no. 2, pp. 343--343 (2019). [27] Cartor, R., Smith-Tone, D.: EFLASH: A new multivariate encryption scheme. In: Proceedings of the International Conference on Selected Areas in Cryptography, pp. 281--299. Springer, Heidelberg (2018). [28] Casanova, A., Faugère, J.-C., Macario-Rat, G., Patarin, J., Perret, L., Ryckeghem, J.: Gemss: A great multivariate short signature. Submission to NIST (2017). [29] Chen, J., Ning, J., Ling, J., Lau, T. S. C., Wang, Y.: A new encryption scheme for multivariate quadratic systems. Theoretical Computer Science, vol. 809, pp. 372--383 (2020). [30] Chen, M.-S., Hülsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: SOFIA: MQ-based signatures in the QROM. In: Proceedings of the IACR International Workshop on Public Key Cryptography, pp. 3--33. Springer, Heidelberg (2018). [31] Ding, J., Petzoldt, A., Schmidt, D.S.: Multivariate Public Key Cryptosystems. 2nd edn. Advances in Information Security. Springer, Heidelberg (2020). [32] Duong, D.H., Tran, H.T.N., Susilo, W., Luyen, L.V.: An efficient multivariate threshold ring signature scheme. Computer Standards \& Interfaces, vol. 74 (2021). [33] Faugère, J.-C., Macario-Rat, G., Patarin, J., Perret, L.: A new perturbation for multivariate public key schemes such as HFE and UOV. Cryptology ePrint Archive (2022). [34] Canteaut, A., Standaert, F.-X. (eds.): Eurocrypt 2021, LNCS, vol. 12696, 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I. Springer, Heidelberg (2021). [35] Saarinen, M.J., Smith, D.T. (eds.): Post Quantum Cryptography, 15th International Workshop,
PQCrypto 2024, Oxford, UK, June 12-14, 2024, Proceedings, Part 2. Springer, Heidelberg (2024). [36] Takagi, T., Wakayama, M., Tanaka, K., Kunihiro, N., Kimoto, K., Ikematsu, Y. (eds.): International Symposium on Mathematics, Quantum Theory, and Cryptography, Proceedings of MQC 2019. Open Access, Springer, Heidelberg (2021). [37] Arai, K. (ed.): Advances in Information and Communication, Proceedings of the 2024 Future of Information and Communication Conference (FICC), Volumes 1-3. Lecture Notes in Networks and Systems, vols. 919-921, Springer, Heidelberg (2024). [38] Ustimenko, V.: Schubert cells and quadratic public keys of Multivariate Cryptography. CEUR
Workshop Proceedings ITTAP, \url{https://ceur-ws.org/Vol-3628/}, last accessed 2024/07/30. [39] Liendo, A. Roots of the affine Cremona group. Transformation Groups 16, 1137–1142 (2011).
https://doi.org/10.1007/s00031-011-9140-y.