# An Injective S-Box Design Scheme over an Ordered Isomorphic Elliptic Curve and Its Characterization

Authors: Naveed Ahmed Azam; Umar Hayat; Ikram Ullah
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Elliptic curves (ECs) are considered as one of the highly secure structures against modern computational attacks. In this paper, we present an efficient method based on an ordered isomorphic EC for the generation of a large number of distinct, mutually uncorrelated, and cryptographically strong injective S-boxes. The proposed scheme is characterized in terms of time complexity and the number of the distinct S-boxes. Furthermore, rigorous analysis and comparison of the newly developed method with some of the existing methods are conducted. Experimental results reveal that the newly developed scheme can efficiently generate a large number of distinct, uncorrelated, and secure S-boxes when compared with some of the well-known existing schemes.


---

## Body

## 1. Introduction

A lot of advancements have been made in the field of computation methods in the past few decades. These advancements necessitate the improvements in the cryptosystems, since their security strength highly depends on the computational power. A cryptosystem is considered to be secure if it can create enough confusion/diffusion in the data [1]. Many well-known and commonly used cryptosystems including Data Encryption Standard (DES), Advanced Encryption Standard (AES), Twofish security system [2], Blowfish cryptosystem [3], and International Data Encryption Algorithm (IDEA) [4] use substitution box (S-box) for the data scrambling.It is easy to observe that the cryptosystems using a single S-box are unable to create enough confusion/diffusion in the modern data with high correlation such as digital images [5]. Therefore, many cryptographers proposed the usage of multiple S-boxes for the encryption of such data. An S-box generation technique is said to be good for the encryption of highly correlated data, if it can efficiently generate a large number of secure and mutually uncorrelated S-boxes.Many researchers have proposed different S-box generation schemes based on different mathematical structures. El-Ramly et al. [6] proposed an approach for the generation of strong S-boxes based on a Latin square. The length of the secret key used for these S-boxes is of 128 bits. Wu et al. [7] proposed Latin square doubly stochastic matrix to develop new S-boxes. Peng et al. [8] generated dynamic S-boxes using spatiotemporal chaotic system. Radhakrishnan et al. [9] developed an analytical approach to generate S-boxes. Wang et al. [10] proposed an S-box using chaos theory. Alkhaldi et al. [11] constructed S-boxes using tangent delay for ellipse cavity chaotic sequence and a particular permutation. The newly generated S-boxes have high resistance against linear and differential attacks. Khan and Azam [12] proposed a method for the construction of multiple S-boxes based on a group action and Gray codes. Similarly, Khan and Azam [13] presented another algorithm for the design of S-boxes based on affine and power mappings. It is shown computationally that all of the newly generated S-boxes have high security against modern attacks. However, each of these methods only generate 256 S-boxes.Recently, elliptic curves (ECs) have received great attention in the field of cryptography. The ECs based cryptosystems provide higher security with smaller key size than classical cryptosystems [14–18]. Jung et al. [19] characterized S-boxes over hyperelliptic curves. Hayat et al. [20, 21] proposed different methods for the generation of an 8×8 S-box by using an elliptic curve (EC) over a prime field. Actually, the scheme in [21] is a generalization of the scheme in [20]. These techniques use x-coordinates of the points on the EC followed by modulo 256 operation. Although, the schemes are capable of generating secure S-boxes, but each has time complexity O(p), where p is the underlying prime. Furthermore, the output of these algorithms is uncertain in the sense that it may or may not generate an S-box for each input parameters, and are independent of the underlying EC. Azam et al. [22] used some typical type of orderings on a class of Mordell elliptic curve (MEC) over a finite field to design an 8×8 S-box in constant time. All these schemes can generate at most one S-box for a given EC.The aim of this paper is to propose a novel method to efficiently construct a large number of distinct, mutually uncorrelated, and cryptographically strong injective S-boxes for a given EC. The proposed scheme usesy-coordinates of the points on an ordered EC isomorphic to the given ordered MEC. The remaining part of the paper is arranged as follows: Section 2 contains some definitions and concepts which are necessary to understand this paper. The proposed algorithm and its characterization are given in Section 3. A detailed analysis and comparison of the newly developed method are given in Section 4. A summary of the paper is given in Section 5.


## 2. Preliminaries

An EC is one of the fundamental concepts in the field of arithmetic geometry and has many applications in the field of applied sciences. For a fieldK and two integers a,b∈K such that 4a3+27b2≠0, theelliptic curveEK,a,b over K is defined to be the set of a symbol ∞ (identity of EK,a,b) and all points (x,y)∈K×K satisfying the following cubic equation(1)y2=x3+ax+b.We call K,a, and b theelliptic curve parameters of the EC EK,a,b. Two ECs EK,a,b and EK,a′,b′ over the field K areisomorphic if and only if there exists an integer t∈K∖{0} such that at4=a′ and bt6=b′. We call t theisomorphism parameter between EK,a,b and EK,a′,b′. In this setting, the isomorphism maps (x,y)∈EK,a,b onto (xt2,yt3)∈EK,a′,b′. It is easy to observe that isomorphism is an equivalence relation on the family of all ECs over the field K.Letp be a prime. It is well-known that for prime p there exists a unique finite field Fp, up to the field isomorphism, with exactly p elements. Note that the arithmetic operations over Fp are performed with respect to the modulo p (mod⁡p). There are total p2-p ECs over the field Fp. The number of ECs isomorphic to a given EC over Fp can be computed by Lemma 1 deduced from [23, Section 1.3 - 1.4].Lemma 1.
Letp>3 be a prime and a,b∈[0,p-1] be two integers. The number of ECs isomorphic to the EC EFp,a,b is (1)
(p-1)/6, if a=0 and Fp has a non-zero element of group order 6;(2)
(p-1)/4, if b=0 and Fp has a non-zero element of group order 4;(3)
(p-1)/2, otherwise.LetEFp,a,b be an EC. A bound on the number #EFp,a,b of points on the EC EFp,a,b can be computed using Hasse’s theorem [24, 25](2)#EFp,a,b-p-1≤2p.Note that the bound is independent of the parameters a and b. An EC EFp,a,b over Fp is said to be aMordell elliptic curve (MEC), if a=0. The following lemma gives the information of points on a special class of MECs.Lemma 2 (see [25]).
A MECEFp,0,b with p≡2 (mod⁡3) has exactly p+1 points with no repetition in their y-coordinates.We denote a MEC withp≡2 (mod⁡3) simply by Ep,b and call it an EC unless stated otherwise.LetEp,b be an EC with a total order ≺ and Ep,b′ be an EC isomorphic to Ep,b with the isomorphism parameter t. We define aninduced total order≺t on Ep,b′ as(3)xt2,yt3≺tx′t2,y′t3⇔x,y≺x′,y′,where (x,y),(x′,y′)∈Ep,b.Anm×nsubstitution box (S-box) is a mapping from F2m to F2n. Henceforth, S-box stands for injective S-box.Azam et al. [22] defined three typical orderings namelynatural N,diffusion D, andmodulo diffusion M on a given EC for the generation of S-boxes. The main idea behind these ordering is the arrangement of the points with the same x-coordinates. For the points (x1,y1),(x2,y2) on a given EC Ep,b,(4)x1,y1Nx2,y2⇔eitherx1<x2;orx1=x2,andy1<y2;(5)x1,y1Dx2,y2⇔eitherx1+y1<x2+y2;orx1+y1=x2+y2,andx1<x2;(6)x1,y1Mx2,y2⇔eitherx1+y1<x2+y2mod⁡p;orx1+y1≡x2+y2mod⁡p,andx1<x2.The natural ordering is the lexicographical order defined so that the points with the same x-coordinates appear consecutively, while the diffusion and modulo diffusion orderings diffuse the points with the same x-coordinates. The effect of these three orderings on the points of E11,1 is shown in Table 1.Table 1
The effect of orderingsN, D, and M on E11,1.
Ordering E 11,1 in non-decreasing order w.r.t. the ordering x 0 0 2 2 5 5 7 7 9 9 10 N y 1 10 3 8 4 7 5 6 2 9 0  x 0 2 5 0 2 10 9 5 7 7 9 D y 1 3 4 10 8 0 2 7 5 6 9  x 9 0 5 7 7 2 9 5 0 2 10 M y 2 1 7 5 6 3 9 4 10 8 0


