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

Abstract

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.

Introduction

In recent years, the popularity of computers and their network connections has grown significantly. It goes without saying that since military communications gather an astounding amount of sensitive information, ensuring access control, confidentiality, and authentication in all defense communications is essential. This led to the realization of the need for authentication and the importance of protecting data and systems from network intrusions; as a result, research on cryptography and other security-related topics is currently happening. The importance of cryptography has grown and changed over time, therefore even a slight increase in the performance efficiency of the cryptographic algorithms is prized.

The main objective of data security is to provide safe data transit via erratic networks. In the context of contemporary digital communications, data security is a complex issue with numerous facets. Data security, which comprises robust data encryption techniques, secure communication protocols, and trustworthy third parties to maintain database security, is the primary subject of this research study. The sciences, in conjunction with graph theory, produce incomprehensible data that requires the use of cryptography to decipher for the intended recipient. By using encryption, change our data into cipher text or another unreadable format. Encryption and decryption are mutually exclusive processes. Therefore, in order to improve data security, effective encryption/decryption techniques must be implemented. The only established technique for preserving data security is encryption. The information might be accessed by an unauthorized person with malicious intent.

Network security and data transfer across wireless networks are achieved through the use of cryptography. The core idea behind safe data transfer on erratic networks is data security. In today’s world of data communications, data security encompasses a wide range of tasks, such as reliable third-party database maintenance, powerful data encryption methods, and secure communication connections. The safe transfer of sensitive (secretive) data is receiving a lot of attention due to the quick advancement and development of information technology. In network security, the neighboring matrix is essential for transmitting the secure keys.

The importance of cryptography has witnessed an immense increase lately, especially for secure sensitive information in the military communication system. In recent research studies, most studies have been toward cryptographic algorithms to achieve better performance and security. The scope of encryption methods-related study should be appreciated from these research studies. For instance, cross-channel color image encryption with a 2D hyperchaotic hybrid map distinctly delivered robust encryption capacities in multimedia applications. In return, such chaotic systems again apply successfully in complex encryption tasks. ³⁴ Cross-channel color image encryption through a 2D hyperchaotic hybrid map of optimization test functions). Another is PSO which is recently used in image encryption. Modular integrated logistic exponential maps are used to enhance security and efficiency in this sense. In the use of a PSO-based image encryption scheme using a modular integrated logistic exponential map, very minimal cryptanalytic attacks were noted. Further, the newly proposed fractional-order 3D Lorenz chaotic systems and 2D discrete polynomial hyper-chaotic maps have demonstrated promising results in multi-image encryption applications for high performance. Exploiting newly designed fractional-order 3D Lorenz chaotic system and 2D discrete polynomial hyperchaotic map for high-performance multi-image encryption. ³⁵

These studies reflect an area that has gained much interest in the intersection of modern cryptography and optimization methods with chaos theory, offering diverse means of improving the efficiency as well as security of encryption methods. Our work aims at integrating these approaches for developing cryptographic systems secure from intrusions. Some of the focus points are of significant importance: S-box designs prove to be crucial in data protection against intrusions into the network.

A novel approach to building durable S-boxes via linear transformation was put forth in. ²⁰ This approach improves the output S-box using the permutation process. The authors additionally create DNA-based cryptographic ciphers and durable S-boxes by following the procedures described in.^21–26 Wang et al. ²⁷ proposed a genetic algorithm and chaos-based strategy for S-box construction after redefining the problem as a traveling salesman problem. Qin et al. ²⁸ applied the algorithm from artificial bee colonies to the design of S-boxes. Wang et al. ²⁹ proposed a strategy for S-box design that combines chaos with optimization of improved nonlinearity. Tian and Lu ³⁰ developed a method for constructing S-boxes by integrating an interwoven logistic map with bacterial foraging optimization. Farah et al. ³¹ provided a method for creating S-boxes. Using a chaotic map and a teaching-learning optimization strategy,

