Block cipher construction using minimum spanning tree from graph theory and its application with image encryption

In modern cryptography, Substitution Boxes (S-boxes) are critical in introducing confusion into ciphertext, significantly enhancing encryption security. With the rising sophistication of hacking techniques, there is a growing need to develop stronger and more dynamic S-boxes. This paper proposes a novel method for constructing cryptographically secure S-boxes using graph theory, specifically based on the Minimum Spanning Tree (MST) of cycle graphs. The process begins by converting plaintext into vertices, forming a cycle graph. Special characters are incorporated, and ASCII-based values are assigned to vertices. The distance between vertices is calculated using their intersections, leading to the creation of an MST graph. The final step involves obtaining the adjacency matrix, which is further processed to generate the S-box. The S-box's unpredictability is enhanced by employing the S₂₅₆ permutation from the symmetric group. Various cryptographic tests are conducted to evaluate the proposed S-box's performance, with results demonstrating its robustness when compared to existing S-box designs. Furthermore, this S-box is applied to an image encryption scheme, and its efficacy is thoroughly assessed. The findings highlight the potential of the proposed method to contribute significantly to cryptographic security.