## 3. The Proposed Scheme and Its Characterization

In this section, we present a simple and efficient method to generate a large number of distinct, mutually uncorrelated, and secure injectivem×n S-boxes based on the y-coordinates of an EC for the encryption of highly correlated data. The proposed method takes inputs integers 0<m≤n, a prime p≥2n, two non-negative integers b and b′, a positive integer t such that b,b′,t≤p-1 and bt6≡b′ (mod p) and a total order ≺ on the EC Ep,b. The output of the method is an injective S-box Sp,b,tm,n,≺ over the EC Ep,b′ isomorphic to Ep,b. The algorithm generates Sp,b,tm,n,≺ by choosing the 2my-coordinates, with values less than 2n, of the first 2n points on the EC Ep,b′ with respect to the induced ordering ≺t. Mathematically, Sp,b,tm,n,≺ can be expressed as (7)Sp,b,tm,n,≺:0,2m-1→0,2n-1defined  bySp,b,tm,n,≺i=yit3mod⁡p,where (xi,yi)∈Ep,b such that (xi-1,yi-1)≺(xi,yi).Note that the condition ofp≥2n is imposed so that the underlying EC has at least 2n points.Remark 3.
By Lemma2, the proposed method always output an S-box for each input parameters.Lemma 4.
The proposed method can be implemented inO(2n·n+log⁡p) time.Proof.
By Lemma2, we know that all integers from the interval [0,2n-1] will uniquely appear as y-coordinate of the points on the EC Ep,b′. Thus, we can generate Sp,b,tm,n,≺ by finding and sorting the set A(8)A=xi,yi∈Ep,b∣0≤i≤2n-1andyit3≡imod⁡p. with respect to the ordering ≺.
Thus, by the group theoretic arguments we have(9)A=xi,yi∈Ep,b∣0≤i≤2n-1andyi≡it3-1mod⁡p=xi,yi∈Ep,b∣0≤i≤2n-1andyi≡it-13mod⁡p, where (t3)-1 and t-1 are the multiplicative inverses of t3 and t in the field Fp, respectively.
Assuming thatt is not a very large number, t-1 can be computed by using extended Euclidean algorithm in time O(log⁡p). Therefore, finding yi for each i and using them in the equation y2≡x3+b (mod p), we can easily compute the set A in O(2n). The sorting operation on A can be performed in time complexity O(2n·n). Hence, Sp,b,tm,n,≺ can be computed in O(2n·n)+O(2n)+O(log⁡p)=O(2n·n+log⁡p).We describe an efficient algorithm for the generation of proposed S-boxes based on Lemma4 in Algorithm 1.Algorithm 1:Efficient generation of the proposed S-boxes.
Input: Two integers 0<m≤n, a prime p≥2n, two non-negative integers b and b′, a positive integert such that b,b′,t≤p-1 and bt6≡b′ (mod p), and a total order≺ on the EC Ep,b. Output: The proposed injective S-box Sp,b,tm,n,≺. (1) Calculate the multiplicative inverse t-1 of t in Fp. (2) Sort all integers in the interval [0,2n-1] as: i is a predecessor of j, if (xi,i(t-1))≺(xj,j(t-1)), for any two integers i,j∈[0,2n-1]. (3) outputSp,b,tm,n,≺ by selecting first 2m integers from the sorted integers in [0,2n-1].LetEp,b be an EC with ordering ≺ and integers 0<m≤n such that 2n≤p. We denote #Sp,b,tm,n,≺ to be the number of distinct m×n S-boxes generated by all ECs isomorphic to Ep,b by using the proposed method. In Lemma 5, we drive an upper bound for the number #Sp,b,tm,n,≺.Lemma 5.
The number of distinct S-boxes#Sp,b,tm,n,≺ generated by the proposed scheme is at most (p-1)/2.Proof.
We know that in a MEC,b≠0. Also p≡2 (mod 3), therefore 3 and 6 are not divisors of p-1. Thus, by group theoretic argument Fp∖{0} does not have an element of order 6. So by Lemma 1(iii), the number of ECs isomorphic to Ep,b is (p-1)/2, and hence the proposed algorithm can generate at most (p-1)/2 distinct S-boxes by using Ep,b.Next, we prove a sufficient condition onn so that the number #Sp,b,tm,n,N of S-boxes generated due to the natural ordering N is equal to the upper bound given in Lemma 5.Lemma 6.
For an integern such that 2n≥(p+1)/2, #Sp,b,tm,n,N is (p-1)/2.Proof.
Without loss of generality, we assume that the points onEp,b are arranged in non-decreasing order with respect to the orderingN and (xi,yi) denotes its i-th element. Note that, for a positive integer k such that k≤2m-1,(p-1)/2 and yk∈[1,p-1], exactly one of the values ±ykt3 is greater than (p-1)/2, since their x-coordinates are same on the EC Ep,bt6. Thus, from the condition 2n≥(p-1)/2 it follows that Sp,b,tm,n,N(k)=min{ykt3,-ykt3}. The proof will complete, if we show that, for some k and any t1,t2∈[1,p-1] such that the ECs Ep,bt16 and Ep,bt26 are different, it holds that Sp,b,t1m,n,N(k)≠Sp,b,t2m,n,N(k) i.e., min{ykt13,-ykt13}≢min{ykt23,-ykt23}. Without loss of generality, suppose on the contrary that(10)min⁡ykt13,-ykt13≡min⁡ykt23,-ykt23≡ykt13.This implies that(11)either-ykt23≡ykt13andykt23≥ykt13;or(12)ykt23≡ykt13.But, ykt23≢ykt13 in (11), since -ykt13 is additive inverse of ykt13. Thus, we have(13)either-ykt23≡ykt13andykt23>ykt13;or(14)ykt23≡ykt13.We show a contradiction for the case (13) and similar arguments can be used to prove for the case (14).
From-ykt23≡ykt13, we have yk(t13+t23)≡0. This implies that yk≡0 or t13+t23≡0, since p is a prime. But, yk∈[1,p-1], and therefore t13+t23≡0 holds. Thus by applying the multiplicative inverse t1-1, we get (-t2t1-1)3≡1, and by group theoretic argument, either t1=-t2 or the group order of -t2t1-1 is 3. But the former implies that Ep,bt16andEp,bt26 are same, while the latter implies that 3 is a divisor of p-1 for p≡2 (mod 3), which are contradictions. This implies that, Sp,b,t1m,n,N(k)≠Sp,b,t2m,n,N(k), for all k. Hence, each EC isomorphic to Ep,b will generate a distinct S-box. Thus, by using Lemma 1, result follows.Based on the computational results, we propose a stronger version of Lemma6 which is independent of the underlying ordering on the EC Ep,b. But, we did not manage to prove it rigorously.Conjecture 7.
For an integern such that 2n≥(p+1)/2, #Sp,b,tm,n,≺ is (p-1)/2.


