# Outer-Convex Dominating Set in the Corona of Graphs as Encryption Key Generator

Authors: Zehui Shao; S. Kosari; R. Anoos; S. M. Sheikholeslami; J. A. Dayap
Journal: Complexity
 (2020)

---

## Abstract

In this paper, we present a new type of symmetric encryption by converting the classical monoalphabetic affine cipher into a polyalphabetic cipher. The proposed encryption utilizes the properties of outer-convex dominating set in the corona of graphs to generate random keys from the shared keyword to every character of the message. The new encryption eliminates the weaknesses of affine cipher, thus increasing the level of confidence for exchanging messages.


---

## Body

## 1. Introduction

The security of a system is highly essential nowadays. In an economic era in which industries are information-intensive, data is considered one of the world’s most treasured resources that fuels economic operations; thus, security of information is a significant requirement. With the rapid growth of the information technology power and with the emergence of the innovative technologies, the number of threats a user is supposed to deal with has grown exponentially. For example, information exchange is challenged by issues pertaining to confidentiality, authenticity, and nonrepudiation. The increasing concern of securing data requires a strong algorithm that enables high level of data protection. This necessitates an algorithm of superior quality which is a combination of both performance and security. Cryptography is where security engineering meets mathematics. It provides us with the tools that underlie most modern security protocols. It is probably the key enabling technology for protecting distributed systems, yet it is surprisingly hard to do right, particularly when one aims for resistance to different types of adversaries. Cryptography consists of processing plain information (plaintext) applying a cipher and producing encoded output (ciphertext), meaningless to a third-party who does not know the key. The process of transforming plaintext into ciphertext is called encryption and the reverse process is called decryption. In cryptography both encryption and decryption phase are determined by one or more keys. The creation of algorithms which enhance protection capabilities continues to be the direction of the growing concern for a secured communication.One of the simplest methods for encrypting text is the substitution cipher. A substitution cipher replaces one symbol with another. If the symbols in the plain text are alphabetical characters, we replace one character with another. Substitution ciphers can be categorized as eithermonoalphabetic ciphers or polyalphabetic ciphers. In monoalphabetic substitution, each character in the plain text is always replaced by the same character in the cipher text regardless of its position in the text. In polyalphabetic substitution, each occurrence of a character may have a different substitute. The relationship between a character in the plain text to a character in the cipher text is one to many [1].Modern ciphers possess two important properties: diffusion and confusion. The idea of diffusion is to hide the relationship between the cipher text and the plain text. This will frustrate the adversary who uses the cipher text statistics to find the plain text. The idea of confusion is to hide the relationship between the cipher text and the key. This will frustrate the adversary who tries to use the cipher text to find the key. Diffusion and confusion can be achieved using the concept of a complex cipher known as a product cipher introduced by Shannon [2]. The success and competence of the cryptographic cipher technique depends upon the fact that how difficult it is to be broken or cracked by a cryptanalyst. Affine cipher is a kind of monoalphabetic substitution cipher, in which each letter in the alphabet is converted to its numeric equivalent, encrypted by a simple arithmetical equation, and converted back to the letter. This cipher is defined by the following rule:(i)
Encryption rule:C≡aP+bmod26(ii)
Decryption rule:P≡a¯C−bmod26Here,C is the ciphertext, P is the plaintext, and K=a,b is the shared key such that 0≤C≤25 and 0≤P≤25 for some a,b∈Z with gcda,26=1, and a¯ is the multiplicative inverse of a in Z26.In this encryption scheme, each letter of the original message is replaced by the same cipher substitute. Thus, such cryptographic systems are highly vulnerable to statistical methods of attack since it preserves the frequency, or relative commonness, of individual letters. Affine ciphers can easily make a system noticeably secure by multiplying each plaintext value by a different number and then inserting a shift. Thus, the said affine cipher will become complex and more secured if it will be converted into a polyalphabetic cipher [3].Domination in graph is seen as a new tool in developing a complex process in encoding messages [4]. Domination is an area in graph theory with numerous research activities. Nowadays, studies in the field of domination have been growing rapidly because of its wide variation of domination parameters and its application such as those found in [5–14]. One of the domination parameters is outer-convex domination number which was introduced by Dayap and Enriquez in [15] and further investigated in [16, 17]. In [15–17], the authors characterized the outer-convex domination in the join of two graphs and outer-convex domination numbers 1 and 2 and characterized the parameter in the corona, composition, and Cartesian product of graphs.In this paper, we propose a complex process of encoding and decoding messages by converting the monoalphabetic affine cipher into polyalphabetic cipher by using the property of outer-convex dominating set in the corona of two graphs to generate random keys from the shared keyword to every character of the message (see Figure1).Figure 1
Proposed polyalphabetic affine cipher based on the minimum outer-convex dominating set in the corona of graphs.


