A Novel Cryptosystem Using Multipartite Graphs

Abstract

Graph theory has a special role in mathematics, both in the abstract and in the applied sense.Therefore, over the years it has attracted mathematicians in diverse disciplines with wide range of applications such as in Computer Science, Engineering, Biology, etc. One such area of application is the use of Graph theoretic concepts in implementing Cryptography algorithms. The introduction of the notion of a graph dated back to 1736 when Leonhard Euler answered the famous Königsberg Bridge Problem in the negative. A graph �� is a union of finite non-empty set of elements called vertices ��(��)and a set of unordered pair of elements of ��(��) called edges,��(��). Cryptography is the art of securing information so that only the intended party received the information. The process of converting a given message (plaintext) to a secure form (ciphertext) is called encryption while the reverse process is called decryption. In the present study, we encrypt a given message into multipartite graphs to form the ciphertextusing the proposed encryption algorithm and it is converted into plaintext by using the decryption algorithm. As a future work, we are planning to introduce an encryption and decryption algorithm by using graph factorizations.