## 4. Analysis and Comparison of the Proposed Method

A rigorous analysis of the proposed method is performed in this section. We used8×8 S-boxes generated by natural orderingN, diffusion orderingD and modulo diffusion orderingM for the analysis, since they are most commonly used in modern cryptosystems.


### 4.1. Security Analysis

We generated the S-boxesS3917,353,168,8,NS3917,3135,138,8,DS3917,210,138,8,MS5003,3666,58,8,NS5003,480,228,8,D, and S5003,2427,58,8,M by sorting the ECs in non-decreasing order with respect toN,D, andM orderings for the security analysis. The S-boxes S3917,353,168,8,NS3917,3135,138,8,D and S3917,210,138,8,M are presented in Tables 2–4, respectively. A comparison of the experimental results with the strongest S-boxes generated by the algorithms in [20–22, 26–34] is also conducted in this section.Table 2
The S-boxS3917,353,168,8,N generated by using the natural ordering.
126 94 73 41 171 110 86 199 215 27 203 3 227 154 55 40 21 113 10 88 150 100 177 35 202 91 211 184 99 146 198 206 147 71 56 46 228 54 84 161 239 61 31 238 192 225 183 137 42 241 193 222 253 7 50 255 254 208 106 164 127 169 246 19 170 48 12 252 231 45 116 233 17 18 87 190 36 219 82 72 214 134 58 96 0 210 243 81 5 30 221 97 34 47 181 200 67 29 180 16 111 77 189 130 115 162 185 186 28 93 135 240 195 159 138 37 108 151 140 201 107 38 247 196 179 230 145 242 237 25 98 64 26 218 132 8 172 131 22 152 53 187 89 166 69 245 65 148 155 68 9 102 104 120 188 20 1 129 103 124 23 6 251 142 60 14 117 15 92 157 123 158 112 141 95 139 2 79 178 39 133 173 213 51 216 197 122 57 207 232 59 223 128 212 224 105 156 4 13 83 176 248 249 143 114 118 49 80 44 153 165 149 220 75 167 33 24 205 217 11 66 76 78 160 90 191 85 226 125 74 168 63 182 209 136 101 234 244 229 204 235 109 163 194 175 43 144 70 174 119 52 121 62 32 236 250Table 3
The S-boxS917,3135,138,8,D generated by using the diffusion ordering.
138 139 82 20 60 65 51 227 172 106 203 134 94 228 247 201 8 239 41 9 161 74 194 175 167 90 84 195 24 136 108 10 191 252 0 144 251 210 117 178 19 233 118 120 83 205 11 235 18 181 109 130 100 16 207 163 145 61 184 21 151 129 86 223 221 193 229 222 165 34 30 46 45 180 48 177 243 23 186 212 248 128 114 28 35 56 209 15 53 112 170 142 85 49 141 52 122 123 217 115 66 202 63 101 71 32 87 224 135 231 208 6 146 232 150 72 113 192 47 127 1 176 188 237 131 244 156 37 111 152 5 93 50 75 121 33 97 154 2 140 253 153 199 14 246 91 119 95 211 99 102 240 59 116 38 73 22 62 182 185 230 55 174 137 255 124 26 147 241 39 3 7 149 242 197 219 245 110 157 29 249 226 54 162 81 43 179 166 98 158 96 69 196 78 57 44 171 67 31 103 126 250 88 70 218 17 190 13 234 160 89 164 107 76 148 12 64 132 68 77 58 204 25 216 225 27 40 125 183 105 80 168 187 254 214 215 143 189 133 155 200 206 213 104 92 198 236 220 42 36 159 169 173 79 238 4Table 4
The S-boxS3917,210,138,8,M generated by using the modulo diffusion ordering.
190 1 122 128 83 139 189 20 7 27 82 116 207 181 152 69 18 252 206 235 85 88 171 123 180 236 120 35 233 125 149 15 51 89 127 23 173 106 144 117 202 36 71 196 138 158 70 145 210 162 25 110 28 38 250 191 221 160 39 198 124 178 114 246 150 98 226 183 179 48 12 40 68 230 255 228 62 30 113 108 72 52 81 211 155 212 79 241 137 56 9 232 22 103 229 84 26 248 49 225 115 166 78 87 169 148 92 209 188 119 102 55 218 176 73 201 59 134 17 131 146 91 253 42 172 44 32 86 186 76 213 157 94 37 109 203 142 242 132 29 227 34 105 104 224 77 223 11 3 192 141 216 112 58 0 63 234 90 45 5 220 193 151 47 31 121 2 251 41 168 244 60 95 67 93 74 237 197 129 130 159 170 65 143 164 133 219 135 222 50 247 161 174 14 16 53 195 24 245 21 136 8 240 96 175 208 97 80 57 46 238 64 214 217 75 10 243 19 239 4 43 165 167 205 199 249 254 187 33 13 99 126 6 107 163 100 66 215 231 101 194 54 184 154 177 185 118 182 140 147 61 204 200 111 156 153


#### 4.1.1. Linear Attacks