### 1.1. Related Works

In [18], they propose a polyalphabetic cipher with diffusion and confusion properties based on the concept of the complex cipher used by combining of Vigenére cipher with Affine cipher. Yamuna et al. [19] presented an encryption mechanism using Hamilton path properties (path that covers all vertices in the graph). They encrypt data twice, first using the Hamilton path and second using the complete graph to impose more secure method. Etaiwi [20] proposed a new symmetric encryption algorithm that uses the concepts of cycle graph, complete graph, and minimum spanning tree to generate a complex cipher text using a shared key. In [5], they provided a method of encrypting any chemical formula using graph domination as a tool for encryption. Here, every chemical formula is converted into a binary string using graph domination and later encrypted using DNA steganography.


### 1.2. Basic Graph Definitions and Properties

Graph theory is the study of graphs, which are mathematical structures used to formulate models in many problems in business, social sciences, physical sciences, and information systems. In this section, we discuss some of the basic concepts of graph that we will encounter throughout our investigation. The definitions and notations are based on [21].Definition 1.
A graphG consists of a pair VG,EG where VG is a nonempty finite set whose elements are called vertices and EG is a set of unordered pairs of distinct elements of VG. The elements of EG are called edges of the graph G. The number of vertices in G is called the order of G. A graph is connected when there is a path between every pair of vertices.Definition 2.
A dominating set for a graphG=VG,EG is a subset S of VG such that every vertex not in S is adjacent to at least one vertex of S.Definition 3.
A subsetC of VG is convex in a graph G if, for every pair of vertices x,y∈C, each x−y geodesic (shortest path, curve, or arc) joining x and y lies completely in C.Definition 4.
Cycle graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3) connected in a closed chain.Definition 5.
Path graph is a graph that can be drawn so that all of its vertices and edges lie on a single straight line.Definition 6.
LetG and H be graphs of order m and n, respectively. The corona of two graphs G and H is the graph G∘H obtained by taking one copy of G and m copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H.Definition 7.
A setS of vertices of a graph G is an outer-convex dominating set if every vertex not in S is adjacent to some vertex in S and VG\S is convex. The minimum outer-convex dominating set of G is the minimum cardinality of an outer-convex dominating set of G.Corollary 1 (see [17]).
LetG be a connected graph of order m≥2 and H be any graph of order n. The set S⊂VG∘H is a minimum outer-convex dominating set in G∘H if S=∪x∈VGSx, where Sx⊆VHx is a minimum outer-convex dominating set in x+Hx.


## 1.1. Related Works

In [18], they propose a polyalphabetic cipher with diffusion and confusion properties based on the concept of the complex cipher used by combining of Vigenére cipher with Affine cipher. Yamuna et al. [19] presented an encryption mechanism using Hamilton path properties (path that covers all vertices in the graph). They encrypt data twice, first using the Hamilton path and second using the complete graph to impose more secure method. Etaiwi [20] proposed a new symmetric encryption algorithm that uses the concepts of cycle graph, complete graph, and minimum spanning tree to generate a complex cipher text using a shared key. In [5], they provided a method of encrypting any chemical formula using graph domination as a tool for encryption. Here, every chemical formula is converted into a binary string using graph domination and later encrypted using DNA steganography.


