# Some Graph-Based Encryption Schemes

Authors: Baizhu Ni; Rabiha Qazi; Shafiq Ur Rehman; Ghulam Farid
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In today’s technological world, confidentiality is an important issue to deal with, and it is carried out through different proficiencies. Cryptography is a scientific technique of securing a communication from unauthenticated approach. There exist many encryption algorithms in cryptography for data security. The need of new nonstandard encryption algorithms has been raised to prevent the communication from traditional attacks. This paper proposes some new encryption algorithms for secure transmission of messages using some special corona graphs and bipartite graph along with some algebraic properties. These proposed encryption schemes will lead to more secure communication of secret messages.


---

## Body

## 1. Introduction

Secret communications have been needed by military officers and diplomats since ancient times. In today’s advanced age, where the internet, mobile phones, and computer technology are widely used in almost every sphere of life, the need to keep important information secure and confidential is also increasing day by day. Overtime, as data security continues to evolve, new ways to break the confidential communication are being discovered.Cryptography is the science of transforming the secret data into coded information with the goal that it can safely reach its end without leakage. It was basically utilized for war time plans. Classical cryptography goes back over two thousand years. Modern cryptography was established by Shannon in 1949 [1]. After the development of digital communications, new forms of cryptography have come. It addresses the problems of secrecy, privacy, authentication, passwords, digital signatures, identification, and digital money. It is now an integral part of a modern society.The process to transform the original message into a code format is called the encryption, and the reverse process is known as decryption [2]. Encryption prevents the original contents from interception. Uncovered message is known as plaintext. In any encryption scheme, the information which is referred as plaintext is encoded or encrypted to generate a cipher text with the help of a specified key. This cipher text is then converted into readable message through decryption. Key is such a piece of information that is used to put the original data in code shape and then decrypt to get real text. Through a provided key, the authorized recipient can open up the hidden message with full ease, but it is not possible for an interceptor. Mainly, three types of schemes are used in modern cryptography, i.e., symmetric key cryptography, public key cryptograph, and hash functions [3]. Symmetric key cryptography uses one key for both encryption and decryption, while the public key cryptography uses one key for encryption and another key for decryption. The hash functions use a transformation to irreversibly encrypt information.We are interested in developing encryption by using graph theory and some algebraic concepts. Firstly, some useful concepts of graph theory are recalled [4]. A graph G=GV,E consists of two sets: the set of vertices VG and the set of edges EG. If the vertex set VG can be partitioned into two disjoint nonempty subsets such that each edge has one vertex in each partition, then the graph G is said to be a bipartite graph. A bipartite graph is said to be complete-bipartite if every vertex in one partition is joined to all vertices of other partition. A complete-bipartite graph, in which only one vertex is in one partition while all other vertices are in second partition, is termed as star graph. A vertex of degree one is named a pendent vertex, and the edge incident to it is pendent edge. The corona of two graphs G and H is the graph G⊙H formed by one copy of G and VG copies of H, where the ith vertex of G is joined to each vertex in the ith copy of H. This product is an important operation between graphs, introduced by Frucht and Harary [5]. The star graph Sn+1 on n+1 vertices can be seen as a corona graph K1⊙Kn¯. The corona graph of the cycle Cn with K1, i.e., Cn⊙K1, is a graph on 2n vertices obtained by attaching n pendant edges in a cycle graph Cn.Graphs can be used for designing different encryption algorithms. The interaction between graph theory and cryptography is quite interesting. For applications of graph theory in cryptography, refer to [6–9]. The recent past has seen a growing interest in exploring graphs as a tool to propose new methodologies in different areas of cryptography (see [10–20]). In [10], Selvakumar and Gupta proposed an innovative algorithm for encryption and decryption using connected graphs. In [11], Kedia and Agrawal discussed a new encryption algorithm, in which data are secured through numeric representation and letters, using basic concepts of mathematics like Venn diagram. In [12], the authors have proposed a graph-based algorithm for encryption in which fundamental circuits are chosen with respect to corresponding weights of edges. In [13], Yamuna and Karthika describe a unique method of transferring data by using bipartite graph. They constructed a numeric table for the representation of alphabets. In [14], Al Etaiwi presented a new symmetric encryption algorithm using cycle graph, complete graph, and minimum spanning tree. It is reflected in paper [15] that the authors highlight some vast applications of bipartite graph in computation. In [16], the authors presented a scheme for securing a data by giving a new concept of line sigraph. Sigraph consists of graphs with sign of edges and belongs to −1,+1 as their labeled number. In [17], the authors proposed a novel bipartite graph-based propagation approach to overcome fraud detection in large advertising system. In [18], Razaq et al. used coset diagram for the action of PSL2,ℤ on projective line over the finite field F29 to construct proposed substitution box (S-box). The strong S-box is an important area of research in cryptography. In [19], Razaq et al. generated a strong S-box using orbits of coset graphs and the action of the symmetric group S256. In [20], Selim G. Akl described an algorithm for encrypting a graph for its secure transmission from a sender to a receiver.Our aim in this work is to describe new encryption algorithms based on some types of graphs, particularly, the corona graphCn⊙K1, K1⊙Kn¯ (also called star graph), and the bipartite graph. The proposed algorithms send and receive secure messages consisting of words of any length by using graphs and certain algebraic properties. After applying prescribed algorithmic steps, data could be fully protected. The recipient then gets the labeled graph and eventually approaches to the original message.In Section2, an encryption scheme is described by using the corona graph Cn⊙K1. Afterwards, an algorithm of this scheme is formulated. Application of this algorithm is studied through an example. However, in Section 3, bipartite graphs are used to construct a secure encryption scheme with described algorithm. This scheme is applicable on important information, shown by an example. In Section 4, a secured encryption scheme is described by using a special corona graph K1⊙Kn¯, also named as a star graph. Its algorithm is mentioned, and application is viewed through an example.