For a secure S-box it is necessary to have high security against linear cryptanalysis. The security of ann×n S-box S against linear attacks is quantified by computing its linear approximation probability LAP(S), non-linearity NL(S), and algebraic complexity AC(S).Thelinear approximation probability LAP(S) is an approximation of S by calculating the coincidence between input and output bits. For α,β∈GF(2n)∖{0}, the mathematical expression of LAP(S) is(15)LAPS=maxα,β#x∈GF2n∣x·α=Sx·β2n-12,where “·” is the dot product over GF(2).Thenon-linearity NL(S) is the minimum distance of S from all affine transformations on the Galois field GF(2n), i.e.,(16)NLS=minα,β,y⁡x∈GF2n∣α·Sx≠β·x⊕y,where α∈GF(2n), β∈GF(2n)∖{0}, y∈GF(2), and “⊕” is the addition over GF(2).Thealgebraic complexity AC(S) is the number of non-zero coefficients in the linear polynomial [35] representation of S.An S-boxS is said to be highly secure against linear attacks if its LAP(S) is small, while NL(S) and AC(S) are large. The LAP, NL and AC of the listed S-boxes are presented in Table 5. It is clear from the table that the LAP of the proposed S-boxes is low, while their NL and AC are high enough to resist the linear attacks efficiently. Note that the average value of LAP of the proposed S-boxes is 0.1445 which is less than that of the S-boxes in [21, 22, 27, 31], while their average NL and AC are 106 and 254 which are higher than that of [20, 26, 27, 29, 31–33] and [28, 30, 31], respectively. This implies that the proposed method is capable of generating S-boxes with high security against linear attacks than some of the listed S-boxes.Table 5
Comparison of the cryptographic properties of some of the newly generated S-boxes with some of the existing S-boxes.
S-boxes Linear Attacks DAP Analysis of Boolean Functions LAP NL AC  SAC(max) SAC(min) BIC(max) BIC(min) Ref. [20] 0.1406 104 255 0.0391 0.6250 0.3906 0.5313 0.4707 Ref. [21] 0.1484 106 254 0.0391 0.5781 0.4375 0.5352 0.4648 Ref. [22] 0.1484 106 255 0.0391 0.6406 0.4063 0.5371 0.4707 Ref. [26] 0.1328 103 255 0.0391 0.5703 0.3984 0.5352 0.4727 Ref. [27] 0.1484 102 254 0.0391 0.6094 0.3750 0.5215 0.4707 Ref. [28] 0.1406 106 251 0.0391 0.5938 0.4375 0.5313 0.4648 Ref. [29] 0.109 104 255 0.0469 0.5930 0.3900 0.499 0.454 Ref. [30] 0.062 112 9 0.0156 0.5620 0.4530 0.504 0.48 Ref. [31] 0.2109 74 253 0.0547 0.6875 0.1094 0.5508 0.4023 Ref. [32] 0.1328 100 255 0.0547 0.6094 0.4219 0.5313 0.4746 Ref. [33] 0.1328 100 255 0.0391 0.5936 0.4219 0.5371 0.4688 Ref. [34] 0.125 110 255 0.0391 05625 0.4375 0.5547 0.4727 S3917,353,168,8,N 0.1875 106 253 0.0391 0.6094 0.4063 0.5273 0.4648 S 3917,3135,13 8,8 , D 0.1484 106 255 0.0391 0.5625 0.4218 0.5195 0.4648 S3917,210,138,8,M 0.1328 106 255 0.0391 0.5781 0.3906 0.5352 0.4648 S5003,3666,58,8,N 0.1328 106 255 0.0391 0.6406 0.4062 0.5213 0.4727 S5003,480,228,8,D 0.1328 106 254 0.0391 0.5938 0.4375 0.5352 0.4766 S5003,2427,58,8,M 0.1328 106 254 0.0391 0.5938 0.4063 0.5352 0.4727


#### 4.1.2. Differential Attacks

In these attacks, the S-boxS is approximated by understanding the effect of input differentials on the outputs. Thedifferential approximation probability DAP(S) of S is a well-known method to measure its resistance against differential attacks. It is computed by finding the coincidence between the difference of outputs and the inputs differing with some value. For din,dout∈GF(2n),(17)DAPS=maxdin,dout#x∈GF2n∣Sx⊕din-Sx=dout2n.The smaller is the DAP(S), the higher is the resistance of S against differential attacks. The results of this test for the listed S-boxes are given in Table 5. The DAP of the newly generated S-boxes is 0.0391, while the DAP of the S-boxes in [20–22, 26–28, 31–34] is at least 0.0391. Thus it follows that S-boxes based on the presented technique have high resistance against differential attacks than the listed S-boxes.


#### 4.1.3. Analysis of Boolean Functions

It is essential for a secure S-box to create confusion/diffusion in the data up to a certain level [1]. The confusion/diffusion creation capabilities of an S-box S are measured by analyzing its Boolean functions. Thestrict avalanche criterion (SAC) and thebit independence criterion (BIC) are the two standard methods to analyze these capabilities. Let 1≤i,j≤n,Si be i-th Boolean function of S and αj∈GF(2n) with weight w(αj)=1. The SAC of S is implemented by computing the matrix MS=[mij]i,j=1i,j=n, where(18)mij=12n∑x∈GF2nwSix⊕αj⊕Six.Similarly, the BIC is applied by calculating the matrix BS=[bij]i,j=1i,j=n, where(19)bij=12n∑x∈GF2n1≤k≤8wSix⊕αj⊕Six⊕Skx+αj⊕Skx.An S-box satisfies the SAC and the BIC if all non-zero entries of MS and BS are close to 0.5. The results of these tests are represented by listing the maximum and minimum non-zero values of their matrices in Table 5. The average of maximum and minimum values of SAC and BIC of the newly constructed S-boxes are 0.5963 and 0.4114 and 0.52895 and 0.4694, respectively. This implies that the entries of MS and BS are approaching the optimal value 0.5. Hence, it is evident from the experiments that the proposed S-box design method is capable of generating cryptographically secure S-boxes.


### 4.2. Statistical Analysis

Statistical analyses are performed on the proposed scheme to quantify its efficiency for the generation of dynamical S-boxes for the encryption of highly correlated data.


#### 4.2.1. Distinct S-Boxes

An S-box generation technique is said to be good for the generation of dynamical S-boxes and highly resistive against the brute force attack, if it can generate a large number of distinct S-boxes. For a given primep and for each EC Ep,b, we have generated all distinct S-boxes by using all ECs isomorphic to Ep,b. The number of distinct S-boxes for some primes is listed in Table 6.Table 6
Comparison of the number of all distinct8×8 S-boxes generated by the proposed method and some of the existing methods over ECs on some primes.
p 257 263 269 281 293 Distinct S-boxes by the proposed method due the ordering N 65536 68644 71824 78400 85264 D 65536 68644 71824 78400 85264 M 65536 68644 71824 78400 85264  Distinct S-boxes by [20, 21] 0  Distinct S-boxes by [22]  256 262 268 280 292Note that, with the increase in the value ofp, the number of S-boxes generated by the proposed method also increases. Thus, by choosing some large prime, the proposed method can generate a large number of dynamic S-boxes, and therefore it can easily resist the brute force attacks. For the comparison, the maximum possible number of S-boxes that can be generated by the other schemes [20–22] over an EC is also listed in Table 6. It is evident from Table 6 that the proposed method is more suitable for the generation of dynamic S-boxes than the listed schemes.