Cryptanalysis of image encryption focuses on the strengths and weaknesses of image encryption algorithms. Cryptanalysis involves discovering weaknesses that may be exploited to break or reduce the security associated with these algorithms. In recent years, several image encryption methods that have their foundation based on quantum chaotic maps and DNA coding used randomness in conjunction with biological-inspired operations to achieve even better security.

For example, cryptanalyses on chaotic map algorithms usually look at the sensitivity to initial conditions and randomness properties of such maps. However, at times an attacker might use flaws in generating keys or odd behavior from chaotic maps for their advantage, so it is necessary to study this kind of cryptanalysis and ensure that the encryption is not easily reversible.

Image encryption cryptanalyses are also conducted to find the vulnerability using differential attacks, chosen-plaintext attacks, and brute force methods among others. Besides, it allows the decryption of such images using an encryption key, and an encrypted image such as this may expose vulnerabilities in an encryption scheme. The vulnerabilities help researchers enhance their algorithms in such a way that they become less vulnerable to attacks and improve data security in general. When it comes to image encryption cryptanalysis, it forms a major activity that helps researchers find the weaknesses in an encryption system and helps enhance cryptographic methods to protect digital images from potential threats. Khan et al. ³² outlined a systematic approach to S-box creation by integrating chaos with optimization of improving differential approximation probability. After studying chaotic maps and artificial bee colony optimization, Ahmad et al. ³³ came up with a plan to construct S-boxes. An innovative method for post-processing to enhance the nonlinearity property in replacement boxes in Ref. ³⁶ . But, the cryptographic features of AES S-boxes differ from those of S-boxes built using these methods.

Increased Need for Cryptography: in this direction, the growing use of digital communications, especially in military systems, has pointed out the necessity for cryptographic techniques to ensure data security, confidentiality, and authentication.

Focus on Encryption for Data Security: Encryption is going to be a vital approach toward securing sensitive data mainly when transmitted across erratic networks. These effective encryption/decryption methods ensure that data security is not compromised by any unauthorized access.

S-box Design for Enhanced Security: The work introduces novel and innovative techniques to design S-boxes using the principles of linear transformation, chaos theory, and optimization methodologies. Such designs result in more robust encryption against network intrusion attempts.

Advancements in Cryptanalysis of Image Encryption: The role focuses on cryptanalysis, which is a crucial aspect for the exploitation of weaknesses in image encryption schemes. It also improves the cryptosystem because it makes it increasingly difficult to attack in differential mode as well as with key-recovery techniques.

In the “Definitions” section, some basic Definitions are discussed. The proposed algorithm and the algebraic structure underlying the suggested work for S-box generation are intended to be provided in the “Proposed Algorithm” section. The proposed S-box’s security analysis component is explained in the “Security Analysis” section along with a comparative examination of other S-boxes. Section “Majority logic criterion” of this paper focuses on implementing the suggested work using picture data and doing various tests. “Conclusion” section describes the conclusion of our work and its limits.

Definitions

Cryptography: This is the process of converting a normal communication into unintelligible cipher text and back again.

Plaintext: is the term used in cryptography to describe the original, readable form of a message or basic text that needs to be encrypted to become unreadable.

Cipher-text: The message that is changed in cryptography after a key is applied to plain text.

Key: A variable that can be used with an algorithm to create encrypted text or decrypt encrypted text. Some unintelligible cipher text, known only to the sender and the recipient, is called a key.

Encryption and Decryption: Encoding a communication with a key or other technique to make its meaning difficult to decipher is known as encryption and decryption. Decryption is the encryption technique’s opposite procedure, which turns cipher text back into ordinary language.

Adjacency matrix

This represents the graph in a matrix. Processors that use computers use it.

Several matrix algebraic results may be voluntarily used to the study of graph structural properties, which is an advantage of adopting an adjacency matrix format.

The vertices that are next to each other are specified in an adjacency list, which depicts a graph with a single edge. Choosing an ordering for the vertices is the foundation of this matrix.