## 2. Secure Data Transfer Using Corona GraphCn⊙K1

To initiate the described algorithm, the first step is to take a simple text which is to be transferred and is to be encrypted before sending. Every letter in data has its unique numeric representation, mentioned in encoding table, which is used to encode each alphabetic character. Then, each digit is transmuted up ton-place, through shift type of cipher. Now, new numeric values ai are obtained. Randomly, some positive integers bi are selected which are relatively prime with ai. By taking inverse of that ai in the modulus of bi, corona graph Cn⊙K1 is considered according to length of simple text with specified outward vertices and allocates the resulting inverses to suspended outward vertices, while main vertices are labeled with bi. The final labeled corona graph Cn⊙K1 is the encrypted data, in which the recipient receives to get required information. Figure 1 replicates the schematic diagram of the proposed algorithm.Figure 1
Schematic diagram.Algorithm for encryption is as follows:Give a plain-text word of lengthn.Give the numerical values to the alphabets of plain-text word and apply shift cipher;enx=x+nmod26, to each numerical value obtained before and get new numerical values, say a1, a2, a3, …, an.Find a sequence;b1, b2, b3, …, bn of positive integers in increasing order such that gcdbi,ai=1 and bi>26.Consider a corona graphCn⊙K1 with 2n vertices and allot weights b1, b2, b3, …, bn to the vertices, adjacent to pendent vertices randomly.Find the inverse ofaimodbi for all i and denote them by ci, i.e., ci=ai−1modbi∀i.Give numeric valuesc1, c2, c3, …, cn to pendent vertices.Send this corona graphCn⊙K1 to the receiver.Algorithm for decryption is as follows.The receiver receives the graph, and following steps are applied to transform the information and get original data:Arrange those vertices which are adjacent to the pendent vertices, in increasing order asb1<b2<b3<⋯<bn.Find the inverse of the weights of pendent verticesci modulus their adjacent vertices bi and denote them by ai for each i.Computewi=ai−order of graph/2mod26,∀i.Convert the numeric valueswi for each i, to relate specific alphabets.Example 1.
Let us suppose we have to transfer information, i.e., EDGE, encrypting it and then sending it to the recipient.
The starting point is to convert the alphabetic letters into numbers of their respective positions through the encoding table, as shown in Figure2:Figure 2
Numeric representation.(1)EDGE5475.Here, length of word isn=4. Applying shift cipher en=x+nmod26, we get(2)5+4=9=a1,4+4=8=a2,7+4=11=a3,5+4=9=a4.Given word is encrypted in the form(3)IHKI.Selecting random increasing integersbi such that value of bi>26:(4)gcdb1,a1=gcd28,9=1,gcdb2,a2=gcd31,8=1,gcdb3,a3=gcd35,11=1,gcdb4,a4=gcd47,9=1.Construct corona graphCn⊙K1 and put value of bi to main vertices randomly, as shown in Figure 3.Now, through the below-mentioned step,(5)ci=ai−1modbi,we get(6)c1=a1−1modb1=9−1mod28=25,c2=a2−1modb2=8−1mod31=4,c3=a3−1modb3=11−1mod35=16,c4=a4−1modb4=9−1mod47=21.These inverse values are given to the adjacent pendant vertices of Figure3, as shown in Figure 4.Send this labeled graph (Figure4) to the receiver.The recipient, after receiving that labeled graph, arranges the main vertices in ascending order such that(7)28<31<35<47,and considers these numbers as values of bi such that(8)b1<b2<b3<b4.Taking inverses of corresponding pendent vertices with respect to the value of eachbi, as shown in Figure 4, we get(9)25−1mod28=9=a1,4−1mod31=8=a2,16−1mod35=11=a3,21−1mod47=9=a4.Now, forwi,(10)wi=ai−2n2mod26.Find values ofa1, a2, a3, and a4:(11)w1=a1−242mod26=5=E,w2=a2−242mod26=4=D,w3=a3−242mod26=7=G,w4=a4−242mod26=5=E.Finally, we get the original text.Figure 3Figure 4