## 1.2. Basic Graph Definitions and Properties

Graph theory is the study of graphs, which are mathematical structures used to formulate models in many problems in business, social sciences, physical sciences, and information systems. In this section, we discuss some of the basic concepts of graph that we will encounter throughout our investigation. The definitions and notations are based on [21].Definition 1.
A graphG consists of a pair VG,EG where VG is a nonempty finite set whose elements are called vertices and EG is a set of unordered pairs of distinct elements of VG. The elements of EG are called edges of the graph G. The number of vertices in G is called the order of G. A graph is connected when there is a path between every pair of vertices.Definition 2.
A dominating set for a graphG=VG,EG is a subset S of VG such that every vertex not in S is adjacent to at least one vertex of S.Definition 3.
A subsetC of VG is convex in a graph G if, for every pair of vertices x,y∈C, each x−y geodesic (shortest path, curve, or arc) joining x and y lies completely in C.Definition 4.
Cycle graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3) connected in a closed chain.Definition 5.
Path graph is a graph that can be drawn so that all of its vertices and edges lie on a single straight line.Definition 6.
LetG and H be graphs of order m and n, respectively. The corona of two graphs G and H is the graph G∘H obtained by taking one copy of G and m copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H.Definition 7.
A setS of vertices of a graph G is an outer-convex dominating set if every vertex not in S is adjacent to some vertex in S and VG\S is convex. The minimum outer-convex dominating set of G is the minimum cardinality of an outer-convex dominating set of G.Corollary 1 (see [17]).
LetG be a connected graph of order m≥2 and H be any graph of order n. The set S⊂VG∘H is a minimum outer-convex dominating set in G∘H if S=∪x∈VGSx, where Sx⊆VHx is a minimum outer-convex dominating set in x+Hx.


## 2. Materials and Methods

### 2.1. Minimum Outer-Convex Dominating Set inPn∘C4

In this section, we present on how to determine the minimum outer-convex dominating set in the corona of two graphs using Corollary1. Here, we let the graph H=C4 (cycle graph of order 4) as a keyword and the graph G=Pn (n is the order of a path graph Pn) as the message to be encrypted.Example 1.
Determine all the minimum outer-convex dominating sets in the graphG=Pn∘C4.Solution.
the graph illustrated in Figure2 is the corona of a path graph of order 3 and a cycle graph of order 4.
Using Corollary1, the elements that consist the minimum outer-convex sets of the graph G are combinations of 1,2,2,1,2,3,3,23,4,4,3,1,4,and4,1. By convention, we let A=1,2, B=2,1, C=2,3, D=3,2, E=3,4, F=4,3, G=1,4, and H=4,1. Thus, the graph G has the minimum outer-convex dominating sets presented in Table 1 (here, we define the minimum outer-convex dominating set as a permutation of the minimum outer-convex dominating set with respect to its position).
The graph in Figure2 has 512 different sets that satisfies the condition of minimum outer-convex dominating set. In general, the graph G=Pn∘C4 has 8n number of different minimum outer-convex dominating sets, where n is the order of graph Pn. To convert the monoalphabetic affine cipher to a polyalphabetic cipher, the key that is used to encrypt and decrypt in every letter of the message must not be the same. Hence, we omit the MOCDS that has the same elements (AAA, BBB, CCC, DDD, EEE, FFF, GGG, and HHH). This implies now that the graph G=Pn∘C4 has 8n−n number of different minimum outer-convex dominating sets.Figure 2
The graph ofG=P3∘C4.Table 1
Minimum outer-convex dominating sets of a graphG=P3∘C4.
AAABAACAADAAEAAFAAGAAHAA⋮⋮⋮⋮⋮⋮⋮⋮AAHBAHCAHDAHEAHFAHGAHHAHABABBACBADBAEBAFBAGBAHBA⋮⋮⋮⋮⋮⋮⋮⋮ABHBBHCBHDBHEBHFBHGBHHBH⋮⋮⋮⋮⋮⋮⋮⋮AGHBGHCGHDGHEGHFGHGGHHGHAHABHACHADHAEHAFHAGHAHHA⋮⋮⋮⋮⋮⋮⋮⋮AHHBHHCHHDHHEHHFHHGHHHHH


