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 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 description of some graph-based ciphers. We introduce new ciphers constructed in terms of D(n, K). Let K be arithmetical ring Zq, q = 2l, l≥3. We will use natural bijection between elements of multiplicative group K* and elements of Zp, p = 2l-1. The space of plaintexts is (Zp)n-s the space of ciphertexts is (Zq)n-s where s of size O(1) can be arbitrary parameter <[(n+2)/5]. The password can be selected as an arbitrary pair of tuples of kind (a1, a2, …, ak) ϵ (K*)k, (d1, d2, …, ds) ϵ (K*)s where even k, k<[(n+5)/2] has size O(1). We prove that different passwords produce distinct ciphertext from the selected plaintext. So the cost of a direct attack by an adversary is qspk. The encryption map has a multivariate nature, it is induced by non-bijective polynomial transformation Fn_of Kn-s to itself of prescribed degree d. Users can select d, d ≥3 as an arbitrary parameter of the size O(n). Appropriate selection of large d makes linearisation attacks on the cipher of multivariate nature unfeasible. The speed of encryption/ decryption is O(n). Additionally, we introduce similar ciphers based on the bijective transformation of the space of plaintexts Kn-s where K is an arbitrary commutative ring with unity with nontrivial multiplicative group K*.
Graph-Based Cryptography (GBC) area is
moving with great speed into the mainstream
of computer design, Information sciences,
Information and Computer programming,
Artificial Intelligence, and design. Applications
of GBC are in diverse areas such as Data
structures, Communication networks, and
their security. A Graph-based approach centers
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, GBC is used for the key
exchange, development of Multivariate Public
Keys, key-dependent message authentication
codes, and algorithms of Noncommutative
Cryptography [
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. This
paper [
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 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. The trapdoor accelerator
(see [
In presented ciphers based on bijective maps correspondents Alice and Bob share file A (the password) and encrypt according to the robust procedure in time O(n) or O(n1+ᾳ) where ᾳ is from the interval [0,1]. The adversary does not have a password he/she can intercept a large amount of pairs of plaintext/corresponding ciphertext and try to approximate maps F-1 and F. So the degree of F is an important parameter for cryptanalytical studies. The most important (active) part of the password is the information about the walk in the algebraic graph.
The first description of selected
graphbased stream cipher based on approximations
of the q-regular tree where q is a prime power
was presented in [4] or [
In [
Section 2 is dedicated to the general schemes of flexible encryption algorithms based on a special family of algebraic graphs defined over a commutative ring. The used class of algebraic graphs is known as the class of linguistic graphs of type (1,1, n-1). Some of these schemes do not use descriptions of connected components of graphs. other schemes are based on the knowledge of connectivity invariants of the graphs. Some of them allow us to define bijective maps of corresponding affine space, and others are used for the creation of an injective map of (K*)n into Kn where K is a commutative ring with the unity and K* is its multiplicative group.
The remarkable well-known family of linguistic graphs D(n, K) defined over K is introduced in Section 3. The connected components of these graphs and their properties and applications are discussed. In particular, we consider the theory of approximations of regular trees and forests with the example q-regular forest approximation D(n, Fq) = D(n, q), n→∞ [2] and tree approximation via linguistic graphs CD(n, q) [3].
The precise description of some graphbased algorithms of Section 2 in the case of D(n, K) is given in Section 4 together with an evaluation of the degrees of the encryption map and its inverse. We select algorithms constructed without the usage of connectivity invariants of graphs.
Section 5 is dedicated to the family of bijective and non-bijective ciphers described in terms of connectivity invariants. We discuss implementations of some of these ciphers in the case of arithmetical rings Zq, q=2l there.
Section 6 contains conclusive remarks.
The families of graphs D(n, K) defined over
arbitrary commutative ring K are linguistic
bipartite graphs of type (1, 1, n-1) with
partition sets which are two copies of Kn (see
[
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.
Parameters n and m are equal to some selected constant. the length of the password is another even constant that has an impact on the speed of encryption. Another option to increase the 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 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), a3X3b3Y3 = f2(X1, X2, Y1, Y2),…, anXn-bnYn = f2(X1, X2,…, Xn1, 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 [
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(1), r(2),…, r(n)) = (r)
S2. He/she computes a(1) = g1(r1), a(2) = g2(r1),…, a(t) = g(r1)
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 the line [y1, y2,…, yn] with the color a. He/she executes the following operation. Computation of v1 = Na(1)(r), v2 = a(2)N(v1), v3 = Na(3)(v2), v4 = a(4)N(v3),…, vt-1 = Na(t-1)(vt-2), vt = a(t)N(vt-1) = u = (u1, u2,…, un)
S4 He/she computes ciphertext as T(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 (Tn)-1(c) = u and getting the solution x = r(1) of equation g(x) = u1
D2. Computation of parameters a(1) = g1(r(1)), a(2) = g2(r(1)),…, a(t-1) = gt1(r(1)) and the completion of the recurrent procedure vt-1 = Na(t-1)(u), vt-2 = a(t-2)N(vt-1), vt3 = Na(t-3)(vt-2), vt-4 = a(4)N(vt-3),…, v1 = Na(1)(vt-2), r(1)N(v4t-1) = r.
D3. Computation of the plaintext (p) as T(r). OBFUSCATIONS OF THE ALGORITHM.
O1. 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)-1, where Jg is a color jump operator acting on points of I(K[x1, x2,…xn] with the color 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 of the bijection of gt on K is immaterial. Encryption procedure requires computation of (Tn)-1(p1, p2, …, pn) = (r(1), r(2),…, r(n)) = (r), the computation of u accordingly step S2. The computation of Jg(u) = u’ and application of affine transformation Tn to the tuple u’.
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(1) of this equation for the computation of a(1) = g1(r(1)), a(2) = g2(r(1)),…, a(t) = gt(r(1)), compute Ja(t)(u’) = (u) = (u1, u2,…, un) in the graph I(K) and execute procedure D2 and D3 to get the original plaintext.
O2. We can use “multiplicative equations” of kind g(x1) = b where g:K*→K* which has a unique solution if bϵK*. In this case, we can use the previous scheme O1 with Tn such that Tn1 = (r(1), r(2),…, r(n)) and r(1) is an element of multiplicative group K*.
O3. Let I(K) be a linguistic graph of type (1,
1, n-1). We say that multivariate function f, f
ϵK[x1, x2,…, xn] is a connectivity invariant of I(K)
if f(x1, x2,…, xn) = f(y1,y2,…yn) for each pair of
points (x1, x2,…, xn), (y1, y2, …, yn) from the same
connected component of the graph I(K).
Assume that f1, f2,…, ft are connectivity
invariants. We can use functions of kind
gi(x1)+fi(x1, x2,…, xn), I = 1.2,…, t instead of gi in
the cases of encryption schemes of type O2.
This idea was proposed in [
O4. We can take T1 and T2 from the group AGLn(K) and use T1GT2 where G is a graphbased transformation.
O5. Let us assume that K = Zq, q = 2m. We can use graph based transformation G introduced in O2_given by polynomials g1(x1), g2(x1),…, gt(x1) and function g(x1) of the “multiplicative equations”. Assume the graph In(K) has connectivity invariants f1, f2,…, fk+1 from K[x1, x2,…, xn]. We change the colors gi and g for hi = gi(x1)+fi(x1, x2,…, xn) and. Let H be the graphbased transformation in terms of In(K) and colors hi and g. Correspondents can work with the graph-based stream cipher defined in terms of the family of graphs In(K) and colors hi(x) and h(x) which has the space of plaintexts (K*)n, encryption function E = T1HT2 where T1, T2 are elements of GLn(K) and T1(x1)ϵK*. Noteworthy that the matrix of the linear transformation T1 can be constructed as a composition of low triangular matrix L = (l(i,j)) (l(i,j) = 0 for j>i) and an upper triangular matrix u = (u(i,j)) (u(i,j = 0 for i > j) such that u(1,1) ϵ K*.
The space of plaintexts can be identified with the (Zp) n, p = 2 m-1. The map ϻ: x→2x+1estabishes the bijection between elements Zp and (Zq)*.
Let us assume that Bob creates the plaintext (p1, p2,…, pn) = v. He computes v* as (ϻ(p1), ϻ(p2),…, ϻ(pn)) and creates the ciphertext E(v*) = c.
Alice computes (T2)-1 (c ) = (b1. b2….,bm). Secondly, she solves for x the equation g(x) = b1.. Let x = x* be the solution.
Alice takes the path in the graph with the starting point d = (x*, b2, b3,…, bn) = d and consecutive colors ht(x*), ht-1(x*), ht-2(x*),…, h1(x*), x*. Notice that for the computation of colors, Alice uses the identity fi(x1, x2,…, xn) = f1(x*, b2, b3,…, bn).
The last vertex of the path is (ϻ(p1), ϻ(p2),…, ϻ(pn)). Alice applies ϻ-1, and gets the plaintext.
of Large Girth
The girth and diameter of a graph are the minimal length of its cycle and the maximal distance of the graph. The construction of finite or infinite graphs with prescribed girth and diameter is an important and difficult task of 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 generalized m-gons as bipartite graphs of girth 2m and diameter m. Feit and Higman proved that finite generalized 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 generalized m-gons for m = 3, 4, 6, 8. Classification of flag transitive generalized m-gons of Moufang type was 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 an infinite family of small world graphs of bounded degree turns out to be very important for various applications of graph theory.
Noteworthy that only one family of
smallworld graphs of large girth is known. This is the
family X(p, q) of Ramanujan graphs introduced
by Gregory Margulis [
We have to admit that studies of families of graphs Γi with well-defined projective limit Γ, which is isomorphic to an infinite tree, are 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 of whether or not CD(n, q) forms a family of small world graphs has been still open since 1995. 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)≥clogk-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 [
Graphs D(n, K) 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 anti-reflexive 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)≤clogk-1(vi), where c Graphs D(n, q) introduced in [2] defines projective limit D(q) which is an infinite bipartite graph with partition sets formed by two infinite vector spaces over the finite field Fq_formed by points (p) = (p01, p11, p12, p21, p22, p’22, …, p’ii, pi i+1, pi+1,i, p+i+1,i+1 …) and 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).
Remark. You can see that indexes of vectors correspond to coordinates of positive roots of root system A1 with a wave.
Graph D(n, q) are bipartite graphs with the partition sets (Fq)n formed by the projections of points and lines of D(q) onto their first n coordinates and incidence given by first n-1 equations in the definition of D(q).
Historically graph D(q) is not the first example
of a description of q-regular forest in terms of
Algebraic Geometry. Geometries of buildings
(see [
In [
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 [
In the case of families X(p, q) and CD(n, q) the constant c is 4/3. So exact computation of the girth is the area of future research. 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.
Families X(p, q) and CD(n, q) can be used for
the construction of LDPC codes for noise
protection in satellite communications. D.
MacKay and M. Postol [
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.
CD(n, K) We can see that graphs D(n, q) are defined as bipartite graphs with the partition sets (Fq)n via the system of homogeneous polynomial equations with nonzero coefficients 1 and -1.
Let K stand for an arbitrary commutative ring. We can introduce graphs D(n, K) via a simple change of vector space (Fq)n on free modules Kn and the use of the same equations (see [4]–[5]).
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 [4]–[5] 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 ur,r+1, ur+1,r, …), 2≤r≤t, α ϵ{(1, 0), (0,1)} is a vertex of D(k, K) and ar = ar(u) = Σi=0,r(uii u’r-i, r-i-ui,i+1 ur-i,r-i-1) for every r from the interval [2, 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 [5] graphs D(n, K) are edge transitive. So their connected components are isomorphic graphs. Let vCD(k, K) be a solution set of a 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 partitions of the vertex set of D(n, K). We consider more general graphs vCD_J(k, K) defined via subset J={i(1),i(2),…, i(s)}, 1≤s≤t-1 of {2, 3,…, t} and tuple (vi(1), vi(2), …, vi(s)) formed by vertices uϵKn such that ai(1)(u) = vi(1), ai(2)(u) = vi(2),…, ai(s)(u) = vi(s).
We refer to vCDJ(k, K) as the J-component of D(n, K). We assume that equations ai(1) = vi(1), ai(2) = vi(2),…,ai(s) = vi(s) define J-component vCDJ(K) of D(K). Noteworthy that in the case of a finite commutative ring vCDJ(K) is a regular forest.
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 [
Theorem [5]. For each commutative integrity ring K with at least 3 elements the families of graphs D(n, K), 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(1), b(2), …,b(k), a(1), a(2),...,a(k), k = t/2 from K* to construct c(i) recurrently via the following rules c(1) = b(1), c(2) = a(1), c(i) = c(i-2)+b(i) if i, i≥3 is odd n and c(i) = c(i-2) = a(i) if i, i≥4 is even.
We refer to the tuple (b(1), b(2),…, b(k), a(1), a(2), …, a(k)) as active password and affine transformation T as passive password.
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 T in the form of a linear map given by the following rule
T(x1) = x1+m(1)x2+…+m(n-1)xn-1 where m(i), i = 1, 2,…, n-1 are elements of K*. T(xi) = xi for i = 2, 3,…, n. So T-1 (x1) = x1-m(1)x2-m(2)x3-…m(n-1)xn. T-1 (xi) = xi for i=2, 3,…, n.
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 T E(n, K) T-1 have a 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 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, p 3, 2, p, 33), …, p’tt=a_t(p01, p11, p12, p21, p22, p'22, …, p’t1,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).
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 the corresponding cipher has the space of plaintexts Kn-t. We use active passwords (b(1), b(2),…, b(k), a(1), a(2), …, a(k)) and linear transformations T of Kn-t constructed via described above rules. We assume that parameters h2, h3, …, ht will be considered as part of the active password and denote the cipher as TCE(n, K)T-1 = TnF(g1, g2,…, gt)Jg(Tn)-1.
We will use the 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 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 [31] 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 ciphers DE(n, K) use cubical encryption maps as well but the usage of disturbance map D: x→xe leads 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 the 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 [
So the directed linearisation attacks are theoretically impossible. The principal difference between DC(n, K) and TCE(n, K)T-1 is the fact that the usage of disturbance implies the fact that the degree of the inverse function is essentially higher than that for the 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(1), i(2), …, i(t(n))} is the subset of {2, 3,…, [(n+2)/4]} = M(n) and tuples (vi(1), vi(2),…, vj(t(n)) are elements of Kt(n).
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 points and lines of vCDJ(k, K) by 1, 2,…, n-k. So x = (x1, x2,…, xn-t(n)).
The nonlinear graph-based transformation N is the following one.
We select parameter k and form tuples ka = (ᾳ(1), a(2),…, a(k)) and kb = (β(1), β(2),…, β(k)) with the coordinates from the multiplicative group K* of the commutative ring K.
Let ᾳN(u) be the operator of taking the neighbor of u = (u1, u2,…, un-t) from the graph vCDJ(k, K) with the color of u1+ᾳ. We consider the sequence 1u = β(1)N(x), 2u = ᾳ(1)N(1u), 3u = β(2)N(2u), 4u = ᾳ(2)N(3u), …,2k-1u = β(k)N(2k-2u), 2ku = ᾳ(k)N(2k-1u) = (w1, w2,…,wn-t). We set N(x1, x2,…, xn-t) = (w1, w2,…, wn-t).
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 the 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 tuples ka = (ᾳ(1), a(2),…, a(k)) and kb = (β(1), β(2),…, β(k)) with the coordinates from the multiplicative group K* of the commutative ring K.
We consider the walk in the graph with the starting point u0 = (x), u1, u2,…., u2k where colors of u1 = x1+ β(1), u2 = x1+ ᾳ(1), ui = ui-2+β(i), I = 3, 5,…, 2k-1, ui = ui-2+ᾳ(i)), I = 4, 6,…, 2k.
Let u2k = (x1+ᾳ(1)+ᾳ(2)+…+ᾳ(k)), F2(x1, x2,…, xn-t), F3(x1, x2,…, xn-t), …, Fn-t(x1, x2,…, xn-t). So we may treat N as the multivariate transformation of Kn-t to itself given by the rule x1→x1+ᾳ(1)+ᾳ(2)+…+ ᾳ(k), x2→ F2(x1, x2,…, xn-t), x3→F3(x1, x2,…, xn-t),…, xn-t→ Fn-t(x1, x2,…, xn-t).
As it follows from [
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(1)x2+…+m(n-t-1)xn-t-1 where m(i), i = 1,2,…, n-1 are elements of K*, .T(xi) = xi for i = 2,3,…, n.
We denoted the described below cipher as kED1 (n-t, K). The map TNT-1 has active password (ᾳ(1), a(2),…, a(k), β(1), β(2),…, β(k)), vi(1), vi(2),…, vj(t(n)).
Parameters m(1), m(2)…, m(n-t-1) together with J = {i(1), i(2),…, i((t(n)) form the passive password. We assume that constants k and t(n) = t can be agreed by correspondents via an open channel. Under the described above assumptions cipher has a linear speed v(n) of size O(n). The slope of the v(n) is defined by the value of the weight parameter w = i(1)+i(2)+…+i(m).
The following important property holds.
The change of the active password leads to the change of the ciphertext for the selected plaintext. It means that a brute 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.
In this section, we concentrate on the case of commutative ring K = Zq, q = 2l, l≥8.
We modify the ciphers kEDt(m, K), m = n-t with the active password (ᾳ(1), a(2),…, a(k), β(1), β(2),…, β(k)), vi(1), vi(2),…, vj(d(n)) and the passive password defined by nonzero parameters m(1), m(2)…, m(n-d(n)-1) together with the set J = {i(1), i(2),…, i((d(n))} accordingly the special case of the scheme O5 given in the Section 2.
Recall that the description of the generic connectivity invariants of D(n, K) is given via expressions ar = ar(u) = Σi=0,r(uii u’r-i, r-i-ui,i+1 ur-i,r-i-1) considered for every r from the interval [2, k] where k = [(n+2)/4].
It means that we can take arbitrary element F from K[y2, y3,…., yk], consider a symbolic 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, …> and gets the connectivity invariant F(a2(x), a3(x),…, ak(x)).
Recall that the induced graph vCDJ(n, K) was obtained via the restriction of the incidence relation of the bipartite graph D(n, K) onto the solutions set of equations ai(k)(<x>) = vi(k). We can get recursively the variables x’i(s),i(s), s = 1, 2,…, d(n) from these equations as quadratic expressions bi in variables of {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, …}-{x’(1),i(1), xi(2),i(2),…, xd(n),d(n)}.
It means that generic connectivity invariants of the graph vCDJ(n, K) can be obtained via consideration of J* = {2, 3,…, m}-J as the specialization Aj of aj, jϵJ* via the substitutions x’ii = bi, iϵJ.
Let J* = {j(1), j(2),…, j(s)}, s = m-d(n). The general connectivity invariant is F(Aj(1), Aj(2),…, Aj(s)) where F is a polynomial function in s variables z1, z2,…, zs. Notice that F can be an expression of any even degree in variables 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, ….
We use forms F(z1, z2,…, zs) of connectivity invariants with density O(1) and degree O(n). In this case, the connectivity invariant can be computed in time O(n).
Assume that one of the correspondents (Alice) creates the map. She selects the parameters n, m, the commutative ring K with at least 2 regular elements, the set J = {i(1), i(2),…, i((d(n))} and the tuple of parameters (vi(1), vi(2), …, vi(d(n))). These parameters allow us to write down the linguistic equations of graphs vCDJ(n, K).
Alice uses the scheme O5 with the following changes of the symbolic path in the graph vCDJ(n, K[x1, x1,1, x1,2, x2,1, x22, ….] to make a difference with the case of cipher kEDt(m, K), m = n-t.
She takes two expressions F1, F2 = K[z1, z2, …, zs], s = m-d(m) of density O(1) and linear degree O(n). Alice works with J* = {j(1), j(2),…, j(s)}, she forms the connectivity invariants F1(Aj(1), Aj(2),…, Aj(s)) = G1(x) and F2(Aj(1), Aj(2),…, Aj(s)) = G2(x). Similarly to the case of the cipher kEDt(m, K), m = n-t. Alice takes tuples of odd residues b(1), b(2), …,b(k), a(1), a(2),...,a(k), k = t/2 from K* to construct c(i) recurrently via the following rules c(1) = b(1), c(2) = a(1), c(i) = c(i-2)+b(i) if i, i≥3 is odd and c(i) = c(i-2)=a(i) if i, i≥4 is even. She constructs gi, I = 1, 2,…, t of the scheme O5 as gi = xi+G1(x)+ci for odd i, gi = x1+G2(x)+ci for even I and takes linear g(x) of kind ax+b, where aϵK*’.
Correspondents select the commutative ring K = Zq, q = 2l, l≥8. They modify the previous algorithm via a selection of g in terms of O5 in the form x3+b for some b from K.
Noteworthy that x3 = d has a unique solution if dϵK* because 3 is mutually prime with φ(2l) where φ is the Euler function.
For the encryption and decryption Alice uses the standard procedures of O5.
Let N = N(b(1), b(2), …, b(k), a(1), a(2), ..., a(k), J, vi(1), vi(2), …, vi(d(n)). F1, F2) stands for the described above encryption function. We use linear transformation T1 and T2 of kind Ti(x1) = x1+ im(2)x2+im(3)x3+…+im(n)xn, I = 1, 2 such that im(2)+im(3)+…+iim(n) is an even parameter to form the encryption map 3E(n, Zq) = T1 N T2.
We assume that tuples (b(1), b(2), …, b(k), a(1), a(2),..., a(k)) and vi(1), vi(2), …, vi(d(n)) form active password of 3E(n, Zq). 2k together with the tuple of elements from Z256 of length 128 to form both passwords.
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 (Fig. 1 and Fig. 2). Forms Fi, I = 1, 2 together with parameters n, q, im(2), im(3),…,im(n) form a passive part of the password.
Alice selects passive and active passwords and delivers them to his correspondent Bob via a secure channel.
One of the option to use connectivity invariants Fi., I = 1, 2 is to use of the forms Fi(z1, z2,…, zs) of kind (zk(1))t(1) (zk(2))t(2)…(zk(r))t(r) for which t(1)+k(2)+…+k(r), r≥1 has linear size ᾳn, ᾳ>0 and r=O(1).
Selection of forms Fi of linear degree ensures that the multivariate standard form of the encryption map has a degree at least ᾳn, ᾳ>0. The use of cubical map g guarantees that the degree of decryption is higher than the degree of encryption transformation.
Similarly to the algorithm described in the previous section described above assumptions ensure that the cipher has a linear speed v(n) of size O(n). The slope of the v(n) is defined by the value of weight parameter w = i(1)+i(2)+…+i(d(n)) and selection of forms Fi, I = 1, 2.
As in the case of kEDt(m, K) the change of the active password leads to the change of the ciphertext for the selected plaintext. It means that a brute force attack on the cipher requires p2kqd(n) elementary operations where p = 2l-1 and q = 2l.
We implement the cipher 3E(n, Zq) with q = 256. So the space of plaintexts is an affine space over Z128 and d(n) = 128 with weights w = 213 and 216. In both cases, the degree of encryption map will be at least 256. So the linearisation attacks by adversaries are unfeasible.
CRYPTALL 7 software is written in C++
programming language and therefore it is
portable and runs on many platforms such as
Unix/Windows. The context diagram is
depicted in Fig. 1. The friendly 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 of Z*256 [
The protocol allows the elaboration of the tuple of nonzero field elements of Z128 of length In both cases, algorithms have nice mixing properties. change of a single character leads to the change of at least 98% of the characters in the ciphertext.
We implement Algorithm 2 in the practically important case of K = Zq, q = 2l. In this case, the space of plaintexts is isomorphic to (Zp)n-s, p = 2l-1.
We use loaded multiplication tables for K*. These tables increase the speed of computations and make immaterial the computational difference between cases of fields Fq and arithmetical rings Zq. Suggested ciphers have good mixing properties, the change of a single character of the active password leads to the change of 98% of characters of ciphertext produced from the selected plaintext.
We hope that new flexible algorithms with resistance to linearization attacks and linear speed of encryption will be successfully used for the protection of Information systems and Big Data Processing.
The first result of the paper (Algorithm 1) is the explicit construction of the family of multivariate maps of affine maps Fn of linear degree s(n) = cn, c>0 based on the graphs D(n, K) with the trapdoor accelerator. Fn acts on the affine space Kn defined over an arbitrary commutative ring K with at least 3 elements. The execution speed of the algorithm with encryption function is O(n). It depends on active password A = (a(1), a(2),…, a(k), b(1), b(2),…, b(k), v1, v2, ..., vs) from (K*)2kKs where parameters k and s can be selected by users. Let p = |K*|, q = |K|.
Different active passwords produce distinct ciphertexts from the same plaintext. It means that the adversary’s direct attack costs p2kqs attempts. Correspondents can govern the security via a choice of parameters k and s.
The map Fn is multivariate. Its degree d depends from the choice of degrees d(1) and d(2) of F1 and F2 from K[z1, z2, …, zl], l = [(n+2)/4]-s and parameter s. We can justify that d = 4d(1)+2d(2)+s is a degree of encryption and decryption maps. It means that users can select F1 and F2 of prescribed degrees and control the parameter d. Constructed trapdoor accelerator consists of active password A, maps F1, F2, g(x)ϵK[x], g(x) = ax+b, aϵK* and two affine transformations Ti, I = 1, 2.
If d is sufficiently large then the [1] computation of the standard form of Fn is an unfeasible task. So this cipher is resistant to linearisation attacks by adversaries.
The important feature of this algorithm is the linear execution speed of size O(n). So this [2] method of encryption can be used for the processing of Big Data.
Another cipher described as Algorithm 2 is an obfuscation of Algorithm 1 obtained via the change of linear g(x) of scheme O5 for g(x) of kind xt+b such that (t, p) = 1, t≤4d(1)+2d(2)+s. [3] This modification can be implemented in the case of commutative ring K with at least 3 regular elements. The active password, transformations F1, F2, and T2 are unchanged, but T1 has to satisfy the condition T(x1)ϵK*. The [4] space of plaintexts of the new algorithm is (K*)n-s but the space of ciphertexts is Kn-s as in the case of Algorithm 1. [5]
Algorithms 1 and 2 have the same degree of encryption map, but the nonlinear nature of g(x) increases the degree of the decryption map.
This research is partially supported by the Fellowship of the British Academy for RaR 2022. [54] V. Romankov, Two General Schemes of Algebraic Cryptography, Groups Complex. Cryptol. 10(2) (2018) 83–98. doi: 10.1515/gcc-2018-0009. [55] V. Roman’kov, An Improved Version of the AAG Cryptographic Protocol, Groups Complex. Cryptol. 11(1) (2019). doi: 10.1515/gcc-2019-2003. [56] B. Tsaban, Polynomial Time Solutions of Computational Problems in Noncommutative Algebraic Cryptography, J. Cryptol. 28(3) (2015) 601–622. doi: 10.1007/s00145-013-9170-9. [57] A. Ben-Zvi, A. Kalka, B. Tsaban, Cryptanalysis via Algebraic Spans, Cryptology—CRYPTO (2018) 1–20.