Discovery of q-regular forest equations over finite field description in terms of an infinite system of quadratic Fq had an impact on the development of Graph Cryptography and constructions of robust stream ciphers. We observe known encryption algorithms based on the forest approximations via families of q-regular graph, their modifications defined over the finite arithmetical rings and implementations of these ciphers. The main result is the construction of new family of stream ciphers based on forest approximation which has multivariate nature. The method allows selection of the polynomial degrees of multivariate encryption and decryption procedures.
Graph Based Cryptography (GBC) area is moving with great speed into the main stream of computer design, Information sciences, Information and
programming,
Intelligence and design, Artificial Intelligent and various field of research. Application of GBC is in diverse area such as Data structures, Communication networks and their security. A Graph-based approach centres on conserving the environment of security events by breaking down factors of observable data into a graph representation of all cyber vestiges, from all data aqueducts, counting for all once and present data. For secret communication, Ciphers can be converted into graphs. The Application of Graph Theory plays a vital role in various field of Engineering and Sciences. GBC is used
for the key exchange, development of Multivariate Public Keys, key dependent message authentication codes and algorithms of Noncommutative Cryptography (see [24]-[38]) Especially
commonly used as a tool of symmetric encryption. First cryptographical applications of Graph Theory appeared in the areas of Symmetric Cryptography and Network Security. This paper reflects some results in the area of applications of families of algebraic graphs of 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 corresponding cipher. The girth of several known families of algebraic graphs of large girth is not computed. It just evaluated via the lower bounds.
2020 Copyright for this paper by its authors. CEUR
ceur-ws.org
Observed and presented new ciphers 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 accordingly 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 (see [21]) is a piece of information A such that the knowledge of A allows to compute the reimage of F in time O(n2).
In presented ciphers correspondents Alice and Bob shares 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 can intercept large amount of pairs plaintext/corresponding ciphertext and try to approximate maps F-1 and F. So degree of F is an important parameter for the cryptanalytical studies. The most important (active) part of password are is the information about the walk in the algebraic graph.
In fact the first description of selected graph based stream cipher based on approximations of qregular tree where q is a prime power was presented in [7] or [45]. The first implementation of this algorithms appeared at the beginning of 2001 [1]. During last twenty years many new results on the construction of new encryption tools and there cryptanalysis were obtained. They lead to understanding of multivariate nature of these algorithms and necessity of usage of infinite algebraic graphs defined over infinite commutative rings of kind Fq [x1, x2 ,…, xn] or more general K[x1, x2,…, xn] where K is a finite commutative ring. Implemented in [1] encryption map is a polynomial map of degree 3 such that their inverse is also cubical transformation. So, adversary can use linearisation attacks and after the interception of O(n3) pairs of kind plaintexts/corresponding ciphertext he/she can approximate the encryption map in time O(n10). So, Section 2 is dedicated to observation of ciphers based on algebraic graphs and resistant to such linearisation attacks.
The general scheme of flexible encryption algorithm based on special family of algebraic graphs defined over commutative ring is presented there.
The theory of approximations of regular trees is presented in Section 3 which contains description of q-regular forest approximation D(n, q), n→∞ [2] and tree approximation CD(n, q) [3]. Analogues of these families of graphs over an arbitrary commutative ring are presented there together with the known results on their properties and applications.
Precise description of observed graph based algorithm is given in the Section 4 together with evaluation of the degrees of encryption map and its inverse.
The special cases of CD(n, 256) defined over the finite field F256 is selected for an implementation. Parameters of corresponding computer simulations are given at the end of Section 4.
Last Section 5 is the conclusion.
We have to report that the implemented case of D(n, q) based encryption E(n, q) is far from being optimal. As it was showed in [4, Serdica] the increase of parameter q leads to faster encryption of files of the same size. Noteworthy that the usage of loaded multiplication tables makes immaterial the difference between case of prime q and composed prime powers. Such tables allow to use q=128 corresponding to the alphabet ASCEE with the essential speed increase comparably to implemented in [1] q=127, where operator of taking modulo 127 is used cn times where constant c depends on the length of the password. The multivariate nature of D(n, q) encryption was noticed in [4] (see also [22] for the case of arbitrary ring K), described their symbolic computations turned out to be cubic. This fact was mathematically proved in [5] for arbitrary parameters n and q.
The standard usage of multivariate transformation E(n, q) with two affine transformation T1 and T2 in the form T1 E(n, q)T2 allow us to improve drastically the mixing properties of the cipher. Noteworthy that in the implemented case of E(n, 127) encryption the change of single characters of the plaintext leads to the change of 48-52 percents of characters of corresponding ciphertexts. The experiment with special linear transformations T1 and T2 was described in [6]. To preserve linear time O(n) of the encryption we have to select sparce transformations, i. e. those with O(n) nonzero entries of corresponding matrices. Special sparce transformations allow us to improve drastically mixing properties of E(n, q) encryption. For selected in [6] cases the single change of a plaintext character leads to the change of more than 98 percents of characters of corresponding ciphertext. As it was shown in [8ust linguistic] transformation E(n, q) with the password of length less than [(n+5)] has no fixed points. This property holds for the case of ciphers of kind T1 E(n, q)(T1 )-1.
More general graphs D(n, K) defined over arbitrary commutative ring K can be obtained via simple change of Fq for K (see [7]). Investigation of dynamical systems corresponding to these graphs showed the similarity of general graphs D(n, K) of the graphs defined for the case of fields (see [8], [9] and [10]. If passwords corresponds to tuples of characters from the multiplicative group K* of the ring K then different passwords of length <[(n+5)/2] produce distinct ciphertext from the selected plaintext. It means that case of arithmetic rings Zm of integers of modulo m is attractive for the implementations.
Noteworthy that the cases of fields Fq, q=2m of characteristic two and rings Z q, q=2m are most convenient for implementations because of files in the computer are presented in the form 0, 1sequences.
Recall that the girth of a graph is the length of its minimal cycle. The connected components CD(n, q), n=2, 3,… of algebraic graphs D(n, q), q>1 form a family of tree approximations, i. e well defined projective limit of them is an infinite q-regular tree. Graphs D(n, q) are edge transitive. So, their connected components are isomorphic. The system of quadratic equations which defines CD(n,q) were presented in [11]. The union of these equations gives an algebraic description of qregular tree. Existence of such description is very important for Computer Science because a q-regular tree is the deterministic part of branching process.
Noteworthy that the plaintext and the ciphertext of E(n, q) encryption are located in the same connected component of D(n, q). Graphs CD(n, q) have a natural analogue CD(n, K) defined over arbitrary commutative ring K with at least two elements, CD(n, K) is an induced subgraph of D(n, K) (see [7]). The description of CD(n, K) in terms of the system of recurrent quadratic equations is given in [7] together with the description of CD(n, K) based encryption CE(n, K).
It works with the space of plaintexts Km, m=3/4n +c where c, c<3 is some nonnegative integer constant. It is important that group of transformations of CE(n,K) corresponding to various passwords acts transitively on the space of plaintexts while the group generated by various transformations of kind E(n, K) is intransitive. It leads to better mixing properties of CE(n, K) in comparison with those of E(n, K). In fact we have to use T1CE(n, K)(T1)-1 where T1 is a special sparce transformation of AGLm(K).
Another q- regular tree approximation A(n, q), q=2,3, …were defined in [43]. It has some advantages in comparison with graphs CD(n, q). For instance the graphs are defined by simple homogeneous equation with two linear and one quadratic monomial terms. Finite field Fq can be substituted by general commutative ring K and graphs A(n, K) can be obtained this way (see [43] or [10]). The girth g(A(n, q)) of the graphs A(n, q)=A(n, Fq) can be bounded from below via inequality g(A(n, q))≥[(n+2)/2] [44]. The computer simulation support the conjecture that A(n, Zm) based encryption with passwords from ((Zm)*) t , m>2, t is an even parameter <[(n+2)/4 is such that different passwords produce distinct ciphertext from the selected plaintext. We will use notation AE(n, K) for the A(n, K) based ciphers.
To summarise written above we discuss some properties of three graph based steam ciphers E(n, K), CE(n, K) and AE(n, K) defined in the case K=Fq, q>m and K=Zm, m>2. All of them can be used for Information Systems protection. For practical implementation case of large finite fields and arithmetic rings Zt, t=2m is preferable.
The families of graphs D(n, K), A(n, K) defined over arbitrary commutative ring K are bipartite graphs of type (1, 1, n-1) with partition sets which are two copies of Kn (see [12]) , 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 colours of the point and the line. The following linguistic property holds. Each vertex of the graph has a unique neighbour of the chosen colour.
Graph CD(n,K) 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.
In fact the architecture require a partition of information into blocks of the same size. So, parameters n and m equals to some selected constant. the length of the password is another even constant which has an impact on the speed of encryption. Other option to increase speed of execution is the increase the cardinality of the ground field or ring. 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 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 ),…, anXnbnYn= 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 from the equations in the definition of the linguistic graph I(K).
We define the polynomial map F from Kn to K n via the following scheme (see [23]). Take the special point X=(x1, x2,…, xn) of I(K[x1, x2,…xn]) and consider the list of colours g1(x1), g2(x1), …, gt(x1). We compute the path v0Iv1Iv2…Ivt where v0=X and vi+1 is the neighbour of vi with the colour gi(x1), i=1,2, …, t and I=I(K[x1, x2,…, xn]). Then the destination point vt of this path can be written as (gt(x1), F2(x1, x2), …, Fn(x1, x2,…, xn)). The map F is given by the rule x1→gt(x1), x2→F(x1, x2),…, xn→F(x1, x2,…, xn). It is easy to see that F=F(g1, g2,…, gt) is a bijective map if and only if the equations of kind gt(x1)=b have unique solutions for unknown x1 for each b from K.
So family of linguistic graphs nI(K), n=2, 3,… together with family of affine transformations Tnϵ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 Tn(F(g1, g2,…, gt)(Tn)-1
Correspondents Alice and Bob share the password given by g1, g2,…, gt and the sequence of transformations Tn , n=2, 3,… We assume that inverse maps (Tn)-1 are computed and presented explicitly. For the encryption of potentially infinite plaintext (p)=(p1, p2,…, pn) they will use transformation TnF(g1, g2,…, gt)(Tn)-1. One of them creates the plaintext (p) and computes the ciphertext Tn(F(g1, g2,…, gt)(Tn)-1(p)=c recurrently. The procedure is the sequence of the following steps.
S1. He/she computes (Tn)-1(p1, p2,…, pn) =(r(
S3. Let Na(x1, x2,…, xn) be the operator of taking the neighbour of point (x1, x2,…, xn) with the
colour a in the linguistic graph nI(K) and aN(y1, y2,…, yn) be an operator of taking the neighbour of
line [y1, y2,…, yn] with the colour a. He/she executes the following operation. Computation of
v1=Na(
Assume that one of correspondents received the ciphertext c. He/she decrypts via the following steps.
D1. Computation of u as (Tn)-1(c)=u and getting the solution x=r(
D3. Computation of the plaintext (p) as T(r).
OBFUSCATION OF THE ALGORITHM.
Let us consider the colour jump operator Ja which transforms point (p1, p2,…, pn) of the graph I(K) to the point (a, p2, p3,…, pn).
We can change the encryption map TnF(g1, g2,…, gt)(Tn)-1 for the TnF(g1, g2,…, gt)Jg(Tn)-, where Jg is a colour jump operator acting on points of I(K[x1, x2,…xn] with the colour g(x1)ϵK(x1) such that the equation of kind g(x1)=b has a unique solution for each parameter b from K.
After this change assumption the bijection of gt on K is immaterial. Encryption procedure requires
computation of (Tn)-1(p1, p2,…, pn) =(r(
For the decryption of ciphertext c the user has to compute u’=(u’1, u’2,…, u’n) as (Tn)-1(c ), solve
for x the equation g(x)=u’1, use the solution x=r(
Girth and diameter of a graph are the minimal length of its cycle and the maximal distance of the graph. The constructions of finite or infinite graphs with prescribed girth and diameter is an important and difficult task of the Graph Theory.
Noteworthy that the incidence of classical projective geometry over various fields is a graph of girth 6 and diameter 3. J. Tits defined generalised m-gons as bipartite graphs of girth 2m and diameter m. Feit and Higman proved that finite generalised m-gons with bi-degrees >2 exist only in the cases of m=3, 4, 6, 8 and 12. Geometries of finite simple groups of rank 2 are natural examples of generalised m-gons for m=3,4,6, 8. Classification of flag transitive generalised m-gons of Moufang type were obtained by J. Tits and R.Weiss.
Infinite families of graphs of large girth of bounded degree are important objects of Extremal Graph Theory which were introduced by P. Erdős’. He proved the existence of such families via his well-known probabilistic method. Nowadays few explicit constructions of such families are known. The concept of infinite family of small world graphs of bounded degree turns out to be very important for various applications of graph theory.
Noteworthy that the only one family of small world graphs of large girth is known. This is the family X(p, q) of Ramanujan graphs introduced by Gregory Margulis [13] and investigated via the computation of their girth, diameter and the second largest eigenvalue by A. Lubotsky, R.Phillips and P.Sarnak [14].
We have to admit that studies of families of graphs Γ i with well defined projective limit Γ , which is isomorphic to infinite tree, is well motivated.
We refer to such family as tree approximation. There is only one approximation by finite graphs which is a family of large girth. This is the mentioned above family of CD(n, q) defined by F. Lazebnik, V. Ustimenko and A.Woldar [3].
The question whether or not CD(n, q) form a family of small world graphs has been still open since 1995.
In 2013 the tree approximation by finite graphs A(n,q) which is a family of small world graphs was presented (see [43]).
One of the main statements of this paper is A(n, q) where n=2, 3,.... is a family of large girth.
We generalise these results in terms of the theory of algebraic graphs defined over arbitrary field and consider properties and applications of above mentioned graphs.
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 antireflexive binary relation on V(Γ ), i.e. E(Γ ) is a subset of V(Γ )×V(Γ ). The length of a path is a 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 maximal distance between its vertices.
Graph is connected if its diameter is finite. 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 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. Projective limit of graphs Γi is well defined and coincides with q-regulat tree Tq.
We refer to family of graphs Γi satisfying condition (iii) as tree approximation. We known example 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 [13] and investigated by A. Lubotzky, Sarnak and Phillips [14]. As it is easy to see the projective limit of X(p, q) does not exist.
Let F be a field. Recall that a projective space over F is a set of elements constructed from a vector space over F such that a distinct element of the projective space consists of all non-zero vectors which are equal up to a multiplication by a non-zero scalar. Its subset is called a quasiprojective variety if it is the set of all solutions of some system of homogeneous polynomial equations and inequalities.
An algebraic graph φ over F consists of two things: the vertex set Q being a quasiprojective variety over F of nonzero dimension and the edge set being a quasiprojective variety φ in Q × Q such that (x, x) is not element of φ for each x ∈ Q and xφy implies yφx (xφy means (x, y) ∈ φ). The graph φ is homogeneous (or M-homogeneous) if for each vertex v ∈ Q the set {x | vφx} is isomorphic to some quasiprojective variety M over F of nonzero dimension. We further assume that M contains at least 3 elements.
Theorem [15]. Let Γ be homogeneous algebraic graph over a field F of girth g such that the dimension of neighborhood for each vertex is N, N ≥ 1. Then [(g − 1)/2] ≤ dim(V)/N.
The following corollary is an analog of Even Circuit Theorem by Erdős’ for finite simple graphs.
Corollary. Let Γ be a homogeneous graph over a field F and E(Γ) be a variety of its edges. Then dim(E(Γ)) ≤ dimV(Γ)(1 + [(g − 1)/2] -1 .
We refer to a family of homogeneous algebraic graphs φn for which the dimension of neighborhood for each vertex is independent constant N, N≥ 1 as a family of large girth if girth of each graph φn is bounded from below by linear function αn +β defined by constants α and β .
We refer to a homogeneous algebraic graph as algebraic forest if it does not contain cycles. Their term algebraic tree stands for the connected algebraic forest.
We say that family of homogeneous algebraic graphs φn is a forest (tree) approximation if projective limit of φn is an algebraic forest (tree). 3. 4. Graphs D(n,K).
Graphs D(n,q) which defines projective limit 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 – p i,i+1 =lii p01 ; l i+1i - p i+1,i = l10p’ii .
This four relations are defined for i≥1, (p’11= p11, l’11= l11).
Remark. You can see that indexes of vectors correspond to coordinates of positive roots of root system A1 with a wave.
Historically graph D(q) is not the first example of description of q-regular forest in terms of Algebraic Geometry. Geometries of buildings (see [16] and further references) corresponding to extended Dynkin diagram A1 as incidence structures are q+1-regular trees or q+1-regular forests. As a result we get a description of a tree in group theoretical terms.
In [17] it was noticed that the restriction of this incidence relation on orbits of Borel subgroup Bacting on maximal parabolic subgroups are q-regular bipartite graphs. So we get a description of a qregular tree in terms of positive roots of A1 with a wave.
In [2] 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. F. Lazebnik conjectured that connected components of graphs D(n, q), n =3,4, … form a family of small world graphs. This conjecture is still open.
In 1994 it was found out how to describe connected components CD(n, q) of graphs D(n, q) in terms of equations (see [11], [3]). 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. In the case of A(n,q) we just get inequality 1≤ c<2. So exact computation of the girth is the area of the future research. There are essential differences between family of graphs X(p, q) and tree approximations. Recall that the projective limit of X(p, q) does not exist.
Families X(p,q), CD(n,q) can be used for the constructions of LDPC codes for noise protection in satellite communications. D. MacKay and M. Postol [19] proved that CD(n, q) based LDPC codes have better properties than those from X(p,q) for the constructions of LDPC codes. In [18] it was proved that A(n,q) based LDPC codes even better than those from CD(n,q).
Cayley nature of X(p,q) does not allow to use these graphs in multivariate cryptography. Various applications of graphs D(n,q) and CD(n,q) have been known since 1998.
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.
Graphs CD(k,K) with k ≥ 6 were introduced in [10], [11] for 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 u r,r +1, u r+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 [11] 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 vCD_J(k, K) defined via subset J={i(
We refer to vCDJ(k, K) as 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 (see [20]). So graph CD(n,q)=CD(n, Fq) for odd q is a connected component of D(n,q).
Theorem [11]. For each commutative integrity ring K the families of graphs D(n, K), n=2,3,…,n=2,3,.. are forest approximations and families of 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 insures that in the case of constant passive password the single change of a single character of active password leads to a change of the ciphertext produced from the selected plaintext. We choose an affine transformation T in the form of linear map given by the following rule
T(x1)=x1+m(
Recall that explicit description of linguistic graphs D(n, K) is given in the previous section and general encryption algorithm is described in section 2. So, ciphers T E(n,K) T-1 and have full description. 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 u r,r +1, u r+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 – p i,i+1 =lii p01 ; l i+1i - p i+1,i = l10p’ii .
where p’ 22 is defined by the equation a2(p 01 , p 11 , p 12, p 21, p 22, p’22 )=h2 and can be written as p’22 = a2(p 01 , p 11 , p 12, p 21, p 22, p’22 )-h1 +p’22 = b2(p 01 , p 11 , p 12, p 21, p 22), other parameters are p’33= a 3(p 01 , p 11 , p 12, p 21, p 22, p’22 , p 2,3, p 3,2, p3,3 p’3,3)-h3 +p’33 = b3(p 01 , p 11 , p 12, p 21, p 22, p’22, p 2,3, p 3, 2, p , 33), …, p’tt=a_t(p01, p11, p12 , p21, p22, p'22 , …, p’t-1,t-1, pt-1, t, p t, 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, p t, t-1 , pt, t ).
The computation of symbolic expressions p’i,i recurrently and their explicit substitution in the system of equations give us the equations of the linguistic graph.
We assume that corresponding cipher has the space of plaintexts Kn-t. We use active passwords
(b(
We will use presented in Section 2 obfuscation scheme for each cipher TE(n, K)T-1 and TCE(n, K)T-1 in the case K=Fq, q>2. We use special disturbance function g of Ig selected as x→xe+b where bϵFq, eϵZd, d=q-1 and (e, d)=1. So, the notations DE(n, K) =TE(n, K)IgT-1 and DC(n,K)=TCE(n, K)IgT-1 will be used for these encryption schemes with the disturbance.
Algorithms with the encryption maps TE(n, K)T-1 independently on the choice of active and passive passwords have multivariate encryption and decryption functions of degree 3. In [39] the linearisations attacks on these ciphers with the interception of O(n3) pairs plaintext/cipheretext are presented. They can be executed in polynomial time O(n10).
The ciphers DE(n, K) use cubical encryption maps as well but the usage of disturbance map D: x→xe lead to the increase of the degree r of inverse maps. Parameter r can be evaluated from below by the polynomial degree of transformation D-1 acting on the elements of multiplicative group K*. So, if K=Fq, q=232 then the order of polynomial decryption map is at least 231. It justifies that direct linearisation attacks are not feasible.
Case TCE(n, K)T-1 is principally different. As it follows from the results of [40] (ust wroblevskska) the encryption function corresponding to selected active password has degree [(n+2)/4]+2. So the generation of standard form for the encryption function can not be done in polynomial time.
So the directed linearisation attacks are theoretically impossible. Principle difference of DC(n, K) and TCE(n, K)T-1 is the fact that the usage of disturbance implies the fact that the degree of inverse function is essentially higher than those for encryption function.
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 the sets 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 points and lines of vCDJ(k, K) by 1,2,…, n-k. So x=(x1, , x2,…, xn-t(n)).
The nonlinear graph N based transformation is the following one.
We select parameter k and form to tuples ka=(ᾳ(
Let ᾳN(u) be the operator of taking the neighbour of u=(u1, u2,…, un-t) from the graph vCDJ(k, K)
with the colour of u1+ᾳ. We consider the sequence 1u= β(
We also will use the obfuscation gN((x1, x2,…, xn-t)=(g(x1), w2,…, wn-t), where g(x) is selected bijective polynomial function on K of degree at most t(n)+2.
Let us investigate the multivariate nature of the map N. We may assume that coordinates of a general point (x) are variables x1, x2,…, xn-t. We consider the multivariate ring K[ x1, x2,…, xn-t ] and the graph vCDJ(K[x1, x2,…, xn-t ]) with points and lines of kind <g1, g2,…, gn-t>, giϵ K[x1, x2,…, xn-t ].
We already select parameter k and form to tuples ka=(ᾳ(
We consider the walk in the graph with the starting point u0=(x), u1, u2,…., u2k where colours of
u1=x1+ β(
Let u2k=(x1+ᾳ(
As it follows from [40 Ust, Wrob] the maximal degree of Fi is t(n)+2. it is clear that the degree of obfuscated map gN is also t(n)+2. If g has degree d, d>2 and order r then g-1 has degree dr-1 and the degree of gN can be evaluated from below as dr-1(t(n)+2).
As in the cases of ciphers based on graphs D(n, K) and CD(n, K) the encryption map will be
conjugated with the special linear transformation T given by the following rule.
T(x1)=x1+m(
We denoted described below cipher as kED1(n-t, K). The map TgNT-1 has active password (ᾳ(
Parameters m(
The following important property holds. The change of the active password lead to the change of the ciphertext for the selected plaintext. It means that brut force attack on the cipher requires p2kqt elementary operations where p is the order of K* and q is the size of the commutative ring K.
The implemented case
For the first two implementation we select the cases of ciphers kEDt(m, K),m=n-t with K= F256, g of kind g= x2+b and t=128 with weights w=213 and 216. In both cases the degree of encryption map will be at least 130 the degree of the encryption map will be bounded below by 130∙128. So the linearisation attacks by adversary are unfeasible. The bruit forth attack require (215)∙255k, where k=2l is the chosen length of the walk in the graph.
CRYPTALL 6 software is written in C++ programming language and therefore it is portable and runs in many platforms such as Unix/Window. The context diagram is depicted in Fig. 1. The interface is friendly. It allows users to enter active and passive password of selected length. The program is supported by key exchange protocol based on Eulerian transformations of F*256 (see [21] ). It allows the elaboration of the tuple of nonzero field elements of length k together with the tuple of arbitrary field elements of length 128 to form both passwords.
Experimental Measurements To evaluate the performance of our algorithm, we use with different size of files. We denote by t (k, L) the time (in millisecond) 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 (Fig. 2 and Fig 3).
L\k
4 12 16 3000 1388 3728.5 4967 8 2625.75 4000 1864 3641.5 4988.25 6592.5
In both cases algorithms have nice mixing properties. change of single character lead to the change at leas 98 percents of the characters in the ciphertext.
The main theoretical result of the paper is explicit construction of the family of multivariate map
of affine maps Fn based on the graphs CD(n, K) with the trapdoor accelerator of linear degree cn ,
c=3/4 acting on affine space Kn defined over arbitrary commutative ring K with at least 3 elements.
Corresponding cipher has execution speed of kind ¼ n2+O(n) which is proportional to the length of
active password of size O(
The disadvantage of Fn in the comparison with the D(n, K) based cipher is essentially lower speed of encryption, O(n2) instead of O(n). So the usage of Fn will drastically improve the security level of the encryption but the speed of processing is essentially slower than in the case of the usage of graphs D(n, K).
Noteworthy that speed of processing is very important parameter. That is why we suggest usage of flexible ciphers kEDt(m, K),m=n-t where t is the selected constant. All of them have a linear speed of execution. Case t=0 corresponds to D(n, K) based cipher. Increasing of parameter t leads to the increase of resistance of cipher against linearisation attacks.
So correspondents can govern the security level within the family of kEDt(m, K),m=n-t ciphers. The idea to use connectivity invariants of graphs D(n, K) was formulated in [42].
The implemented stream ciphers based on algebraic graphs given by equations found practical usage in Fiji Islands and Australia (see [1], [42], [46], [55], [56], [57]), Ukraine ([41], [58], [65]), Poland ([6], [39], [50], [54],[55], [62]), Brasil ([47]Ustimenko Futorny), Sultanate of Oman ([48], [52],[62], [63],) and Canada [59], [60], [64]). In all cases the degree of the inverse map was bounded by 3. We suggest new class of ciphers based on algebraic graphs with option to unbounded increase of the inverse map by customers. We hope that new algorithms with the resistant to linearization attacks and linear speed of encryption will be successfully used for protection of Information systems and Big Data Processing.
This research is partially supported by the Fellowship of British Academy for RaR 2022. [8] V. Ustimenko (2007). Linguistic Dynamical Systems, Graphs of Large Girth and Cryptography, Journal of Mathematical Sciences, Springer, 140, No. 3, p. 412-434. https:/doi.org/ 10.1007/s10958-007-0453-2 [9] V. A. Ustimenko, U. Romanczuk, On Dynamical Systems of Large Girth or Cycle Indicator and their applications to Multivariate Cryptography, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics ", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, 427, 2012, p. 231-256, https:/doi.org/ 10.1007/978-3-642-296949_10 [10] V. A. Ustimenko, U. Romanczuk, On Extremal Graph Theory, Explicit Algebraic Constructions of Extremal Graphs and Corresponding Turing Encryption Machines, in "Artificial Intelligence, Evolutionary Computing and Metaheuristics ", In the footsteps of Alan Turing Series: Studies in Computational Intelligence, Vol. 427, Springer, January, 2013, 257-285. [11] F.Lazebnik, V. Ustimenko and A. J. Woldar (1996). A characterisation of the components of the graphs D(k,q), Discrete Mathematics,157, p. 271-283. https:/doi.org/10.1016/S0012365X(96)83019-6 [12] V. Ustimenko, Maximality of affine group, hidden graph cryptosystem and graph's stream ciphers, Journal of Algebra and Discrete Mathematics, 2005, v.1, pp 51-65. [13] G. Margulis(1988). Explicit group-theoretical constructions of combinatorial schemes and their application to design of expanders and concentrators, Probl. Peredachi Informatsii, 24, No. 1, p.51-60. [14] A. Lubotsky, R. Philips, P. Sarnak (1989). Ramanujan graphs, J. Comb. Theory, 115, No. 2, p.
62-89. https://doi.org/10.1007/BF02126799 [15] T. Shaska, V. Ustimenko (2009). On the homogeneous algebraic graphs of large girth and their applications, Linear Algebra and its Applications, 430, No. 7, p. 1826-1837. https:/doi.org/10.1016/j.laa.2008.08.023 [16] F. Buekenhout (editor), Handbook in Incidence Geometry, Ch. 9, North Holland, Amsterdam, 1995. [17] V. Ustimenko (1989). Affine system of roots and Tits geometries, Voprosy teorii grupp i gomologicheskoy algebry, Yaroslavl, p.155-157. [18] M. Polak, V. A. Ustimenko (2012). On LDPC Codes Corresponding to Infinite Family of Graphs A(k,K). Proceedings of the Federated Conference on Computer Science and Information Systems (FedCSIS), CANA , Wroclaw, p. 11-23. [19] D. MacKay and M. Postol (2003). Weakness of Margulis and Ramanujan - Margulis Low Dencity Parity Check Codes, Electronic Notes in Theoretical Computer Science, 74, p.97-104. https:/doi.org/ 10.1016/S1571- 0661(04)80768-0 [20] V. Ustimenko (2009). Algebraic groups and small world graphs of high girth, Albanian Journal of Mathematics,3, No. 1, p. 25-33. [21] V. Ustimenko, On Extremal Algebraic Graphs and Multivariate Cryptosystems, Cryptology ePrint Archive, reprint 2022/1537. [22] V. Ustimenko, On the extremal graph theory for directed graphs and its cryptographical applications In: T. Shaska, W.C. Huffman, D. Joener and V. Ustimenko, Advances in Coding Theory and Cryptography, Series on Coding and Cryptology, vol. 3, 181-200 (2007). [23] V. Ustimenko, Graphs in terms of Algebraic Geometry, symbolic computations and secure communications in Post-Quantum world, Editorial House of University of Maria Curie – Sklodowska, Lublin, November, 2022, 196 pages. [24] Geetha N K, Ragavi V, Graph Theory Matrix Approach in Cryptography and Network Security, Proceedings of 2022 Algorithms, Computing and Mathematics Conference (ACM), 29-30 Aug. 2022, https://ieeexplore.ieee.org/document/10202460 [25] Costache, A., Feigon, B., Lauter, K., Massierer, M., Puskás, A. (2019). Ramanujan Graphs in Cryptography. In: Balakrishnan, J., Folsom, A., Lalín, M., Manes, M. (eds) Research Directions in Number Theory. Association for Women in Mathematics Series, vol 19. Springer, Cham. https://doi.org/10.1007/978-3-030-19478-9_1 [26] P.L. K. Priyadarsini, A Survey on some Applications of Graph Theory in Cryptography, Journal of Discrete Mathematical Sciences and Cryptography, https://www.tandfonline.com/doi/abs/10.1080/09720529.2013.878819 [27] W. M. Al Etaiwi, , Encryption Algorithm Using Graph Theory, ;Journal of Scientific Research &
Reports3(19): 2519-2527, 2014; Article no. JSRR.2014.19.004. [28] Samid Gideon, Denial Cryptography based on Graph Theory, US patent 6823068-2004 http://www.patentstorm.us/patents/6823068.html [29] Lothrop Mittenthal, Sequencings and Directed Graphs with Applications to Cryptography, S.W.
Golomb et al. (Eds.): Springer-Varlag LNCS 4893, pp 70–81, 2007. [30] Moni Naor and Adi Shamir. Visual cryptography. In Advances in Cryptology - EURO
CRYPT'94, LNCS, vol 950, pp 1–12, 1994. [31] Steve Lu, Daniel Manchala and Rafail Ostrovsky, Visual Cryptography on Graphs, COCOON 2008: pp. 225–234, 2008. [32] William Stallings, Cryptography and Network Security Principles and Practices, Prentice Hall
India, 2006. [33] Dawn Song, David Zuckermany and J. D. Tygar, Expander Graphs for Digital Stream Authentication and Robust Overlay Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy (S&P.02), 2002. [34] M Yamuna, Meenal Gogia, Ashish Sikka and Md. Jazib Hayat Khan, "Encryption using graph theory and linear algebra", International Journal of Computer Application, pp. 2250-1797, 2012. [35] A Paszkiewicz et al., Proposals of graph based ciphers theory and implementations. Research
Gate, 2001. [36] Cusack, B.; Chapman, E. Using graphic methods to challenge cryptographic performance. In Proceedings of the 14th Australian Information Security Management Conference, Edith Cowan University, Perth, Australia, 5–6 December 2016; pp. 30–36. [Google Scholar] [37] Chapman, E. Using Graphic Based Systems to Improve Cryptographic Algorithms. Ph.D. Thesis,
Auckland University of Technology, Auckland, New Zealand, 2016. [Google Scholar] [38] Kinani, E.H.E. Fast Mapping Method based on Matrix Approach For Elliptic Curve
Cryptography. Int. J. Inf. Netw. Secur. (IJINS) 2012, 1, 54–59. [39] M. Klisowski. Zwiększenie bezpieczeństwa kryptograficznych algorytmów wielu zmiennych bazujących na algebraicznej teorii grafów. Rozprawa doktorska, Politechnika Częstochowska, Częstochowa, 2014. [40] Vasyl Ustimenko , Aneta Wroblewska, On the key exchange and multivariate encryption with nonlinear polynomial maps of stable degree, DOI: http://dx.doi.org/10.2478/v10065-012-0047-6, Annales of UMCS, Informatica, Vol 13, No 1 (2013) , pp. 63-80. [41] Pustovit O.S. Application of the theory of extreme graphs to modern problems of information security. - Dissertation for obtaining the scientific degree of candidate of technical sciences in the specialty 05.13.06 - Information technologies. – Institute of Telecommunications and Global Information Space of the National Academy of Sciences of Ukraine, Kyiv, 2021. [42] V. Ustimenko, Graphs with special arcs and cryptography, Acta Applicandae Mathematicae (Kluwer) 2002, 74, pp. 117-153. [43] V. А. Ustimenko. On the extremal graph theory and symbolic computations, Dopovidi National
Academy of Sci, Ukraine, 2013, No. 2, p. 42-49. [44] V. Ustimenko, On new results on extremal graph theory, theory of algebraic graphs, and their applications, Reports of National Acad. of Sci. of Ukraine, 2022, N4, pp. 25-32. [45] V. Ustimenko, Random Walks on graphs and Cryptography, Extended abstracts, AMS meeting,
March, Louisville, 1998. [46] V. Ustimenko, D. Sharma, Special Graphs in Cryptography, The Poster Papers Collection,
Third International Workshop on Practice and Theory in Public Key Cryptography , PKC 2000. [47] V. Futorny, V. Ustimenko, On small world semiplanes with generalised Schubert cells, Acta
Applicandae Mathematicae, 98, N1 (2007) 47-61. [48] V. Ustimenko, On the Cryptography with “Mathematica package”, Proceedings of the conference ”Leaning Mathematics and Technology Middle East Conference” , University of Arizona and Sultan Qaboos University, Oman, March, 2007, 11 p. [49] A. Tousene, V. Ustimenko, Graph based private key cryptosystem, International Journal on
Computer Research, Nova Science Publisher, 2005, vol.13, issue 4 (with A Touzene) 12p. [50] V. Ustimenko, S. Kotorowicz, On the properties of Stream Ciphers Based on Extremal Directed graphs, In "Cryptography Research Perspectives", Nova Publishers, Ronald E. Chen (the editor), 2008. [51] Y. Khmelevsky, Gaetan Hains, E. Ozan, V. Ustimenko, Chris Kluka and D. Syrotovsky) International Cooperation in SW Engineering Research Projects, Proceedings of Western Canadien Conference on Computing Education, University of Northen British Columbia, Prince George BC, May 6-7, 2011, 14p. [52] A. Touzene, Marwa AlRaisi, Imene Boudelioua, Performance of Algebraic Graphs Based
Stream-Ciphers Using Large Finite Fields, Annalles UMCS Informatica AI X1, 2 (2011), 81-93. [53] J. Kotorowicz U. Romanczuk, V. Ustimenko, Implementation of stream ciphers based on a new family of algebraic graphs, Proceedings of Federated Conference on Computer Science and Information Systems (FedCSIS), 2011, 13 pp. [54] V. Ustimenko, M. Klisowski, On the Comparison of Cryptographical Properties of Two Different Families of Graphs with Large Cycle Indicator // Mathematics in Computer Science, 2012, Volume 6, Number 2, Pages 181-198. [55] V. Ustimenko, D. Sharma, CRYPTIM: system to encrypt text and image data, Proceedings of
International ICSC Congress on Intelligent Systems 2000, Wollongong, 2001, 11pp. [56] V. Ustimenko, Yu Khmelevsky, Walks on graphs as symmetric and asymmetric tools for encryption, 2002, South Pacific Journal of Natural Studies, 2002, vol. 20, 23-41. www.usp.ac.fj/spjns [57] V. Ustimenko, Yu Khmelevsky, Practical aspects of the Informational Systems reengineering, The South Pacific Journal of Natural Science, volume 21, 2003, p.75-21. www.usp.ac.fj/spjns/volume21 [58] V. Ustimenko, A Tousene, CRYPTALL - a System to Encrypt All types of Data , Notices of
Kiev - Mohyla Academy, v. 23, 2004,pp 12-15. [59] Y. Khmelevsky, M. Govorov,S. Sharma, v. Ustimenko, Security Solutions for Spatial Data in Storage (Implementation Case within Oracle 9iAS), Proceeings the 8th World Multiconference on Systemics, Cybernetics and Informatics (SCI 2004) Orlando, USA, in July 18-21, 2004. [60] Y. Khmelevsky, Gaetan Hains, E. Ozan, Chris Kluka , V.,Ustimenko and D. Syrotovsky) International Cooperation in SW Engineering Research Projects, Proceedings of Western Canadien Conference on Computing Education, University of Northen British Columbia, Prince George BC, May 6-7, 2011, 14pp. [61] S. Kotorowicz, V. Ustimenko, On the properties of Stream Ciphers Based on Extremal Directed graphs, In "Cryptography Research Perspectives", Nova Publishers, Ronald E. Chen (the editor), 2008. (with S. Kotorowicz). [62] V. Ustimenko, A. Touzene, Graph Based Private KeyCrypto System, International Journal on
Computer Research, NovaScience Publisher, volume 13 (2006), issue 4, 12p. [63] A. Touzene, V. Ustimenko, Private and Public Key Systems Using Graphs of High Girth,In "Cryptography Research Perspectives", Nova Publishers, Ronald E. Chen (the editor), 2008, pp. 205-216. [64] M. Govorov, Y. Khmelevsky, V. Ustimenko, and A. Khorev, “Security for GIS N-tier architecture,” Developments in Spatial Data Handling, pp. 71–83, 2005. [65] Pustovit O., Ustymenko V., Pro zastosuvannia alhebraichnoi kombinatoryky do problem koduvannia ta kryptohrafii [On the application of algebraic combinatorics to the problems of coding and cryptography] // Matematychne modeliuvannia v ekonomitsi, No 1-2. - Kyiv. - 2017. - s. 31-46.