ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.617232 J. Algebra Comb. Discrete Appl. 6(3) • 123–134 Received: 4 July 2018 Accepted: 23 April 2019 Journal of Algebra Combinatorics Discrete Structures and Applications Bijective S-boxes of different sizes obtained from quasi-cyclic codes∗ Research Article Dusan Bikov, Iliya Bouyukliev, Stefka Bouyuklieva Abstract: The aim of this paper is to construct S-boxes of different sizes with good cryptographic properties. An algebraic construction for bijective S-boxes is described. It uses quasi-cyclic representations of the binary simplex code. Good S-boxes of sizes 4, 6, 8, 9, 10, 11, 12, 14, 15, 16 and 18 are obtained. 2010 MSC: 94A60, 11T71, 06E30, 94B05 Keywords: S-box, Simplex code, Quasi-cyclic codes 1. Introduction S-boxes are among the most common and essential components of the block ciphers. They provide block ciphers with resistance to known and potential cryptanalytic attacks. Therefore significant research effort has been made in developing methods for constructing S-boxes with optimal parameters and de- sirable cryptographic properties. There are well studied criteria that a good S-box has to fulfill to make the cipher resistant against differential and linear cryptanalyses. However, the construction of a crypto- graphically secure S-box is still a problem. For many years, properties as well as various techniques and methods for constructing good S-boxes have been investigated. The popular techniques for construct- ing S-boxes can be classified into three categories: algebraic structures, pseudo-random generation and different heuristic approaches. The aim of this paper is the constructions of bijective S-boxes of different sizes with good cryp- tographic properties. To do this, we use binary quasi-cyclic codes. We need a method to construct ∗ This work was supported by Bulgarian Science Fund under Contract DN-02-2/13.12.2016. Dusan Bikov; Faculty of Computer Science, Goce Delchev University, Shtip, Macedonia (email: du- san.bikov@ugd.edu.mk). Iliya Bouyukliev; Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, P.O.Box 323, 5000 Veliko Tarnovo, Bulgaria (email: iliyab@math.bas.bg). Stefka Bouyuklieva (Corresponding Author); Faculty of Mathematics and Informatics, St. Cyril and St. Method- ius University of Veliko Tarnovo, Bulgaria (email: stefka@ts.uni-vt.bg). 123 https://orcid.org/0000-0002-5145-5297 https://orcid.org/0000-0002-6730-1129 https://orcid.org/0000-0002-9557-4749 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 the codes, then effective algorithms to compute the parameters of the corresponding S-boxes, and fast programs that implement these algorithms. Increasing the size of input data leads to complicated computations that become more difficult and use too many objects. On the other hand, some of the algorithms are suitable for parallel implementation, which makes it possible to scan the intermediate objects at the same time, and thus allows the study of S-boxes of relatively large sizes. Therefore we have used the parallel library BoolSPLG [1] to realize the presented constructions and to calculate the parameters of the obtained S-boxes. For the programs we have used GPU computing model with CUDA. This allows us to interact directly with the GPUs and run programs on them, thus effectively utilizing the advantages of parallelization (many details about the parallel algorithms and programs are given in [2]). For this research, we have used a graphic card NVIDIA GeForce Titan X Pascal which we have as a donation from NVIDIA Corporation. The bijective S-boxes of size n = 4 have been extensively studied, classifications have been made, criteria of optimality are defined [12, 16, 17]. A general classification of all optimal S-boxes of size n = 4 is given in the work of Leander and Poschmann [12] in 2007, where the authors make a comprehensive analysis and find all classes of affine equivalent S-boxes for which they explore linearity, differential uniformity, and algebraic degree. Saarinen [16] in 2011 has extended the work of Leander and Poschmann, making a comprehensive analysis and finding all classes of linear equivalence. In the article [17] from 2015, a new classification of S-boxes of size n = 4 is made, dividing them into 183 different categories. Almost everything about the S-boxes with size n = 4 is clear, but the situation for larger sizes is radically different. S-boxes with size n = 8 are of particular interest due to the fact that these cryptographic primitives are embedded in the widely used cryptographic standards. It is still unclear whether there are S-boxes for n = 8 with nonlinearity greater than 112 or other better cryptographic properties. Therefore, a construction of S-boxes with better "optimal" cryptographic properties is a very topical issue. We construct bijective S-boxes of sizes 4, 6, 8, 9, 10, 11, 12, 14, 15, 16 and 18. The paper is organized as follows. Section 2 provides the necessary definitions and assertions required for our constructions and for the investigation of the obtained S-boxes. In Section 3 we describe the constructions that we use. The results are presented in Section 4. 2. Preliminaries S-boxes are also called multi-output Boolean functions or vectorial Boolean functions because of their connection with Boolean functions. They are defined as functions from Fn2 to F m 2 (also called (n,m)-functions or (n,m) S-boxes) where n and m are positive integers. An S-box can be represented by the vector (f1,f2, . . . ,fm), where fi are Boolean functions of n variables, called its coordinate functions, i = 1,2, . . . ,m. Then the m×2n matrix BS =   TT(f1)... TT(fm)   also represents the considered S-box, where TT(fi) is the Truth Table of the Boolean function fi, i = 1, . . . ,m [5]. An S-box is bijective (or invertible), if n = m and S is an invertible function. If an S-box is represented by the matrix BS, then it is bijective if and only if n = m and the columns of BS are all binary vectors of length n. To connect the codes with S-boxes, we consider the binary simplex codes. An [n,k] linear code C over the binary field F2 is a k-dimensional linear subspace of Fn2 . The Hamming weight of a vector in Fn2 is equal to the number of its nonzero coordinates, and the Hamming distance between two vectors is the number of positions in which they differ. We call C an [n,k,d] code if d is the minimum distance of the code, d = min{d(x,y), x,y ∈ C,x 6= y}. Two binary codes of length n are equivalent if there is a permutation σ ∈ Sn which maps one code to the other. Let GS be an n× (2n −1) binary matrix whose columns are all nonzero binary vectors of length n. 124 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 The code generated by GS is called a binary simplex code and we denote it by Sn. This is a constant weight code with nonzero weight 2n−1 and its dual code is the [2n−1,2n−1−n,3] binary Hamming code (for more information see [14]). The simplex code Sn can be considered as an irreducible cyclic code. Moreover, if h(x) is any primitive polynomial (a minimal polynomial of a primitive element α of the field F2n over F2), the code with check polynomial h(x) is equivalent to the simplex code Sn [14]. The columns of GS can be considered as the binary representations of the integers 1, . . . ,2n − 1 which we denote by 1, . . . ,2n −1, respectively. Suppose that the columns of GS are ordered as GS = (1 T · · · 2n −1T ). Let GS = (0 T 1 T · · · 2n −1T ). Obviously, GS =   TT(x1)... TT(xn)   and so S n = 〈TT(x1), . . . ,TT(xn)〉, where S n is the extended simplex code (extended with a zero coordinate). This proves the following theorem that is very important in our research. Theorem 2.1. An S-box is invertible if and only if n = m and the matrix BS generates a [2n,n,2n−1] code equivalent to the extended simplex code S n. In order to study the cryptographic properties of an S-box related to the linearity, we need to consider all non-zero linear combinations of its coordinate functions, namely Sb = b ·S = b1f1⊕···⊕bmfm, where b = (b1, . . . ,bm) ∈ Fm2 , b 6= 0. These are the component functions of the considered S-box. The Truth Tables of the component functions are all nonzero linear combinations of the rows of matrix BS and so they coincide with the nonzero codewords of the linear code generated by BS. In the case of bijective S-box, instead of a generator matrix we can consider a (2n − 1) × 2n matrix whose rows are all nonzero codewords of the given extended simplex code (which are the component functions of the corresponding S-box). There are a few different definitions for equivalence of S-boxes but for all of them equivalent but different linear codes can lead to nonequivalent S-boxes with different characteristics. Therefore we consider different codes all of which are equivalent to S n, and these codes produce S-boxes with different cryptographic properties. Since the building blocks of an S-box are Boolean functions, we define in the beginning some of their parameters which are important for cryptography. Let f : Fn2 → F2 be a Boolean function of n variables. The functions of the form fa(x) = a1x1 ⊕a2x2 ⊕···⊕anxn = a ·x are linear, and fa(x)⊕b = a1x1 ⊕a2x2 ⊕···⊕anxn⊕b are affine functions, a = (a1, . . . ,an) ∈ Fn2 , b ∈ F2, x = (x1,x2, . . . ,xn). The Walsh coefficients of the Boolean function f are defined as fW (a) = ∑ x∈Fn2 (−1)f(x)⊕fa(x). The 2n-tuple (fW (0),fW (1), . . . ,fW (2n −1) is called the Walsh spectrum of the function f, the set of all Walsh coefficients is its Walsh distribution, and the maximum absolute value of an Walsh coefficient of f is its linearity Lin(f) = max{|fW (a)| | a ∈ Fn2}. Another important parameter which is closely connected with the linearity is the nonlinearity. Non- linearity nl(f) of the Boolean function f is the minimum Hamming distance from f to the nearest affine function: nl(f) = min{dH(f,g) | g − affine function}. The relation between the linearity and nonlinearity is given by the equality Lin(f) = 2n − 2nl(f) [4]. Obviously, the minimum linearity corresponds to maximum nonlinearity. The Parseval’s equality∑ a∈Fn2 (fW (a))2 = 22n gives that Lin(f) ≥ 2n/2 [4]. Functions attaining this lower bound are called bent functions. 125 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 The Walsh spectrum of S is defined as the collection of all Walsh spectra of its component functions. The linearity and nonlinearity of S are defined as Lin(S) = max b∈Fm2 \{0} Lin(b ·S), nl(S) = min b∈Fm2 \{0} nl(b ·S). The nonlinearity and the Walsh spectrum of a Boolean function can be calculated using linear codes. It is well known that the set of Truth Tables of all affine Boolean functions coincides with the set of codewords of the Reed-Muller code of first order RM(1,n), which is a linear [2n,n + 1,2n−1] code with a generator matrix G(RM(1,n)) =   TT(1) TT(x1) ... TT(xn)   . The code RM(1,n) is obtained from the extended simplex code by adding the all ones vector 1 to its generator matrix. This means that RM(1,n) consist of the codewords of S n and their complements, or RM(1,n) = S n ∪ (1 + S n). The nonlinearity of the Boolean function f is the Hamming distance from TT(f) to the Reed-Muller code RM(1,n), or nl(f) = dH(TT(f),RM(1,n)). This means that we can use algorithms for calculating the distance from a vector to a code (or for minimum distance of a linear code) to find the nonlinearity and linearity of a Boolean function without having the whole Walsh spectrum. If f is an affine function then nl(f) = 0, otherwise nl(f) is equal to the minimum distance of the linear code with a generator matrix Gf = ( G(RM(1,n)) TT(f) ) . This helps us to calculate the nonlinearity of an S-box as the minimum distance of the linear code generated by the matrix BS = ( G(RM(1,n)) BS ) . Let us recall that if there is a coordinate function Sb which is affine then nl(S) = 0. Other important parameters of an S-box are the algebraic degree deg(S), the differential uniformity δ and the autocorrelation AC(S). Any Boolean function f can be represented uniquely as a binary polynomial of n variables whose monomials have the form xi1xi2 · · ·xik, 1 ≤ i1 < i2 < · · · < ik ≤ n, 0 ≤ k ≤ n, which is called the algebraic normal form ANF of f. The degree of this polynomial is the algebraic degree of the Boolean function denoted by deg(f). The algebraic degree of an m×n S-box is equal to the minimum algebraic degree of the component functions of S, deg(S) = min{deg(b · S),b ∈ Fm2 \{0}}. Autocorrelation of the Boolean function f is defined by AC(f) = max{| ∑ x∈Fn2 (−1)f(x)⊕f(x⊕w)| | w ∈ Fn2}. The autocorrelation of an S-box is the maximal autocorrelation of its components functions, AC(S) = max{AC(b ·S),b ∈ Fm2 \{0}}. The differential uniformity of an (n×n) S-box S is defined by: δ = max α,β∈Fn2 ,α6=0 |{x ∈ Fn2 |S(x)⊕S(x⊕α) = β}|. An S-box should have a differential uniformity as low as possible. The smallest possible value of δ in the case of bijective S-boxes is 2. Summarized results for good S-boxes are presented in [9, 10]. 126 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 3. The considered constructions In this section we present the main definitions and properties of the linear codes that are important for our constructions. A linear code of length n is quasi-cyclic (QC) code if a cyclic shift of a codeword by m positions results in another codeword. Obviously, m must divide the length n of the code, and n/m is called index of the considered QC code. If m = 1 the code is cyclic so QC codes are a generalization of cyclic codes. Many quasi-cyclic codes have the largest minimum distance among the linear codes with given length and dimension. There are different methods to construct quasi-cyclic codes. A QC code of length lm and index l is generated by a block matrix such that each block is an m×m circulant. The structure of QC codes is studied in [6, 11, 13]. To connect the codes with S-boxes, we consider the binary simplex codes as quasi-cyclic codes. As we defined in Section 2, GS is the n× (2n −1) generator matrix of Sn such that the columns of GS are ordered as GS = (1 · · · 2n −1). We use two more constructions for the codes equivalent to Sn. Let K = F2n be a finite field, α be its primitive element, 2n − 1 = mr, 1 < m,r < 2n − 1, and β = αr. If G = 〈β〉 < K∗ then G is a cyclic group of order m and G,αG,α2G,.. . ,αr−1G are all different cosets of G in K∗. For our constructions, we use left circulant matrices and the trace map. The trace map Tr : K → F2 is defined as Tr(ξ) = ξ + ξ2 + ξ4 + · · ·+ ξ2 n−1 , ξ ∈ K. We present two constructions of quasi-cyclic codes. For the first construction, we need the left circulant m×m matrices Ca = (Tr(αmaβi+j))0≤i,j≤m−1, a = 0,1, . . . ,r−1, and the left circulant block matrix M1 =   C0 C1 . . . Cr−1 C1 C2 . . . C0 ... ... ... ... Cr−1 C0 . . . Cr−2   . (1) The second construction is similar to the first one but the constructed block matrix is not circulant. We use again left circulant matrices but these are Da = (Tr(αaβi+j))0≤i,j≤m−1, a = 0,1, . . . ,2r−2. We construct a block matrix M2 in the following way: M2 =   D0 D1 . . . Dr−1 D1 D2 . . . Dr ... ... ... ... Dr−1 Dr . . . D2r−2   . (2) There are two main differences between these two constructions. First, in the circulants Ca and Da we multiply the powers of β by αma and αa, respectively. Second, in the block matrix M1 we take the indexes of the circulants modulo r. The following theorem is important for our research. Both codes generated by M1 and M2 are quasi-cyclic. Theorem 3.1. The code whose nonzero codewords are the rows of the matrix M2 is equivalent to the simplex [2n−1 = mr,n,2n−1] code. If m and r are coprime, the same is true for the code whose nonzero codewords are the rows of the matrix M1. Proof. The proof consists of two parts. First, we will prove that the Hamming weight of each row of both matrices is 2n−1. Second, the sum of any two rows of M1 (respectively M2) is a row in the same matrix. This proves that the rows in any of both matrices are the nonzero codewords of a linear code of length 2n − 1 and dimension n. Moreover, all nonzero codewords of the corresponding code have the same weight 2n−1 and therefore it is a linear constant-weight [2n − 1,n,2n−1] code. Up to equivalence, the simplex code Sn is the unique code with these parameters for a given positive integer n. Consider the elements M1[i,j] and M2[i,j], 0 ≤ i,j ≤ 2n − 2. If i = mi1 + i2, j = mj1 + j2, 127 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 0 ≤ i1,j1 ≤ r −1, 0 ≤ i2,j2 ≤ m−1, then M2[i,j] = Di1+j1[i2,j2] = Tr(α r(i2+j2)+i1+j1) = Tr(α(i1+ri2)+(j1+rj2)), M1[i,j] = C(i1+j1)r [i2,j2] = Tr(α r(i2+j2)+m(i1+j1)) = Tr(α(mi1+ri2)+(mj1+rj2)), where (i1 + j1)r = (i1 + j1) mod r. If m and r are coprime, for a fixed i the exponents (mi1+ri2)+(mj′1+rj ′ 2) and (mi1+ri2)+(mj ′′ 1 +rj ′′ 2 ) are different for j′ = mj′1 + j ′ 2 6= j′′ = mj′′1 + j′′2 , where j′,j′′ ∈{0,1, . . . ,mr −1}. Hence the i-th row of M1 consists of the traces of all nonzero elements of the field K, and this holds for all i = 0,1, . . . ,mr−1. Since exactly half of the elements of the field have trace 1 and the other half (including 0) have trace 0, the Hamming weight of each row is 2n−1. For the matrix M2 the integers m and r are not necessarily coprime. It is easy to see that if j′1 + rj ′ 2 = j ′′ 1 + rj ′′ 2 , 0 ≤ j′1,j′′1 ≤ r −1, 0 ≤ j′2,j′′2 ≤ m−1, then j′1 − j ′′ 1 = r(j ′′ 2 − j ′ 2) ⇒ r | j ′ 1 − j ′′ 1 ⇒ j ′ 1 = j ′′ 1 ⇒ j ′ 2 = j ′′ 2 . Hence the i-th row of M2 consists of the traces of all nonzero elements of the field, and this holds for all i = 0,1, . . . ,mr −1. Take the s-th and the t-th rows of the matrix M1 (respectively M2), and s = ms1 +s2, t = mt1 +t2, 0 ≤ s1, t1 ≤ r −1, 0 ≤ s2, t2 ≤ m−1. Then M1[s] + M1[t] = (Tr(α (ms1+rs2)+(mj1+rj2)) + Tr(α(mt1+rt2)+(mj1+rj2)))j=0,...,mr−1 = (Tr(α(ms1+rs2)+(mj1+rj2) + α(mt1+rt2)+(mj1+rj2)))j=0,...,mr−1 = (Tr((α(ms1+rs2) + α(mt1+rt2))α(mj1+rj2)))j=0,...,mr−1. Since ms1 + rs2 6≡ mt1 + rt2 (mod mr), then α(ms1+rs2) + α(mt1+rt2) 6= 0 and so α(ms1+rs2) + α(mt1+rt2) = αc for some c ∈{0,1, . . . ,mr − 1}. If m and r are coprime, c = mc1 + rc2, 0 ≤ c1 ≤ r − 1, 0 ≤ c2 ≤ m−1. It follows that M1[s] + M1[t] = (Tr(α cαmj1+rj2))j=0,...,mr−1 = (Tr(α mc1+rc2αmj1+rj2))j=0,...,mr−1 = (Tr(αm(c1+j1)αr(c2+j2)))j=0,...,mr−1 = (Tr(α m(c1+j1)βc2+j2))j=0,...,mr−1 ⇒ M1[s] + M1[t] = (Cc1[c2],Cc1+1[c2], . . . ,Cc1−1[c2]). Hence M1[s] + M1[t] is equal to the c-th row of M1. In the similar way we obtain that M2[s] + M2[t] is equal to the c-th row of M2, where αs1+rs2 + αt1+rt2 = αc, 0 ≤ c ≤ mr −1. So we proved that the rows of the matrix Mi, i = 1,2, are all nonzero codewords in a linear code, equivalent to Sn (for M1 we need m and r to be coprime). Denote by C(M1) and C(M2) the codes generated by M1 and M2, respectively. The above theorem says that C(M1) ∼= C(M2) ∼= Sn. Let M1 be the matrix M1 extended with one zero column in the beginning, and C(M1) be the code whose codewords are the rows of M1 (the same for M2). Then any generator matrix of C(M1) can be considered as an invertible S-box. Since all these S-boxes generate the same code C(M1) and have the same component Boolean functions, they have the same linearity, nonlinearity, degree, autocorrelation and differential uniformity. Therefore it doesn’t matter which gen- erator matrix of C(M1) (or C(M2)) we consider, so we take the matrices G(Mi) whose rows are the first n linearly independent rows of Mi, i = 1,2. 128 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 We use the described constructions of quasi-cyclic codes to obtain S-boxes in two different ways. The constructed S-boxes are called here QCS-boxes. Moreover, we take a permutation π ∈ Sr which permutes the block-columns of M1 (or M2). Unfortunately, the QCS-boxes G(M1π) and G(M2π) do not have good nonlinearity. This construction is natural but looking for better results we transform the matrices M1 and M2. (C1) First construction: We describe this construction for the matrix M1, but we use it in the same way for M2. Let σ ∈ S2n permutes the columns of the matrix G(M1) into the vectors 0,1, . . . ,2n −1. Now we consider the QCS-box, represented by the matrix σ(G(M1π)). The nonlinearity of this QCS-box is equal to the minimum distance d of the code generated by the matrix G (π) 1 =   1 11 . . .10 G(M1) 0 G(M1π)   . This follows from the fact that σ maps the above matrix into  111 . . .1σ(G(M1)) σ(G(M1π))   = ( G(RM(1,n)) σ(G(M1π)) ) . The quasi-cyclic structure of the matrices provides a faster algorithm for calculating linearity of the obtained QCS-boxes. The code generated by G(π)1 is invariant under the action of the cyclic group 〈τ〉 where τ ∈ S2n is presented as a product of independent cycles in the following way τ = (1,2, . . . ,m)(m + 1, . . . ,2m) . . .(mr −r + 1, . . . ,mr). The group 〈τ〉 defines a relation of equivalence in the considered code (two codewords u and v are equivalent if u = τs(v), 0 ≤ s ≤ m− 1). To calculate the minimum distance d of the above code we need only one codeword from each equivalence class. We present this observation in the next proposition Proposition 3.2. Let A = (A0,A1, . . . ,Ar−1) and B = (B0,B1, . . . ,Br−1) be block matrices, where Ai and Bi are m × m circulants, i = 0,1, . . . ,r − 1. If a0,a1, . . . ,am−1 are the rows of A, and b0,b1, . . . ,bm−1 are the rows of B, then d(ai,bj) = d(ai+1,bj+1) for 0 ≤ i,j ≤ m−1 (i+ 1 and j + 1 are taken modulo m). Since fW (a) = 2n−2d(f,fa) [4], Proposition 3.2 shows that the Walsh distributions of all Boolean function in one equivalence class are the same. This allows us to calculate the linearity (the same for the other parameters) listing only r of the component functions of the considered QCS-box. (C2) Second construction: For each of the circulants C0,C1, . . . ,Cr−1 we reorder the columns in the following way: first we take the last column, then the previous one, and in the end the first one. In this way we obtain the circulants C′0, C ′ 1, . . . , C ′ r−1, which define the matrix G(M ′ 1). If Ca =   c (a) 1 c (a) 2 · · · c (a) m−1 c (a) m c (a) 2 c (a) 3 · · · c (a) m c (a) 1 ... ... ... ... ... c (a) m−1 c (a) m · · · c (a) m−3 c (a) m−2 c (a) m c (a) 1 · · · c (a) m−2 c (a) m−1   , then C ′ a =   c (a) m c (a) m−1 · · · c (a) 2 c (a) 1 c (a) 1 c (a) m · · · c (a) 3 c (a) 2 ... ... ... ... ... c (a) m−2 c (a) m−3 · · · c (a) m c (a) m−1 c (a) m−1 c (a) m−2 · · · c (a) 1 c (a) m   . 129 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 Hence C′a is a right circulant matrix, and since Ca = (Tr(α maβi+j))0≤i,j≤m−1, then C′a = (Tr(αmaβi−j−1))0≤i,j≤m−1, a = 0,1, . . . ,r − 1. So M′1 is a left circulant block matrix whose blocks are right circulants. We use G(M′1π), where π ∈ Sr is a permutation on the block-columns of G(M′1), but now we compute the minimum distance d of the code generated by the matrix G (π) 2 =   1 11 . . .10 G(M1) 0 G(M′1π)   . If σ is defined as in (C1) then d is the nonlinearity of the QCS-box represented by the matrix σ(G(M′1π)). This construction extends the first construction C1. Using such constructions we can easily compute the Walsh distributions of the considered QCS-boxes and take only those that have large nonlinearity. We apply these constructions to obtain n×n bijective S-boxes with sizes 4 ≤ n ≤ 18 such that 2n −1 is not prime. Remark 3.3. In our paper [3] we considered only the first construction technique and its application only in the case of 8×8 S-boxes. Now we extend our study to more construction methods with applications to bijective S-boxes of sizes 4, 6, 8, 9, 10, 11, 12, 14, 15, 16 and 18. 4. Constructed QCS-boxes In this section we present the constructed QCS-boxes, that have linearity close to the Parseval bound, small differential uniformity δ (δ ≥ 2), high algebraic degree and small autocorrelation AC(S), and compare them with the best known S-boxes. We use a fixed finite field with 2n elements, generated by a primitive binary polynomial g(x) of degree n, and take α = x. If we change the generator polynomial of the field, we can get different results, but we have not studied how the selected field affects the parameters of the constructed S-boxes. This is still an open problem as well as the equivalence of the constructed QCS-boxes with respect to an equivalence relation (affine, CCZ, or another equivalence relation). The obtained results are presented in tables. The first column shows the used construction (C1 or C2), the used matrix (M1 or M2) and the integers m and r, the next columns contain the values of the computed cryptographic parameters, and the last column gives the number of the constructed QCS-boxes in each of the cases. For r ≤ 15 we study the S-boxes for all permutations π ∈ Sr used as it is described in C1 and C2, otherwise we consider only a part of the permutations (in this cases the study of the S-boxes constructed from the matrices M1 and M2 using construction methods C1 and C2 is not completed - we put ∗ in the last column of the corresponding row in the table). In the tables we list only those S-boxes which have linearity Lin ≤ 2n/2+1. For example, if m = 5, r = 3, we have 3! = 6 permutations π but only three of the S-boxes constructed in the combination (C1, M1) have linearity 8 (the other three S-boxes have bigger linearity). All QCS-boxes with minimum linearity among the constructed S-boxes of even sizes have linearity Lin(S) = 2n/2+1 (respectively nonlinearity nl(S) = 2n−1 − 2n/2). This is the best known linearity for S-box of the corresponding sizes but it is far from the Parseval bound Lin(S) ≥ 2n/2. 1. n=4: A definition for optimal 4×4 S-boxes is given in [12]. Using our constructions and the field generated by the polynomial 1 + x + x4, we obtain many optimal S-boxes presented in Table 1. All of them have the same parameters Lin(S) = 8, nl(S) = 4, deg(S) = 3, AC(S) = 8, and δ = 4. 2. n=6: The used generator polynomial is g(x) = 1+x+x3 +x4 +x6. The constructed bijective 6×6 QCS-boxes with best cryptographic properties are given in Table 2. They have linearity 16, most of them have algebraic degree 5, all but one have differential uniformity 4, and their autocorrelations are 16, 32, 64. 130 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 Table 1. Bijective 4 × 4 QCS-boxes QCS-boxes Lin nl δ deg(S) AC(S) number C1, M1, m = 5,r = 3 8 4 4 3 8 3 C1, M1, m = 3,r = 5 8 4 4 3 8 60 C1, M2, m = 5,r = 3 8 4 4 3 8 3 C1, M2, m = 3,r = 5 8 4 4 3 8 28 C2, M1, m = 5,r = 3 8 4 4 3 8 3 C2, M1, m = 3,r = 5 8 4 4 3 8 60 C2, M2, m = 5,r = 3 8 4 4 3 8 6 C2, M2, m = 3,r = 5 8 4 4 3 8 28 3. n=8: In this case g(x) = 1+x+x3 +x5 +x8. Many of the constructed bijective 8×8 QCS-boxes for different values of m and r have parameters close or equal to the best known nonlinearity for this size, namely nl(S) = 112. This is the nonlinearity of the S-box of the most popular block cipher AES [8]. Our results are described in Table 3. Table 2. Bijective 6 × 6 QCS-boxes QCS-boxes Lin nl δ deg(S) AC(S) number C1, M1, m = 9,r = 7 16 24 4 5 16 7 16 24 4 3 32 7 16 24 4 2 64 7 C1, M2, m = 7,r = 9 16 24 8 4 24 1 C2, M1, m = 9,r = 7 16 24 4 5 16 7 C2, M1, m = 7,r = 9 16 24 4 5 16 18 C2, M2, m = 21,r = 3 16 24 4 5 16 1 C2, M2, m = 9,r = 7 16 24 4 5 16 1 C2, M2, m = 7,r = 9 16 24 4 5 16 1 4. n ≥ 10: We consider the sizes n = 10, n = 12, n = 14, n = 16 and n = 18. For these sizes we obtain QCS-boxes with nonlinearity nl(S) = 2n−1 −2n/2. The AES S-box have the same nonlinearity for n = 8 but these values are not so close to the Parseval bound nl(S) =≤ 2n−1 − 2n/2−1. The used generator polynomials of the considered fields, as well as the cryptographic parameters of the constructed S-boxes in this case are presented in Table 4. 5. n odd: For the odd values of n, we apply all our constructions for sizes n = 9, n = 11 and n = 15 but only the second construction gives bijective S-boxes with good cryptographic properties. We list them in Table 5. The used generator polynomials are 1+x5+x9, 1+x+x2+x3+x6+x7+x9+x10+x11 and 1 + x2 + x4 + x5 + x15, respectively. We use the procedures from the parallel library BoolSPLG [1] to design algorithms realizing the presented constructions. BoolSPLG is a CUDA library that includes algorithms for calculation of some cryptographic parameters and characteristics of Boolean and vectorial Boolean functions (S-boxes) (see 131 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 Table 3. Bijective 8 × 8 QCS-boxes S-boxes Lin nl δ deg(S) AC(S) number AES S-box [8] 32 112 4 7 32 / C1, M1, m = 17,r = 15 32 112 4 7 32 15 C1, M1, m = 15,r = 17 32 112 4 5 48 4* 32 112 4 5 56 4* C2, M1, m = 85,r = 3 32 112 4 7 32 3 C2, M1, m = 51,r = 5 32 112 4 7 32 5 C2, M1, m = 17,r = 15 32 112 4 7 32 15 C2, M1, m = 15,r = 17 32 112 4 7 32 1* C2, M2, m = 85,r = 3 32 112 4 7 32 1 C2, M2, m = 51,r = 5 32 112 4 7 32 1 C2, M2, m = 17,r = 15 32 112 4 7 32 1 [7] for more information about CUDA parallel computing platform). The advantage of using parallel algorithms is essential for bigger values of n (especially for n ≥ 14). For our calculations, we used a server with Intel Xeon E5-2640 processor that contains two graphics cards. The first graphics card is NVIDIA GeForce GTX TITAN [15], which has 2688 cores running at 837 MHz and 288.4 GB/sec memory bandwidth. The second graphics card is NVIDIA TITAN X Pascal [15], which has 3584 cores running at 1.5 GHz and 549 GB/sec memory bandwidth. We have used CUDA Toolkit 8.0 and developed environment MS Visual Studio 2012. All constructed QCS-boxes are available at the web page of the second author: http://www.moi.math.bas.bg/~iliya/. Each S-box is represented as a sequence of hexadecimal num- bers, representing the corresponding columns in the matrix BS. We give two examples. 1. The sequence (0,b,2,7,4,5,f,3,d,9,a,1,e,8,c,6) represents the S-box with BS =   0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 0   . We give also the values of n, m and r, the permutation π in word representation, and the parameters Lin(S), nl(S), AC(S) and δ. In this case n = 4, m = 5, r = 3, π = (1, 0, 2), Lin(S) = 8, nl(S) = 4, deg(S) = 3, AC(S) = 8, and δ = 4. 2. One of the obtained 6×6 S-boxes is 0,2f,17,25,2b,1c,32,f,3a,15,21,2e,1b,19,34,7,3d,33,2a,2c,30,9,37,2, 29,d,1d,c,5,1a,20,23,1e,a,39,1f,35,3,36,28,27,18,12,4,13,3b,b,1,14, 3f,6,11,e,24,26,16,3e,22,8,2d,3c,10,38,31. Its parameters are n = 6, m = 9, r = 7, π = (6, 5, 4, 3, 2, 1, 0), Lin(S) = 16, nl(S) = 24, deg(S) = 5, AC(S) = 16, δ = 4. Acknowledgment: We gratefully acknowledge the support of NVIDIA Corporation with the do- nation of the Titan X Pascal GPU used for this research. We also thank the anonymous reviewer for his/her valuable comments. 132 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 Table 4. Bijective QCS-boxes for n = 10, n = 12, n = 14, n = 16 and n = 18 QCS-boxes Lin nl δ deg(S) AC(S) number n = 10 g(x) = 1 + x3 + x4 + x8 + x10 C1, M1, m = 33,r = 31 64 480 4 9 64 1* C2, M1, m = 341,r = 3 64 480 4 9 64 3 C2, M1, m = 93,r = 11 64 480 4 9 64 11 C2, M1, m = 33,r = 31 64 480 4 9 64 1* C2, M2, m = 341,r = 3 64 480 4 9 64 1 C2, M2, m = 93,r = 11 64 480 4 9 64 1 n = 12 g(x) = 1 + x + x5 + x8 + x10 + x11 + x12 C1, M1, m = 65,r = 63 128 1984 4 11 128 1* C2, M1, m = 819,r = 5 128 1984 4 11 128 5 C2, M1, m = 585,r = 7 128 1984 4 11 128 7 C2, M1, m = 455,r = 9 128 1984 4 11 128 9 C2, M1, m = 315,r = 13 128 1984 4 11 128 13 C2, M2, m = 1365,r = 3 128 1984 4 11 128 1 C2, M2, m = 819,r = 5 128 1984 4 11 128 1 C2, M2, m = 585,r = 7 128 1984 4 11 128 1 C2, M2, m = 455,r = 9 128 1984 4 11 128 1 C2, M2, m = 315,r = 13 128 1984 4 11 128 1 n = 14 g(x) = 1 + x + x2 + x3 + x10 + x12 + x14 C1, M1, m = 129,r = 127 256 8064 4 13 256 1* C2, M1, m = 5461,r = 3 256 8064 4 13 256 3 C2, M2, m = 5461,r = 3 256 8064 4 13 256 1 n = 16 g(x) = 1 + x + x2 + x4 + x5 + x9 + x10 + x12 + x16 C1, M1, m = 257,r = 255 512 32512 4 15 512 1* C2, M1, m = 21845,r = 3 512 32512 4 15 512 3 C2, M1, m = 13107,r = 5 512 32512 4 15 512 5 C2, M2, m = 21845,r = 3 512 32512 4 15 512 1 C2, M2, m = 13107,r = 5 512 32512 4 15 512 1 n = 18 g(x) = 1 + x2 + x4 + x5 + x6 + x9 + x10 + x11 + x15 + x17 + x18 C1, M1, m = 513,r = 511 1024 130560 4 17 1024 1* Table 5. Bijective QCS-boxes for n = 9, n = 11 and n = 15 QCS-boxes Lin nl δ deg(S) AC(S) number C2, M1, n = 9, m = 73,r = 7 44 234 2 8 48 7 C2, M2, n = 9, m = 73,r = 7 44 234 2 8 48 1 C2, M1, n = 11, m = 89,r = 23 88 980 2 10 88 1* C2, M1, n = 15, m = 4681,r = 7 360 16204 2 14 360 7 C2, M2, n = 15, m = 4681,r = 7 360 16204 2 14 360 1 133 D. Bikov et al. / J. Algebra Comb. Discrete Appl. 6(3) (2019) 123–134 References [1] D. Bikov, I. Bouyukliev, BoolSPLG: A library with parallel algorithms for Boolean functions and S-boxes for GPU. [2] D. Bikov, I. Bouyukliev, Parallel Fast Walsh Transform Algorithm and its implementation with CUDA on GPUs, Cybernetics and Information Technologies, Cybernetics and Information Tech- nologies 18(5) (2018) 21–43. [3] I. Bouyukliev, D. Bikov, S. Bouyuklieva, S-boxes from binary quasi-cyclic codes, Electronic Notes in Discrete Mathematics 57 (2017) 67–72. [4] C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes, In: Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Crama, Hammer, Cambridge University Press, 2010. [5] C. Carlet, Vectorial Boolean Functions for Cryptography, In: Boolean Models and Methods in Math- ematics, Computer Science, and Engineering, Crama, Hammer, (Eds.), Cambridge University Press, 2010. [6] E. Z. Chen, New quasi-cyclic codes from simplex codes, IEEE Trans. Inform. Theory 53(3) (2007) 1193–1196. [7] CUDA Zone. [8] J.Daeman, V.Rijmen, The Design of Rijndael, AES–the advanced encryption standard, Springer- Verlag Berlin Heidelberg, 2002. [9] I. Hussain, T. Shah, M. A. Gondal, W. A. Khan, Construction of Cryptographically Strong 8 × 8 S-boxes, World Applied Sciences Journal 13 (2011) 2389–2395. [10] G. Ivanov, N. Nikolov, S. Nikova, Reversed genetic algorithms for generation of bijective S-boxes with good cryptographic properties, Cryptogr. Commun. 8(2) (2016) 247–276. [11] K. Lally, P. Fitzpatrick, Algebraic structure of quasi-cyclic codes, Discrete Applied Mathematics 111(1–2) (2001) 157–175. [12] G. Leander, A. Poschmann, On the Classification of 4 Bit S-Boxes, In: Carlet C., Sunar B. (eds) Arithmetic of Finite Fields. WAIFI 2007. Lecture Notes in Computer Science, vol 4547. Springer, Berlin, Heidelberg (2007) 159–176. [13] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: finite fields, IEEE Trans. Inform. Theory 47(7) (2001) 2751–2760. [14] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Ams- terdam 1977. [15] NVIDIA Data Center. [16] M. J. O. Saarinen, Cryptographic Analysis of all 4 × 4–bit S–boxes, In: Proceedings of the 18th International Conference on Selected Areas in Cryptography, ser. SAC 11. Springer-Verlag (2012) 118–133. [17] W. Zhang, Z. Bao, V. Rijmen, M. Liu, A New Classification of 4-bit Optimal S-boxes and Its Application to PRESENT, RECTANGLE and SPONGENT. In: Leander G. (eds) Fast Software Encryption. Lecture Notes in Computer Science, vol 9054. Springer, Berlin, Heidelberg (2015) 494– 515. 134 http://www.moi.math.bas.bg/moiuser/~data/Results/Crypto/BoolSPL.html http://www.moi.math.bas.bg/moiuser/~data/Results/Crypto/BoolSPL.html https://www.doi.org/10.2478/cait-2018-0018 https://www.doi.org/10.2478/cait-2018-0018 https://www.doi.org/10.2478/cait-2018-0018 https://doi.org/10.1016/j.endm.2017.02.012 https://doi.org/10.1016/j.endm.2017.02.012 https://doi.org/10.1109/TIT.2006.890727 https://doi.org/10.1109/TIT.2006.890727 https://developer.nvidia.com/cuda-zone/ https://mathscinet.ams.org/mathscinet-getitem?mr=1986943 https://mathscinet.ams.org/mathscinet-getitem?mr=1986943 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.390.7159 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.390.7159 https://doi.org/10.1007/s12095-015-0170-5 https://doi.org/10.1007/s12095-015-0170-5 https://doi.org/10.1016/S0166-218X(00)00350-4 https://doi.org/10.1016/S0166-218X(00)00350-4 https://doi.org/10.1007/978-3-540-73074-3_13 https://doi.org/10.1007/978-3-540-73074-3_13 https://doi.org/10.1007/978-3-540-73074-3_13 https://doi.org/10.1109/18.959257 https://doi.org/10.1109/18.959257 https://mathscinet.ams.org/mathscinet-getitem?mr=465509 https://mathscinet.ams.org/mathscinet-getitem?mr=465509 https://www.nvidia.com/en-us/data-center/ https://www.springer.com/gp/book/9783642284953 https://www.springer.com/gp/book/9783642284953 https://www.springer.com/gp/book/9783642284953 https://doi.org/10.1007/978-3-662-48116-5_24 https://doi.org/10.1007/978-3-662-48116-5_24 https://doi.org/10.1007/978-3-662-48116-5_24 https://doi.org/10.1007/978-3-662-48116-5_24 Introduction Preliminaries The considered constructions Constructed QCS-boxes References