### 2.2. Lists of Tables of Minimum Outer-Convex Dominating Sets (MOCDS) ofG=Pn∘C4 with Their Corresponding Locator Given the Order of Graph Pn

In this section, we provide some of the lists of minimum outer-convex dominating sets ofG=Pn∘C4 with their corresponding locator. This locator will be used as part of the proposed encryption scheme.By convention, we let(1)A=a1,a2B=a2,a1C=a2,a3D=a3,a2E=a3,a4F=a4,a3G=a4,a1H=a1,a4,where(i)
a1, a2a3, and a4 are the equivalent numbers of the first, second, third, and fourth letter of the keyword, respectively.Forn=1,2,3, the lists of minimum outer-convex dominating sets of Pn∘C4 is given in Tables 2–4, respectively.Table 2
Minimum outer-convex dominating sets ofG, where n=1.
LocatorMOCDS0A4E1B5F2C6G3D7HTable 3
Minimum outer-convex dominating sets ofG, where n=2.
LocatorMOCDS0AA⋮⋮7AH8BA⋮⋮15BH16CA⋮⋮23CH24DA⋮⋮31DH32EA⋮⋮39FA40FB⋮⋮47CA48GA⋮⋮55GH56HA⋮⋮63HHTable 4
Minimum outer-convex dominating sets ofG, where n=3.
LocatorMOCDS0AAA⋮⋮7AAH⋮⋮63AHH64BAA⋮⋮71BAH72BBA⋮⋮79BBH⋮⋮127BHH128CAA⋮⋮135CAH⋮⋮191CHH192DAA⋮⋮199DAH200DBA⋮⋮207DBH⋮⋮255DHH256EAA⋮⋮263EAH⋮⋮319EHH320FAA⋮⋮327FAH328FBA⋮⋮335FBH⋮⋮383FHH384GAA⋮⋮391GAH⋮⋮447GHH448HAA⋮⋮455HAH456HBA⋮⋮463HBH⋮⋮511HHHFor the succeeding tables, we follow the pattern presented above (i.e., there is an alternation of letters from right to left with a given pattern of 1, 8, 64, 512, …) in listing all the minimum outer-convex dominating sets with their corresponding locator.


### 2.3. Encryption Algorithm

In this section, we propose a cryptography algorithm to encrypt data to be transmitted using properties of outer-convex dominating set. This algorithm is a symmetric cryptography wherein it uses the concept of shared key that must be predefined and shared between the sender and receiver. The four-letterkeyword and key (c,d) are the keys being shared by the sender and receiver:(1)
Draw the graphG=Pn∘C4, where n is equal to the number of letters of the message to be encrypted.(2)
Write each letter of the original message inside the nodes ofPn and each four-letter keyword inside the nodes of C4. The equivalent numerical value of each letter of the keyword must be relatively prime with 8n.(3)
Replace the letters into its equivalent numerical value presented in the encoded Table5.Table 5
Encoded table based on the letters of the alphabet.
ABCDEFGHIJKLMNOPQRSTUVWXYZ0001020304050607080910111213141516171819202122232425(4)
Locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(2)LMOCDS≡cM+dmod8n,as a locator, where(i)
c,d is the agreed key such that c,d∈Z(ii)
M is the product of the equivalent numerical values of the agreed keyword(iii)
n is the number of letters of the original message (note: if the resulting locator will give a minimum outer-convex dominating set of the same element such as AA, BBB, CCCC, and DDDD, reject it and select the next locator in determining the MOCDS).(5)
Encrypt the message using the affine transformation:(3)C≡aP+bmod26,where(i)
a,b is the equivalent numerical value in the identified minimum outer-convex dominating set which is adjacent to the letter to be encrypted(ii)
P is the equivalent numerical value of the plaintext(iii)
C is the equivalent numerical value of the ciphertext.And replace the resulting number into its corresponding letter presented in Table5.