## 3. Secure Data Transfer Using Bipartite Graphs

In this section, we propose an encryption algorithm for the secure and confidential communication of messages between two communicating parties. The construction of this encryption algorithm is based on bipartite graph and the concept of unique factorization domain (UFD). The following are the steps of algorithm.Algorithm for encryption is as follows:Take a UFD with infinite primes. For example,ℤ.Take a setPn of first “n” primes, where n=⌈26/k+k⌉, 2<k<13, and k = key (which is fixed according to length of a word).Consider a message, for encryption with length S.Then, make a tablen−k×k such that the first value shows number of rows and second value shows the number of columns.After that, alphabets are partitioned as1st,2nd,3rd,…,kth position primes. (horizontally)while;(k + 1)th, (k + 2)th, (k + 3)th, …, nth position primes. (vertically)Now, label the alphabets with the integersrici ; ri=row position, ci=column position.Label the entryij with rici, where k+1≤i≤n, 1≤j≤kForming each number as vertex of path graph (according to sequence of letters).Multiplyingi.j and then label each vertex with that number (say, ap where 1≤p≤k). Keeping in view that, one place digits are not taken in column position. In other words, we say that column position has just 2-digit primes.Construct a path graph by giving consecutivei,j numbers to each vertex.Separate the graph labels as row and column numbers;V1  = {first place numbers from i}V2  = {second place numbers from j}Edge set ofG becomes (r1,c1), (r2,c2), …, (rn,cn).Now construct a bipartite graph with mentioned edge set. Edges move fromri to ci.Assign random numbers to the edges as weight in increasing order.Send that labeled graph.Algorithm for decryption is as follows.The recipient receives the labeled bipartite graph.Arrange the weight of edges in increasing order.Then, arrange edges with respect to weights in a set of order pair such that number of rows at first and number of columns at second position.Construct path graph with the help of order pair information.Find prime factorization of each vertex label.Resultantly, required alphabets are taken through factorization, by using table (described).Example 2.
For defining the scheme, we have to explain an example. Take a word,G R A P H. Numerically, corresponding digits are 7, 18, 1, 16, and 8, respectively. Here, length of word is k=5.Step 1: take a UFD with infinite primes, i.e.,ℤ.Step 2: in this example,n=⌈26/5+5⌉; 2<k<13. So, n=11. Take a set P11 of first 11 primes. As, P11=2,3,5,7,11,13,17,19,23,29,31.Step 3: Figure5 shows a table. For making a table, n−k×k=6×5. First value, i.e., 6 shows the number of rows and 5 the number of columns.Step 4: message becomesG=173, R=235, A=132, P=232, H=175; 6≤i≤11, 1≤j≤5.Step 5: corresponding values are(12)a1=17×3=51,a2=23×5=115,a3=13×2=26,a4=23×2=46,a5=17×5=85.
Next, we construct a path graph by labelling the vertices, as shown in Figure6
Here,V1=5,11,2,4,8 and V2=1,5,6.
The vertex set of bipartite graph becomes(13)GV1,V2=5,1,11,5,2,6,4,6,8,5.
Graph is obtained as shown in Figure7.
Now, apply arbitrary weights to the adjacent edges of the bipartite graph in Figure7, as shown in Figure 8.
Send the labeled graph in Figure8 to the receiving authority. Then, apply the steps for decryption:Step 1: at first, arrange the weight of the edges in ascending order:(14)W=10,18,21,36,41.Step 2: now, arrange edges {(5,1), (11,5), (2,6), (4,6), (8,5)}.The corresponding path graph is shown in Figure9.Step 3: prime factorization of each vertex label. As,51=3×17, …, 85=5×17. Numerical values are 173,235,132,232,and175, respectively.Step 4: we finally get the alphabetsG R A P H according to values in the described table. Keep in view that one place digits are not in column position.Figure 5Figure 6Figure 7Figure 8Figure 9The examples prove the security of described algorithm. This tells a simple bipartite graph can make secrecy of information very strong, that is, the major output of any encryption scheme.


## 4. Secure Data Transfer Using Star Graphs