#### 4.2.2. Correlation Test

An S-box design technique is good for the encryption of highly correlated data, if its S-boxes can generate enough confusion/diffusion in the data. The confusion/diffusion creation capability of an S-box scheme can be evaluated by computing the correlation coefficient (CC) and the number of fixed points in its S-boxes. The CCs of distinct S-boxes for some values ofp and b are shown in Figure 1. For each listed p and b, the S-boxes are indexed in an increasing order with respect to their isomorphism parameter t.Figure 1
Correlation analysis.
(a)
p = 257, b=41, and t=1 - 256 (b)
p = 293, b=41, and t=1 - 292 (c)
p = 521, b=41, and t=1 - 520 (d)
p = 839, b=188, and t=1 - 838The average CCs between the S-boxes in Figures1(a)–1(d) are 0.0085, 0.0026, 0.0015, and 0.00034, respectively, which are very close to 0. Therefore, the newly generated S-boxes are highly uncorrelated. Furthermore, we have calculated the average number of fixed points in all S-boxes for the primes used in Table 6. The results are shown in Table 7.Table 7
Comparison of the average number of the fixed points over all distinct8×8 S-boxes for some primes.
p 257 263 269 281 293 Avg. # fixed points by the proposed method and ordering N 0.9929 0.9979 1.0061 0.9976 0.9912 D 1.0554 1.0828 1.0643 1.0687 1.0782 M 1.0001 0.9991 1.0018 0.9998 0.9970  Avg. # fixed points by [22]  0.9766 1.0611 0.9291 1.1107 1.2089Experimental results show that the average number of the fixed points generated by the proposed method is at most 1 (by rounding to the nearest integer). Hence, by correlation test and fixed point test, it is evident that the proposed S-box design technique is capable of generating high confusion/diffusion in a highly correlated data.


### 4.3. Complexity Analysis

It is necessary for a good S-box design scheme to generate secure S-boxes efficiently. By Lemma4, the time complexity of the proposed method for the generation of 8×8 S-box is O(log⁡p), where p is the underlying prime. A comparison of the time complexity of different S-box schemes over ECs is given in Table 8. It is evident from the comparison that the proposed S-box generation method is efficient than the techniques in [20, 21].Table 8
Comparison of time complexity of different S-box schemes over ECs.
S-box [20] [21] [22] Proposed method  Time complexity O ( p ) O ( p ) O ( 1 ) O(log⁡p)


## 4.1. Security Analysis

We generated the S-boxesS3917,353,168,8,NS3917,3135,138,8,DS3917,210,138,8,MS5003,3666,58,8,NS5003,480,228,8,D, and S5003,2427,58,8,M by sorting the ECs in non-decreasing order with respect toN,D, andM orderings for the security analysis. The S-boxes S3917,353,168,8,NS3917,3135,138,8,D and S3917,210,138,8,M are presented in Tables 2–4, respectively. A comparison of the experimental results with the strongest S-boxes generated by the algorithms in [20–22, 26–34] is also conducted in this section.Table 2
The S-boxS3917,353,168,8,N generated by using the natural ordering.
126 94 73 41 171 110 86 199 215 27 203 3 227 154 55 40 21 113 10 88 150 100 177 35 202 91 211 184 99 146 198 206 147 71 56 46 228 54 84 161 239 61 31 238 192 225 183 137 42 241 193 222 253 7 50 255 254 208 106 164 127 169 246 19 170 48 12 252 231 45 116 233 17 18 87 190 36 219 82 72 214 134 58 96 0 210 243 81 5 30 221 97 34 47 181 200 67 29 180 16 111 77 189 130 115 162 185 186 28 93 135 240 195 159 138 37 108 151 140 201 107 38 247 196 179 230 145 242 237 25 98 64 26 218 132 8 172 131 22 152 53 187 89 166 69 245 65 148 155 68 9 102 104 120 188 20 1 129 103 124 23 6 251 142 60 14 117 15 92 157 123 158 112 141 95 139 2 79 178 39 133 173 213 51 216 197 122 57 207 232 59 223 128 212 224 105 156 4 13 83 176 248 249 143 114 118 49 80 44 153 165 149 220 75 167 33 24 205 217 11 66 76 78 160 90 191 85 226 125 74 168 63 182 209 136 101 234 244 229 204 235 109 163 194 175 43 144 70 174 119 52 121 62 32 236 250Table 3
The S-boxS917,3135,138,8,D generated by using the diffusion ordering.
138 139 82 20 60 65 51 227 172 106 203 134 94 228 247 201 8 239 41 9 161 74 194 175 167 90 84 195 24 136 108 10 191 252 0 144 251 210 117 178 19 233 118 120 83 205 11 235 18 181 109 130 100 16 207 163 145 61 184 21 151 129 86 223 221 193 229 222 165 34 30 46 45 180 48 177 243 23 186 212 248 128 114 28 35 56 209 15 53 112 170 142 85 49 141 52 122 123 217 115 66 202 63 101 71 32 87 224 135 231 208 6 146 232 150 72 113 192 47 127 1 176 188 237 131 244 156 37 111 152 5 93 50 75 121 33 97 154 2 140 253 153 199 14 246 91 119 95 211 99 102 240 59 116 38 73 22 62 182 185 230 55 174 137 255 124 26 147 241 39 3 7 149 242 197 219 245 110 157 29 249 226 54 162 81 43 179 166 98 158 96 69 196 78 57 44 171 67 31 103 126 250 88 70 218 17 190 13 234 160 89 164 107 76 148 12 64 132 68 77 58 204 25 216 225 27 40 125 183 105 80 168 187 254 214 215 143 189 133 155 200 206 213 104 92 198 236 220 42 36 159 169 173 79 238 4Table 4
The S-boxS3917,210,138,8,M generated by using the modulo diffusion ordering.
190 1 122 128 83 139 189 20 7 27 82 116 207 181 152 69 18 252 206 235 85 88 171 123 180 236 120 35 233 125 149 15 51 89 127 23 173 106 144 117 202 36 71 196 138 158 70 145 210 162 25 110 28 38 250 191 221 160 39 198 124 178 114 246 150 98 226 183 179 48 12 40 68 230 255 228 62 30 113 108 72 52 81 211 155 212 79 241 137 56 9 232 22 103 229 84 26 248 49 225 115 166 78 87 169 148 92 209 188 119 102 55 218 176 73 201 59 134 17 131 146 91 253 42 172 44 32 86 186 76 213 157 94 37 109 203 142 242 132 29 227 34 105 104 224 77 223 11 3 192 141 216 112 58 0 63 234 90 45 5 220 193 151 47 31 121 2 251 41 168 244 60 95 67 93 74 237 197 129 130 159 170 65 143 164 133 219 135 222 50 247 161 174 14 16 53 195 24 245 21 136 8 240 96 175 208 97 80 57 46 238 64 214 217 75 10 243 19 239 4 43 165 167 205 199 249 254 187 33 13 99 126 6 107 163 100 66 215 231 101 194 54 184 154 177 185 118 182 140 147 61 204 200 111 156 153


