Volume 2, No. 12, August 2014 ISSN – 2278-1080 The International Journal of Computer Science & Applications (TIJCSA) RESEARCH PAPER Available Online at http://www.journalofcomputerscience.com/ Binary String as a Rigid Very Excellent Graph M. Yamuna SAS, VIT University Vellore, Tamilnadu, India [email protected] Abstract Binary string encryption is always an existing problem and various methods are devised. Graph theory is recently used in encryption. In this paper a method of encrypting a binary string as a graph is proposed using rigid very excellent graphs as the key for encryption. Keywords - Graph, Encryption, Encryption, Binary, Excellent. 1. Introduction Graph theory is slowly used in encryption methods due to its ease of representation in computers and numerous properties. Domination is one property of graph theory, which uses properties of vertices. Many encryption methods are proposed using domination properties. In [ 1 ] a method of encrypting text messages using unique dominating set is provided. In [ 2 ] adjacency matrices is used for encryption. Dominating sets are used in chemical representations also. In this paper we propose a method of encrypting binary string using rigid very excellent graphs is provided. 2. Materials and Methods Here we list some results on graph theory used in the article. 2. 1 Graph In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pair wise relations between objects. A "graph" in this context is made up of "vertices" or "nodes" and lines called edges that connect them. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another [ 3 ]. For results on graph theory we refer to [ 4 ]. 2.2 Dominating Set A set of vertices D in a graph G = ( V, E ) is a dominating set if every vertex of V – D is adjacent to some vertex of D. If D has the smallest possible cardinality of any dominating set of G, then D is called a minimum dominating set — abbreviated MDS. The cardinality of any MDS for G is called the domination number of G and it is denoted by γ ( G ). A γ - set © 2014, http://www.journalofcomputerscience.com - TIJCSA All Rights Reserved 11 M. Yamuna, The International Journal of Computer Science & Applications (TIJCSA) 2278-1080, Vol. 2 No. 12 August 2014 ISSN – denotes a dominating set for G with minimum cardinality. For information on dominating sets we refer to [ 4 ]. A graph G is said to be an excellent graph if every vertex in G is contained in some γ set. An Excellent Graph G is said to be very excellent, if there is a γ - set S of G such that to each vertex u∈V−S, there exist a vertex v ∈ S such that ( S − v ) ∪ { u } is a γ - set of G. A γ - set S of G satisfying this property is called a Very Excellent γ-set of G [ 6 ]. 2.3 Rigid Very Excellent Graphs Let G be a very excellent graph and D be a very excellent γ-set of G. To each u ∉ D, let E ( u , D ) = { v ∈ D | ( D – v ) ∪ { u } is a γ - set of G }. If | E ( u, D ) |= 1, for all u ∉ D, D is said to be a rigid very excellent γ - set of G. If G has at least one rigid very excellent γ set then G is said to be Rigid Very Excellent ( RVE ) [ 6 ]. Fig. 1 The graph in Fig. 1 represents a RVE graph. The encircled vertices represent a γ - set. Say D = { 2, 4 ). Vertices 1, 3 are interchangeable with 4 and vertex 5 with 2 ie., D – { 4 } ∪ { 1}, D – { 4 } ∪ { 3 }, D – { 2 } ∪ { 5 } are γ - sets for the graph. It is to be noted that vertices 1 and 3 cannot be interchanged with 2, vertex 5 cannot be interchanged with 4. In all the graphs encircled vertices represents a γ - set for G. 3. Proposed Encryption Scheme Let the binary string to be encrypted be of length k say S = {w1, w2,w3,…,wk}. We now choose a RVE graph so that γ ( G ) = k = say { v1, v2, v3,…, vk}, so that each vertex in γ( G ) is used for atleast one vertex exchange. Choose arbitrary ui such that D – {vi} ∪ { ui } is a γ set for G for all i = 1,2,…, k. Now we have picked the edges (vi, ui ), i = 1,2,…, k, ie., we have picked k edges. Assign the characters in the string as the edge weights. Now for the remaining edges, assign random weights ( weight 0, 1 ). We then send the weighted graph to the receiver. It need to be noted here that for each edge not in the set D, there is a vertex exchange in D. So, we need to assign weights ( 0, 1 ) for the edges (vi, ui). But for the edges ( vi, vi ) or ( ui, ui ) we can assign any weight including 0, 1. Let the binary string to be encrypted be S = {w1, w2,w3,…,w10} = { 1011011010 }. 3.1 Encryption Algorithm Step 1 Choose a RVE graph such that D = γ( G ) = k = { v1, v2, v3,…, vk}. © 2014, http://www.journalofcomputerscience.com - TIJCSA All Rights Reserved 12 M. Yamuna, The International Journal of Computer Science & Applications (TIJCSA) 2278-1080, Vol. 2 No. 12 August 2014 ISSN – For S we need to choose a graph G such that the graph is RVE and γ( G ) = 10 = | S |. The graph in Fig. 2 is a RVE graph. The encircled vertices forms a RVE γ - set for G ie., D = γ ( G ) = 10 = { v1, v2, v3,…, vk} = { 1, 2, 13, 14, 5, 6, 17, 18, 9, 10 }. Fig. 2 Step 2 Among the vertices that can be exchanged with each vi, i = 1,2,…, k choose k arbitrary vertices ui, i = 1,2,…, k. For the graph in Fig. 2, each vertex in D is used only once for vertex exchange. 11 with 1, 12 with 2, 3 with 13, 4 with 14, 15 with 5, 16 with 6, 7 with 17, 8 with 18, 19 with 9, 20 with 10. So { u1, u2,…, u10 } = { 11, 12, 3, 4, 15, 16, 7, 8, 19, 20 }. Step 3 Assign the weights of the edges ( vi, ui ), the weights wi, i = 1,2,…, k. For the graph in Fig. 2 ( vi, ui ) = { ( 1, 11 ), ( 2, 12 ), ( 13, 3 ), ( 14, 4 ), ( 5, 15 ), ( 6, 16 ), ( 17, 8 ), ( 18, 8 ), ( 9, 19 ) ( 10, 20 ) }. The weights to be assigned to these edges are {w1, w2,w3,…,w10} = { 1011011010 }. The resulting graph is as seen in Fig. 3. Fig. 3 Step 4 Assign random weights to the remaining edges. The resulting graph is as seen in Fig. 4. Fig. 5 It is to be noted that in the graph in Fig. 5 if necessary all the edges can receive binary weights also. This is because the edges that are to be assigned random weights are in the set ( vi, vi ). Step 5 Send the weighted graph to the receiver. © 2014, http://www.journalofcomputerscience.com - TIJCSA All Rights Reserved 13 M. Yamuna, The International Journal of Computer Science & Applications (TIJCSA) 2278-1080, Vol. 2 No. 12 August 2014 ISSN – In the above example we send the graph in Fig. 5 to the receiver. Decryption can be done by reversing the procedure. Suppose the received graph is Fig. 6 Suppose the γ - set is as seen in Fig. 7. Fig. 7 Here the γ - set D = { v1, v2 } = { 2, 4 }. The vertices exchangeable with 2 are 1, 3 and vertex 5 is exchangeable with 2. Now edge (4, 1 ) has received weight 10, while the edge ( 4, 3 ) has received weight 0. So { u1, u2 } = { 3, 5 }. So the received message is S = { w1, w2 } = { 00 }. 4. Conclusion A graph can have more than one RVE γ - set. Also more than one vertex can be exchanged with a vertex in the γ - set. So unless the specific dominating set is known, and the unique vertex it is used for exchanging is known, it is tough to guess the string. Also in some graphs, like the one on Fig. 2, all the edges in the graph can receive binary edge weights. This increases the safety of the encryption. Moreover numerous weighted graphs satisfying various properties are available in public domain, and it is not possible to find the difference between those graphs and the encrypted one. So we conclude that the proposed method is safe for encryption of any binary string. References © 2014, http://www.journalofcomputerscience.com - TIJCSA All Rights Reserved 14 M. Yamuna, The International Journal of Computer Science & Applications (TIJCSA) 2278-1080, Vol. 2 No. 12 August 2014 ISSN – [ 1 ] M. Yamuna, Khyati R. Vora, A. Ashwini, S. Elavarasi, Encryption Using Braille Alphabets and Graph Domination, The International Journal of Computer Science and Applications, Volume 2, No6, August – 2013 ( 22 – 42 ). [ 2 ] M. Yamuna, K. Karthika, Chemical Formula: Encryption Using Graph Domination and Molecular Biology, International Journal of Chem Tech Research, Vol. 5, No 6, Oct – Dec – 2013 ( 2747 – 2756 ). [ 3 ] http://en.wikipedia.org/wiki/Graph_theory [ 4 ] Narsingh Deo, Graph Theory and its Applications to Computer Science, Prentice Hall, India ( 2010 ). [ 5 ] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, ( 1998 ). [ 6 ] Very Excellent Graphs and Rigid Very Excellent Graphs, AKCE International Journal Of Graphs and Combinatorics, 4, No. 2 ( 2007 ), pp. 211 - 221. © 2014, http://www.journalofcomputerscience.com - TIJCSA All Rights Reserved 15