Jordan-Gauss graphs are bipartite graphs given by special quadratic equations over the commutative ring K with unity with partition sets K n and K m such that the neighbour of each vertex is defined by the system of linear equation given in its row-echelon form. We use special families of such graphs of increasing girth defined over arithmetical rings Zq, q=2m for the construction of new graph based stream ciphers of multivariate nature. The degree of multivariate encryption map is not bounded by the constant. So cryptosystem is resistant to Post Quantum adversarial attacks with the interception of many pair of kind plaintext/ciphertext. The speed of encryption is lnear ly dependent from the growth of the dimension of space of plaintext. It is of size O(n). The cipher has good mixing properties. This is the first family of graph based stream ciphers such that the information on the graph is partially hidden s part of the password. So adversary is unable to use Dijkstra algorithm of finding shortest pass for cryptanalytical studies. The algorithm is given with the infrastructure for the key establishment based on ideas of Noncommutative Cryptography and the use of generators of pseudorandom or genuinely random sequences of symbols.
Graph based cryptography is rapidly developing now. Papers [1, 2] (see also [3–5]) were the first publications on graph based cryptography. In fact [1] was the first paper on the cryptographical applications of algebraic graphs given defined by the system of equations over commutative ring K. The paper [1] presents generalisations D(n, K) of known algebraic graphs D(n, q), defined over the finite field qF(see [6] and further references). The properties of cryptographic algorithms based of D(n, K) essentially depend on the choice of finite commutative ring K. The case when K is arithmetical ring Zq, q=2r, r>1 is very convenient for the design of stream ciphers. First implementation of these stream ciphers were described in [6]. We refer to this encryption algorithm as UMCS-cipher.
Some stream ciphers based on graphs given by adjacency matrices can be found in [9–11] or survey [12]. Matrices of graphs also were used for the constructions of key dependent message authentication codes (see [13–15]). Cryptanalytic results on these codes can be found in [16]. Recently new message authentications codes based on graphs D(n. q) were presented [17]. Graphs D(n,q) together with Cayley expanding graphs were used also for the construction of LDPC codes [18–20].
Conventionally the encryption algorithm has to be known and its security rests on the password which correspondents keep in a secure way.
That is why the graph used in UMCS cipher is known. In current paper we use generalisations of graphs D(n, K) introduced in [8]. The equations of these graphs depends on the set S of positive integers of prescribed cardinality. We present the algorithm based on the graphs where large subset of S is the part of the key. Our task is to preserve good properties of the UMCS cipher such as linear execution speed, good mixing properties, high level of avalanche effect, the change of single character of the plaintext lead to the change of at least 98 percents of the characters in the corresponding ciphertext.
The key parameters of new and old algorithm are subdivided into passive and active passwords which are tuples in the alphabet K. In fact coordinates of the active keys are elements of the multiplicative group K* of the commutative ring K. The active key is an element of (K*)l(n), l(n)=O(n) where n is the dimension of the affine space of plaintexts. In fact any parameter l(n), l(n)<n/4 can be selected. It means that if the adversary knows plaintext and does not possess an access to plaintexts then in the case of K=Zq he/she has to use (q/2)l(n) attempts to break the cipher.
The disadvantage of the UMCS stream cipher proposed is the cubic nature of the inverse for the cubic encryption map in many variables. M. Klisowski [21] discovered that the interception of O(n3) pairs of kind plaintext/ciphertext allows to break the cryptosystem in time O(n10).
New cryptosystem is resistant against plaintext /ciphertext attack because of encryption map has degree m, m>cn for some positive constant c.
The introduced cryptosystem allows various obfuscations without the change of mentioned above positive features. One can change the ring Zq for the general finite commutative ringK. The graph used for encryption possess the homomorphism on graphs D(m, K) for the selected parameter m. This graph can be changed for any sparce linguistic cover of D(m, K), i. e. on linguistic graph given by equations with O(n) coefficients such that first m-1 of them coincide with the equations of D(m, K). Some obfuscation options are discussed in Section 4.
Section 2 contains definitions of linguistic graphs, Jordan-Gauss graphs and family of graphs D(n, K). The new stream cipher over the ring Zq, q=2r is introduced in Section 3.
In Section 5 we discuss the implementation of the algorithm. Conclusive remarks are located in Section 6.
Let us assume that K is a commutative ring with unity and nI(K)= nI is a bipartite linguistic graph of
type (1, 1, n-1) , i. e. the incidence structure with the partition sets formed by points (x)=(x1, x2, ... ,
xn), xiϵK and lines [y1, y2,…, yn], yiϵK such that (x)nI[y] if and only if the following equations hold.
a2x2-b2x2=f2(x1, y1),
a3x3 -b3x3=f3(x1, x2, y1, y2), (
We use term linguistic graph also for bipartite graphs with infinite tuples of kind(x1, x2, ... , xn,...)
as points and infinite tuples [y1, y2,…, yn,…] defined by infinite system of equations of kind (
We define the operatorNa(v) of taking neighbour of colour a via the following rule. If vertex v is the point (p) then Na(p) is the neighbouring line of this point with the colour a, i. e line [l]=[a, l2,..., ln] where li, i=2, 3,..., n are defined recurrently from the equationsa2p2-b2l2=p1a, a3p3-b3l3=f3(p1, p2, l1, l2), ..., aipi-bili=fi(p1, p2, ..., pi-1, l1, l2, ... , li-1). If vertex v is the line [l] then Na(l) is the neighbouring point of the line with the colour a, i. e. point (p)=(a, p2,..., pn) where pi, i=2, 3,..., n are defined recurrently from the equations a2p2-b2l2=al1, a3p3-b3l3=f3(p1, p2, l1, l2), ..., aipi-bili=fi(p1, p2, ..., pi-1, l1, l2, ... , li-1).
where ai and bi are elements of multiplicative group K* of the K and fi ϵK[x1, x2,…., xi-1, y1, y2,…, yi-1]. The first coordinates ϱ(x) =x1 and ϱ(y)=y1 defines colours of the point and line. The walk v0Iv1Iv2 ...vk-1Ivk such that colours of all points and colours of all lines are different is the path in the graph formed by distinct vertices.
If Fn(K) is a family of linguistic graphs then the growth of n to infinity defines projective limit F(K). We say that a linguistic graph is of Jordan-Gauss type if the map [(x), [y]] →(f2(x1, y1), f3(x1, x2, y1, y2), .. . . , fn(x1, x2, . . . , xn-1, y1, y2, . . . , yn-1)) is a bilinear map into Kn-1.
Thus, all fi are special quadratic maps. In the case of Jordan-Gauss graphs, the neighbourhood of each vertex is given by the system of linear equations written in its row-echelon form.
Let nI=nI(K) be a linguistic graph defined over the commutative ringK. For each b ∈ K and (p) = (p1, p2, . . . , pn), there is the unique neighbour [l] = Nb(p) of the point with the color b. Similarly, for each c ∈ K and line l = [l1, l2, . . . , ln] there is the unique neighbour (p) = Nc([l]) of the line with the color c.
Let i(
We say that n+mI(K) is linguistic cover of nI(K) if first n-1 equations of n+mI(K) coincides with the equations of nI(K).
Note that the projection of points and lines of n+mI(K) on its first n coordinates defines homomorphism of the graph n+mI(K) onto nI(K).
The following statements instantly follows from the definitions.
Proposition 2.1
Let n+mI(K) be a linguistic cover of nI(K). Then triangular linguistic connectivity invariants of nI(K) are triangular connectivity invariants of n+mI(K).
We refer to the cycle C of linguistic graph nI of type (1, 1, n-1) as multiplicative cycle if for each vertex v of C the difference of colours of its neighbours is an element of multiplicative group K* of K.
We define multiplicative girth mug=mug(nI(K) ) of nI(K) as minimal length of its multiplicative cycle.
As it follows from the fact that linguistic graphs are bipartite graphs its multiplicative girth is even parameter.
Note that if K is a field then multiplicative girth of linguistic graph I over K coincides with its girth.
We say that the path of vertexes v1, v2, ... , vs of even length of linguistic graph is multiplicative of length s if
the differences of colours of vi-vi+2 are elements of K* for i=0, 1,..., s-2. The linguistic graph I has multiplicative depth d=mud(I) if d is the maximal number such that ends of distinct multiplicative paths started at arbitrary vertex v_0 are distinct.
The multiplicative depth of the graph D(n, K) is at lease [(m+3)/2].
Proposition 2.2. Let us n+mI(K) be a linguistic cover of nI(K). Then mug ( n+mI(K) ) ≥ mug (nI(K)) and mud ( n+mI(K) ) ≥ mud (nI(K)).
Assume that K=Zq, q=2r. We use the family of linguistic graphs nI(K), n=2, 3,… for which mug (nI(K))≥m(n), where m(n) some increasing function. Assume that l(n) is function with the value of size O(n). For each parameter n the linguistic cover n+l(n)I(K) is defined . We assume that for each parameter n the list gi(s)(x1, x2, …, xi(s))ϵK[x1, x2, …, xi(s)] , s=1, 2,…, k, k=k(n) of triangular connectivity invariants of In(K) is known.
We assume that graph nI(K) and its triangular connectivity invariants are known for public, but
equations with numbers n, n+1,…, n+l(n) of n+l(n)I(K) are part of the secret key. So adversary knows
just parameter l(n).
The secret key of our stream cipher is the tuples (α2, α3, ..., αs) , (γ2, γ3, ..., γs) where αjϵ(Zq)* and (λ2,
λ3, ..., λs) where λi are even residues together with the tuple ((a(
The active password is formed by depth parameter t of size O(
Algorithm. Correspondents work with the space of plaintexts K s, s=n+l(n) The encryption.
We consider bijective transformations L of kind x1→x1+α2x2+...+asxs, xj →xj, j=2, 3,..., s and Q
=Q(x1, x2,..., xn) which sends x1 to x1(λ2x2+γ2)a(
Assume that the input is plaintext (x1, x2, ...., xs).
Encryption procedure.
Step 1. Compute Q(x1, x2,..., xs) =(z1, z2, ..., zs)=y(0) and treat this vector as a point of graph sI(K). Set a=z1.
Step 2. Compute gi(j)(y1, y2, …, yi(j))=ai(j), j=1, 2,…, k(n) and element (2f(ai(
Assume that correspondent get the ciphertext v from his/her partner. The following steps will allow to restore the plaintext p.
Step 1. The computation of u= L-1(v)=(u1, u2, ..., un, un+1,…, us).
Step 2. It gives the option to compute the values of triangular connectivity invariants of the graph nI(K) on intermediate point Q(p)=(z1, z2,..., zs). Recall that s=n+l(n). We compute list gi(j)(z1, z2, …, zi(s))ϵK[z1, z2, …, zi(j)] , j=1, 2,…, k, k=k(n) as aj= gi(j)(u1, u2, …, ui(s)) , j=1, 2,…, k, k=k(n).
Step 3. The computation of z1=a as a solution of (2f(ai(
a(t)=a(t-1)+β(t), u1.
Step 4. The computation of intermediate vector (z)=(z1, z2,..., zs). We compute recurrently y(t)=Na(t)(u),
Z(t-1)=Nc(t-1)(y(t)), y(t-1)=Na(t-1)(z(t-1)), z(t-2)=Nc(t-2)(y(t-1),…, z(
Step 4. The computation of plaintext x as Q-1(z1, z2,…., zs).
Standard obfuscation.
Let E be the described above encryption map on the affine space Kn of plaintexts. We select
linear maps L1 and L2 of kind x1→x1, xi→li(x1, x2, ..., xn), i=1, 2,..., n with linear forms li of density
O(
The projective limit D(K) of linguistic graphs D(n, K) can be naturally defined via positive roots of
the root system Ext A1 (A1 with wawe or extended Dynkin diagram of A1), see [23]. It is convinient
to use positive roots of this root system as indexes of points and lines. The positive real roots of Ext
A1 are (k+1)α1+kα2, kα1+(k+1)α2 where k≥0 and α1, α2 are simple roots The system also contains so
called imaginary roots of kind kα1+kα2 where k≥1. We identify roots with their coordinates in the
lattice generated by simple roots. Thus we get the list (k+1, k), (k, k+1) , (k+1, k+1), k≥0. We
introduce “twins’’ of imaginary roots denoted as (k, k)’ and assume that (
Let us consider affine space of all functions P= KR-{0,1} and L=K R-{1,0} from R-((
This four relations are defined fori≥1 under condition that x’11= x11, y’11= y11.
Recall that tuples (x) and [y] have finite support, i. e. only finite number of their coordinates differ from zero. Coordinates x’ii and y’ii correspond to the root (i, i)’.
As It follows instantly from the results of [22] the infinite Jordan Gauss graphs D(K) does not have multiplicative cycles.
We define graphD(n, K) as the homomorphic image of D(K) defined by the projection of points and lines onto ther first n coordinates. So the incidence of Jordan-Gauss graphD(n, K) is defined by the firstn-1 equations of D(K).
The following statement follows from the results of [22].
Proposition 3. 1. Let K be arbitrary commutative ring. Then mug(D(n, K)≥n+5.
To introduce triangular connectivity invariants of D(n, K), it will be convenient for us to define y-1,0 = x0,-1 = y1,0 = xl0,1= 0, y0,0= x00= -1, y’0,0 = x’0,0 = -1.
Graphs CD(k,K) with k ≥ 6 were introduced in [22] 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 [22] 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. Each vCD(k,K) is the disjoint union of some connected components of graph D(n,K). It is known that if K is commutative ring with unity then vCD(k,K) are connected and in the case of K=F4 each vCD(k,K) is union of 4 connected components (see 8] and further references).
The following graphs were introduced in [8]. Let us take graph of kind D(k+m, K) with the triangular connectivity invariants aj, j =2, 3,…, [(k+2)/4], [(k+2)/4]+1,…, [k+m+2]4.
We consider the set k+mS of indexes for the coordinates of points and lines of D(k+m, K) with
indexes (i, i)’ where i=[(k+2)/4]+1, [(k+2)/4]+2,…, [(k+m+2)/4] of cardinality
d=[(k+m+2)/4-[k+2]/4]+1. We select subset J of k+mS and delete coordinates of D(k+m, k) with
indexes (i, i)’, j ϵJ together with the corresponding equations
x’ii –y’ii = xi,i-1 y01 and change the next equation of (
We have to select finite commutative ring K=Zq, q=2r, r>2. So we will work with the space of
plaintexts Kr. For the selection of our passive password we present n as k+m-d where k, m and d
are linear functions of kind αn+ β, 0<α<1 of size O(n). We will work with the graph JDk, m(K) where |
J|=d. We assume that m, k, d and the subset J of {2, 3,…, [(k+2)/4], [(k+2)/4]+1,…, [k+m+2]/4} are the
part of the passive password. We use invariants a2 , a3 ,…, al, l=[(k+2)/4] of the graph. We selects for
the passive password the tuples (α2, α3, ..., αn) , (γ2, γ3, ..., γn) where αjϵ(Zq)* , (λ2, λ3, ..., λn) where λi
are even residues together with the tuple ((a(
We chose f as (2z1+1)k(
The active password is formed by depth parameter t of size O(
We implemented our algorithms in the case of commutative ring Z256 which has the same size with the binary alphabet.
We select the parameters of the passive password as follows. Only O(
We refer to d=2m as the length of active password. High multiplicative girth of the graph insures the following property: change of active password leads to the change of intermediate output v=(v1, v2,..., vn).
Computer simulation demonstrate high level of the avalanche effect. We can see that single change of the character of initial file or single change of the character of active password lead to the change of 98% of characters of the ciphertext. Our computations are described in terms of basic operations of the commutative ring K=Z256 . To speed up the performance of our stream cipher we present the operations of addition and multiplication of the ring via the loaded addition and multiplication tables. So we have embedded functions x+y and xꞏy where x and y are taken from the set of residues mod q. We will use another embedded power function xy where x is from the domain of all odd residues and y is the residue modulo 2m-1 which is the order of multiplicative group K*. The measurements of the execution time are given in Fig 1.
Our software is written in C++ programming language and therefore it is portable and runs in many platforms such as Unix/Window. To evaluate the performance of our algorithm, we use with different size of files. We measure the time needed to produce the digest in millisecond)and the file size of files in kilobytes for passwords of length d. We use an average PC with processor Pentium 3.00 GHz, 2GB memory RAM and system Windows 7. The following diagram presents the time of the algorithms execution in the case of selected graph as function from size of the file and the length of the active key. For the generation of passive key one of correspondents can use the pseudorandom (or random) generator of elements of the arithmetical ring Z256. Currently there are large varieties of generators with the use of different ideas such as classical deterministic methods, use of artificial intelligence (machine learning, neural networks) or quantum computing. Assume that one ( correspondents generates the pseudorandom sequence (p1, p2, ..., pn). Then he/she can form (α2, α3, ..., αn) (or (γ2, γ3, ..., γn) as sequence (2p1+1, 2p2+1, ...., 2ps-1+1, the sequence (λ2, λ3, ..., λn) can be formed as (2p1, 2p2, ...., 2ps-1) and (c1, c2,..., cl) as (p1, p2, ..., pl). The characteristic function of a subset J of S can be formed as (p1(mod 2), p2(mod 2),...pk(mod 2)) where k is the cardinality of S.
We refer to the sequences of parameters αi, γi, λi and the set J as pseudorandom data of the key.
The vast majority of parameters a(
During the communication session protected by the stream cipher correspondent can use pseudorandom sequences of kind (p1, p2,..., pn) as plaintexts. So they can safely change pseudorandom data of the key as well as other parameters of the key. Some new algorithms of generating pseudorandom or genuinely random sequences appear recently. They are based on the use of Artificial Intelligence, Machine Learning , Neural Networks and Quantum Computing. (see [32–36]).
In fact computer simulation show us the algorithm is very sensitive to the change of pseudorandom data.
We suggest to use some of the protocols of Noncommutative Cryptography (see [25–27]) implemented with multivariate platforms, We select the implementation [24] for the key establishment before the beginning of communication session. Reader can find some recent cryptanalytic results on Noncommutative Cryptography in [28–30] and [31].
The idea is the following. Correspondents Alice and Bob use the protocol to elaborate nonlinear
multivariate map of kind x1→f1(x1, x2,..., xs), x2→f2(x1, x2,..., xs), ..., xn→fs(x1, x2,..., xs), where fi, i=1,
2,..., s are elements of K[x1, x2,..., xs]. Alice uses the pseudorandom generator to construct sequences
u=(u1, u2,..., us). and (p1, p2,..., ps). She sends u to Bob via open channel together with (p1+f1(u1, u2,...,
us), p2+f2(u1, u2,..., us), ..., ps+fs(u1, u2,..., us)). He restores (p1, p2,..., ps). Note that O(
We introduce graph based stream cipher which use algebraic graph defined by partially hidden equations. The graph is homomorphic image of well known algebraic bipartite graph D(k+m, K) with the partitions sets isomorphic to the affine space Km under the homomorphism of deletion of special coordinates indexed by j, j ≥k+1. The subset J of cardinality t of coordinates for possible deletion can be arbitrary subset of the set of cardinality p=[(k+m+2)/4]-[(k+2)/4]. So we have 2p options to select S. If n is the dimension of the space of plaintexts then the equality m+k-t=n, where m, k are of linear size of kind αn+b with 0<α<1. The subset S is the part of the key of our stream cipher. So adversary do not know the basic graph in the definition of encryption process.
Note that in all previously known graph based stream ciphers the basic graph was known for the adversary. So he/she could use Dijkstra algorithm of finding the shortest pass for the cryptanalytic investigations of the stream cipher based on walks in the graph.
The idea to use connectivity invariants of graphs D(n, K) for the design of stream cipher was presented in [22] but the previous implementation in the case of K=Zq, q=2r did not use them (see [7], we refer to this cryptosystem as UMCS-cipher). In our new algorithm we preserve the following property of UMCS-cipher. Different active passwords produce distinct corresponding ciphertexts.
It means that in the case when adversary has passive password and does not have access to encrypted data he/ she has to complete the brut force search of all (q/2)k options for possible active password. Note that k is a linear function in variable n of kind αn+β with 0<α<1. So resistance to such attacks by adversary is increasing with the growth of parameter n.
The encryption map of UMCS-cipher as well as its inverse are cubic multivariate cubic transformation. As it was shown in [21] adversary can intercept O(n3) pairs of kind plaintext/ciphertext and approximate the encryption map and its inverse in time O(n10). The advantage of stream cipher is that the degree of its encryption map is >2n and the inverse is given by rational function. Thus attacks with the interception of plaintexts and corresponding ciphertext are unfeasible.
The algorithm is given with the procedure to change the passive and active key during the communication process.
Declaration on Generative AI While preparing this work, the authors used the AI programs Grammarly Pro to correct text grammar and Strike Plagiarism to search for possible plagiarism. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content.