### 2.4. Decryption Algorithm

Here, we provide the decryption algorithm that decrypts the message based on the proposed encryption algorithm in the previous section.(1)
Locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(4)LMOCDS≡cM+dmod8n,as a locator, where(i)
(c,d) is the agreed key such that c,d∈Z(ii)
M is the product of the equivalent numerical values of the agreed keyword(iii)
n is the number of letters of the ciphertext (note: if the resulting locator will give a minimum outer-convex dominating set of the same element such as AA, BBB, CCCC, and DDDD, reject it and select the next locator in determining the MOCDS)(2)
Decrypt the message using the affine transformation:(5)P≡a¯C−bmod26,where(i)
(a,b) is the equivalent numerical value in the identified minimum outer-convex dominating set which is adjacent to the letter to be encrypted and a¯ is the inverse of a in mod 26(ii)
P is the equivalent numerical value of the plaintext(iii)
C is the equivalent numerical value of the ciphertext.And replace the resulting number into its corresponding letter.


## 2.1. Minimum Outer-Convex Dominating Set inPn∘C4

In this section, we present on how to determine the minimum outer-convex dominating set in the corona of two graphs using Corollary1. Here, we let the graph H=C4 (cycle graph of order 4) as a keyword and the graph G=Pn (n is the order of a path graph Pn) as the message to be encrypted.Example 1.
Determine all the minimum outer-convex dominating sets in the graphG=Pn∘C4.Solution.
the graph illustrated in Figure2 is the corona of a path graph of order 3 and a cycle graph of order 4.
Using Corollary1, the elements that consist the minimum outer-convex sets of the graph G are combinations of 1,2,2,1,2,3,3,23,4,4,3,1,4,and4,1. By convention, we let A=1,2, B=2,1, C=2,3, D=3,2, E=3,4, F=4,3, G=1,4, and H=4,1. Thus, the graph G has the minimum outer-convex dominating sets presented in Table 1 (here, we define the minimum outer-convex dominating set as a permutation of the minimum outer-convex dominating set with respect to its position).
The graph in Figure2 has 512 different sets that satisfies the condition of minimum outer-convex dominating set. In general, the graph G=Pn∘C4 has 8n number of different minimum outer-convex dominating sets, where n is the order of graph Pn. To convert the monoalphabetic affine cipher to a polyalphabetic cipher, the key that is used to encrypt and decrypt in every letter of the message must not be the same. Hence, we omit the MOCDS that has the same elements (AAA, BBB, CCC, DDD, EEE, FFF, GGG, and HHH). This implies now that the graph G=Pn∘C4 has 8n−n number of different minimum outer-convex dominating sets.Figure 2
The graph ofG=P3∘C4.Table 1
Minimum outer-convex dominating sets of a graphG=P3∘C4.
AAABAACAADAAEAAFAAGAAHAA⋮⋮⋮⋮⋮⋮⋮⋮AAHBAHCAHDAHEAHFAHGAHHAHABABBACBADBAEBAFBAGBAHBA⋮⋮⋮⋮⋮⋮⋮⋮ABHBBHCBHDBHEBHFBHGBHHBH⋮⋮⋮⋮⋮⋮⋮⋮AGHBGHCGHDGHEGHFGHGGHHGHAHABHACHADHAEHAFHAGHAHHA⋮⋮⋮⋮⋮⋮⋮⋮AHHBHHCHHDHHEHHFHHGHHHHH