### 4.1.1. Linear Attacks

For a secure S-box it is necessary to have high security against linear cryptanalysis. The security of ann×n S-box S against linear attacks is quantified by computing its linear approximation probability LAP(S), non-linearity NL(S), and algebraic complexity AC(S).Thelinear approximation probability LAP(S) is an approximation of S by calculating the coincidence between input and output bits. For α,β∈GF(2n)∖{0}, the mathematical expression of LAP(S) is(15)LAPS=maxα,β#x∈GF2n∣x·α=Sx·β2n-12,where “·” is the dot product over GF(2).Thenon-linearity NL(S) is the minimum distance of S from all affine transformations on the Galois field GF(2n), i.e.,(16)NLS=minα,β,y⁡x∈GF2n∣α·Sx≠β·x⊕y,where α∈GF(2n), β∈GF(2n)∖{0}, y∈GF(2), and “⊕” is the addition over GF(2).Thealgebraic complexity AC(S) is the number of non-zero coefficients in the linear polynomial [35] representation of S.An S-boxS is said to be highly secure against linear attacks if its LAP(S) is small, while NL(S) and AC(S) are large. The LAP, NL and AC of the listed S-boxes are presented in Table 5. It is clear from the table that the LAP of the proposed S-boxes is low, while their NL and AC are high enough to resist the linear attacks efficiently. Note that the average value of LAP of the proposed S-boxes is 0.1445 which is less than that of the S-boxes in [21, 22, 27, 31], while their average NL and AC are 106 and 254 which are higher than that of [20, 26, 27, 29, 31–33] and [28, 30, 31], respectively. This implies that the proposed method is capable of generating S-boxes with high security against linear attacks than some of the listed S-boxes.Table 5
Comparison of the cryptographic properties of some of the newly generated S-boxes with some of the existing S-boxes.
S-boxes Linear Attacks DAP Analysis of Boolean Functions LAP NL AC  SAC(max) SAC(min) BIC(max) BIC(min) Ref. [20] 0.1406 104 255 0.0391 0.6250 0.3906 0.5313 0.4707 Ref. [21] 0.1484 106 254 0.0391 0.5781 0.4375 0.5352 0.4648 Ref. [22] 0.1484 106 255 0.0391 0.6406 0.4063 0.5371 0.4707 Ref. [26] 0.1328 103 255 0.0391 0.5703 0.3984 0.5352 0.4727 Ref. [27] 0.1484 102 254 0.0391 0.6094 0.3750 0.5215 0.4707 Ref. [28] 0.1406 106 251 0.0391 0.5938 0.4375 0.5313 0.4648 Ref. [29] 0.109 104 255 0.0469 0.5930 0.3900 0.499 0.454 Ref. [30] 0.062 112 9 0.0156 0.5620 0.4530 0.504 0.48 Ref. [31] 0.2109 74 253 0.0547 0.6875 0.1094 0.5508 0.4023 Ref. [32] 0.1328 100 255 0.0547 0.6094 0.4219 0.5313 0.4746 Ref. [33] 0.1328 100 255 0.0391 0.5936 0.4219 0.5371 0.4688 Ref. [34] 0.125 110 255 0.0391 05625 0.4375 0.5547 0.4727 S3917,353,168,8,N 0.1875 106 253 0.0391 0.6094 0.4063 0.5273 0.4648 S 3917,3135,13 8,8 , D 0.1484 106 255 0.0391 0.5625 0.4218 0.5195 0.4648 S3917,210,138,8,M 0.1328 106 255 0.0391 0.5781 0.3906 0.5352 0.4648 S5003,3666,58,8,N 0.1328 106 255 0.0391 0.6406 0.4062 0.5213 0.4727 S5003,480,228,8,D 0.1328 106 254 0.0391 0.5938 0.4375 0.5352 0.4766 S5003,2427,58,8,M 0.1328 106 254 0.0391 0.5938 0.4063 0.5352 0.4727


### 4.1.2. Differential Attacks

In these attacks, the S-boxS is approximated by understanding the effect of input differentials on the outputs. Thedifferential approximation probability DAP(S) of S is a well-known method to measure its resistance against differential attacks. It is computed by finding the coincidence between the difference of outputs and the inputs differing with some value. For din,dout∈GF(2n),(17)DAPS=maxdin,dout#x∈GF2n∣Sx⊕din-Sx=dout2n.The smaller is the DAP(S), the higher is the resistance of S against differential attacks. The results of this test for the listed S-boxes are given in Table 5. The DAP of the newly generated S-boxes is 0.0391, while the DAP of the S-boxes in [20–22, 26–28, 31–34] is at least 0.0391. Thus it follows that S-boxes based on the presented technique have high resistance against differential attacks than the listed S-boxes.


### 4.1.3. Analysis of Boolean Functions

It is essential for a secure S-box to create confusion/diffusion in the data up to a certain level [1]. The confusion/diffusion creation capabilities of an S-box S are measured by analyzing its Boolean functions. Thestrict avalanche criterion (SAC) and thebit independence criterion (BIC) are the two standard methods to analyze these capabilities. Let 1≤i,j≤n,Si be i-th Boolean function of S and αj∈GF(2n) with weight w(αj)=1. The SAC of S is implemented by computing the matrix MS=[mij]i,j=1i,j=n, where(18)mij=12n∑x∈GF2nwSix⊕αj⊕Six.Similarly, the BIC is applied by calculating the matrix BS=[bij]i,j=1i,j=n, where(19)bij=12n∑x∈GF2n1≤k≤8wSix⊕αj⊕Six⊕Skx+αj⊕Skx.An S-box satisfies the SAC and the BIC if all non-zero entries of MS and BS are close to 0.5. The results of these tests are represented by listing the maximum and minimum non-zero values of their matrices in Table 5. The average of maximum and minimum values of SAC and BIC of the newly constructed S-boxes are 0.5963 and 0.4114 and 0.52895 and 0.4694, respectively. This implies that the entries of MS and BS are approaching the optimal value 0.5. Hence, it is evident from the experiments that the proposed S-box design method is capable of generating cryptographically secure S-boxes.


## 4.1.1. Linear Attacks