It is possible to depict directed and undirected graphs with this matrix.

Incidence matrix

The $n\times m$ matrix $(b_{ij})$ represents the incidence matrix G. The values n and m denote the number of vertices and edges, respectively. In this case, matrix $b_{ij}$ equals 1 if vertex $v_i$ and edge $e_j$ are incident and 0 otherwise.

Proposed Algorithm

Convert text into vertex.

Give value to each vertex according to ASCII Table. Join each vertex to make a cycle graph.

Calculate edge weight using the distance formula.

Add a Special character (@) and find the minimum spanning tree of the cycle graph. Also, find the edge weight of the special character in the same way.

Make an adjacency matrix of the data.

Convert Diagonal Entries to x and apply summation on the matrix.

Invert the summation and solve it under modulo 257 for the domain values 0 to 255.

Construction of S-Box

Let the text be “WATER” and convert all text into vertices. Add the vertices with each other which gives us the Cycle Graph and gives the Weight According to ASCII Table 1. Find out the Edge weight by using the ASCII distance Formula for two consecutive vertexes shown in Figures 1–4, respectively.

Figure 1.

Convert text into vertices.

Figure 2.

Join of vertex to make cycle graph.

Figure 3.

Edge weight with cycle graph.

Figure 4.

Special character with minimum spanning tree.

Table 1.

ASCII (encoding) table.

Character	@	A	B	C	…	I	J	K	L	…	X	Y	Z
Decimal value	64	65	66	67	…	73	74	75	76	…	88	89	90

Add Special Character (@) and find its edge weight with connected Vertex. Find out the minimum spanning tree of a given graph that is produced and shown in Figure 4.

Now make the adjacency matrix by using edge weight

$$M=\left[\begin{array}{c}0230000\\ 230-22000\\ 0-2201900\\ 00190-150\\ 000-15013\\ 0000130\end{array}\right]$$

Replace diagonal entries with x

$$M=\left[\begin{array}{c}x230000\\ 23x-22000\\ 0-22x1900\\ 0019x-150\\ 000-15x13\\ 000013x\end{array}\right]$$

Find out the summation of the matrix, invert the summation, and solve $(i)$ under modulo 257 for all the values of x 0 to 255. Input 108 gives 256 which is not in range so it can be replaced with 0 and input 251 gives infinity so it is replaced with the missing element which is 60 which completes the initial S-Box entries shown in Table 2.

$$f(x)=\sum {\displaystyle \frac{1}{6x+36}mod257(i)}$$

Table 2.

Initial S-box.

50	153	166	119	30	74	25	201	205	20	83	63	188	124	15	51
37	203	141	12	229	211	231	161	10	76	170	196	160	82	94	22
62	67	136	70	154	1	147	178	230	72	199	132	36	179	228	223
66	151	3	176	139	215	250	113	158	255	117	123	213	93	122	105
192	92	233	108	155	9	131	217	112	109	19	208	137	57	171	86
200	120	49	238	148	145	40	126	6	21	243	59	234	169	244	127
209	53	5	224	38	17	85	143	98	39	80	239	41	73	47	71
11	4	31	84	162	212	68	156	35	16	77	64	129	225	202	90
89	249	115	111	248	102	149	24	165	65	152	135	164	44	134	140
2	99	144	7	42	118	81	254	106	191	34	29	78	221	146	142
8	168	167	55	32	128	193	180	241	222	101	189	45	95	173	226
253	246	186	210	184	216	18	177	218	159	114	172	240	219	33	252
204	48	130	13	88	23	198	14	236	251	125	58	185	27	79	110
0	103	187	121	190	195	235	163	175	97	61	87	181	247	96	26
46	28	245	116	54	220	206	242	133	69	194	174	237	52	56	232
183	227	138	91	104	207	197	182	157	107	214	60	43	150	100	75

