All the communications, whether it is social, business, or any other networking are done using digital technology. The world is getting more and more digitalized to make the life easy. The technology is compact in our hands and any work can be done with just a click. As everything is getting digitalized, it is the responsibility of the service provider, to make their system as safe and secure for their clients. Hence, updating security in a system becomes essential and a continuous process.

The coronavirus Covid-19 has affected almost all the countries and lakhs and lakhs of people got infected and millions of deaths have been reported globally. This pandemic forced the countries to shut down all their businesses. The governments are completely engaged in keeping the death rate of their countries under control. They are continuously motivating researchers to find vaccines for this virulent disease. The hackers have started using this unprecedented opportunity of chaos and panic to wield social, economic, and financial crises for their gain

The cryptography

Graph theory is a field having a lot of applications; any real-life problem is simplified using graphs and can be solved using graph theory properties and techniques. The flexibility of graph properties strengthens the cryptosystem. The graph structures play an important role in the encryption and decryption process. The literature survey given in

Any important secret document which has to be shared among people will be encrypted by a password. This encrypted document and the secret key to decrypt the document will be sent separately to the receiver. Mostly a single word is used as a password.

In this paper, a new cryptosystem using the amalgamation of paths, its double vertex graph and edge labelling has been proposed.

Graph theory

Alavi et al.

Comparing to the original graph, the distance between any two vertices is increased in its double vertex graph

In general, graphs can be represented in two ways namely adjacency list and adjacency matrix

The adjacency matrix

In this section, we first introduce an encryption algorithm based on a double vertex graph of a path. This path is constructed from the given password. An illustration is given for this encryption algorithm by considering a password. Then a decryption algorithm is introduced to decrypt the encrypted word. We use the encoding table

Alphabet |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |

Coding Number |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |

Alphabet |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z |

Coding Number |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |

The double vertex graph

Consider an edge

By the definition of double vertex graph, the corresponding edges in double vertex graph

Number of horizontal edges in

Number of vertical edges in

Therefore, the number of edges for

Hence the proof.

Let the first edge be labelled as,

The second edge to ^{rd} edges are labelled as

The ^{nd} edge is labelled as

The steps in the encryption algorithm using double vertex graph are as follows:

Convert the Plaintext to number string

Label the edges

Construct

Form an adjacency matrix

Extract the entries of

The encrypted message will be of the following form

Encrypted message

Suppose we want to send a message

The plaintext is “STRIKE”, which is a six-letter word. Therefore

In

By Theorem 3.1, each edge in

Consider the edge

Therefore, 45 =

Similarly, the weights of other edges in the path

46 = 10 + 8 + 6 + 5 + 17

44 = 9 + 7 + 6 + 5 + 17

35 = 7 + 6 + 5 + 4 + 13

37 = 8 + 6 + 5 + 4 + 14

31 = 7 + 5 + 4 + 3 + 12

(21, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 7, 0, 6, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 6, 0, 5, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 5, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 5, 0, 5, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0, 4, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 4, 0, 0, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 4, 0, 3, 4, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 3, 0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 12, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0)

Form a matrix using the encrypted message and name it as A

Construct a graph using A, which would be

Extract

Calculate

Convert the number string

In this study, a double vertex graph to encrypt a word was proposed. First, the given message was encoded using the encoding table. In the second step, the plain text was converted into a path graph. From this path graph, a double vertex graph was constructed. Then an adjacency matrix is formed from this double vertex graph. These four stages make the encryption stronger. Without the knowledge of graph theory, it is very difficult to hack and decrypt the encrypted word. This kind of cryptosystem is used to communicate single word like password securely. This study can be extended to encrypt a sentence. This work can also be extended to other big graph structure to make the password even more secure and strong.

The authors wish to thank the management of Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam 603 110 for their continuous support and encouragement for the research work.