Many schemes are introduced to protect data. The mentioned scheme is based on star graphs. Information is transferred with full secrecy of main idea. These steps are followed to encrypt data and then decrypt it by applying decryption steps.Algorithm for encryption is as follows:LetM be the message which is to be encrypted. Length is l(say).Here, we have to use shift cipher with formulation:(15)ekx=x+kmod26.Keepingk=l (fixed).Converting the plaintext message to a sequence of integers by addingk into every value, by reducing every sum into modulo 26.Now, take a star graphSn+1=K1⊙Kn¯, corresponding to the length of message, by fixing center vertex with the numeric value zero, such that number of vertices of star graph = 1 + number of alphabetic characters in the text.Representing data as vertices of a graph, each vertex is represented by a letter. However, all adjacent vertices of a graph will be represented as adjacent letters.Now label each vertex with respect to their numeric representation in shift cipher.Next, give weightsw1,w2,w3,…,wn to each edge e1,e2,e3,…,en in such a way that(16)w1e1<w2e2<w3e3<⋯<wnen.Method for finding weights of edges.Subtract increasing power of 10 from each vertex label, adjacently with respect to edges, such that(17)V1−10,V2−102,V3−103,…,Vn−10n,whereVi∈vertex texi=1,2,3,…,n.These resulting values become weight of corresponding edgesei.Now, the final graph is the star graph with edge’s weights (hiding the vertex label).Send this graph to the receiver.After explaining the encryption procedure, we have to explain the decryption scheme as well.Algorithm for decryption is as follows:Arrange the weight of edges in ascending order.Now add up the increasing power of 10, respectively.Apply the decryption formulation for shift cipher in the resulting number.Decode the characters from encoding table, and eventually, we get the required text.Example 3.
For explaining the described scheme, we have to take an example for satisfying the steps. Let us take a wordCODE. We have to send this word by encrypting it with the help of such scheme.
Replace the alphabetic characters with their numeric representation. Length of message isk=4:(18)CODE31545.
Now, consider a star graphS5=K1⊙K4¯, such that the number of its corner vertices is equal to the length of message. Figure 10 shows the respective star graph in such a way that edges are labeled as e1, e2, e3, and e4.
Apply the shift type of cipher as shifting up to the lengthk of the message. In this example, translated through formula,(19)e4x=x+4mod6.
New shifted numeric values are7,19,8,and9, respectively. The related graph becomes as shown in Figure 11.
After that, apply weightswi,∀i∈1,2,3,4 to the corresponding edges of the vertices:(20)w17<w219<w38<w49.
Weights are given by subtracting the increasing power of 10 from each adjacent numeric value in Figure11:(21)weight of edgee1=w1=7−10,weight of edgee2=w2=19−102,weight of edgee3=w3=8−103,weight of edgee4=w4=9−104.
Resulting star graph is shown in Figure12.
This is the final labeled graph, which is to be send to the second authority. Now, describe the decryption process. Firstly, the recipient receives the labeled graph, as shown in Figure12.
The initial step is arranging the weights of edges (Figure13) in ascending order of mod values, i.e.,(22)−3<−81<−992<−9991.
Add the increasing power of 10 to each adjacent value such that(23)−3+10<−81+100<−992+1000<−9991+10000.
Through this mod operation, we get the values:(24)7,19,8,9.
Apply inverse shifting by guessing the number of edges of the star graph, which is 4. So, the values become as follows:(25)7−4=3,19−4=15,8−4=4,9−4=5.
Finally, we get the values3,15,4,5. Through the encoding table, we get their respective letters as C O D E. Get the required hidden text.
This example explains that any type of data is hidden and is kept secure until it approaches to the receiver. The algorithm depends on star graphs. Labeled graphs are sent to the recipient. It is a best possible way to secure the data.Figure 10Figure 11Figure 12Figure 13


## 5. Conclusion

This work presents graph theoretic-based schemes to improve encryption quality. Three new encryption algorithms are proposed which are very helpful for secure communication of secret messages. In the first algorithm, encryption and decryption is performed by using a specific corona graphCn⊙K1 along with some basic algebraic properties. The second algorithm is based on encoding table, bipartite graph, and the concept of unique factorization domain (UFD). In third algorithm, we used a certain labeling of vertices and edges of the star graph K1⊙Kn¯. These symmetric algorithms use the concept of shared key that must be predefined and shared between two communicating parties. We can modify the proposed algorithms, to be applicable for the communication of sentences or the set of sentences. Furthermore, for more complexity, these algorithms could be improved by using the public key cryptography. Moreover, we can try to implement these algorithms using any programming language like C++, JAVA, or Microsoft.Net.



---

*Source: 6614172-2021-02-19.xml*