For a secure S-box it is necessary to have high security against linear cryptanalysis. The security of ann×n S-box S against linear attacks is quantified by computing its linear approximation probability LAP(S), non-linearity NL(S), and algebraic complexity AC(S).Thelinear approximation probability LAP(S) is an approximation of S by calculating the coincidence between input and output bits. For α,β∈GF(2n)∖{0}, the mathematical expression of LAP(S) is(15)LAPS=maxα,β#x∈GF2n∣x·α=Sx·β2n-12,where “·” is the dot product over GF(2).Thenon-linearity NL(S) is the minimum distance of S from all affine transformations on the Galois field GF(2n), i.e.,(16)NLS=minα,β,y⁡x∈GF2n∣α·Sx≠β·x⊕y,where α∈GF(2n), β∈GF(2n)∖{0}, y∈GF(2), and “⊕” is the addition over GF(2).Thealgebraic complexity AC(S) is the number of non-zero coefficients in the linear polynomial [35] representation of S.An S-boxS is said to be highly secure against linear attacks if its LAP(S) is small, while NL(S) and AC(S) are large. The LAP, NL and AC of the listed S-boxes are presented in Table 5. It is clear from the table that the LAP of the proposed S-boxes is low, while their NL and AC are high enough to resist the linear attacks efficiently. Note that the average value of LAP of the proposed S-boxes is 0.1445 which is less than that of the S-boxes in [21, 22, 27, 31], while their average NL and AC are 106 and 254 which are higher than that of [20, 26, 27, 29, 31–33] and [28, 30, 31], respectively. This implies that the proposed method is capable of generating S-boxes with high security against linear attacks than some of the listed S-boxes.Table 5
Comparison of the cryptographic properties of some of the newly generated S-boxes with some of the existing S-boxes.
S-boxes Linear Attacks DAP Analysis of Boolean Functions LAP NL AC  SAC(max) SAC(min) BIC(max) BIC(min) Ref. [20] 0.1406 104 255 0.0391 0.6250 0.3906 0.5313 0.4707 Ref. [21] 0.1484 106 254 0.0391 0.5781 0.4375 0.5352 0.4648 Ref. [22] 0.1484 106 255 0.0391 0.6406 0.4063 0.5371 0.4707 Ref. [26] 0.1328 103 255 0.0391 0.5703 0.3984 0.5352 0.4727 Ref. [27] 0.1484 102 254 0.0391 0.6094 0.3750 0.5215 0.4707 Ref. [28] 0.1406 106 251 0.0391 0.5938 0.4375 0.5313 0.4648 Ref. [29] 0.109 104 255 0.0469 0.5930 0.3900 0.499 0.454 Ref. [30] 0.062 112 9 0.0156 0.5620 0.4530 0.504 0.48 Ref. [31] 0.2109 74 253 0.0547 0.6875 0.1094 0.5508 0.4023 Ref. [32] 0.1328 100 255 0.0547 0.6094 0.4219 0.5313 0.4746 Ref. [33] 0.1328 100 255 0.0391 0.5936 0.4219 0.5371 0.4688 Ref. [34] 0.125 110 255 0.0391 05625 0.4375 0.5547 0.4727 S3917,353,168,8,N 0.1875 106 253 0.0391 0.6094 0.4063 0.5273 0.4648 S 3917,3135,13 8,8 , D 0.1484 106 255 0.0391 0.5625 0.4218 0.5195 0.4648 S3917,210,138,8,M 0.1328 106 255 0.0391 0.5781 0.3906 0.5352 0.4648 S5003,3666,58,8,N 0.1328 106 255 0.0391 0.6406 0.4062 0.5213 0.4727 S5003,480,228,8,D 0.1328 106 254 0.0391 0.5938 0.4375 0.5352 0.4766 S5003,2427,58,8,M 0.1328 106 254 0.0391 0.5938 0.4063 0.5352 0.4727


## 4.1.2. Differential Attacks

In these attacks, the S-boxS is approximated by understanding the effect of input differentials on the outputs. Thedifferential approximation probability DAP(S) of S is a well-known method to measure its resistance against differential attacks. It is computed by finding the coincidence between the difference of outputs and the inputs differing with some value. For din,dout∈GF(2n),(17)DAPS=maxdin,dout#x∈GF2n∣Sx⊕din-Sx=dout2n.The smaller is the DAP(S), the higher is the resistance of S against differential attacks. The results of this test for the listed S-boxes are given in Table 5. The DAP of the newly generated S-boxes is 0.0391, while the DAP of the S-boxes in [20–22, 26–28, 31–34] is at least 0.0391. Thus it follows that S-boxes based on the presented technique have high resistance against differential attacks than the listed S-boxes.


## 4.1.3. Analysis of Boolean Functions

It is essential for a secure S-box to create confusion/diffusion in the data up to a certain level [1]. The confusion/diffusion creation capabilities of an S-box S are measured by analyzing its Boolean functions. Thestrict avalanche criterion (SAC) and thebit independence criterion (BIC) are the two standard methods to analyze these capabilities. Let 1≤i,j≤n,Si be i-th Boolean function of S and αj∈GF(2n) with weight w(αj)=1. The SAC of S is implemented by computing the matrix MS=[mij]i,j=1i,j=n, where(18)mij=12n∑x∈GF2nwSix⊕αj⊕Six.Similarly, the BIC is applied by calculating the matrix BS=[bij]i,j=1i,j=n, where(19)bij=12n∑x∈GF2n1≤k≤8wSix⊕αj⊕Six⊕Skx+αj⊕Skx.An S-box satisfies the SAC and the BIC if all non-zero entries of MS and BS are close to 0.5. The results of these tests are represented by listing the maximum and minimum non-zero values of their matrices in Table 5. The average of maximum and minimum values of SAC and BIC of the newly constructed S-boxes are 0.5963 and 0.4114 and 0.52895 and 0.4694, respectively. This implies that the entries of MS and BS are approaching the optimal value 0.5. Hence, it is evident from the experiments that the proposed S-box design method is capable of generating cryptographically secure S-boxes.


## 4.2. Statistical Analysis

Statistical analyses are performed on the proposed scheme to quantify its efficiency for the generation of dynamical S-boxes for the encryption of highly correlated data.


### 4.2.1. Distinct S-Boxes

An S-box generation technique is said to be good for the generation of dynamical S-boxes and highly resistive against the brute force attack, if it can generate a large number of distinct S-boxes. For a given primep and for each EC Ep,b, we have generated all distinct S-boxes by using all ECs isomorphic to Ep,b. The number of distinct S-boxes for some primes is listed in Table 6.Table 6
Comparison of the number of all distinct8×8 S-boxes generated by the proposed method and some of the existing methods over ECs on some primes.
p 257 263 269 281 293 Distinct S-boxes by the proposed method due the ordering N 65536 68644 71824 78400 85264 D 65536 68644 71824 78400 85264 M 65536 68644 71824 78400 85264  Distinct S-boxes by [20, 21] 0  Distinct S-boxes by [22]  256 262 268 280 292Note that, with the increase in the value ofp, the number of S-boxes generated by the proposed method also increases. Thus, by choosing some large prime, the proposed method can generate a large number of dynamic S-boxes, and therefore it can easily resist the brute force attacks. For the comparison, the maximum possible number of S-boxes that can be generated by the other schemes [20–22] over an EC is also listed in Table 6. It is evident from Table 6 that the proposed method is more suitable for the generation of dynamic S-boxes than the listed schemes.