## 2.2. Lists of Tables of Minimum Outer-Convex Dominating Sets (MOCDS) ofG=Pn∘C4 with Their Corresponding Locator Given the Order of Graph Pn

In this section, we provide some of the lists of minimum outer-convex dominating sets ofG=Pn∘C4 with their corresponding locator. This locator will be used as part of the proposed encryption scheme.By convention, we let(1)A=a1,a2B=a2,a1C=a2,a3D=a3,a2E=a3,a4F=a4,a3G=a4,a1H=a1,a4,where(i)
a1, a2a3, and a4 are the equivalent numbers of the first, second, third, and fourth letter of the keyword, respectively.Forn=1,2,3, the lists of minimum outer-convex dominating sets of Pn∘C4 is given in Tables 2–4, respectively.Table 2
Minimum outer-convex dominating sets ofG, where n=1.
LocatorMOCDS0A4E1B5F2C6G3D7HTable 3
Minimum outer-convex dominating sets ofG, where n=2.
LocatorMOCDS0AA⋮⋮7AH8BA⋮⋮15BH16CA⋮⋮23CH24DA⋮⋮31DH32EA⋮⋮39FA40FB⋮⋮47CA48GA⋮⋮55GH56HA⋮⋮63HHTable 4
Minimum outer-convex dominating sets ofG, where n=3.
LocatorMOCDS0AAA⋮⋮7AAH⋮⋮63AHH64BAA⋮⋮71BAH72BBA⋮⋮79BBH⋮⋮127BHH128CAA⋮⋮135CAH⋮⋮191CHH192DAA⋮⋮199DAH200DBA⋮⋮207DBH⋮⋮255DHH256EAA⋮⋮263EAH⋮⋮319EHH320FAA⋮⋮327FAH328FBA⋮⋮335FBH⋮⋮383FHH384GAA⋮⋮391GAH⋮⋮447GHH448HAA⋮⋮455HAH456HBA⋮⋮463HBH⋮⋮511HHHFor the succeeding tables, we follow the pattern presented above (i.e., there is an alternation of letters from right to left with a given pattern of 1, 8, 64, 512, …) in listing all the minimum outer-convex dominating sets with their corresponding locator.


## 2.3. Encryption Algorithm

In this section, we propose a cryptography algorithm to encrypt data to be transmitted using properties of outer-convex dominating set. This algorithm is a symmetric cryptography wherein it uses the concept of shared key that must be predefined and shared between the sender and receiver. The four-letterkeyword and key (c,d) are the keys being shared by the sender and receiver:(1)
Draw the graphG=Pn∘C4, where n is equal to the number of letters of the message to be encrypted.(2)
Write each letter of the original message inside the nodes ofPn and each four-letter keyword inside the nodes of C4. The equivalent numerical value of each letter of the keyword must be relatively prime with 8n.(3)
Replace the letters into its equivalent numerical value presented in the encoded Table5.Table 5
Encoded table based on the letters of the alphabet.
ABCDEFGHIJKLMNOPQRSTUVWXYZ0001020304050607080910111213141516171819202122232425(4)
Locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(2)LMOCDS≡cM+dmod8n,as a locator, where(i)
c,d is the agreed key such that c,d∈Z(ii)
M is the product of the equivalent numerical values of the agreed keyword(iii)
n is the number of letters of the original message (note: if the resulting locator will give a minimum outer-convex dominating set of the same element such as AA, BBB, CCCC, and DDDD, reject it and select the next locator in determining the MOCDS).(5)
Encrypt the message using the affine transformation:(3)C≡aP+bmod26,where(i)
a,b is the equivalent numerical value in the identified minimum outer-convex dominating set which is adjacent to the letter to be encrypted(ii)
P is the equivalent numerical value of the plaintext(iii)
C is the equivalent numerical value of the ciphertext.And replace the resulting number into its corresponding letter presented in Table5.


