We present two families of new ciphers with the spaces of plaintexts of kind Kn-r, K = Fq or K = Zq, q = 2s and the variety of active passwords of kind A, (α1, α2, …αr) ϵ Kr, (β1, β2,…,βt) ϵ (K*)t, where A is a subset of cardinality r of the set {1, 2, …, [(n+2)/4]-1} car, r<[(n+2)/4], even t<[n+5]/2]. It is proven that different active passwords produce distinct ciphertexts from the same plaintext. If freely selected parameters r and t have size O (1) then the execution speed of the cipher is O (n). These families of encryption maps are defined in terms of well-known algebraic graphs D (n, K) which form a family of graphs of large girth in the case when K is a finite field. The encryption map is defined as a combination of the graph-based encryption and two polynomial transformations of (Zd,) n-r d = 2s+1 preserving (Z*d) n-r and acting naturally on K n-r. This trick does not allow to interpretation of the encryption map as a multivariate transformation over some commutative ring. It prevents linearization attacks by adversaries. We can change the defined above commutative rings Fq and K = Zq for Boolean ring Bs of size 2s and obtain the third stream cipher with similar properties.
Everybody knows that each computation can be defined in terms of finite automaton, a roughly directed graph with labels on arrows, various applications of automata theory to cryptography are very hard to observe. So Graph Based Cryptography is a natural direction of research. It is used for the key exchange, development of Multivariate Public Keys, key-dependent message authentication codes, and algorithms of Noncommutative Cryptography [3–17].
Especially Graph theory is commonly used as a tool for symmetric encryption. The first cryptographical applications of Graph Theory appeared in the areas of Symmetric Cryptography and Network Security. The monograph [1] and papers [2, 40] reflect some results in the area of applications of families of algebraic graphs of the large girth of Extremal Graph Theory to the development of fast and secure encryption tools to process Big Data files. The vertices and edges of algebraic graphs form algebraic varieties defined over the field. The girth is the length of the minimal cycle in the graph. This parameter defines the size of the key space of the corresponding cipher.
Several known ciphers based on algebraic graphs have a multivariate nature. The space of plaintexts is an affine variety Kn defined over finite commutative ring K. Bijective encryption map F can be given by nonlinear multivariate polynomials f1, f2, …, fn from the multivariate commutative ring K [x1, x2, …, xn]. It acts on the affine space according to the rule (x1, x2, …, xn)→(f1(x1, x2, …, xn), f2(x1, x2, …, xn), …, fn(x1, x2, …, xn)), where fi are given via corresponding list of monomial terms. Trapdoor accelerator [41] is a piece of information A such that the knowledge of A allows us to compute the reimage of F in time O (n2).
In ciphers based on algebraic graphs correspondents Alice and Bob share file A (the password) and encrypt according to the robust procedure in time O(n) or O(n2). The adversary does not have a password, he/she has to intercept large amounts of pairs of plaintext/corresponding ciphertext and try to approximate multivariate maps F-1 and F. So degree of F is an important parameter for the cryptanalytical studies. The most important (active) part of the password is the information about the walk in the algebraic graph.
The first construction of graph-based stream cipher of multivariate nature based on algebraic approximations of q-regular tree or forest where q is a prime power was presented in [42] or [43]. The first implementation of these algorithms appeared at the beginning of 2001 [44].
The discovery of q-regular forest description in terms of an infinite system of quadratic equations over a finite field Fq had an impact on the development of Graph-Based Cryptography and various constructions of robust stream ciphers. The family of algebraic graphs D(n, K) defined over arbitrary commutative ring K with unity already was used for the development of some graph-based ciphers. The survey of known D(n, K) based stream ciphers reader can be found in [1–2] or [40] where several encryption schemes of a multivariate nature were described.
In this paper we construct the modification of stream cipher suggested in [40] such that the encryption map is the conjugation of kind F = YXY–1 of multivariate map X defined on the affine space V = Kn where K is F2s–1, Z2s–1 or Boolean ring Bs-1 of size 2s–1 and multivariate map Y acting on affine space (Z2s) n of Eulerian type. The map Y preserves the variety(Z*2s) n which can be identified with Kn via the natural bijection between these sets.
The encryption map F cannot be interpreted as a multivariate map over a single commutative ring. Thus multivariate linearization attacks are not feasible.
The cipher has a large space of active passwords such the different passwords produce distinct ciphertexts from the chosen plaintext.
of three stream ciphers in the different cases of commutative ring.
Section 3 is dedicated to tame Eulerian transformations which will be used as maps Y in the above scheme.
In Section 4 we consider trapdoor accelerators T of multivariate ciphers based on linguistic graphs of type (1, 1, n–1) defined over the commutative ring K. The map X = XT can be used in the composition YXY–1.
Ciphers constructed in terms of linguistic graphs D(n, K) and their connected components are presented in section 5.
Section 6 is dedicated to combinations of Eulerian tame transformations with the ciphers defined in Section 5. We present the evaluation of the execution speed of chosen cases of implementations. Results of computer simulations are presented in Tables 1 and 2 and Figs. 1 and 2.
Section 7 contains conclusive remarks and suggestions of supporting protocols of Noncommutative Cryptography (NC) suggested in [45–46]. Of course, other postquantum secure protocols of NC can be used. This area is developing very fast [18–39].
The idea to combine general bijective multivariate map E of bounded degree with Eulerian transformation ψ sending each variable xi into the monomial term for getting x→E(ψ(x)) was considered in [47–48]. If the restriction of ψ onto (K*)n acts bijectively on this set then the transformation E maps (K*)n to Kn injectively. So E can be used as an encryption map with the space of plaintexts (K*)n and the space of ciphertext Kn.
The case of K = Z2s is an interesting one. It is easy to see that linear bijective maps H satisfying condition H((K*)n) = (K*)n exist. The matrix M of H transfers (x1, x2, …, xn) ϵ (K*)n to (x1, x2, …, xn)M from (K*)n if and only if each column of M contains an odd number of odd residues modulo 2s. We can consider bijective map G on (K*)n of kind ψ1Hψ2. If the matrix of H has O(n2) nonzero entries and Eulerian transformations ψi, i = 1, 2 have linear degrees then G has linear degree and exponential density (number of monomial terms in all G(xi)) [46].
It means that if correspondents share information on ψi and H and know Eulerian inverses (ψi)–1 then they can use G as an encryption tool on the space (K*)n. The knowledge of the decomposition of G allows them to encrypt. The complexity of encryption and decryption is O(n2). We refer to this encryption scheme as Double Eulerian cipher.
The highly nonlinear nature of G makes the linearization attacks by adversaries impossible to conduct.
Of course, we have to consider the change of H on the nonlinear family of bijective multivariate maps nF such that computation of nF(p) and reimage of nF takes O(n) if some trapdoor information is known. The problem is the hardness of the investigation of the condition nF((K*)n) = (K*)n. To avoid this complication we use the following alternative approach.
We consider some computational relations between Z2s–1, Z*2s, and F2s–1.
Recall that Z*2s is the totality of odd residues modulo 2s.
We consider the map ϭ from Z2s–1 to Z*2s such that ϭ(t mod 2s-1) is 2t+1 mod 2s. It is a bijection. Let ϭ-1 be the inverse map from Z*2s to Z2s–1.
Notice that elements from Z2s–1 can be written as b = e0+e12+e222+…+es-22s-2mod 2s–1, where ei ϵ {0,1}. Element of the finite field Fq, q=2s1 can be written as g(x) = e0+e1x+e2x2+…+es-2xs-2 mod p(x) where p(x) is the irreducible polynomial of degree s-1. Let π be the map such that π(b) = g(x) and π–1 is the inverse map from Fq, q = 2s–1 onto Z2s–1.
We consider the map ∆ from Fq onto (F2)s–1 sending g(x) to Boolean vector (e0, e1, …, es–2) which we identify with the element of Boolean ring Bs–1 of size 2s–1.
Let us consider the map S of (Z*2s)n onto (Z2s–1)n which sends (x1, x2, …, xn) to (ϭ-1(x1), ϭ–1(x2)), …, ϭ–1(xn)). We define the map P of (Z*2s)n onto (F2s–1)n which sends (x1, x2, …, xn) to (π(ϭ–1(x1)), π(ϭ–1(x2)), …, π(ϭ–1(xn)). Let D be the map of (Z*2s)n onto (Bs–1)n
Sending (x1, x2, …, xn) to (∆(π(ϭ–1(x1))), ∆(π(ϭ–1(x2))),…., ∆(π(ϭ–1(xn)))). We assume that S–1, P–1, and D–1 are inverses of bijective maps S, P, and D.
Let us consider several modifications of the Double Eulerian cipher.
from Kn to Kn. Let T be a piece of information such that the knowledge of T allows us to compute the value of F on the given element of Kn and the reimage of F in time O(n2). We refer to T as a symmetric trapdoor accelerator. We say that pair (F, T) is a linear accelerator if it allows us to compute the reimage of F in time O(n).
We suggest the following encryption schemes.
M1. Let K = Z2s–1 and nF be the family of polynomial maps of Kn onto Kn, i. e nF(xi) is an element of K[x1, x2, …, xn]. Assume that nF has a trapdoor accelerator T.
Alice and Bob share (nF, T) and Eulerian transformations ψi, i = 1, 2 defined on (Z2s)n with their Eulerian inverses (ψi)–1 for which ψi(ψi)–1(x) = x for x ϵ (Z*2s)n.
Then they can work with the family of ciphers with the space of plaintexts (Z*2s)n and use the encryption function G = ψ1SnF (S–1) ψ2. The knowledge of T and the decomposition of G and G–1 into ψi, nF, S, and their inverses allows to encrypt and decrypt in time O(n2).
M2. Let K = F2s–1 and nF be the family of polynomial maps of Kn onto Kn, i. e. nF(xi) is an element of K[x1, x2, …, xn]. Assume that nF has a trapdoor accelerator T.
Alice and Bob share (nF, T) and Eulerian transformations ψi, i = 1, 2 defined on (Z2s)n with their Eulerian inverses (ψi)–1 for which ψi(ψi)–1(x) = x for x ϵ (Z*2s)n.
Then they can work with the family of ciphers with the space of plaintexts (Z*2s)n and use the encryption function G = ψ1PnF (P–1) ψ2. The knowledge of T and the decomposition of G and G–1 into ψi, nF, P, and their inverses allows to encrypt and decrypt in time O(n2).
M3. Let K = Bs–1 and nF be the family of polynomial maps of Kn onto Kn, i. e nF(xi) is an element of K [x1, x2, …, xn]. Assume that nF has a trapdoor accelerator T,
Alice and Bob share (nF, T) and Eulerian transformations ψi, i = 1, 2 defined on (Z2s)n with their Eulerian inverses (ψi)-1 for which ψi(ψi) –1(x) = x for x ϵ (Z*2s)n.
Then they can work with the family of ciphers with the space of plaintexts (Z*2s)n and use the encryption function G = ψ1DnF (D–1) ψ2. The knowledge of T and the decomposition of G and G–1 into ψi, nF, P, and their inverses allows to encrypt and decrypt in time O(n2).
REMARK 1. In each of the described above cases we can substitute nF with the trapdoor accelerator for its affine deformation, i. e. the map nF of kind L1nFL2, LiϵAGLn(K) which has a trapdoor accelerator L1, L2, T.
REMARK 2. We can identify (Z*2s)nwith (Bs–1)n and interpret the encryption function of Mi, i = 1, 2, 3 as the Boolean maps.
Investigation of classes of these maps is an interesting theoretical task.
REMARK 3. The Boolean functions defined above are given via the following three algebraic operations. They are the multiplication of Z2s and the multiplication and addition of one of the rings Z2s–1, F2s–1, and Bs-1. So the encryption is not defined as a multivariate map. This fact eliminates cryptanalytic studies in terms of multivariate Cryptography such as linearisation attacks.
REMARK 4. The schemes Mi, i = 1, 2, 3 are defined as the obfuscation of Double Eulerian cipher with the multivariate encryption map of linear degree and exponential density. We believe that this fact supports the conjecture that the cryptanalytic task is a hard problem.
Let K be a finite commutative ring with the
multiplicative group K* of regular elements of
the ring. We take Cartesian power nE(K) = (K*)n
and consider an Eulerian semigroup nES(K) of
transformations of the kind
x1 → ϻ1x1 a(
(
Let nEG(K) stand for the Eulerian group of invertible transformations from nES(K). A simple example of an element from nEG(K) is a written above transformation where a(i,j) = 1 for i ≠ j or i = j = 1, and a(j,j) = 2 for j ≥ 2. It is easy to see that the group of monomial linear transformations Mn is a subgroup of nEG(K). So semigroup nES(K) is a highly noncommutative algebraic system. Each element from nES(K) can be considered as a transformation of a free module Kn.
Let π and δ be two permutations on the set {1, 2, ..., n}. Let K be a commutative ring with unity which has nontrivial multiplicative group K* of order d = |K*| > 1 and n ≥ 1. We define transformation AJG(π, δ) of the variety (K*)n, where A is a triangular matrix with positive integer entries 0 ≤ a(i,j) ≤ d, i ≥ d defined by the following closed formula.
yπ(
We refer to AJG(π, δ) as Jordan transformations Gauss multiplicative transformation, or simply JG element. It is an invertible element of nES(K) with the inverse of kind BJG(δ, π) such that a(i,i)b(i,i) = 1 (mod d).
Notice that in the case K = Zm straightforward process of computation the inverse of JG element is connected with the factorization problem of integer m. If n = 1 and m is a product of two large primes p and q the complexity of the problem is used in the RSA public key algorithm. The idea to use the composition of JG elements or their generalizations with injective maps of Kn into Kn was used in [47] (K = Zm) and [48] (K = Fq.).
We say that is a tame Eulerian element over the commutative ring K if it is a composition of several Jordan Gauss multiplicative maps over a commutative ring or field respectively. It is clear that sends variable xi to a certain monomial term. The decomposition into a product of Jordan Gauss transformation allows us to find the solution of equations τ(x) = b for x from (Z m* )n or (F*q)m. So tame Eulerian transformations over Zm or Fq. are special elements of nEG(Zm) or nEG(Fq) respectively.
We refer to elements of nES(K) as multiplicative Cremona elements. Assume that the order of K is constant. As it follows from the definition the computation of the value of element from nES(K) on the given element of Kn is estimated by O(n2). The product of two multiplicative Cremona elements can be computed in time O(n3).
We are not discussing here the complexity of computing the inverse for general element gϵ nEG(K) on the Turing machine or Quantum The families of graphs D(n, K), defined over arbitrary commutative ring K are bipartite linguistic graphs of type (1, 1, n–1) with partition sets which are two copies of Kn [42, 49–50], i.e. graphs with the incidence I = I(K) = nI(K) between points (x1, x2, …, xn) and lines [y1, y2, …, yn] given by the system of equations a2x2–b2y2 = f2(x1, y1), a3x3–b3y3 = f2(x1, x2, y1, y2),…, anxn–bnyn = f2(x1, x2, …, xn–1, y1, y2, …, yn-1) where parameters a2, a3, …, an–1 and b2, b3, …, bn–1 are taken from the multiplicative group K* of the commutative ring K. Parameters ρ((x1, x2, …, xn)) = x1 and ρ([y1, y2, …, yn]) = y1 serve as colors of the point and the line. The following linguistic property holds. Each vertex of the graph has a unique neighbor of the chosen color.
Graph CD(n, K) defined in [42] after the elimination of computed recurrently parameters also can be written as linguistic graphs of type (1, 1, m–1) where m = [3/4n] + c.
Let us consider the general scheme of creating the cipher based on the family of linguistic graphs nI(K), n = 2, 3, ….
Noteworthy that we can expand the defined above I(K) to the infinite linguistic graph I(K[x1, x2, …, xn]) defined over the ring K[x1, x2, …, xn] of all multivariate polynomials with coefficients from K and the variables xi, i = 1, 2, …, n. So points and lines of this graph are X = (X1(x1, x2, …, xn), X2(x1, x2, …, xn),…, Xn(x1, x2, …, xn) and Y = [Y1(x1, x2, …, xn), Y2(x1, x2, …, xn), …, Yn(x1, x2, …, xn)]. The incidence of this bipartite graph is given by equations a2X2–b2Y2 = f2(X1, Y1), a3X3–b3Y3 = f2(X1, X2, Y1, Y2), …, anXn–bnYn = f2(X1, X2, …, Xn–1, Y1, Y2, …, Yn–1), where parameters a2, a3,…, an-1, b2, b3, …, bn–1 and polynomials fi, i = 2, 3, …, n with coefficients from K are taken computer and the problem of finding the from the equations in the definition of the inverse for tame Eulerian elements. linguistic graph I(K).
If G is a tame Eulerian transformation of We define the polynomial map F from Kn to
(K*)n, K = Z2s which is defined as a composition Kn via the following scheme [1]. Take the
of Jordan-Gauss transformations J1, J2, …, Jk, special point X = (x1, x2, …, xn) of I(K[x1, x2, …, xn])
k > 1, k = O(
So family of linguistic graphs nI(K), n = 2, 3, … together with two families of affine transformations 1LnϵAGLn(K), 2LnϵAGLn(K), can be used as a cipher with the space of plaintexts Kn and the password g1(x), g2(x), …, gt(x) and the encryption map 1Ln(F(g1, g2, …, gt)2Ln.
Correspondents Alice and Bob share the password given by g1, g2, …, gt, and the sequences of transformations 1Ln, 2Ln n = 2, 3, … We assume that inverse maps (iLn)–1, i = 1, 2 are computed and presented explicitly. For the encryption of potentially infinite plaintext (p) = (p1, p2, …, pn) they will use transformation G = 1LnF(g1, g2, …, gt)2Ln. One of them creates the plaintext (pp’77p) and computes the ciphertext
1LnF(g1, g2, …, gt)2Ln(p) = c recurrently. The procedure is the sequence of the following steps.
S1. He/she computes (1Ln)(p1, p2, …, pn) = (r(
S2. He/she computes a(
S3. Let Na(x1, x2, …, xn) be the operator of taking the neighbor of point (x1, x2, …, xn) with the color a in the linguistic graph nI(K) and aN(y1, y2, …, yn) be an operator of taking the neighbor of a line [y1, y2, …, yn] with the color a.
He/she executes the following operation. The
computation of v1 = Na(
S4. He/she computes ciphertext as 2L(u) = c DECRYPTION PROCEDURE.
Assume that one of the correspondents received the ciphertext c. He/she decrypts via the following steps.
D1. Computation of u as (2Ln)–1(c) = u and
getting the solution x = r(
D2. Computation of parameters
a(
D3. Computation of the plaintext (p) as (1L)–1 (r)).
Let us assume that transformation G is
given in its standard form, i. e. via the list of
monomial terms G(xi) ordered
lexicographically. Assume that multivariate
polynomials fi in the definition of I(K) and
polynomials gi(x) have densities O(
Assume that ψ is some Eulerian transformations defined over the commutative ring K. It acts naturally on the sets (K*)n and Kn.
Assume that F is a multivariate map of Kn onto Kn of density O(nd) where d is the constant.
Then Eulerisation E = F(ψ(x)) is well defined and has density O(nd+1).
Some cryptographic applications of the Eulerisation procedure for special multivariate maps were considered in [47–48, 1].
In the special cases of K = Z2s–1, K = F2s–1, and K = Bs–1 we define procedures Mi, i = 1, 2, 3 to modify the multivariate map F on Kn with the trapdoor accelerator T via the composition with two tame Eulerian transformations ψ1 and ψ2 defined on the affine space (Z2s)n. In the case of T = [I(K), L1, L2, g1, g2,…, gt] as a result of double Eulerisation, we get a new transformation of Kn with the trapdoor accelerator ψi, (ψi)–1, i = 1, 2, I(K), L1, L2, g1, g2, …, gt.
accelerator can be given to the public. In the case of graph-based ciphers graph I(K) traditionally is known to the public.
In the next section, we apply double Eulerisation to stream cipher defined in terms of special induced subgraphs of the linguistic graph D(n, K), K ϵ { Z2s–1, F2s–1, Bs–1}.
All graphs we consider are simple, i. e. undirected without loops and multiple edges. Let V(Γ) and E(Γ) denote the set of vertices and the set of edges of Γ, respectively. The parameter |V(Γ)| is called the order of Γ, and |E(G)| is called the size of Γ. A path in Γ is called simple if all its vertices are distinct. When it is convenient we shall identify Γ with the corresponding antireflective binary relation on V(Γ), i. e. E(Γ) is a subset of V(Γ)×V(Γ). The length of a path is the number of its edges. The girth of a graph Γ, denoted by g = g(Γ), is the length of the shortest cycle in Γ. Let k≥3 and g≥3 be integers. The distance between vertices v and u of the graph Γ is a minimal length of the path between them. The diameter of the graph is the maximal distance between its vertices.
The graph is connected if its diameter is finite. The graph is k-regular if each vertex of the graph is incident exactly to k other vertexes. A tree is a connected graph which does not contain cycles: 1. An infinite family of simple regular graphs Γi of constant degree k and order vi such that diam (Γi)≤c logk–1(vi), where c is the independent of i constant and diam (Γi) is the diameter of Γi, is called a family of small world graphs. 2. Recall that infinite families of simple regular graphs Γi of constant degree k and order vi such that g(Γi)≥c logk–1(vi), where c is the independent of i constant and g(Γi) is a girth of Γi are called families of graphs of large girth. Tree (q-regular simple graph without cycles) in terms of algebraic geometry over finite field Fq. 3. The projective limit of graphs Γi is well defined and coincides with the q-regulate tree Tq.
We refer to a family of graphs Γi satisfying condition (iii) as tree approximation. We know examples of the family satisfying conditions 1, 2, and 3.
The family X(p, q) formed Cayley graphs for PSL2(p), where p and q are primes, had been defined by G. Margulis [51] and investigated by A. Lubotzky, Sarnak, and Phillips [52]. As it is easy to see the projective limit of X(p, q) does not exist.
D(q) with points (p) = (p01, p11, p12, p21, p22, p’22, …, p’ii, pi i+1, pi+1,i, p+i+1,i +1 … ), lines [l] = [l10, l11, l12, l21, l22, l’22 , …, l’ii, li i+1, li+1,i, l+i+1,i+1 …] and incidence relation given by equations lii – pii = l10 pi-1,i l’ii – p’ii = li,i-1 p01 li,i+1 – pi,i+1 = lii p01 li+1i – pi+1,i = l10p’ii.
These four relations are defined for i≥1, (p’11 = p11, l’11 = l11).
Historically graph D(q) is the first example of a description of q-regular forest in terms of Algebraic Geometry.
In [53] authors proved that D(n,q) defined via first n-1equations of D(q) form a family of graphs of large girth. The general point and line of these graphs are projections of (p) and [l] onto the tuples of their first n coordinates.
Unexpectedly it was discovered that these graphs are disconnected if n ≥ 6. So forest D(q) contains infinitely many trees and the diameter is an infinity.
In 1994 it was found out how to describe connected components CD(n, q) of graphs D(n, q) in terms of equations [54–55. In the case of families of graphs of large girth, we would like to have “speed of growth” c of the girth “as large as it is possible”. P. Erdos proved the existence of such a family with arbitrary large but bounded degree k with c = 1/4 by his probabilistic method.
In the case of families X(p, q) and CD(n, q) the constant c is 4/3. There are essential differences between the family of graphs X(p, q) and tree approximations. Recall that the projective limit of X(p, q) does not exist.
Cayley nature of X(p, q) does not allow to use of these graphs in multivariate cryptography. Various applications of graphs D(n, q) and CD(n, q) have been known since 1998. Let us consider the system of equations that defines linguistic graphs CD(n, K).
Let K stand for an arbitrary commutative ring. Noteworthy that graphs D(n, K) are defined over arbitrary commutative ring K have been already presented.
To facilitate notation in the future results on “connectivity invariants” of D(n, K), it will be convenient for us to define p-1,0 = l0,1 = p1,0 = l0,1 = 0, p0,0 = l00 = -1, p’0,0 = l’0,0 = -1, p1,1 = p’1,1, l1,1 = l’1,1 and to assume that our equations are defined for i≥0.
in [42, 49] 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α, u11, u12, u21, …, ur,r, u’r,r, ut t+1,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 [49] graphs D(n, K) are edge transitive. So their connected components are isomorphic graphs. Let vCD(k, K) be a solution set of 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).
It is easy to see that sets of vertices of
vCD(k, K), v ϵ Kt–1 form a partitions of the vertex
set of D(n, K). We consider more general
graphs vCDJ(k, K) defined via subset J = {i(
We refer to vCDJ(k, K) as the J-component of
D(n, K). We assume that equations ai(
The concept of quasiprojective variety over commutative ring K can be introduced via simple substitution of K instead of field F. It leads to concepts of homogeneous algebraic graphs over K, forest and tree approximations, and families of graphs of large girth over K. It was proven that for the case of commutative ring K with unity of odd characteristic graphs CD(n, K) are connected. So graph CD(n, q) = CD(n, Fq) for odd q is a connected component of D(n, q).
The following statement was proven in [49].
Proposition. For each commutative integrity ring K the families of graphs D(n, K), n = 2, 3, …, are forest approximations and families of graphs of large girth.
Let us describe selected multivariate algorithms based on algebraic graphs of large girth.
To achieve linear speed O(n) of the encryption described in Section 1 functions gi, i = 1, 2, …, t are selected in the form x1+c(i), c(i) ϵ K and the parameter t will be selected within the interval [2, [(n+5)/2]) when I(K) = D(n, K) or I(K) = CD(n, K).
Additionally we take parameters b(
We refer to the tuple (b(
Our choice ensures that in the case of a constant passive password, the single change of a single character of an active password leads to a change of the ciphertext produced from the selected plaintext. We choose an affine transformation L in the form of a linear map given by the following rule
L(x1) = x1+m(
Recall that an explicit description of linguistic graphs D(n, K) is given in the previous section and the general encryption algorithm is described in section 2. So, ciphers L E(n, K) L-1 and have a full description. In fact, we take the case of L1 = L and L2 = L-1. In the case of graph CD(n, K) we will use in fact the induced subgraph hCD(n, K), h = (h2, h3, …, ht), t = [(n+2)/4] of D(n, K) of all points and lines u = (uα, u11, u12, u21, …, ur,r, u’r,r , ut t+1 ur,r+1, ur+1,r, …) satisfying conditions ai(u) = hi.
Linguistic graph hCD(n, K) can be thought as bipartite graph with points (p) = (p01, p11, p12, p21, …, pi i+1, pi+1,i, p+i+1,i+1…), i = 2,3,…, t-1 and lines [l] = [l10, l11, l12, l21, l22,…, li i+1, li+1,i, l+i+1,i+1…], i = 2,3,…, t-1 of length n-t.
Their incidence is given by the following system of equations lii–pii = l10 pi–1,i li,i+1–pi,i+1 = lii p01 li+1i–pi+1,i = l10p’ii.
where p’22 is defined by the equation a2(p01, p11, p12, p21, p22, p’22) = h2 and can be written as p’22 = a2(p01, p11, p12, p21, p22, p’22)– h1+p’22 = b2(p01, p11, p12, p21, p22), other parameters are p’33 = a3(p01, p11, p12, p21, p22, p’22, p2,3, p3,2, p3,3 p’3,3)–h3+p’33 = b3(p01, p11, p12, p21, p22, p’22, p2,3, p3,2, p, 33), …, p’tt = at(p01, p11, p12, p21, p22, p’22, …, p’t–1,t–1, pt–1, t, pt, t–1, pt,t, p’t, t)–ht+p’t,t = bt(p01, p11, p12, p21, p22, p’22, …, p’t–1,t–1, pt–1, t, pt, t–1, pt, t).
p’i,i recurrently and their explicit substitution in the system of equations give us the equations of the linguistic graph.
We assume that the corresponding cipher
has the space of plaintexts Kn-t. We use active
passwords (b(
Algorithms with the encryption map TE(n, K)T-1 independently on the choice of active and passive passwords have multivariate encryption and decryption functions of degree 3.
In [56] the linearisation attacks on these ciphers with the interception of O(n3) pairs plaintext/ciphertext are presented. They can be executed in polynomial time O(n10).
The case LCE(n, K)L-1 is principally different.
As it follows from the results of [57] the encryption function corresponding to the selected active password has degree [(n+2)/4]+2. So the generation of a standard form for the encryption function can not be done in polynomial time.
So the directed linearisation attacks are theoretically impossible.
We can use induced graphs vCDJ(k, K) of
graphs D(n, K) which are J-components of them
where J = J(n) = {i(
Similarly to the case of CD(n, K) when J(n) = M(n) we can find the equations for vCDJ(n, K) via the elimination of special symbolic coordinates of general vertex <x> = <x1, x1,1, x12, x2,1, x2,2, x2,2, x2,3, x32, x3,3, x’33, …, xi,i, xi,i+1, xi+1,i+1, x’i+1,i+1,…>, 3 ≤ i ≤ [(n+2)/4–1] (point or line) of D(n, K) given by the list x’i(k),i(k), k = 2, 3, …, t(n).
The variable x’i(k, i(k)) can be found from the equation ai(k)(<x>) = vi(k). The substitution of symbolic expressions of x’i(k), i(k) into the incidence conditions of D(n, K) gives us the linguistic interpretation of vCDJ(n, K). This bipartite graph has sets of points and lines isomorphic to the affine space Kl where l = n– t(n).
We associate with the family of graphs vCDJ(n, K) the sequence of encryption maps obtained by the following rules. We assume that symbolic vertex <x> = (x) from Kn–t(n) is a point and the graph is given in its linguistic interpretation. Let us rename the indexes of passive password. We assume that constants k points and lines of vCDJ(k, K) by 1, 2, …, n–k. So and t(n) = t can be agreed by correspondents x = (x1, x2, …, xn–t(n)). via an open channel. Under the described
The nonlinear graph-based transformation above assumptions cipher has a linear speed N is the following one. v(n) of size O(n). The slope of the v(n) is defined
We select parameter k and form tuples by the value of the weight parameter
ka = (ᾳ(
Let ᾳN(u) be the operator of taking the plaintext. It means that a brute force attack on
neighbor of u = (u1, u2, …, un–t) from the graph the cipher requires p2kqt elementary
vCDJ(k, K) with the color of u1+ᾳ. We consider operations where p is the order of K* and q is
the sequence 1u = β(
We already select parameter k and form xi→xi, i = 2, 3,…, n–t–1 where elements d(i)
tuples ka = (ᾳ(
We consider the walk in the graph with the Let us consider double Eulerisation kF(s–1,
starting point u0 = (x), u1, u2, …, u2k where colors n, t) of E = kEDt(n, F2s–1) given by
of u1 = x1+β(
Let u2k = (x1+ᾳ(
As it follows from [57] the maximal degree n, t) of E = kEDt(n, Bs–1), given by the of Fi is t(n)+2. transformation D–1JDED–1J–1D acting on the
As in the cases of ciphers based on graphs affine space (Bs–1)n–t.
D(n, K) and CD(n, K) the encryption map will be Noteworthy that Double Eulerisations
conjugated with the special linear kF(s–1, n, t), kE(s–1, n, t) and kB(s–1, n, t) have
transformation L given by the following rule. the same active passwords with the
L(x1) = x1+m(
We denoted described below cipher as of new ciphers we need just simply add
kEDt(n, K). The map LNL-1 has active password parameters d(
Parameters m(
In the case of arithmetical rings, we have to change the parameter p = 2s–1–1 for p = 2s–2.
In the case of Boolean ring Bs–1, its
multiplicative group is trivial. We simply take
tuples (ᾳ(
For the first two implementations, we select the double Eulerisations of ciphers kEDt(m, K), m = n-t with K = F256, and t = 128 with weights w = 213 and 216.
Core encryption map has a highly nonlinear nature. Additionally, Eulerisation eliminates the multivariate nature of the encryption and decryption.
So the linearisation attacks by adversaries are unfeasible. The bruit fourth attack requires (215)∙255k, where k = 2l is the chosen length of the walk in the graph.
Our software is written in C++ programming language and therefore it is portable and runs on many platforms such as Unix/Windows. The interface allows users to enter active and passive passwords of selected length. The program is supported by a key exchange protocol based on Eulerian transformations from nES(Z512) of Z512 [45–46]. It allows the elaboration of the tuple of nonzero elements from Z*512 of length n together with the matrix of size n times n with entries from Z512. This data can be used for the construction of passive and active passwords.
Experimental Measurements. To evaluate the performance of our algorithm, we use different sizes of files. We denote by t (k, L) the time (in milliseconds) that is needed to encrypt or decrypt (because of symmetry). The file size is in kilobytes for passwords of length L. Then the value of t(k, L) can be represented by the following matrices (Figs. 1 and 2).
Figure 2 Run time for the System In the implemented case the algorithm has nice mixing properties. change of a single character leads to the change of at least 98 percent of the characters in the ciphertext.
In [42] the first stream cipher based on algebraic graphs defined over the commutative ring K with unity was suggested. The corresponding bijective multivariate map acting on Kn was a cubical transformation as well as the inverse map. It means that the cost of linearisation attacks by an adversary is O(n10) under the condition that the adversary intercepts O(n3) distinct pairs of kind plaintext. For the improvement of resistance of cipher against linearisation attack, many modifications and obfuscations of this algorithm were proposed. Despite the various changes, all these modifications use the encryption map of a multivariate nature.
Our paper is the first attempt to construct a symmetric cipher of hidden multivariate nature of encryption and decryption procedures [46] where this general idea is used for the construction of asymmetrical cryptosystems.
In the case of K = Z2s-1, K = F2s–1, and Boolean rind Bs-1 of order 2s-1 we use tame Eulerian transformations ψ1 and ψ2 from the group nEG (Z2s) sending variable xi to a monomial term. Assume that 1T and 2T are information about corresponding decompositions of ψi into Jordan-Gauss transformations. We use the bijection BK between elements of the multiplicative group Z*2s of Z2s and elements of the ring K.
Effectively computable examples of such correspondences are presented above.
Let nB be the map sending tuple (x1, x2, ..., xn) to (BK(x1), BK(x2),..., BK(xn)) and nB-1 is the inverse map from Kn to (Z*2 s).
Assume that F is a multivariate map from Kn to Kn and T its trapdoor accelerator. We can consider map nE = nB-1 ψ1 nB F nB–1 ψ2 nB which maps Kn to Kn.
If correspondents Alice and Bob share the information on symmetric trapdoor accelerators T, 1T, and 2T then the family of transformations nE can be used as stream cipher. The encryption and decryption procedures have complexity O(n2).
We use this scheme with sparse Eulerian transformations ψ1, ψ2 and graph-based pair (F, T) such that their reimages can be computed in time O(n).
The D(n, K) graph description which is part of information piece T can be given publicly.
In fact, the encryption procedure is given via the walk w in the induced subgraph DJ(n, K) which is the union of several connected components of the D(n, K).
The transformation F is an affine deformation of L1GL2 of the DJ(K) = DJ,a(K) based transformation G induced via the special walk w(J, a) on the graph. The set J of cardinality r < t, t = [(n+2)/4]–1 is some subset of {2, 3, ..., t} and the tuple a = (a1, a2, ..., ar) is formed by elements from K. So we have C rn–rqr, q = 2s–1 nonintersecting induced subgraphs. The transformation G is induced by the path w = w(b1, b2, ..., b2k) of selected length 2k depending on the parameters biϵK* if K = Z2s–1 or K = F2s–1 and ai ϵ Bs-1–{0} in the remaining case K = Bs–1.
Different pieces of information (J, (a1, a2, ..., ar), (b1, b2, ..., b2k)) form the active passwords of the cipher.
Selected sparse linear transformation L1 = L which depends on the selected tuple (m1, m2, ..., mn–r–1) from (K–{0})n–r–1 n–r and L2 = L–1 hide the graph-based transformation.
Selected space Eulerian transformation G1 of the variety (Z2s)n–r depends on an element from (Z2s)n–r–1. G2 is defined as the inverse of G1. Eulerian transformations allow us to hide the multivariate nature of the encryption map.
The following fact is important.
Different active passwords produce distinct ciphertexts from the chosen plaintext.
If the length of tuples is O(
We suggest supporting the stream cipher by
the key exchange protocol of Noncommutative
Cryptography implemented with the platform
of Eulerian transformation nES(Z2s) defined
over the commutative ring Z2s [45–46]. Assume
that secure protocol allows Alice and Bob to
elaborate on the transformation of kind (
Then they share ϻ1, ϻ2, …, ϻn from Z*2s and n2 elements a(i,j) from Z2s–1.
Correspondents can use the defined above bijections between Z*2s, Z2s–1, F2s–1, and Bs–1 to form the passive and active passwords of the stream cipher.
The main result of the paper is a complex cryptographical algorithm based on a highly noncommutative group of polynomial transformations GA(n, K) of Kn, n = 2, 3, … defined over finite commutative ring K with a unity.
In the current postquantum reality the idea to change the cyclic group of Diffie Hellman protocol for a noncommutative group or semigroup with several generators can lead to safe protocols of Algebraic Postquantum Cryptography (APQ).
We suggest using GA(m, K) for the safe elaboration of collision polynomial map G of degree 3 from Kn to Km. G is written in its standard form of Computer Algebra. We can use O(m4) of its coefficients for the extraction of some “seed” S of size s(m).
This research is partially supported by the British Academy Fellowship for Researchers under Risk 2022 and partially supported by the British Academy award LTRSF\100333.