To create a highly nonlinear substitution box (S-Box), apply a symmetric permutation of 256 on the initial S-Box table. This resulted in Table 3, which exhibits greater security than the existing AES substitution boxes. Our proposed S-Box achieves an average nonlinearity value of 113, making it significantly more secure. The safety and robustness of the proposed S-Box have been validated through various cryptographic analyses. Additionally, we employed this S-Box in an image encryption application, demonstrating its practical effectiveness in enhancing security.

Table 3.

Proposed S-box.

187	61	78	3	85	48	12	216	185	18	101	253	248	233	103	157
70	140	230	63	100	174	105	207	217	74	20	81	143	235	152	10
56	237	255	59	246	151	218	24	154	228	28	26	39	214	52	128
79	247	17	93	198	136	232	94	33	126	242	222	170	77	112	195
219	192	66	113	62	51	199	32	90	29	35	175	135	171	183	36
250	8	161	122	238	125	189	165	208	116	164	188	141	163	46	215
220	200	88	145	197	44	110	92	229	21	236	179	55	96	206	42
99	60	72	47	186	252	0	226	147	176	231	244	169	43	13	118
251	76	180	239	123	53	166	84	225	37	177	133	137	130	2	83
240	109	204	191	160	49	196	68	16	212	213	65	162	124	108	211
38	203	223	111	149	40	98	54	69	87	30	178	227	25	5	150
224	107	75	159	7	132	155	182	4	41	64	9	104	146	148	73
129	134	210	15	172	201	142	119	245	193	138	14	243	50	80	57
205	241	202	95	34	23	27	91	89	115	153	144	249	45	1	184
168	167	58	31	86	22	121	194	158	114	117	127	67	234	156	190
181	131	102	221	106	173	11	71	139	209	254	82	120	19	97	6

Symmetric permutation 256

(1,206,215,30,252,114,185,39,121,75,254,176,120,239,33,69,183,10,27,61,155,213,240,55,81,98,134,243,203,86,100,177,12,20,7,174,212,231,111,116,136,40,172,87,166,48,163,226,43,71,242,173,222,50,38,223,110,192,118,154,148,181,224,44,182,8,198,214,64,23,123,62,52,122,153,245,189,145,143,194,6,26,130,221,241,79,78,208,103,5,171,11,144,18,162,225,95,124,187,234,169,210,15,196,127,211)(2219)(3,135,165,72,25,32,230,97,250,178,37,41,19,93,238,47,42,115,228,90,106,45,80,229,168,131,218,255,21,105,167,202,129,217,76,89,256,179,115,157)(4,200,204,227,201,107,207,49,67,14,158,244,216,94,125,193,147,220,170,60,133,13,92,36,17,138,156,74,146,113,247,101,161,82,253,126,137,88,58,35,54,96,236,22,160,199,53,249,16,70,188,197,99,175,246,24,283,150,128,73,63,84,85,191,57,233,140,77,141,91,205,9,209,119,152,251,46,108,132,164,109,186,180,195,142,102,51)(28,151)(29,149,112,248,184,139,31,56,68,159,191,65,66,104)(34,237)(59,235,232)

Security Analysis

Strict Avalanche Criterion

According to the rigorous strict avalanche criterion (SAC), if you change an input, it will affect the output. This metric is a combination of the avalanche effect and completeness. The avalanche effect states that half of the bits in the cipher text should be affected by a one-bit change in the plaintext (see Table 4). If you want your output to be full, every bit of the plaintext has to go into it. By analyzing the cipher text, a cryptanalysis specialist can determine the key using a known plaintext attack, as long as they modify only a little piece of the plaintext. This is possible because of the relationship between input and output.

Table 4.

Strict avalanche criterion.

0.5156	0.5312	0.5156	0.5156	0.4688	0.5	0.4688	0.4531
0.4844	0.5156	0.5156	0.5312	0.5156	0.5	0.4844	0.5156
0.5156	0.5	0.4219	0.5	0.4688	0.4531	0.4531	0.5312
0.4688	0.5	0.5312	0.4844	0.5156	0.4531	0.5156	0.5156
0.5	0.5469	0.5312	0.4844	0.5469	0.4688	0.4844	0.5
0.4688	0.4844	0.4688	0.4688	0.4688	0.5312	0.5781	0.5156
0.5	0.5312	0.5156	0.5469	0.4531	0.4688	0.5625	0.5
0.5312	0.5625	0.5625	0.5156	0.5	0.5625	0.4844	0.5156

