Enhancement of Non-Permutation Binomial Power Functions to Construct Cryptographically Strong S-Boxes

Abstract

A Substitution box (S-box) is an important component used in symmetric key cryptosystems to satisfy Shannon’s property on confusion. As the only nonlinear operation, the S-box must be cryptographically strong to thwart any cryptanalysis tools on cryptosystems. Generally, the S-boxes can be constructed using any of the following approaches: the random search approach, heuristic/evolutionary approach or mathematical approach. However, the current S-box construction has some drawbacks, such as low cryptographic properties for the random search approach and the fact that it is hard to develop mathematical functions that can be used to construct a cryptographically strong S-box. In this paper, we explore the non-permutation function that was generated from the binomial operation of the power function to construct a cryptographically strong S-box. By adopting the method called the Redundancy Removal Algorithm, we propose some enhancement in the algorithm such that the desired result can be obtained. The analytical results of our experiment indicate that all criteria such as bijective, nonlinearity, differential uniformity, algebraic degree and linear approximation are found to hold in the obtained S-boxes. Our proposed S-box also surpassed several bijective S-boxes available in the literature in terms of cryptographic properties.

1. Introduction

At a fundamental level, Claude Shannon’s properties of confusion and diffusion [1] often made for bench marking the security of a symmetric encryption. Confusion is defined as the complexity of the relationship between secret-key and cipher-text while diffusion is defined as the degree of influence of single input bit changed in the resulting ciphertext. To realize the confusion and diffusion of a symmetric encryption, several layers of substitution and permutation operation, called Substitution-Permutation Networks (SPNs), are applied. The substitution layer is a nonlinear operation used to improve the overall confusion of the encryption. On the contrary, the permutation layer is a linear operation that increases the measure of diffusion.

In symmetric encryption, the substitution layer is typically referred to as Substitution box (S-box). An S-box plays a crucial role against various cryptanalysis. Therefore, an S-box needs to be cryptographically strong by at least having high nonlinearity, low differential uniformity, a high algebraic degree and complex algebraic expression to resist cryptanalysis, such as differential attack first introduced by Biham and Shamir [2], linear attack described by Matsui [3], higher order differential attacks that were introduced by Lai [4] and Knudsen [5], interpolation attacks introduced by Jakobsen and Knudsen [6] and, lastly, algebraic attack introduced by Courtois and Pieprzyk [7]. As a result, research to improve the cryptographic properties of an S-box and its implementation efficiency can be found in the literature. To date, most published constructions of an S-box are based on the bijective functions of elements of four or eight bits.

1.1. Problem Statement

Over the last 20 years, there has been great progress in the field of nonlinear power functions which serve as an S-box. The most successful and widely used technique is the one adopted by the Advanced Encryption Standard (AES) [8] that makes use of the multiplicative inverse function over a finite field ${\mathbb{F}}_{2^8}$. Often, the cryptographic properties exhibited by AES’s S-box become a benchmark for other researchers to construct their S-boxes. This is because AES S-box is conjectured as having optimal cryptographic properties [9] with respect to resistance against linear, differential and algebraic attacks.

Nonlinearity, which is one of the cryptographic properties of S-box, remains a great challenge for future research. Among the main considerations in constructing a new S-box is the following question: Are there more optimal cryptographic properties than the one achieved by AES’s S-box? In other words, this question exclusively relates to the nonlinearity property achieved by an AES S-box. Although there were many new constructions proposed in the last 20 years, the cryptographic properties achieved by AES S-box remain unbeatable. Therefore, we aim to further explore the construction of an S-box.

Our main interest is the construction of bijective S-boxes when n is even, (i.e., n = 8). Most of our research relates to the non-permutation of binomial power functions over ${\mathbb{F}}_{2^8}$. The design criteria of an S-box are affected by resistance against the main attacks on block ciphers [10], as mentioned earlier. All these attacks contribute to the countermeasures of cryptographically strong S-boxes.

1.2. Contribution

Generally, S-box construction can be categorized into three generic methods which are random search, heuristic method and mathematical function approaches. There also exist S-box constructions that combine all or several of these generic methods to produce their desired result. In this paper, we are more interested in exploring and enhancing the S-box construction from a non-permutation power function as previously proposed by Mamadolimov et al. [11] and subsequently improved by Isa et al. [12]. Their method starts with the binomial operation of power functions over a finite field to select the initial S-box. The main criteria in selecting the initial S-box are that the S-box must exhibit optimal cryptographic properties, except balancedness. Then, using a heuristic algorithm known as the Redundancy Removal Algorithm, the final result with the permutation function is produced.

We improve the method by examining the properties exhibits from binomial power functions in more detail. This includes the main cryptographic properties (i.e., NL, DU and AD) and its redundant elements, since composition of two power functions are prone to produce a non-permutation power function [13]. From there, several other steps such as elements exchange and elements rotation are conducted to produce final S-box with desired cryptographically strong properties. The final S-box that we obtained exhibits better cryptographic properties compared to S-box with the same construction proposed by Mamadolimov et al. [11] and Isa et al. [12].

1.3. Organisation

The rest of the paper is organized as follows. In the second section, we discuss the security requirements for an S-box and the available S-box design methods in the literature. In the third section, we present some preliminaries and our proposed S-box construction. Following this, in the fourth section, we provide a discussion and comparative analysis between our findings and the S-boxes available in the literature. We conclude our paper in last section.

2. Security Requirement and S-Box Design Methods

2.1. S-Box Properties

An S-box plays a crucial role in resisting cryptanalysis. A cryptographically strong S-box is classified based on its exhibited cryptographic properties. Moreover, an S-box must exhibit high nonlinearity, low differential uniformity, a high algebraic degree and complex algebraic expression to resist cryptanalysis, such as linear [3], differential [2], algebraic [7] and interpolation [6] attacks. Therefore, a lot of research is still in place to investigate and strengthen the cryptographic properties of each S-box proposed.