## 2.4. Decryption Algorithm

Here, we provide the decryption algorithm that decrypts the message based on the proposed encryption algorithm in the previous section.(1)
Locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(4)LMOCDS≡cM+dmod8n,as a locator, where(i)
(c,d) is the agreed key such that c,d∈Z(ii)
M is the product of the equivalent numerical values of the agreed keyword(iii)
n is the number of letters of the ciphertext (note: if the resulting locator will give a minimum outer-convex dominating set of the same element such as AA, BBB, CCCC, and DDDD, reject it and select the next locator in determining the MOCDS)(2)
Decrypt the message using the affine transformation:(5)P≡a¯C−bmod26,where(i)
(a,b) is the equivalent numerical value in the identified minimum outer-convex dominating set which is adjacent to the letter to be encrypted and a¯ is the inverse of a in mod 26(ii)
P is the equivalent numerical value of the plaintext(iii)
C is the equivalent numerical value of the ciphertext.And replace the resulting number into its corresponding letter.


## 3. Results and Discussion

### 3.1. Implementation of Modified Affine Cipher

Example 2.
Encrypt the message OUR with a keyword FLPR and a key (5, 3).Solution.
(i)
Step 1: draw the graphG=Pn∘C4, where n is equal to the number of letters of the message to be encrypted. Since the message to be encrypted has three letters, we have a graph G=P3∘C4, as shown in Figure 3.(ii)
Step 2: write each letter of the original message inside the nodes ofPn and each four-letter keyword inside the nodes of C4 (see Figure 4).
See Table6.Figure 3
The graphG=P3∘C4.Figure 4
The graphG=P3∘C4 with its corresponding letters.(iii)
Step 3: peplace the letters with their equivalent numerical values (see Figure5).Figure 5
A graphG=P3∘C4 with its equivalent numerical values.(iv)
Step 4: locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(6)LMOCDS≡cM+dmod8n.The agreed key (c,d) is (5, 3), the M is 14, 025, and n is 3. Thus,(7)LMOCDS≡514,025+3mod83=496,implying that the desired minimum outer-convex dominating set is on the496th location. Using the table in Section 2.2, the 496th MOCDS is H,G,A, that is, 5,17,17,5,5,11.(v)
Step 5: encrypt the message using the affine transformation,C≡aP+bmod26, and replace the resulting number with its corresponding letter presented on the encoded Table 5.Table 6
Solution on the evaluated affine transformation,C≡aP+bmod26.
PlaintextOUR142017C≡aP+bmod26C≡514+17mod26C≡1720+5mod26C≡517+11mod269718CiphertextJHSExample 3.
Decrypt the message JHS with a keyword FLPR and a key (5, 3).Solution.
(i)
Step 1: locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation(8)LMOCDS≡cM+dmod8n.Sincec=5,d=3,n=3, and M=14,025, it follows that(9)LMOCDS≡514,025+3mod64=496.This implies that the desired minimum outer-convex dominating set is on the496th location. Using the table in Section 2.2, the 496th MOCDS is H,G,A, that is, 5,17,17,5,5,11.(ii)
Step 2: decrypt the message using the affine transformation:(10)P≡a¯C−bmod26,and replace the resulting number with its corresponding letter, see Table 7.Table 7
Solution on the evaluated affine transformation,P≡a¯C−bmod26.
CiphertextJHS9718P≡a¯C−bmod26P≡5¯9−17mod26P≡17¯7−5mod26P≡5¯18−11mod26P≡219−17mod26P≡237−5mod26P≡2118−11mod26142017PlaintextOUR


### 3.2. Security Analysis

