A symmetric cryptographic scheme using graceful labeling of alkane graphs

Abstract

Cryptography is the study and application of techniques for securing information. Cryptosystems are broadly classified as symmetric, which use the same key for both encryption and decryption, and asymmetric, which use a public-private key pair. The scheme used in this study is based on symmetric ciphers, in which a secret key is exchanged between the sender and the receiver for the encoding and decoding to take place. This proposed scheme is based on the graceful labeling of alkane graphs which are acyclic (tree-like) graphs derived from the chemical structure of saturated hydrocarbons (CnH2n+2). A graceful labeling assigns distinct integers to vertices so that each edge is labeled by the absolute difference of the numbers on its endpoints, with all edge labels required to be unique. This inherent uniqueness forms the foundation of the cryptosystem. In our scheme, we define a labeling function with parameters tied to the graph structure and then reduce all labels modulo 31 to ensure a consistent and balanced correspondence between vertices and edges. Then map them into a character set comprising the English lowercase alphabet and a few punctuation symbols. The encryption involves dividing the plaintext into four-character blocks, padding with underscores if necessary. Each character in a block is substituted using a column-based shifting mechanism derived from the labeled graph. The decryption inverts this mapping using the same graph structure and parameters, ensuring accurate recovery of the original message. The scheme successfully produced non-repetitive substitution patterns during testing, enabling accurate encryption and decryption and making it a practical option for securing information.