Graph-Based Cryptographic Key Generation for Secure Text Encryption

The aim of this study is to use a new text encryption technique that provides two-stage secure communication. This encryption technique also aims to reveal the relationship between graph theory and cryptography. In this article, the spanning-tree graph, which is a subgraph of an undirected graph used in graph theory and includes all the vertices of the graph G, will be used. The first phase employs a mono-alphabetic substitution cipher, utilizing predefined character-swapping arrangements between authorized individuals along with an alphabetical encryption table. The next step strengthens security by supporting graph theory for key generation. Specially, the Kruskal algorithm was used to compute the minimum spanning-tree, which enables the creation of an encrypted text with a shared key that is derived from the graph structures. When adjacency matrices, spanning trees, and graph-isomorphism were used, the proposed method strengthened cryptographic security while maintaining effective use of computational resources. The security analysis shows that it is resilient against common cryptographic attacks. This makes it a promising alternative for secure communication and text encryption.