(1)
The frequency analysis is not possible to perform in this algorithm because the characters are encrypted as one to many. That is, a single character is mapped to many characters while performing encryption.(2)
Kasiski Test fails because the key in this algorithm is not repeating, i.e., the key is based on the locator of the minimum outer-convex dominating set.


## 3.1. Implementation of Modified Affine Cipher

Example 2.
Encrypt the message OUR with a keyword FLPR and a key (5, 3).Solution.
(i)
Step 1: draw the graphG=Pn∘C4, where n is equal to the number of letters of the message to be encrypted. Since the message to be encrypted has three letters, we have a graph G=P3∘C4, as shown in Figure 3.(ii)
Step 2: write each letter of the original message inside the nodes ofPn and each four-letter keyword inside the nodes of C4 (see Figure 4).
See Table6.Figure 3
The graphG=P3∘C4.Figure 4
The graphG=P3∘C4 with its corresponding letters.(iii)
Step 3: peplace the letters with their equivalent numerical values (see Figure5).Figure 5
A graphG=P3∘C4 with its equivalent numerical values.(iv)
Step 4: locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation:(6)LMOCDS≡cM+dmod8n.The agreed key (c,d) is (5, 3), the M is 14, 025, and n is 3. Thus,(7)LMOCDS≡514,025+3mod83=496,implying that the desired minimum outer-convex dominating set is on the496th location. Using the table in Section 2.2, the 496th MOCDS is H,G,A, that is, 5,17,17,5,5,11.(v)
Step 5: encrypt the message using the affine transformation,C≡aP+bmod26, and replace the resulting number with its corresponding letter presented on the encoded Table 5.Table 6
Solution on the evaluated affine transformation,C≡aP+bmod26.
PlaintextOUR142017C≡aP+bmod26C≡514+17mod26C≡1720+5mod26C≡517+11mod269718CiphertextJHSExample 3.
Decrypt the message JHS with a keyword FLPR and a key (5, 3).Solution.
(i)
Step 1: locate and determine the minimum outer-convex dominating set (MOCDS) by using the congruence equation(8)LMOCDS≡cM+dmod8n.Sincec=5,d=3,n=3, and M=14,025, it follows that(9)LMOCDS≡514,025+3mod64=496.This implies that the desired minimum outer-convex dominating set is on the496th location. Using the table in Section 2.2, the 496th MOCDS is H,G,A, that is, 5,17,17,5,5,11.(ii)
Step 2: decrypt the message using the affine transformation:(10)P≡a¯C−bmod26,and replace the resulting number with its corresponding letter, see Table 7.Table 7
Solution on the evaluated affine transformation,P≡a¯C−bmod26.
CiphertextJHS9718P≡a¯C−bmod26P≡5¯9−17mod26P≡17¯7−5mod26P≡5¯18−11mod26P≡219−17mod26P≡237−5mod26P≡2118−11mod26142017PlaintextOUR


## 3.2. Security Analysis

(1)
The frequency analysis is not possible to perform in this algorithm because the characters are encrypted as one to many. That is, a single character is mapped to many characters while performing encryption.(2)
Kasiski Test fails because the key in this algorithm is not repeating, i.e., the key is based on the locator of the minimum outer-convex dominating set.


## 4. Conclusions

In this proposed encryption, graph properties are used, specifically, the properties of minimum outer-convex dominating set for encryption. The adversary’s knowledge on the affine transformation alone does not guarantee breaking the code. Utilizing the property of outer-convex dominating sets in the corona of two graphs makes it possible for every letter to have its corresponding key. It is shown that the total number of combinations of minimum outer-convex dominating sets is8n, where n is the size of the message. These features of the proposed method of encryption increase the difficulty of unauthorized parties to gain access to the intelligible message. The proposed algorithm overcomes the existing drawbacks of the classical affine encryption scheme, thus promoting a more secure information and communication. This study paved a way to new research on applying and evaluating different domination parameters as tool for a more secured encryption algorithm.



---

*Source: 8316454-2020-10-26.xml*