The SAC is an essential component of any cryptography S-box. This S-box can pass the rigorous avalanche tests if it meets the completeness and avalanche requirements. By changing the $n^{th}$ bit of x (the input value to the S function), we can find the likelihood that the $n^{th}$ bit of y that the S function returns is close to $\frac{1}{2}$ .

Bit independent criterion

When one input bit changes, this test finds the correlation between each pair of output bits (as suggested by. ³⁷ This test yields a $n\times n$ symmetric matrix devoid of the diagonal. The row-wise matrix element in rows i and j shows the interdependence of the S-box output bits i and $j$ . The formula can be used to obtain the BIC of a $n\times n$ S-box, denoted as S.

$$BI{C}_{l,m}(S)={\displaystyle \frac{1}{n\times 2^n}\sum _{i=1}^n\mathrm{\#}\{x\in B_n|V_{i,l}(x)=V_{i,m}(x)\}(ii)}$$

The S-box meets the BIC condition if the $BI{C}_{l,m}(S)\cong 0.5,{\mathrm{\forall }}_{l,m}\in \{1,\dots ,n\},andl\ne m$ shows that the output bits are pairwise uncorrelated. The output bit dependence matrix for an example S-box generated by the recommended method is shown in Tables 5 and 6. The absolute offset $|BI{C}_{l,m}(S)-0.5|\le 0.0176$ indicates that the output bits are pairwise uncorrelated.

Table 5.

BIC-SAC.

0	0.4883	0.5117	0.4922	0.4961	0.502	0.4961	0.5059
0.4883	0	0.4902	0.502	0.4707	0.5039	0.5078	0.5176
0.5117	0.4902	0	0.5117	0.4883	0.5039	0.5098	0.4844
0.4922	0.502	0.5117	0	0.498	0.5137	0.5215	0.5156
0.4961	0.4707	0.4883	0.498	0	0.4902	0.459	0.5293
0.502	0.5039	0.5039	0.5137	0.4902	0	0.4941	0.4961
0.4961	0.5078	0.5098	0.5215	0.459	0.4941	0	0.5039
0.5059	0.5176	0.4844	0.5156	0.5293	0.4961	0.5039	0

Table 6.

BIC NL.

0	104	102	106	104	102	106	104
104	0	104	102	106	102	102	98
102	104	0	108	106	108	104	102
106	102	108	0	106	106	104	108
104	106	106	106	0	104	104	106
102	102	108	106	104	0	106	102
106	102	104	104	104	106	0	102
104	98	102	108	106	102	102	0

Linear approximation probability

A measure of the S-box’s fortitude or resistance to linear assaults is the linear approximation probability (LAP) criterion. The S-box’s security strength increases as the LAP value decreases. The resulting S-box’s LAP, which is 0.1484, is less than that of.^2–13 This illustrates that the proposed technique has the capacity to produce a robust, effective, and attack-resistant S-box.

Differential uniformity

The differential probability (DP) or equiprobable input/output XOR distribution of a particular S-box can be found using the formula.

$$D{P}_f=\left({\displaystyle \frac{\mathrm{\#}\{\alpha \in A\wedge f(\alpha )\oplus f(\alpha \oplus \mathrm{\Delta }\alpha )=\mathrm{\Delta }z}{2^k}}\right)(iii)$$

where delta denotes the set of all possible input values and $2^k$ represents the total number of its elements. Bihan and Shamir introduced the idea of an equiprobable input/output XOR distribution in, ¹ which makes use of imbalances in the input and output (Table 7).

Table 7.

Input/output XOR distribution table.

8	8	6	6	6	6	8	8	8	6	6	6	6	8	8	6
6	8	6	6	6	6	6	6	8	6	8	6	6	6	6	6
6	8	6	6	6	6	6	6	6	6	8	6	8	8	4	6
6	6	8	6	6	8	6	8	6	6	6	8	6	6	6	6
8	6	6	6	6	6	4	8	6	6	6	6	6	8	6	6
6	8	8	6	6	6	8	6	8	6	6	6	6	6	6	8
6	8	8	6	8	6	6	6	6	6	6	8	8	6	6	6
4	6	6	8	6	8	8	8	6	6	6	6	8	6	6	8
8	8	6	6	6	6	8	6	6	6	8	6	6	6	6	6
8	6	6	6	8	6	6	8	6	6	6	6	6	8	6	6
8	6	8	6	6	4	8	8	6	6	6	6	6	8	8	8
6	6	8	6	6	8	8	6	6	6	6	6	8	8	8	6
6	6	6	6	6	6	8	8	6	6	8	8	8	6	6	8
6	6	6	8	8	6	6	6	8	6	6	8	8	8	8	8
6	8	6	6	8	4	8	6	6	6	6	6	6	4	6	8
6	6	8	6	6	6	8	8	8	8	8	6	8	8	6	0

The suggested S-box is resistant to differential attacks since the anticipated S-box’s DP is 0.03137. Table 8 offers the differential approach table for the suggested S-box and the DP for different S-boxes. These tables corroborate the claim that the proposed S-box outperforms several other options

Table 8.

A comparison of BIC-NL, BIC-SAC, SAC and DP values of S-boxes.

S-boxes	BIC-SAC	SAC	BIC-NL	DP
Specimen S-box	0.5001	0.5034	104.21	0.031
Ref. [2]	0.5023	0.4976	100	0.039
Ref. [3]	0.4983	0.4995	98	0.039
Ref. [4]	0.5020	0.5073	100	0.039
Ref. [5]	0.4951	0.5034	100	0.039
Ref. [6]	0.5022	0.4076	98	0.039
Ref. [7]	0.5065	0.5066	96	0.0469
Ref. [8]	0.4967	0.4812	96	0.0625
Ref. [9]	0.5034	0.4971	96	0.039
Ref. [10]	0.4988	0.4946	96	0.039
Ref. [11]	0.4957	0.4941	98	0.039
Ref. [12]	0.4980	0.5034	98	0.0469
Ref. [13]	0.507	0.503	100	0.039

Majority logic criterion

It is helpful to assess an S-box’s eligibility for usage in an encryption process by applying the majority logic criteria (MLC). Five analyses are used to determine the degree of randomness in the encoded picture: energy, entropy, homogeneity, contrast, and correlation.

The characteristics of the encoded image are recognized through the use of homogeneity and energy. The degree of similarity between the host and encrypted image is evaluated by the correlation test. A lower correlation coefficient suggests that encryption is causing more distortion. The plaintext image’s decreasing brightness is evaluated using contrast. The encryption process is more effective the higher the contrast value. The plaintext is distorted during the encryption process, and statistical characteristics describe the S-box’s resilience.

This S-box is then used to encrypt digital photos. To conduct MLC, four $256\times 256$ JPEG photographs of the cameraman, pepper, and monkey are selected.

The proposed S-box is employed in two substitution steps in the encryption process. Two phases are involved in the S-box replacement process to achieve encryption. During the first stage, the substitution is done backward after moving forward from the starting pixel to the last pixel. Every simulation was executed using MATLAB programming. The original and encrypted photographs are shown in Figure 5. The matched undistorted photographs and the distorted images differ significantly. There is a great deal of visual content, but there isn’t any structure that would induce security lapses from the host image. The results of every MLC test that was done are displayed in Table 9. The correlation coefficients for images that were calculated are shown in Table 9.

Figure 5.

Image encryption.

Table 9.

Comparison table with different s-boxes image encryption results.

S-boxes	Entropy	Contrast	Correlation	Energy	Homogeneity
Cameraman
Proposed S-box	7.9970	8.2919	0.0407	0.0174	0.4207
Ref. [14]	7.9812	8.3154	−0.0045	0.0177	0.4091
Ref. [15]	7.9431	8.2113	0.0155	0.0219	0.4248
Ref. [16]	7.9591	8.2314	−0.0441	0.0202	0.4151
Pepper
Proposed S-box	7.9971	8.6817	−0.0146	0.0174	0.4042
Ref. [14]	7.9824	8.7348	−0.0043	0.0172	0.4074
Ref. [15]	7.9233	8.1423	−0.0112	0.0286	0.4648
Ref. [16]	7.9562	8.3129	0.0103	0.0180	0.4219
Baboon
Proposed S-box	7.9967	8.5184	0.0035	0.0174	0.4093
Ref. [17]	7.9970	10.4087	0.0053	0.0157	0.3813
Ref. [18]	7.9974	10.3977	0.0032	0.0157	0.3839
Ref. [19]	7.9971	10.5391	0.0020	0.0157	0.3833

The findings show that the created replacement box is suitable for encryption and sufficient for use in systems meant to ensure the dependability and security of sensitive data.

Peak signal-to-noise ratio

A metric called PSNR (peak signal-to-noise ratio) is used to compare the quality of an original image or video to one that has been rebuilt or compressed. Higher values denote higher quality. It is commonly used in image processing to assess the integrity of compressed images. Decibels (dB) are used to express the PSNR.

Formula:

$$PSNR=10\cdot {\log }_{10}\left({\displaystyle \frac{MA{X}^2}{MSE}}\right)PSNR=10\cdot {\log }_{10}\left({\displaystyle \frac{MA{X}^2}{MSE}}\right)$$

where

MAX is the maximum possible pixel value of the image (typically 255 for 8-bit images).

MSE (mean squared error) is the average squared difference between pixel values of the original and compressed image.

Results:

Cameraman Image (PSNR = 8.35 dB):

This PSNR value suggests the quality of the compressed or reconstructed image is quite poor, with noticeable differences compared to the original image.

Paper Image (PSNR = 7.94 dB):

• A PSNR of 7.94 dB is even lower, implying that the paper image reconstruction or compression resulted in heavy loss of information or increased noise.

Baboon Image (PSNR = 8.30 dB):

• Similarly, a PSNR of 8.30 dB for the baboon image also indicates significant distortion or noise in the processed image.

Requirements for performing image encryption

Hardware Configuration:

Intel i5, 4th Generation PC includes RAM size 12 GB and ROM size 128 GB SSD.

Software Configuration:

Windows 10.

Specify the version of MATLAB R2007b and some results found through Python Programs.

Benchmark Image Datasets:

Only one image in each dataset and their characteristics (e.g. $256\times 256$ , grayscale).

Conclusion

This work has focused on the development of a symmetric permutation approach for constructing S-boxes, leveraging the least spanning tree of the Cycle graph over a finite field of order 257. A key challenge in cryptography is improving the strength and efficiency of S-boxes, which are critical for secure encryption. By introducing an asymmetric permutation applied to the initial S-box, we address this issue and significantly enhance the performance and durability of the S-box, ensuring a more robust encryption process. The proposed method outperforms advanced S-box construction algorithms, achieving better results in terms of mean nonlinearity score, LP, SAC, and BIC scores. Evaluation of the S-box on specific plaintext images demonstrates its superior performance in secure encryption. The integration of symmetric permutation and minimum spanning tree significantly improves the encryption process by creating stronger, more efficient S-boxes. The comparative analysis confirms that the new S-box design excels in resisting cryptographic attacks through improved statistical measures. While the method shows promising results for certain types of plaintext images, its performance on other image types and larger datasets requires further exploration. The current study is limited to the application of the proposed S-box in specific encryption scenarios, lacking extensive real-world testing.