### 4.2.2. Correlation Test

An S-box design technique is good for the encryption of highly correlated data, if its S-boxes can generate enough confusion/diffusion in the data. The confusion/diffusion creation capability of an S-box scheme can be evaluated by computing the correlation coefficient (CC) and the number of fixed points in its S-boxes. The CCs of distinct S-boxes for some values ofp and b are shown in Figure 1. For each listed p and b, the S-boxes are indexed in an increasing order with respect to their isomorphism parameter t.Figure 1
Correlation analysis.
(a)
p = 257, b=41, and t=1 - 256 (b)
p = 293, b=41, and t=1 - 292 (c)
p = 521, b=41, and t=1 - 520 (d)
p = 839, b=188, and t=1 - 838The average CCs between the S-boxes in Figures1(a)–1(d) are 0.0085, 0.0026, 0.0015, and 0.00034, respectively, which are very close to 0. Therefore, the newly generated S-boxes are highly uncorrelated. Furthermore, we have calculated the average number of fixed points in all S-boxes for the primes used in Table 6. The results are shown in Table 7.Table 7
Comparison of the average number of the fixed points over all distinct8×8 S-boxes for some primes.
p 257 263 269 281 293 Avg. # fixed points by the proposed method and ordering N 0.9929 0.9979 1.0061 0.9976 0.9912 D 1.0554 1.0828 1.0643 1.0687 1.0782 M 1.0001 0.9991 1.0018 0.9998 0.9970  Avg. # fixed points by [22]  0.9766 1.0611 0.9291 1.1107 1.2089Experimental results show that the average number of the fixed points generated by the proposed method is at most 1 (by rounding to the nearest integer). Hence, by correlation test and fixed point test, it is evident that the proposed S-box design technique is capable of generating high confusion/diffusion in a highly correlated data.


## 4.2.1. Distinct S-Boxes

An S-box generation technique is said to be good for the generation of dynamical S-boxes and highly resistive against the brute force attack, if it can generate a large number of distinct S-boxes. For a given primep and for each EC Ep,b, we have generated all distinct S-boxes by using all ECs isomorphic to Ep,b. The number of distinct S-boxes for some primes is listed in Table 6.Table 6
Comparison of the number of all distinct8×8 S-boxes generated by the proposed method and some of the existing methods over ECs on some primes.
p 257 263 269 281 293 Distinct S-boxes by the proposed method due the ordering N 65536 68644 71824 78400 85264 D 65536 68644 71824 78400 85264 M 65536 68644 71824 78400 85264  Distinct S-boxes by [20, 21] 0  Distinct S-boxes by [22]  256 262 268 280 292Note that, with the increase in the value ofp, the number of S-boxes generated by the proposed method also increases. Thus, by choosing some large prime, the proposed method can generate a large number of dynamic S-boxes, and therefore it can easily resist the brute force attacks. For the comparison, the maximum possible number of S-boxes that can be generated by the other schemes [20–22] over an EC is also listed in Table 6. It is evident from Table 6 that the proposed method is more suitable for the generation of dynamic S-boxes than the listed schemes.


## 4.2.2. Correlation Test

An S-box design technique is good for the encryption of highly correlated data, if its S-boxes can generate enough confusion/diffusion in the data. The confusion/diffusion creation capability of an S-box scheme can be evaluated by computing the correlation coefficient (CC) and the number of fixed points in its S-boxes. The CCs of distinct S-boxes for some values ofp and b are shown in Figure 1. For each listed p and b, the S-boxes are indexed in an increasing order with respect to their isomorphism parameter t.Figure 1
Correlation analysis.
(a)
p = 257, b=41, and t=1 - 256 (b)
p = 293, b=41, and t=1 - 292 (c)
p = 521, b=41, and t=1 - 520 (d)
p = 839, b=188, and t=1 - 838The average CCs between the S-boxes in Figures1(a)–1(d) are 0.0085, 0.0026, 0.0015, and 0.00034, respectively, which are very close to 0. Therefore, the newly generated S-boxes are highly uncorrelated. Furthermore, we have calculated the average number of fixed points in all S-boxes for the primes used in Table 6. The results are shown in Table 7.Table 7
Comparison of the average number of the fixed points over all distinct8×8 S-boxes for some primes.
p 257 263 269 281 293 Avg. # fixed points by the proposed method and ordering N 0.9929 0.9979 1.0061 0.9976 0.9912 D 1.0554 1.0828 1.0643 1.0687 1.0782 M 1.0001 0.9991 1.0018 0.9998 0.9970  Avg. # fixed points by [22]  0.9766 1.0611 0.9291 1.1107 1.2089Experimental results show that the average number of the fixed points generated by the proposed method is at most 1 (by rounding to the nearest integer). Hence, by correlation test and fixed point test, it is evident that the proposed S-box design technique is capable of generating high confusion/diffusion in a highly correlated data.


## 4.3. Complexity Analysis

It is necessary for a good S-box design scheme to generate secure S-boxes efficiently. By Lemma4, the time complexity of the proposed method for the generation of 8×8 S-box is O(log⁡p), where p is the underlying prime. A comparison of the time complexity of different S-box schemes over ECs is given in Table 8. It is evident from the comparison that the proposed S-box generation method is efficient than the techniques in [20, 21].Table 8
Comparison of time complexity of different S-box schemes over ECs.
S-box [20] [21] [22] Proposed method  Time complexity O ( p ) O ( p ) O ( 1 ) O(log⁡p)


## 5. Conclusion

An efficient method for the generation of a large number of distinct, uncorrelated, and cryptographically secure injectivem×n multiple S-boxes is presented in this paper. The proposed scheme uses an elliptic curve (EC) isomorphic to a given ordered Mordell elliptic curve (MEC) Ep,b over Fp, where p≡2 (mod 3). It is proved that the proposed method can be implemented efficiently in O(2n·log⁡n+log⁡p). An upper bound is derived on the number of S-boxes generated by the proposed method for the EC Ep,b. It is also shown that the upper bound can be achieved for the natural ordering if 2n≥(p+1)/2. Furthermore, a detailed security analysis and comparison of the proposed method with some of the existing schemes is conducted. Experimental results reveal that the newly developed method can efficiently generate cryptographically secure, dynamic, and uncorrelated S-boxes. Hence, the proposed method is secure for the encryption of highly correlated data.



---

*Source: 3421725-2018-12-02.xml*