There is also much research conducted in designing and constructing an S-box. Typically, the measurement of cryptographically strong S-box properties depends on assumptions. To avoid more confusion in determining a cryptographically strong S-box, Carlet takes responsibility by facilitating and simplifying the desired properties in designing good S-boxes [14]. In particular, the desired properties suggested by Carlet [14] and later followed by Piret et al. [15], are bench-marked against AES’s S-box. This is because AES’s S-box is already conjectured as having the optimal cryptographic properties [9].

Therefore, based on the suggestions made in [14,15], we set the desired values for each of the S-box properties to be considered cryptographically strong, as summarized in

Table 1. Desired Value for Cryptographically Strong S-boxes.

Properties	Desired Value
High Nonlinearity	$100<\mathrm{NL}\le 120$
Low Differential Uniformity	$2\le \mathrm{DU}\le 6$
High Algebraic Degree	$4\le \mathrm{AD}\le 7$
Low Linear Approximation	$8\le \mathrm{LA}<28$
Algebraic Complexity	Complex
Fixed Opposite Fixed Points	None/Low
Balanced Output	Permutation

. The following subsections explain each property in detail.

Let $\mathbb{F}$ be a finite field with $\mathbf{2}$ elements, while ${\mathbb{F}}_{2^n}$ is a finite field with ${\mathbf{2}}^{\mathbf{n}}$ elements. An $\mathit{n}\times \mathit{n}$ S-box is a Boolean map:

$$F:{\mathbb{F}}_{2^n}\to {\mathbb{F}}_{2^n}=(f_1(x_1,\dots ,x_n),\dots ,f_n(x_1,\dots ,x_n))$$

where $f_1(x_1,\dots ,x_n)$ to $f_n(x_1,\dots ,x_n))$ are called as component functions of F.

2.1.1. Nonlinearity (NL)

Let $c=(c_1,c_2,\dots ,c_n)$ be a nonzero element in ${\mathbb{F}}_{2^n}$ and $c·F=c_1{f}_1+c_2{f}_2+\dots +c_n{f}_n$ be a linear combination of the coordinate Boolean functions $(f_1,f_2,\dots ,f_n)$ of F. The NL of an S-box, F, is the Hamming distance between the set of all affine functions over ${\mathbb{F}}_{2^n}$ and the set of all non-constant linear combinations of component functions of F, as defined below:

$$\mathrm{NL}\left(F\right)=\underset{c\in {\mathbb{F}}_{2^n},c\ne 0}{min}\mathrm{NL}(c·F)$$

Claude [14] suggested that the value of NL should be as close as possible to the best-known NL (i.e., $\mathrm{NL}\approx 112$) to thwart linear cryptanalysis [3]. In our study, we set the minimum threshold for NL as 100 (i.e., $\mathrm{NL}=100$).

2.1.2. Differential Uniformity (DU)

By excluding the trivial entry case (i.e., $a=b=0$) from the difference distribution table, the largest value present in the table can determine the value of DU. The value of DU is defined as follows:    

$$\mathrm{DU}\left(F\right)=\underset{a,b\in {\mathbb{F}}_{2^n},a\ne 0}{max}\left|\{x\in {\mathbb{F}}_{2^n}:F(x+a)+F\left(x\right)=b\}\right|$$

A smaller value of DU is preferable [14]. In our case, we determine that the value of DU must lie in the range of $2\le \mathrm{DU}\le 6$ to resist differential cryptanalysis [2].

2.1.3. Algebraic Degree (AD)

$deg\left(f\right)$ is denoted from the number of variables in the largest monomial for the component function f of an S-box. Therefore, the AD of an S-box is determined by the maximum degree of all component functions, as follows:

$$\mathrm{AD}\left(F\right)=max\{deg\left(f_1\right),deg\left(f_2\right),\dots ,deg\left(f_n\right)\}$$

The value of the AD of an S-box must be high [14] in order to resist higher order differential cryptanalysis [5]. In our study, we set $\mathrm{AD}\ge 4$.

2.1.4. Linear Approximation (LA)

The LA of an S-box is defined as follows:

$$\mathrm{LA}\left(F\right)=\underset{\alpha ,\beta \in {\mathbb{F}}_{2^n},\alpha \ne 0}{max}\{\#\{X\in {\mathbb{F}}_{2^n}|\alpha ·X=\beta ·f\left(X\right)\}-2^{n-1}\}$$

where $\alpha \in {\mathbb{F}}_{2^n}$, $\beta \in \{{\mathbb{F}}_{2^n}\backslash 0\}$ and $\alpha ·X$, $\beta ·f\left(X\right)$ are evaluated over ${\mathbb{F}}_2$. The operation $\alpha ·X$ denotes the inner product of vectors $\alpha$ and input X of the S-box. $\beta ·f\left(X\right)$ denotes the product of vectors $\beta$ and output $f\left(X\right)$ of the S-box.

By omitting the trivial case $\alpha =\beta =0$, the LA can be determined through the maximum entry in linear approximation table of the S-box. The lower value of LA is preferable in resistance against linear cryptanalysis [3]. Usually, the value of LA must be less than 28 (i.e., $\mathrm{LA}<28$).

2.1.5. Algebraic Complexity (AlC)

The Lagrange interpolation polynomial is the polynomial $P\left(x\right)$ of degree $\le (n-1)$ that passes through n points $(x_1,y_1=f\left(x_1\right)),(x_2,y_2=f\left(x_2\right)),\cdots ,(x_n,y_n=f\left(x_n\right))$ and is given by:

$$P\left(x\right)=\sum _{j=1}^n{P}_j\left(x\right),$$

where

$$P_j\left(x\right)=y_j\prod _{k=1,k\ne j}^n\frac{x-x_k}{x_j-x_k}$$

The number of terms in $P_j\left(x\right)$ determines whether an S-box has a simple or complex algebraic expression, thereby classifying whether the S-box has a low or high algebraic complexity. A complex AlC is needed to resist an interpolation attack [6] and other concerning algebraic attacks [7].

2.1.6. Fixed Points (Fp) and Opposite Fixed Points (OFp)

For an S-box, a fixed point is defined as $f\left(x\right)=x$. This mean if an input x is given, the output is also x. An opposite fixed point is defined as $f\left(x\right)=\overline{x}$, where $\overline{x}$ denotes the bit-wise complement of x. The number of $Fp$ and $OFp$ should be kept as low as possible to avoid any leakage in statistical cryptanalysis.

2.1.7. Balancedness

An n-variable Boolean function f is said to be balanced if $wt\left(f\right)=2^{n-1}$, where $wt\left(f\right)$ is the Hamming weight of f for the n-variable. An S-box is called balanced if every value in ${\mathbb{F}}_{2^n}$ occurs once. This implies that the function is bijective (also known as the permutation function).

2.2. S-Box Design Methods

In this section, we review several $8\times 8$ S-box constructions available in literature and classify them into three generic methods which are random generation, evolutionary or heuristic, and a mathematical function. In general, the classification of each S-box proposal is based on its construction. As an example, random methods that use a pseudo-random generator to generate a key and/or select a key randomly from its construction elements are categorized as a random generation approach. Likewise, using mathematical functions as the core of S-box construction will be categorized as a mathematical function approach. The S-box constructions that use neither a random generator nor mathematical function can be categorized as heuristic approaches. In addition, we also classify S-box constructions that use more than one generic method as a Combination Method.

The random generation approach is the simplest technique to construct an S-box; however, its disadvantage is that most of the final S-boxes generated do not achieve our desired value for cryptographically strong S-boxes, as stated in Table 1. Conversely, the mathematical function approach is the best technique with which to achieve the desired S-box properties; however, it is difficult to find this function. For the heuristic approach, the latest S-box construction proposals show an improvement compared to the early proposal in terms of its S-box properties. Therefore, nowadays, researchers focus their attention on exploring heuristic approaches to generate cryptographically strong S-boxes since the implementation of this approach is convenient in both hardware and software.

To facilitate the classification of S-box construction, we divide the S-box design methods into two subsections. The first subsection reviews the S-box constructions which are implemented in the block ciphers proposal, while the second subsection reviews other S-box constructions available in literature.

2.2.1. S-Boxes in Block Ciphers

Mathematical Function

The block ciphers SQUARE [16], BKSQ [17] and Rijndael [18,19] were developed by the same designer in the late 1990s. All S-boxes in these three block ciphers were constructed using similar transformations which take the multiplicative inverse over finite field ${\mathbb{F}}_{2^8}$, as suggested in [20]; then, an affine transformation over ${\mathbb{F}}_2$ is applied to the output bits. Rijndael block cipher was then promoted as the Advanced Encryption Standard (AES) by the National Institute of Standards and Technology (NIST) in 2001 [8]. Following the same construction and transformations are the S-boxes used in block cipher Camellia [21], Mercy [22], ARIA [23], SMS4 [24] and BC2 [25]. The S-box in HyRAL [26] block cipher was also constructed based on multiplicative inverse over ${\mathbb{F}}_{2^8}$ using the irreducible polynomial of $z^8+z^4+z^3+z+1$ with two transformations performed beforehand, namely affine transformation (i.e., $y=x\oplus 64$) and Gray code transformation (i.e., $z=y\oplus (y<<1)$). Therefore, HyRAL S-box is classified as a mathematical function approach.

Another block cipher proposed in 2010 is called PP-1 [27]. The S-box construction is classified as a mathematical function approach since they use a multiplicative inverse procedure over finite field, similar to AES but with a randomly chosen primitive polynomial (i.e., $z^7+z^2+z+1$). In the studies of Fuller et al. [28] for removing linear redundancy in S-boxes, they select several random pairs of S-box elements and rearrange four corresponding S-box entries in such a way that the S-box produced is an  involution S-box.

Heuristic

CS-Cipher [29] and CRYPTON [30] block cipher use a 3-round Feistel cipher to generate $8\times 8$ S-box. In general, their S-box is constructed with concatenation of elements generated in ${\mathbb{F}}_{2^4}$ and pre-determined parameters to produce $8\times 8$ S-box. Using the same construction is the S-box used in PICARO [15] block cipher. However, the S-box generated in PICARO is a non-bijective S-box. The ZORRO [31] block cipher proposed an improvement to PICARO’s S-box construction. They instantiate a 4-round Feistel network with a monomial $x^3$ generated in ${\mathbb{F}}_{2^4}$. Then, they add an 8-bit linear transformation at the end of each round and lastly, an affine transformation to remove the fixed point. Unlike PICARO, the final S-box of ZORRO is bijective but the construction classification technique is the same, i.e., a heuristic approach.

S-box used in Skipjack [32] and FOX [33] block ciphers are also classified as a heuristic approach. Although the real S-box construction in Skipjack is unknown, the research of Biryukov and Perrin [34] on the reverse-engineering of S-boxes, concludes that the Skipjack’s S-box construction is not the result of random generation. The method of S-box construction used in the FOX block cipher consists of a three-round Lai–Massey scheme to avoid a purely algebraic construction. The three rounds of the Lai–Massey scheme take three different small S-boxes as the round function F.

Random Generation

CHAIN [35] block ciphers generate their S-box using random generation while ANUBIS [36] block ciphers generate theirs using a pseudo-random number generator with consideration of the involution S-box as a result. An involution S-box is where the S-box has an inverse onto itself. Therefore, the same S-box can be used in encryption and decryption processes. The S-box used in KHAZAD [37] block ciphers is an improvement of ANUBIS’s S-box that uses linear shuffling. The same linear shuffling for S-box construction is also adopted in the ICEBERG [38] block cipher.

KAMKAR [39] block ciphers use a key-dependent S-box. KAMKAR uses two different generators of a quasi-random sequence of numbers to alternately trigger based on the scanned cipher key. Then, the generators are used to generate two random numbers and derive two integers between 0 and 255 to be used for swapping the location from the initial S-box. In KAMKAR, the initial S-box is fixed with a linear power function (i.e., x over ${\mathbb{F}}_{2^8}$). The iteration continues until all bytes are scanned and swapped.

Combination Method

The Hierocrypt [40] block cipher uses two different S-boxes, namely a high-level S-box and lower-level S-box. For high-level S-box, the construction is based on bit permutation, followed by a power polynomial of $x^{247}$ over ${\mathbb{F}}_{2^8}$ using the irreducible polynomial of $z^8+z^6+z^5+z+1$. Lastly, an affine transformation over ${\mathbb{F}}_2$ is applied on the output. The construction for a lower-level S-box is not described; therefore, we conclude that they used the heuristic approach for lower-level S-box. Using the same approach, the CLEFIA [41] block cipher employs two different S-boxes constructed using inverse function over ${\mathbb{F}}_{2^8}$ and using four 4-bit random S-boxes for the second construction. Therefore, Hierocrypt’s and CLEFIA’s S-box construction are combination methods because they use the mathematical function approach for the first S-box and heuristic approach for the second S-box.

The KALYNA [42] block cipher adopted the S-box construction proposed by Kazymyrov et al. [43], which was constructed based on gradient descent. This S-box construction is basically an enhancement of the improved hill climbing method proposed by Gao et al. [44] in 2010. Generally, they generate an initial solution, S, which is a bijective S-box with a minimum value of DU based on function F. The function F is basically determined as an inverse function over finite field ${\mathbb{F}}_{2^8}$. Then, they randomly swap a number of values in S to generate $S_t$ as the final S-box. Therefore, we classify this construction as a combination method since they combine the mathematical function approach with the random generation approach.

2.2.2. Other S-Boxes Proposal

Aside from the S-boxes used in block ciphers, there exist a large number of S-box construction proposals in the literature. We have reviewed, analyzed and categorized all the S-box proposals that we have collected into random generation, heuristic, mathematical function and combination methods.

Random Generation

There are several S-box constructions that generate dynamic S-boxes which depend on a key. Among others are the proposal in [45,46,47,48]. In particular, their construction begins with an initial S-box, then a string of keys is generated to permute the content of the initial S-box. Thus, a new S-box is constructed. Various methods are used to generate the keys such as random generation, a pseudo-random number generator (PRNG) or a round key obtained from the RC4 algorithm [49].

Mamadolimov et al. [50] also proposed an S-box construction based on random generation. The initial S-box is represented as eight component functions. The first three component functions are deterministically constructed, such that the highest nonlinearity for each Boolean function is found. Then, the other five component functions are generated randomly to complete the S-box.

However, the S-box construction using random generation has received less attention among researchers. This might be because of the unfavorable cryptographic properties exhibited by this approach.

Heuristic

The heuristic approach has received more attention from researchers, especially on chaos-based S-box construction. This might be because chaos is a stochastic process in nonlinear dynamic systems, thus satisfying the need for nonlinearity in block ciphers. Among the popular chaotic maps used are the Chebyshev map [51,52], Baker map [53,54], Lorenz systems [55,56], logistic map [57,58], neural network [59,60], piecewise linear chaotic map [61,62], tent map [63,64] and Van Der Pol oscillator [65]. In general, chaos-based S-box construction starts with the selection of an initial value in selected chaotic map. Then, they iterate the chaotic map and use their defined technique to obtain an integer that lies between 0 and 255. This procedure is repeated to generate another integer until all 256 elements of the $8\times 8$ S-box are fulfilled.

Furthermore, there are several S-box proposals that we categorized as heuristic approaches, such as the S-box construction using hill climbing [43,66], Latin square [67], analytical approach [68], genetic algorithm [69,70], simulated annealing [71,72], cellular automata [73,74], ant colony optimization [75], artificial immune system [76] and bee waggle dance [77]. Nature-inspired systems, such as genetic algorithms, work in reverse, i.e., [70], gradient descent [43] (i.e., modified hill climbing), artificial immune system [76] and bee waggle dance [77] show encouraging developments in S-box construction using the heuristic approach.

Mathematical Function

The main criterion for categorizing S-box proposals as mathematical functions is that designers use the same transformation as AES [8]. This includes either revising the transformation [78,79,80] itself by using different irreducible polynomials or by adding another affine transformations [81,82,83,84] in their construction.

Moreover, some S-box proposals using mathematical functions other than AES were found in the literature, such as linear fractional transformation or projective general linear group [85,86,87], trace-representation polynomial function [88], gray code encode [89], semi-fields pseudo-extensions [90] and using finite field power functions [91]. All these S-box constructions provide encouraging results and can be categorized among cryptographically strong S-boxes.

Combination Method

Fuller et al. proposed 2-step tweaking [28] and 4-step tweaking [92] in order to avoid linear redundancy and preserve the involution properties of an S-box, respectively. We categorized their proposed techniques as a combination method since they used methods such as divide and swap in the tweaking of the initial S-box that was generated based on a multiplicative inverse function over ${\mathbb{F}}_{2^8}$. Mamadolimov et al. [11] and Isa et al. [12,93] also proposed an S-box construction using a combination method. In this proposal, they constructed an initial S-box based on the non-permutation power function followed by a heuristic approach, which is an algorithm to make the S-box bijective as a final result.

3. S-Box Construction

3.1. Preliminaries

Table 2. $x^3$ over ${\mathbb{F}}_{2^4}$.

x	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
$x^3$	0	1	8	F	C	A	1	1	A	F	F	C	8	A	8	C

is an example of a non-permutation power function generated over finite field in ${\mathbb{F}}_{2^4}$. In this case, we use $x^3$. We can extract the following information: (1) ${\mathrm{D}}_{\mathrm{EL}}$, (2) ${\mathrm{R}}_{\mathrm{EL}}$ and (3) ${\mathrm{N}}_{\mathrm{EL}}$ from Table 2.

${\mathrm{D}}_{\mathrm{EL}}$ is a notation for Desired Element. A desired element only occurs once in a permutation function, such that a bijective S-box is achieved. From Table 2, only one element is found in the ${\mathrm{D}}_{\mathrm{EL}}$ category, which is the element 0.

${\mathrm{R}}_{\mathrm{EL}}$ is a notation for Repeated Elements. The repeated elements were obtained from generated functions that occur more than once. From the analysis of Table 2, there are five elements that fall into this category, which are the elements 1, 8, A, C and F. All five repeated elements are found to be repeated three times.

${\mathrm{N}}_{\mathrm{EL}}$ denotes the Non-existent Elements which means that the elements are ’missing’ from the generated function. This happens because the element that should exist has been replaced by a repeated element. From Table 2, we can determine that there are a total of 10 elements that do not exist in $x^3$ over ${\mathbb{F}}_{2^4}$, which are 2, 3, 4, 5, 6, 7, 9, B, D and E.

After these three group of elements are obtained, a Redundancy Analysis Table will be constructed. The Redundancy Analysis Table is a representation of bits error between all elements in ${\mathrm{R}}_{\mathrm{EL}}$ compared to the elements in ${\mathrm{N}}_{\mathrm{EL}}$.

Table 3. Redundancy Analysis Table for $x^3$ over ${\mathbb{F}}_{2^4}$.

	${\mathbf{N}}_{\mathbf{EL}}$	2	3	4	5	6	7	9	B	D	E
${\mathbf{R}}_{\mathbf{EL}}$
1		2	1	2	1	3	2	1	2	3	2
8		2	3	2	3	3	4	1	2	1	2
A		1	2	3	4	2	3	2	1	2	3
C		3	4	1	2	2	3	2	3	0	1
F		3	2	3	2	2	1	2	1	2	1

shows the redundancy analysis table of $x^3$ over the finite field ${\mathbb{F}}_{2^4}$. For example, there are 3 bits that needs to be changed to replace element 1 from ${\mathrm{R}}_{\mathrm{EL}}$ with element 6 from ${\mathrm{N}}_{\mathrm{EL}}$, as illustrated in Figure 1. Likewise, the element F from ${\mathrm{R}}_{\mathrm{EL}}$ has three options which only involve one bit change. The elements listed from ${\mathrm{N}}_{\mathrm{EL}}$ are 7, B and E.

3.2. Our Proposed Construction

Let $x^d$ denote a power function in ${\mathbb{F}}_{2^8}$ using the irreducible polynomial $x^8+x^4+x^3+x^2+1$, where $d=\{1,2,\dots ,2^8-2\}$ and $x\in {\mathbb{F}}_{2^8}$. All power functions (i.e., $x^d$) can be classified into linearly non-equivalent functions using the squaring method [94], as shown in

Table 4. Classification of linearly non-equivalent power function, $x^d$ based on maximum NL in ${\mathbb{F}}_{2^8}$.

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

. The first column of Table 4 represents the powers d that are non-equivalent to each other. The second column lists all the equivalent power functions for each power d. For instance, the power function $x^{253}$ is equivalent to $x^{127}$, as is the case with $x^{191}$. Four more columns in Table 4 denote the values of NL, DU, AD and LA produced by the underlying power function. The ${\mathrm{N}}_{\mathrm{EL}}$ column lists the number of non-existent elements, while the ${\mathrm{R}}_{\mathrm{EL}}$ column lists the number of repeated elements in each of the involved power functions. The last column denotes whether the power function is a permutation or otherwise, based on the number given in columns ${\mathrm{N}}_{\mathrm{EL}}$ and ${\mathrm{R}}_{\mathrm{EL}}$ (i.e., label ‘Y’ is given when ${\mathrm{N}}_{\mathrm{EL}}$ = ${\mathrm{R}}_{\mathrm{EL}}$ = 0, otherwise label ‘N’ will be given).

Our construction starts with the generation of binomial power functions. ${\mathtt{F}}_1$ and ${\mathtt{F}}_2$ which are two different power functions selected over finite field ${\mathbb{F}}_{2^8}$ is added to produce a new function $\mathtt{F}$ (i.e., $\mathtt{F}={\mathtt{F}}_1+{\mathtt{F}}_2$). In total, there are ${\mathtt{C}}_2^{2^8-2}=32,131$ possible combination of binomial power functions produced from this operation and none of them are permutation function. We analyzed its repeated elements (${\mathrm{R}}_{\mathrm{EL}}$) and non-existent elements (${\mathrm{N}}_{\mathrm{EL}}$), then summarized the findings in

Table 5. Redundancy Analysis of Binomial Power Functions.

	${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Total		${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Total		${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Total		${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Total		${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Total
1	15	1	1024	27	85	35	256	53	85	55	256	79	77	69	128	105	96	80	256
2	17	1	128	28	221	35	64	54	80	56	256	80	85	69	384	106	100	80	256
3	51	1	256	29	75	37	256	55	90	58	512	81	97	69	128	107	85	81	896
4	85	1	128	30	217	39	64	56	89	59	1024	82	187	69	192	108	125	81	256
5	16	2	128	31	45	41	128	57	88	60	256	83	78	70	128	109	175	81	512
6	254	2	1	32	81	41	512	58	92	60	384	84	92	70	768	110	104	82	256
7	253	3	2	33	85	41	256	59	75	61	256	85	94	70	128	111	105	83	256
8	252	4	4	34	214	42	64	60	99	61	768	86	96	70	128	112	97	85	256
9	251	5	4	35	85	43	512	61	195	61	64	87	93	71	256	113	105	85	128
10	40	6	128	36	213	43	256	62	84	62	128	88	185	71	64	114	171	85	256
11	250	6	4	37	50	46	128	63	85	63	256	89	84	72	128	115	90	86	128
12	248	8	12	38	82	46	256	64	89	63	768	90	92	72	256	116	102	86	128
13	247	9	8	39	90	46	512	65	193	63	64	91	75	73	640	117	120	86	128
14	246	10	8	40	210	46	64	66	84	64	128	92	93	73	256	118	170	86	64
15	245	11	32	41	209	47	64	67	88	64	384	93	97	73	256	119	96	88	256
16	244	12	8	42	75	49	128	68	96	64	256	94	99	73	640	120	104	88	256
17	243	13	32	43	99	49	256	69	192	64	128	95	123	73	256	121	102	90	256
18	80	16	128	44	207	49	256	70	89	65	640	96	183	73	320	122	160	96	64
19	240	16	96	45	206	50	128	71	191	65	128	97	92	74	256	123	99	97	128
20	239	17	112	46	85	51	256	72	94	66	256	98	93	75	128	124	100	98	128
21	68	18	128	47	125	51	128	73	85	67	256	99	181	75	320	125	108	100	128
22	238	18	16	48	205	51	224	74	93	67	256	100	84	76	256	126	144	112	64
23	64	22	256	49	72	52	256	75	97	67	256	101	108	76	256	127	113	113	128
24	51	25	512	50	84	52	640	76	189	67	64	102	179	77	1024	128	120	120	128
25	230	26	16	51	204	52	64	77	84	68	384	103	178	78	64	129	136	120	192
26	69	31	512	52	77	53	256	78	92	68	768	104	177	79	128	130	128	128	576
Overall Total																			32,131

.

Table 5 lists the number of binomial power functions according to (${\mathrm{N}}_{\mathrm{EL}}$, ${\mathrm{R}}_{\mathrm{EL}}$) pairs. As an example, there are a total of 1024 binomial power functions that produce 15 non-existent elements over only one repeated element. In addition, there are a total of 576 generated binomial power functions that produce the same number of ${\mathrm{N}}_{\mathrm{EL}}$ and ${\mathrm{R}}_{\mathrm{EL}}$, which are equal to 128. Other than that, we can categorize the generated binomial power functions into 130 groups based on (${\mathrm{N}}_{\mathrm{EL}}$, ${\mathrm{R}}_{\mathrm{EL}}$) pairs.

Overall, our proposed algorithm in constructing cryptographically strong S-boxes is illustrated in Figure 2, which is inspired by the S-box construction of Isa et al. [12]. Our initial S-box is selected from the groups of binomial power functions that produce only one (1) repeated element. This includes (${\mathrm{N}}_{\mathrm{EL}}$, ${\mathrm{R}}_{\mathrm{EL}}$) pairs of (15, 1), (17, 1), (51, 1) and (85, 1) from Table 5.

In total, there are 1540 candidates that can be used for our initial S-box. However, this number of candidates can be minimized to 200 using the squaring method [94] because of its linearly non-equivalent properties, as shown in

Table 6. Linearly Non-Equivalent Functions for ${\mathrm{R}}_{\mathrm{EL}}$ = 1.

	${\mathrm{N}}_{\mathbf{EL}}$	${\mathrm{R}}_{\mathbf{EL}}$	Distinct Total	Linearly Non-Equivalent Total
1	15	1	1024	136
2	17	1	128	16
3	51	1	256	32
4	85	1	128	16
Overall Total			1540	200

. The complete list of linearly non-equivalent binomial power functions that produces one repeated element from these four groups is included in Appendix A. In this study, we select and limit the selection of the initial S-box to only one repeated element to preserve the cryptographic properties of the newly generated function such that it is not compromised significantly.

The construction continues with the addition of an S-box candidate with another power function (i.e., $\mathtt{F}=\mathtt{F}+{\mathtt{F}}_3$), where the selection of a new power function must not include the previously selected power function. After a new function $\mathtt{F}$ is generated, we extract the information of ${\mathrm{D}}_{\mathrm{EL}}$, ${\mathrm{R}}_{\mathrm{EL}}$ and ${\mathrm{N}}_{\mathrm{EL}}$ on the function, as described in Section 3.1. If ${\mathrm{N}}_{\mathrm{EL}}$ contains no element, that means the function is already bijective. Then, we measure its cryptographic properties and store it as the proposed S-box if it exhibits the desired strong properties.

Otherwise, if ${\mathrm{N}}_{\mathrm{EL}}$ contains any element, we construct a redundancy analysis table by determining all the elements in ${\mathrm{N}}_{\mathrm{EL}}$ and ${\mathrm{R}}_{\mathrm{EL}}$ groups of $\mathtt{F}$. Then, the bit errors rate between all elements in ${\mathrm{N}}_{\mathrm{EL}}$ and all elements in ${\mathrm{R}}_{\mathrm{EL}}$ are produced to complete the redundancy analysis table. The bit error rate is the number of bit errors per unit time. In this study, the bit errors range from a minimum of one (1) bit, up to the maximum of eight (8) bits since we construct an $8\times 8$ S-box.

From the redundancy analysis table, we identify one current ’smallest’ bit error. If there are several choices obtained from the table, the selection will be made randomly. Then, we determine the actual element of ${\mathrm{N}}_{\mathrm{EL}}$ and ${\mathrm{R}}_{\mathrm{EL}}$ that correspond with the selected smallest bit error. Next, the exact location of the selected ${\mathrm{R}}_{\mathrm{EL}}$ is identified in function $\mathtt{F}$ and lastly we swap the element with the previously selected ${\mathrm{N}}_{\mathrm{EL}}$ (i.e., $\mathtt{F}\left({\mathrm{R}}_{\mathrm{EL}}\right)={\mathrm{N}}_{\mathrm{EL}}$). Similarly, the selection will be made randomly if more than one option of the identified ${\mathrm{R}}_{\mathrm{EL}}$ is located. By selecting the smallest bit errors, we expect that the cryptographic properties of the newly generated function will not be compromised significantly.

After the swapping process, we measure the cryptographic properties of this newly generated function. We store it as the proposed S-box if it exhibits the desired strong properties. Otherwise, the function will be denoted as ${\mathtt{F}}_p$ and rotated by n places. This rotation step that we proposed is operated based on circular rotation either column-wise (i.e., rotation of component function) or row-wise (i.e., rotation of elements in the function). The purpose of this step is to increase the algebraic expression (i.e., no. of terms (#term)) of the function ${\mathtt{F}}_p$ while preserving its cryptographic properties. Current construction, which exhibits the algebraic expression with simple terms, might expose ciphers using the S-box to an interpolation attack [6]. From our observation, column-wise rotation does not impact the cryptographic properties of the function. However, different to row-wise rotation, the cryptographic properties might change significantly. Our analysis found that, for row-wise rotations of 64, 128 and 192 places, the cryptographic properties of the S-box can preserved.

Then, another round of iteration will be conducted in our algorithm. The next iteration contains a multiplication step of ${\mathtt{F}}_p$ with a coefficient $\alpha$ where $\alpha$ ranges from 0 to 255; it then continues again with a redundancy analysis table. The stopping criteria that we fix in our iterations are based on the final S-box produced that meets our requirement or based on the cryptographic properties of ${\mathtt{F}}_p$ that are found to worsen (i.e., the cryptographic properties exhibited are lower than the values stated in Table 1). In both cases, another set of $\mathtt{F}={\mathtt{F}}_1+{\mathtt{F}}_2$ will be selected for our next experiments.

Table 7. Optimal S-box using Proposed Technique.

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	8B	C3	6E	5E	9B	E9	03	68	BE	BD	12	27	2C	F4	BB	41
1	31	A3	8A	86	C8	38	94	3C	08	32	3E	B5	56	ED	14	47
2	37	1B	7B	DE	35	99	1F	A0	81	65	8D	5B	DC	E3	79	9C
3	64	E5	90	06	D5	3A	AE	B4	DF	71	6D	16	A9	6C	25	BA
4	CF	9D	30	D3	EC	A5	D8	B0	05	C1	6F	0E	7F	D4	91	62
5	B9	E1	61	C9	D6	C6	43	E2	88	52	0B	87	4E	17	EF	CC
6	60	2D	3F	78	2E	24	45	CB	D1	C4	FC	1C	22	FE	4D	6B
7	B6	CE	07	6A	66	58	F8	0F	70	67	F5	98	74	D0	FD	82
8	3B	FB	B3	9A	EE	75	F2	77	76	34	63	E7	29	10	36	44
9	4A	89	BC	DB	18	2F	DA	FA	19	AB	EB	7A	13	72	50	D2
A	9F	4F	96	F3	7C	CA	7D	C0	09	D7	B1	C5	57	73	48	04
B	A6	5A	11	A7	93	97	1A	0D	26	0A	C7	69	F0	3D	39	8E
C	00	20	A4	95	AC	E6	40	59	23	92	A8	33	49	02	F1	AA
D	15	8F	5F	1E	80	53	4B	42	F6	7E	2B	01	9E	E4	CD	AF
E	5C	2A	55	F7	8C	28	0C	E8	B8	5D	4C	E0	84	21	FF	A1
F	B7	A2	B2	BF	F9	DD	54	83	1D	EA	C2	85	51	AD	46	D9
	NL = 108				DU = 4				AD = 7				LA = 20
	(Fp/OFp) = (1/0)				#term = 255				AlC = Complex				PERM = Y

shows the optimal S-box obtained from the proposed method and is represented as hexadecimal. The first column in Table 7 denotes the first four bits, while the first row denotes the remaining four bits of the 8-bit input to the S-box. For instance, the input 71 gives the output CE, (i.e., F(71) = CE. For input 71, element 7 is selected from the first column while element 1 is selected from the first row). The cryptographic properties exhibited by this S-box meet all the desired values stated in Table 1.

4. Discussion

Table 8. S-Boxes Ranks.

Rank	S-Box	NL	DU	AD	LA	#Term	Design Method
1	AES [9]	112	4	7	16	9	Mathematical
	Hierocrypt [40]	112	4	7	16	255
	Camellia [21]	112	4	7	16	254
	ARIA [23]	112	4	7	16	9
	CLEFIA [41]	112	4	7	16	254
	HyRAL [26]	112	4	7	16	253
	Yang et al. [80]	112	4	7	16	1
	Cui et al. [82]	112	4	7	16	253
	Hussain et al. [57]	112	4	7	16	254
	Dumas and Orfila [90]	112	4	7	16	254
	Gondal et al. [54]	112	4	7	16	251
	Khan and Azam [79]	112	4	7	16	252
	Tran et al. [89]	112	4	7	16	254
	Kapalova et al. [84]	112	4	7	16	255
2	Li et al. [91]	112	4	5	16	217	Mathematical + Heuristic
3	Yang et al. [80]	112	6	7	16	250	Mathematical
	Ivanov et al. [70]	112	6	7	16	253	Mathematical + Heuristic
4	Yang et al. [80]	110	4	7	18	253	Mathematical
5	Yang et al. [80]	110	6	7	18	253	Mathematical
	Ivanov et al. [70]	110	6	7	18	254	Mathematical + Heuristic
6	This Paper	108	4	7	20	255	Mathematical + Heuristic
	Isa et al. [93]	108	4	7	20	3	Mathematical
7	Ivanov et al. [70]	108	6	7	20	253	Mathematical + Heuristic
	Isa et al. [77]	108	6	7	20	253
8	Isa et al. [93]	108	6	4	20	3	Mathematical
9	Ivanov et al. [70]	106	6	7	22	252	Mathematical + Heuristic
	Fuller et al. [28,92]	106	6	7	22	254
	Hierocrypt [40]	106	6	7	22	253
	Isa et al. [93]	106	6	7	22	3	Mathematical
10	Isa et al. [12]	104	6	7	24	255	Mathematical + Heuristic
	Ivanov et al. [70]	104	6	7	24	255
11	KALYNA [42]	104	8	7	24	254	Heuristic
	Kazymyrov et al. [43]	104	8	7	24	254	Random
12	Mamadolimov et al. [11]	102	8	7	26	254	Mathematical + Heuristic
13	Kazymyrov et al. [43]	100	8	7	28	254	Random
14	Picek et al. [69]	100	10	7	28	254	Heuristic
15	CLEFIA [41]	100	10	6	28	246	Mathematical
16	Picek et al. [69]	100	12	7	28	253	Heuristic
	SKIPJACK [32]	100	12	7	28	255

compares our obtained S-box with the existing $8\times 8$ cryptographically strong S-boxes available in literature, as discussed in the previous section. Only S-boxes that satisfy our prerequisite requirements are selected for comparison. The S-boxes were then arranged based on the optimal cryptographic properties exhibits by each S-box, starting with the highest NL, lowest DU, highest AD and, lastly, lowest LA. From there, we rank the S-boxes based on these four properties. Also included in Table 8 are the number of terms exhibited by an S-box and lastly the generic design method of each proposal.

In total, there are 39 S-boxes listed in Table 8 where we classify 16 ranks. The first rank is occupied by the AES S-box which was constructed using multiplicative inversion in ${\mathbb{F}}_{2^8}$. There are 13 others S-box construction that are similar to AES’s S-box construction; thus, they exhibit the same cryptographic properties as AES, which consists of (112, 4, 7, 16) for its (NL, DU, AD, LA), respectively. So far, this multiplicative inverse technique over finite field ${\mathbb{F}}_{2^8}$ leads to the best-known cryptographic properties for an $8\times 8$ S-box.

Ranked second is the S-box construction proposed by Li et al. [91]. Their S-box construction exhibits cryptographic properties of (112, 4, 5, 16) for (NL, DU, AD, LA), respectively. Their S-box proposal is constructed in ${\mathbb{F}}_{2^9}$ using Quadratic APN functions which are heuristically converted into an $8\times 8$ S-box as the final result.

There are also some authors that proposed several S-boxes such as Yang et al. [80], Kazymyrov et al. [43], Ivanov et al. [70] and Isa et al. in [12,77,93]. The S-box constructions proposed by Yang et al. [80] are ranked third, fourth and fifth and classified as mathematical functions-generated methods, as multiplicative inverse, addition and multiplication are only used in the algorithm. Ranked third and fifth are the S-boxes proposed by Ivanov et al. [70] that use the reversed genetic algorithm on the initial S-box that was generated beforehand using multiplicative inverse. Thus, we classify this algorithm as a combination method that lies between the mathematical function approach and heuristic approach. The third ranked S-box has the same nonlinearity as AES (i.e., NL = 112); however, the value for differential uniformity is slightly higher which is DU = 6. By the same S-box construction, Ivanov et al. [70] also produced S-boxes that are ranked seventh, ninth and tenth in Table 8.

We classify the S-box construction of Kazymyrov et al. [43] as random generation. This is because the S-box is constructed by randomly swapping two elements in an initial function. This step is repeated until their desired criteria are achieved. Their best proposed S-box is ranked eleventh with cryptographic properties of (104, 8, 7, 24), while the other one is ranked thirteenth.

Our proposed S-box construction is ranked sixth. The final S-box that we obtained exhibits cryptographic properties of (108, 4, 7, 20). The S-box also produces a complex algebraic expression of 255 terms. The best S-box by Isa et al. [93] shares the same rank of sixth, while the other two proposed S-boxes are ranked eighth and ninth with cryptographic properties of (108, 6, 4, 20) and (106, 6, 7, 22) for (NL, DU, AD, LA), respectively. However, their S-box, which can be constructed using simple algebraic expression (i.e., only three terms involved), might be vulnerable to an interpolation attack [6].

There are other S-boxes proposed by Isa et al. in [12,77] using the combination method. Ranked seventh, Isa et al. [77] used an algorithm called Bee Waggle Dance on the multiplicative inverse function. This construction produced an S-box with cryptographic properties of (108, 6, 7, 20). Ranked tenth is the construction of Isa et al. [12], who used an algorithm called the Redundancy Removal Algorithm on the non-permutation power function that exhibits cryptographic properties of (104, 6, 7, 24). Mamadolimov et al. [11] first introduced the original version of the Redundancy Removal Algorithm, which is ranked twelfth and has cryptographic properties of (102, 8, 7, 26). Empirically, our proposed construction, which is an inspired and enhanced version of the Redundancy Removal Algorithm, managed to obtain cryptographically strong S-boxes that compare well with and even outperform the originally proposed constructions [11,12].

From our observation, all the S-boxes listed in Table 8 are designed and constructed either through mathematical functions or through combination methods between mathematical functions and heuristic methods. So far, the best S-box that we found using random generation is the S-box proposed by Kazymyrov et al. [43], which is ranked eleventh. Nevertheless, this S-box exhibits DU = 8; thus, it fails to fulfill our cryptographically strong criteria. In fact, the S-boxes ranked from eleventh to sixteenth all fail to fulfill our prerequisite requirement for cryptographically strong S-boxes. The S-boxes are included in Table 8 for a comparative analysis.

The research results that are included in the comparative analysis are obtained by applying the security measurement using a mini-workstation with properties of Intel (R) Core (TM) i7-6600U CPU @ 2.60 GHz, 16 GB of RAM, 64-bit Operating System and pre-installed with MATLAB R2022a. All simulations were performed in MATLAB programming language, and no external embedded devices were involved. Since MATLAB is a high-level programming language, we did not conduct a computational complexity analysis of our S-box construction.

5. Conclusions

In this paper, we analyzed the cryptographic properties of binomial power functions. Through our observation of the redundancy table, we discover that all binomial power functions generated over a finite field ${\mathbb{F}}_{2^8}$ are not bijective. We modify and enhance the method called the Redundancy Removal Algorithm to obtain cryptographically strong S-boxes. Our proposed S-box exhibits cryptographic properties of (108, 4, 7, 20) for (NL, DU, AD, LA), respectively; thus all our prerequisite requirements are fulfilled and the performance of the original algorithm proposed by Mamadolimov et al. and Isa et al. is surpassed.

From our comparative analysis, the mathematical function remains the best method to construct a cryptographically strong S-box. The production of a new mathematical function that can challenge multiplicative inversion is an interest of many researchers. However, recent research developments on combination methods of mathematical functions and the heuristic approach show an encouraging trend in the construction of a cryptographically strong S-box. As for random generation, this method is unfavorable since there are no recent developments driven by this approach.

In future work, our proposed S-box can be applied to a working encryption algorithm to analyze its efficiency and accuracy. To achieve this, we have to convert our script into a low-level programming language and implement it in an embedded device. We are also interested in categorizing our S-box collections based on equivalence classes. To the best of our knowledge, there are three types of equivalence classes in literature which are linear and affine equivalence, extended affine (EA-) equivalent and Carlet–Charpin–Zinoviev (CCZ-) equivalent.