# More Low Differential Uniformity Permutations overF22k with k Odd

Authors: Yue Leng; Jinyang Chen; Tao Xie
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Permutations with low differential uniformity, high algebraic degree, and high nonlinearity overF22k can be used as the substitution boxes for many block ciphers. In this paper, several classes of low differential uniformity permutations are constructed based on the method of choosing two permutations over F22k to get the desired permutations. The resulted low differential uniformity permutations have high algebraic degrees and nonlinearities simultaneously, which provide more choices for the substitution boxes. Moreover, some numerical examples are provided to show the efficacy of the theoretical results.


---

## Body

## 1. Introduction

Suppose thatn be a positive even integer. We always denote by F2n the finite field of even characteristic with degree n and F2n∗ the multiplicative group of nonzero elements of F2n. Every map from F2n to itself is called an n,n-function, and bijective n,n-function is called a permutation over F2n. It is well known that confusion introduced by Shannon [1] is one of the most generally accepted design principles for block ciphers and stream ciphers, which means making the relation between the ciphertext and the plaintext as complex as possible for the attacker. The substitution boxes (S-boxes) with good cryptographic properties are used to create confusion in block ciphers and often chosen to be permutations over F2n. As pointed out in [2], since it needs to resist the differential attack on the block cipher algorithm, the differential uniformity of those permutations as S-boxes is required to be as low as possible. The permutations as S-boxes should also have high algebraic degree to resist the higher order differential attack and high nonlinearity to resist the linear attack (see, for instance, [3, 4]).It is well known that the lowest differential uniformity of ann,n-function over F2n is not less than 2. Those n,n-functions with differential uniformity 2 are called almost perfect nonlinear (APN) function, which has many interesting properties studied in the last decades (see, for instance, [5–7] and references). However, it is difficult to find APN permutations over the finite field F2n for n≥6. Up to now, a few examples of APN permutations have been found over F26 [8–10]. Naturally, people pay more attention to those permutations with differential uniformity 4 or 6 for S-boxes, and a lot of work has been done (see, for instance, [11–25]). Although low differential uniformity permutations are not an optimal choice of S-boxes, they are still an efficient way to against differential attacks. For example, the famous advanced encryption standard (AES) chooses differential 4-uniformity permutation x−10−1:=0 as its S-box.The original differential 4-uniformity permutations select Gold functions [12], the Kasami functions [13], the inverse functions [15], and the Bracken–Leander functions [11]. In 2012, Bracken et al. [26] constructed a class of binomials as differential 4-uniformity permutations with high nonlinearity. Inspired by the idea of Carlet [27], Li and Wang [28] obtained a construction of differential 4-uniformity permutations over F2n from quadratic APN permutations over F2n+1. The modern method to construct differential 4-uniformity permutation is the switching method proposed by Dillon. In recent years, the power of this method has been shown in the construction of differential 4-uniformity permutations. Qu et al. in [21] constructed differential 4-uniformity permutations by composing the inverse function and permutations over F2n and, in [22], proved that the number of CCZ-inequivalent differential 4-uniformity permutations over F2n increases exponentially. For more details, the readers can refer to [14, 19, 23–25, 29, 30].Different from the above method, in [31, 32], some monomials with differential 6-uniformity over F2n for 17≤n≤31 are constructed and in the family of functions:(1)Gt=x2t−1x∈F2n,1<t<n.In 2014, Zha et al. [33] presented three classes of nonmonomial with differential 6-uniformity by modifying the image values of the Gold function. In recent years, more nonmonomial permutations of differential 6-uniformity are proposed. Tu et al. [34, 35] constructed several classes of differential 6-uniformity permutations by selecting the inverse function as a special type of rational functions over F2n.Inspired by the idea of [18], we construct some new low differential uniformity permutations. Compared with the previous similar works, our construction can provide a large number of CCZ-inequivalent classes of functions. Precisely, for any ε,s∈F4 and some U being a subset of F22k with an odd integer k, we prove that the permutations(2)Fx=x+ε−1+s,x∈U,x−1,x∈F22k\U,have low differential uniformity 4 or 6. It is pointed out here that all of differentially 6-uniform permutations in our construction are CCZ-inequivalent to the existing ones, and it is surprising that there are two new differential 4-uniformity permutations for k=3 CCZ-inequivalent to the previous ones mentioned above. Moreover, all these functions have the optimal algebraic degree and we get a lower bound of the high nonlinearity of F.The rest of this paper is organized as follows. In the next section, we recall some definitions and general properties of the differential uniformity, algebraic degree, and nonlinearity ofn,n-functions. In Section 3, we present a new construction of low differential uniformity permutations and discuss the differential uniformity of these permutations over F22k with k odd. In Section 4, we consider their other cryptographic properties. Finally, Section 5 concludes the paper.


## 2. Preliminaries

Letn be a positive even integer and F be an n,n-function. We know that any n,n-function can be uniquely represented as a univariate polynomial in F2nx:(3)Fx=∑i=02n−1αixi,where αi∈F2n, 0≤i≤2n−1. Let i∈ℤ+, t∈ℕ and i0,i1,…,it∈0,1. We say that i0,i1,…,it is the binary expansion of i if i=i020+i121+⋯+it2t and wti:=jij≠0,0≤j≤t is the 2-weight of i. The algebraic degree degF of Fx is defined as follows:(4)degF:=maxαi≠0wti0≤i≤2n−1.Ann,n-function F is affine if degF≤1. For any n,n-permutation F, it is known that degF≤n−1. If this upper bound is achieved, then F is said to have optimal algebraic degree.For ann,n-function F and a,b∈F2n∗×F2n, denote by δFa,b the number of solutions of the equation Fx+a+Fx=b. We call the multiset(5)∗δFa,ba,b∈F2n∗×F2n∗,the differential spectrum of F. The maximum value in the differential spectrum of F is called the differential uniformity of F and denoted by δ, and F is called a differential δ-uniform function [15]. Observe that if x is a solution of Fx+a+Fx=b, then x+a is also a solution of the equation, and then it follows that δF must be an even number greater than or equal to 2.Letn be a positive integer and k a divisor of n. The trace map Trknx from F2n onto its subfield F2k is defined by(6)Trknx:=x+x2k+x22k+⋯+x2n−k.In particular, fork=1, Trknx is called the absolute trace map and denoted by Trx simply.For ann,n-function Fx, the Walsh transform of the function F is defined as follows:(7)FWa,b:=∑x∈F2n−1TraFx+bx,a,b∈F2n∗×F2n.The multisets∗FWa,ba,b∈F2n∗×F2n∗ and ∗FWa,ba,b∈F2n∗×F2n∗ are called Walsh spectrum and extended Walsh spectrum of Fx, respectively. The nonlinearity of F is defined as follows:(8)NLF:=2n−1−12maxa,b∈F2n∗×F2nFWa,b.It is well known thatNLF≤2n−1−2n−1/2 when n is odd. For the case n even, 2n−1−2n/2 is conjectured to be an upper bound of NLF [36].For twon,n-functions G1x and G2x, if there exist two affine permutations A1x and A2x such that G1x=A1G2A2x, then G1x and G2x are called affine equivalent; if there exists an affine function Ax such that G1x=A1G2A2x+Ax, then G1x and G2x are called extended affine (EA) equivalent. If the graphs of G1x and G2x are EA-equivalent, then they are said to be Carlet–Charpin–Zinoviev (CCZ) equivalent, where the graph of Gx is x,Gxx∈F2n. It is known that EA-equivalence implies CCZ-equivalence, and the converse is not always right. Moreover, CCZ-equivalence and EA-equivalence preserve the extended Walsh spectrum and the differential spectrum, and EA-equivalence also preserves the algebraic degree when it is greater than 2 [37, 38].Definition 1.
LetHx and Gx be two permutations over F2n. Given α∈F2n, if there exist some positive integer t and some set C=α1,α2,…,αt of F2n with α1=α such that(9)Hα1=Gα2,…,Hαt−1=Gαt,Hαt=Gα1,then the t-subset C is called a t-cycle set of the function H related to the function G and we denote by Cα. Obviously, β∈Cα if and only if Cβ=Cα. All the t-cycle sets for 1≤t≤2n are also called cycle sets [18].
We still need some helpful lemmas. The following famous lemma reveals that the nonlinearity of the inverse function could achieve the upper bound2n−1−2n/2 of NLF.Lemma 1 (see [39]).
For any positive integern and any a,b∈F2n×F2n∗, the value of(10)∑x∈F2n−1Trax+bx−1,can take any integer divisible by 4 in the range −2n/2+1+1,2n/2+1+1.Lemma 2 (see [40]).
Letn be a positive integer. For any a,b,c∈F2n with ab≠0, the equation(11)ax2+bx+c=0,has two solutions in F2n if and only if Trac/b2=0.Lemma 3 (see [18]).
LetHx and Gx be two permutations over F2n. Then, the function(12)Fx=Hx,x∈U,Gx,x∈F2n\U,is a permutation over F2n if and only if U is a union of some cycle sets of Hx related to Gx.


## 3. Construction of Low Differential Uniformity Permutations

In this section, we always assume thatk≥3 is odd. For any ε,s∈F4, we select Hx=x+ε−1+s and Gx=x−1 and define Fx as(13)Fx=x+ε−1+s,x∈U,x−1,x∈F22k\U,where U is a disjoint union of the cycle set of Hx related to Gx.Firstly, we find all the cycle setsCα of Hx related to Gx for α∈F22k\F4, where Cα is as defined in Definition 1. In what follows, we always write that ω is a primitive element in F4.Lemma 4.
For anyα∈F22k\F4, the cycle set Cα of Hx related to Gx can be expressed as follows:(1)
Ifε=0,(14)Cα=α,s=0,α,α1+sα,s≠0.(2)
Ifε=1,(15)Cα=α,α+1,s=0,α,1+1α,1α+1,s=1,α,α+1s2+sα,1+s2α,s2α+1,s2+sαα+s2,otherwise.(3)
Ifε=ω,(16)Cα=α,α+ω,s=0,α,α+ωω2+α,ω+ωα,ωα+ω,ω2α+ωα+1,s=1,α,α+ωω+ωα,ω+1α,1α+ω,ω+ωα1+αω,s=ω,α,ω+ω2α,ω2α+ω,s=ω2.Proof.
By similarity, we only give the details of (1) and (2).
We first prove (1). Forε=0, obviously, Hx=x−1+s and Gx=x−1. When s=0, for any α∈F2n\F4, we have Hα=Gα. Therefore, the cycle set of Hx related to Gx is a 1-cycle set, i.e., Cα=α. When s+t≠0, we let α1:=α and conclude that α2=α/1+sα by Hα1=Gα2. It computes that Hα2=Gα directly. This shows that the cycle set of Hx related to Gx is a 2-cycle set and Cα=α,α/1+sα.
To show (2), we setα1=α. Since ε=1, we have Hx=x+1−1+s and Gx=x−1. When s=0, by Hα1=Gα2, we get α2=α+1. Then we also get Hα2=Gα. Therefore, the cycle set of Hx related to Gx is just a 2-cycle set and Cα=α,α+1. In the case of s=1, we calculate α2=1+1/α by Hα1=Gα2 and α3=1/α+1 by Hα2=Gα3. Furthermore, Hα3=Gα. It follows that the cycle set of Hx related to Gx is a 3-cycle set Cα=α,1+1/α,1/α+1. Similarly, we obtain that(17)Cα=α,α+1s2+sα,1+s2α,s2α+1,s2+sαα+s2,either s=ω or ω2.Remark 1.
Whenε=ω2, the cycle sets of Hx related to Gx are equivalent to Lemma 4 (3) since ω is a primitive element of F4if and only if ω2 is also a primitive element of F4.
Some properties of these cycle sets are listed as follows.Lemma 5.
LetCα and ε be the same as in Lemma 4. Then(a)
Cα+ε=Cα+ε.(b)
For anyη∈Cα, Cη=Cα.(c)
For anyα,β∈F2n\F4, Cα=Cβ; otherwise, Cα∩Cβ=∅.Proof.
For (a), by similarity, we only prove it forε=1. If s=0, it is easy to check that Cα+1=α+1,α+1+1=Cα+1. If s=1, we have(18)Cα+1=α+1,1+1α+1,1α=α+1,1+1α+1,1α+1+1=Cα+1.
And ifs=ω or s=ω2,(19)Cα+1=α+1,α1+sα,1+s2α+1,s2α,1+sαα+s=α+1,s2+sαα+s2+1,1+s2α+1,s2α+1+1,α+1s2+sα+1=Cα+1.
The proof of (b) is very simple and we omit the details.
To prove (c), we suppose thatCα∩Cβ≠∅. Then there exists γ∈Cα∩Cβ, which together with (b) implies Cα=Cγ=Cβ. We complete the proof of Lemma 5.Remark 2.
There are 2-cycle sets ofHx=x+ε−1 related to Gx=x−1 over F4∗, where ε∈F4∗. We can define the 2-cycle set as I′ and easily get that(20)I′=ω,ω2,ε=1,1,ε2,ε≠1,is closed under addition by ε.
To decomposeF22k\F4, we still introduce the set Sα as(21)Sα=Cα,s=0orε=0,Cα∪Cα+ε,otherwise,where Cα is the same as in Lemma 4.
Fixε,s∈F4. For any α∈F22k\F4, each set Sα is a subset of F22kF4. Noticing that, for any α∈F22k\F4 and k≥3 odd, Sα is a positive divisor of 22k−4, by Lemma 5 (c), F22k\F4 could be decomposed into a total of 22k−4/Sα such subsets.Example 1.
Letε=ω,s=ω, and α be the primitive element of F26. Then, F4=0,1,α21,α42 and(22)F26\F4=Sα∪Sα2∪Sα4∪Sα8∪Sα10∪Sα17,where(23)Sα=αll=1,3,14,23,30,33,40,49,60,62,Sα2=αll=2,5,13,18,25,38,45,50,58,61,Sα4=αll=4,6,7,12,29,34,51,56,57,59,Sα8=αll=8,9,11,20,26,37,43,52,54,55,Sα10=αll=10,15,16,24,28,35,39,47,48,53,Sα17=αll=17,19,22,27,31,32,36,41,44,46.
IfF22k\F4=Sα1∪Sα2∪⋯∪S22k−4/Sα, we set(24)L=α1,α2,…,α22k−4/Sα,where every αi is the leading element of Sαi, i∈1,…,22k−4/Sα. By Lemma 5, the sets Sα, α∈F2n\F4, have a nice structure which is stated in the following proposition. The details are omitted.Proposition 1.
Letα∈F2n\F4. Then Sα is closed under addition by ε.Theorem 1.
Fx is a permutation over F22k if the following conditions hold:(25)U=∪α∈F22kF4Sα,ε=0,∪α∈JSα∪I′,ε≠0,s=0,∪α∈JSα,ε≠0,s≠0,where J is a subset of L and the set I′ has been defined in Remark 2.Proof.
By the definition ofSα, we know that all of U is a union of some cycle sets of Hx related to Gx, which, associated with Lemma 3, implies Theorem 1 holds.
The next step is to study the differential uniformity ofFx. For any a,b∈F22k∗×F22k and ε,s∈F4, the equation Fx+a+Fx=b is equivalent to the following four equations on F22k:(26)x+a−1+x−1=b,x,x+a∈F22k\U,(27)x+a+ε−1+x+ε−1=b,x,x+a∈U,(28)x+a−1+x+ε−1=b+s,x∈U,x+a∈F22k\U,(29)x+a+ε−1+x−1=b+s,x∈F22k\U,x+a∈U.
As the statement of [18], the notations of roots and solutions have different meanings for those equations. For example, we say x0 is a root of equation (26) if x0+a−1+x0−1=b, and say x0 is a solution of equation (26) if x0 is a root of (26) with x0,x0+a∈F22k\U.Lemma 6.
For the roots of equations (26)–(29), we have the following:(a)
Ifx is a root of equation (26), then x+ε is a root of equation (27), and vice versa. Moreover, x+a is also a root of equation (26).(b)
Ifx is a root of equation (28), then x+ε is a root of equation (29), and vice versa. Moreover, x+a+ε is also a root of equation (28).Proof.
Ifx is a root of equation (26), then we have x+a−1+x−1=b, which is equivalent to the equation x+ε+a+ε−1+x+ε+ε−1=b. This shows that x+ε is a root of equation (27). Obviously, x+a is another root of equation (26) and x+a+ε is also a root of equation (27). It finishes the proof of (a) and the proof of (b) can be similarly proved.
We also consider the following equations:(30)bx2+abx+a=0,x,x+a∈F22k\U,(31)bx2+abx+bε2+abε+a=0,x,x+a∈U,(32)b+sx2+b+sa+εx+b+saε+ε+a=0,x∈U,x+a∈F22k\U,(33)b+sx2+b+sa+εx+a+ε=0,x∈F22k\U,x+a∈U.Remark 3.
Leta,b∈F22k∗×F22k. When b≠a−1, equations (26) and (27) are equivalent to the following two equations (30) and (31), respectively. When b≠a+ε−1+s, equations (28) and (29) are equivalent to the following two equations (32) and (33), respectively.
If we denote byCi the set of all solutions of equations (30)∼(33), respectively, then we have the following results for the cardinals of Ci, i=6,7,8,9.Lemma 7.
(1)
Ci=0 or Ci=2, i=6,7 and C6+C7≤2(2)
Ci=0 or Ci=1, i=8,9 and C8=1 if and only if C9=1Proof.
We only prove (1) by similarity. IfC6≠∅, then there exists λ∈C6 being the solution of equation (30). So is λ+a. Noting that equation (30) has at most two solutions for any pair a,b∈F22k∗×F22k, we have C6=2. Similarly, if C7≠∅, then C7=2. Now we prove that C6+C7≤2. Suppose that λ1,λ1+a∈C6 and λ2,λ2+a∈C7. By Lemma 6 (1), we may write λ2=λ1+ε. However, the fact that λ1∉U and λ2∈U meet a contradiction by Proposition 1. Thus, C6+C7≤2.
Denoting byTi the sets of all solutions of equation (26)∼(29), i=2,3,4,5.
Whenε=0, it is obvious that the function in (13) is a differential 4-uniformity permutation over F22k if s=0. If s≠0, Zha et al. [24] proved F in (13) is a differential 4-uniformity permutation over F22k as a special case. Now, we only need to show that the differential uniformity of the permutation F is as in (13) when ε≠0.Theorem 2.
Letε≠0 and s=0. If U as in Theorem 1 satisfies that, for any x∈U, Trε/x=1. Then, the function(34)Fx=x+ε−1+s,x∈U,x−1,x∈F22k\U,is of differential 4-uniformity.Proof.
By Theorem1, it suffices to prove that Fx+a+Fx=b has at most 4 solutions. It is equivalent to show that the sum of the numbers of solutions of equations (26) to (29) is less than 4.
Leta,b∈ε×F22k∗. The fact that x−1 is of differential uniformity 4 implies that the total of the numbers of solutions of equations (26) and (27) is at most 4. Moreover, (28) and (29) have no solutions. Thus, in this case, F is of differential 4-uniformity.
Now we prove thatFx+Fx+a=b has at most 4 solutions for a,b∈F22k∗\ε×F22k∗. To end this, we consider it to three cases:(1)
b≠a−1 and b≠a+ε−1. From Lemma 7, it follows that(35)∑i=14Ti=∑i=14Ci≤4,which shows thatFx+Fx+a=b has at most 4 solutions.(2)
b=a−1. When a∈U, by the fact that 0∉U, we know that a is not a solution of equation (26). Neither is 0. The sum of the numbers of equations (26) and (27) is at most 2. Since b≠a+ε−1, by Lemma 7 (2), the sum of the numbers of equations (28) and (29) is also at most 2. And hence, Fx+Fx+a=b has at most 4 solutions. When a∉U, obviously, 0 and a are the solutions of equation (26). In addition, since ab=1 and Tr1=0, by Lemma 2, equation (30) has two solutions aω and aω2, where that ω is a primitive element in F4. We have T2=4. By ε,a+ε∉U and Lemma 7 (1), we conclude that T3 is empty. Moreover, we claim that equations (28) and (29) have no solutions. In fact, by Lemma 7, we only need to show that equation (31) or (32) has no solutions. If λ is a solution of equation (32), we get a2+λa+λε+λ2=0. However,(36)Trλε+λ2λ2=Trελ=1,which together with Lemma2 implies that a2+λa+λε+λ2≠0 for any a∈F22k. It is a contradiction. Thus, Fx+Fx+a=b has 4 solutions.(3)
b=a+ε−1. Similar to the statement of the proof of the case b=a−1, we also obtain Fx+Fx+a=b has at most 4 solutions.
Together with the discussion of the above three cases, we know thatF is of differential 4-uniformity. Therefore, it finishes the proof of Theorem 1.Remark 4.
(1)
Letε=ω,s=0, and α be the primitive element of F26. If we choose U=Sα6=αll=6,29, then U satisfies all conditions of Theorem 2.(2)
Whenε=1 and s=0, Tang et al. [23] also obtained Theorem 2 and constructed 22 classes of CCZ-inequivalent differential 4-uniformity permutations. In this case, however, we find 27 classes of CCZ-inequivalent differential 4-uniformity permutations based on CCZ-invariant (see Table 1).Theorem 3.
Ifε≠0 and s≠0,(37)Fx=x+ε−1+s,x∈U,x−1,x∈F22k\U,where U=∪α∈JSα, then the differential uniformity of the function is of 4 or 6.Table 1
CCZ-inequivalent differential 4-uniformity permutations in Theorem2 over F26 with ε=1,s=0.
No.NLExtend Walsh spectrumDifferential spectrum122{∗0 [783], 4 [1206], 8 [1024], 12 [798], 16 [209], 20 [12]∗}{∗0 [2127], 2 [1794], 4 [111]∗}222{∗0 [795], 4 [1210], 8 [1008], 12 [792], 16 [213], 20 [14]∗}{∗0 [2139], 2 [1770], 4 [123]∗}322{∗0 [794], 4 [1236], 8 [1012], 12 [751], 16 [210], 20 [29]∗}{∗0 [2181], 2 [1686], 4 [165]∗}420{∗0 [805], 4 [1214], 8 [1014], 12 [774], 16 [195], 20 [28], 24 [2]∗}{∗0 [2181], 2 [1686], 4 [165]∗}520{∗0 [797], 4 [1240], 8 [998], 12 [755], 16 [219], 20 [21], 24 [2]∗}{∗0 [2181], 2 [1686], 4 [165]∗}620{..0 [799], 4 [1242], 8 [999], 12 [748], 16 [217], 20 [26], 24 [1]∗}{∗0 [2187], 2 [1674], 4 [171]∗}720{∗0 [813], 4 [1244], 8 [991], 12 [737], 16 [211], 20 [35], 24 [1]∗}{∗0 [2211], 2 [1626], 4 [195]∗}820{∗0 [790], 4 [1252], 8 [1017], 12 [731], 16 [206], 20 [33], 24 [3]∗}{∗0 [2211], 2 [1626], 4 [195]∗}920{∗0 [804], 4 [1254], 8 [991], 12 [736], 16 [216], 20 [26], 24 [5]∗}{∗0 [2217], 2 [1614], 4 [201]∗}1018{∗0 [841], 4 [1216], 8 [966], 12 [774], 16 [207], 20 [24], 24 [2], 28 [2]∗}{∗0 [2217], 2 [1614], 4 [201]∗}1120{∗0 [810], 4 [1242], 8 [999], 12 [742], 16 [202], 20 [32], 24 [5]∗}{∗0 [2223], 2 [1602], 4 [207]∗}1220{∗0 [831], 4 [1230], 8 [981], 12 [750], 16 [201], 20 [36], 24 [3]∗}{∗0 [2223], 2 [1602], 4 [207]∗}1320{∗0 [803], 4 [1264], 8 [988], 12 [723], 16 [221], 20 [29], 24 [4]∗}{∗0 [2223], 2 [1602], 4 [207]∗}1418{∗0 [808], 4 [1262], 8 [993], 12 [716], 16 [212], 20 [38], 24 [3]∗}{∗0 [2235], 2 [1578], 4 [219]∗}1520{∗0 [815], 4 [1262], 8 [997], 12 [726], 16 [217], 20 [28], 24 [7]∗∗}{∗0 [2241], 2 [1566], 4 [225]∗}1618{∗0 [815], 4 [1255], 8 [990], 12 [722], 16 [209], 20 [38], 24 [2], 28 [1]∗}{∗0 [2241], 2 [1566], 4 [225]∗}1718{∗0 [822], 4 [1240], 8 [983], 12 [748], 16 [206], 20 [26], 24 [5], 28 [2]∗}{∗0 [2241], 2 [1566], 4 [225]∗}1820{∗0 [801], 4 [1258], 8 [1008], 12 [724], 16 [199], 20 [34], 24 [8]∗}{∗0 [2247], 2 [1554], 4 [231]∗}1920{∗0 [801], 4 [1278], 8 [994], 12 [702], 16 [215], 20 [36], 24 [6]∗}{∗0 [2253], 2 [1542], 4 [237]∗}2018{∗0 [816], 4 [1265], 8 [971], 12 [729], 16 [220], 20 [21], 24 [9], 28 [1]∗}{∗0 [2253], 2 [1542], 4 [237]∗}2120{∗0 [803], 4 [1286], 8 [986], 12 [694], 16 [221], 20 [36], 24 [6]∗}{∗0 [2259], 2 [1530], 4 [243]∗}2218{∗0 [820], 4 [1257], 8 [980], 12 [729], 16 [208], 20 [29], 24 [8], 28 [1]∗}{∗0 [2259], 2 [1530], 4 [243]∗}2318{∗0 [801], 4 [1276], 8 [994], 12 [708], 16 [215], 20 [30], 24 [6], 28 [2]∗}{∗0 [2259], 2 [1530], 4 [249]∗}2418{∗0 [805], 4 [1266], 8 [996], 12 [718], 16 [211], 20 [28], 24 [4], 28 [4]∗}{∗0 [2271], 2 [1506], 4 [255]∗}2522{∗0 [795], 4 [1302], 8 [1008], 12 [654], 16 [213], 20 [60]∗}{∗0 [2277], 2 [1494], 4 [261]∗}2618{∗0 [795], 4 [1284], 8 [1000], 12 [700], 16 [213], 20 [30], 24 [8], 28 [2]∗}{∗0 [2277], 2 [1494], 4 [261]∗}2720{∗0 [783], 4 [1302], 8 [1012], 12 [678], 16 [209], 20 [36], 24 [12]∗}{∗0 [2289], 2 [1470], 4 [273]∗}Table 2
CCZ-inequivalent differential 4-uniformity permutations in Theorem3 over F26 with ε=s=ω.
No.NLExtend Walsh spectrumDifferential spectrum122{∗0 [795], 4 [1266], 8 [1008], 12 [708], 16 [213], 20 [42]∗}{∗0 [2223], 2 [1602], 4 [207]∗}220{∗0 [783], 4 [1254], 8 [1038], 12 [718], 16 [193], 20 [44], 24 [2]∗}{∗0 [2223], 2 [1602], 4 [207]∗}Table 3
CCZ-inequivalent differential 6-uniformity permutations in Theorem3 over F26 with ε=s=ω.
No.NLExtend Walsh spectrumDifferential spectrum120{∗0 [803], 4 [1246], 8 [1014], 12 [738], 16 [189], 20 [32], 24 [10]∗}{∗0 [2239], 2 [1578], 4 [207], 6 [8]∗}218{∗0 [795], 4 [1234], 8 [1040], 12 [738], 16 [181], 20 [40], 24 [0], 28 [4]∗}{∗0 [2239], 2 [1578], 4 [207], 6 [8]∗}320{∗0 [795], 4 [1258], 8 [1014], 12 [728], 16 [197], 20 [30], 24 [10]∗}{∗0 [2239], 2 [1578], 4 [207], 6 [8]∗}420{∗0 [765], 4 [1302], 8 [1042], 12 [666], 16 [203], 20 [48], 24 [6]∗}{∗0 [2259], 2 [1542], 4 [219], 6 [12]∗}520{∗0 [801], 4 [1246], 8 [1026], 12 [726], 16 [183], 20 [44], 24 [6]∗}{∗0 [2243], 2 [1566], 4 [219], 6 [4]∗}620{∗0 [817], 4 [1278], 8 [976], 12 [702], 16 [215], 20 [36], 24 [8]∗}{∗0 [2263], 2 [1530], 4 [231], 6 [8]∗}718{∗0 [801], 4 [1268], 8 [1012], 12 [704], 16 [199], 20 [42], 24 [4], 28 [2]∗}{∗0 [2263], 2 [1530], 4 [231], 6 [8]∗}818{∗0 [805], 4 [1278], 8 [992], 12 [708], 16 [211], 20 [26], 24 [8], 28 [4]∗}{∗0 [2279], 2 [1506], 4 [231], 6 [16]∗}918{∗0 [813], 4 [1258], 8 [1000], 12 [714], 16 [203], 20 [40], 24 [0], 28 [4]∗}{∗0 [2263], 2 [1530], 4 [231], 6 [8]∗}1018{∗0 [773], 4 [1268], 8 [1038], 12 [720], 16 [195], 20 [26], 24 [10], 28 [2]∗}{∗0 [2257], 2 [1536], 4 [237], 6 [2]∗}1118{∗0 [797], 4 [1264], 8 [1010], 12 [718], 16 [203], 20 [32], 24 [6], 28 [2]∗}{∗0 [2257], 2 [1536], 4 [237], 6 [2]∗}1218{∗0 [815], 4 [1256], 8 [998], 12 [726], 16 [193], 20 [32], 24 [10], 28 [2]∗}{∗0 [2273], 2 [1512], 4 [237], 6 [10]∗}1320{∗0 [791], 4 [1274], 8 [1016], 12 [704], 16 [210], 20 [38], 24 [8]∗}{∗0 [2249], 2 [1560], 4 [213], 6 [10]∗}1420{∗0 [825], 4 [1246], 8 [980], 12 [734], 16 [207], 20 [36], 24 [4]∗}{∗0 [2233], 2 [1584], 4 [213], 6 [2]∗}1520{∗0 [795], 4 [1238], 8 [1018], 12 [750], 16 [197], 20 [28], 24 [6]∗}{∗0 [2209], 2 [1632], 4 [189], 6 [2]∗}1620{∗0 [771], 4 [1270], 8 [1022], 12 [718], 16 [221], 20 [28], 24 [2]∗}{∗0 [2159], 2 [1662], 4 [171], 6 [4]∗}1720{∗0 [817], 4 [1270], 8 [990], 12 [706], 16 [199], 20 [40], 24 [10]∗}{∗0 [2277], 2 [1500], 4 [249], 6 [6]∗}1820{∗0 [779], 4 [1258], 8 [1036], 12 [720], 16 [197], 20 [38], 24 [4]∗}{∗0 [2215], 2 [1626], 4 [183], 6 [8]∗}1920{∗0 [813], 4 [1254], 8 [1006], 12 [722], 16 [187], 20 [40], 24 [10]∗}{∗0 [2267], 2 [1518], 4 [243], 6 [4]∗}2020{∗0 [783], 4 [1274], 8 [1020], 12 [704], 16 [209], 20 [38], 24 [4]∗}{∗0 [2229], 2 [1596], 4 [201], 6 [6]∗}Proof.
Since the proof of Theorem3 is very similar to that of Theorem 2, we omit the details.Remark 5.
(1)
The permutationsF constructed in Theorem 3 are of differential 4-uniformity for all of U if εands satisfy one of the following three cases: (1) ε=s=1; (2) ε=ω,s=ω2; and (3) ε=ω2,s=ω.(2)
The permutationsF are of differential 4-uniformity when U=∪α∈LSα (i.e., U=F22kF4), where L has been defined above. In this case, the proof can refer to the case that F in (13) with ε=0 and s≠0, since U is closed under addition by ε.(3)
The permutationsF constructed in Theorem 3 are of differential 6-uniformity for all of U=∪α∈J⊂LSα (J is a proper subset of L) if εands satisfy one of the following two cases: (1) ε=1,s=ω or ω2 and (2) ε=ω or ω2,s=1.(4)
Whenε=s=ω or ω2, the differential uniformity of the permutations F depends on the choice of U=∪α∈J⊂LSα. For example, let ε=s=ω and k=3, F constructed in Theorem 3 are differential 4-uniformity permutations over F26 if U=Sα∪Sα4∪Sα10 or U=Sα∪Sα2∪Sα10∪Sα17, where Sαi comes from Example 1 (see Table 2). Otherwise, F constructed in Theorem 3 are differential 6-uniformity permutations over F26 (see Table 3).


## 4. Other Cryptographic Properties

In this section, we study the algebraic degree and nonlinearity ofFx over F22k∗. Moreover, we present some numerical results about the differential spectra, extend Walsh spectra, and nonlinearities of Fx. We also discuss the CCZ-equivalence of Fx constructed in Section 3.


### 4.1. Algebraic Degree and Nonlinearity

The aim of this section is to prove that all functions we constructed have the optimal algebraic degree. For any given permutationF over F2n∗, the algebraic degree of Fx is at most n−1. As noticed in [23] that, for any n,1-function hx (or n-variable Boolean function) with deghx≤n−k−1, if Fx has algebraic degree at most k, one must have(38)Tr∑x∈F2naFxhx=∑x∈F2nTraFxhx=0,∀a∈F2n∗.It follows that the size of the setx∈F2nTrFxhx=0 must be even from the fact that the algebraic degree of TraFxhx is at most n−1. Hence, for a permutation Fx over F2n∗, if we can show that there exists some Boolean function hx with algebraic degree at most 1 such that(39)∑x∈F2nFxhx≠0,then we can conclude that the algebraic degree of F is at least n−1.Theorem 4.
Letk≥3 be an odd integer. For any ε,s∈F4, Fx as in (13) has the optimal algebraic degree 2k−1.Proof.
Whenε=0, Zha et al. [24] proved Theorem 4 as a special case. Now we turn to prove it for ε≠0. To end this, we only need to show that there exists some Boolean function hx with algebraic degree at most 1 such that∑x∈F2nFxhx≠0.
Letε≠0. Taking hx=Trε−1x, we know that it is of algebraic degree 1. By Trε−1x+ε=Trε−1x+Tr1 and Tr1=0, we have(40)∑x∈F22kFxhx=∑x∈UTrε−1xx+ε−1+s∑x∈UTrε−1x+∑x∈F22k\UTrε−1xx−1=∑x∈UTrε−1x+εx−1+∑x∈F22k\UTrε−1xx−1+s∑x∈UTrε−1x=∑x∈F22kTrε−1xx−1+s∑x∈UTrε−1x,where U is the same as in Theorem 1. For any x∈U, we have x+ε∈U. Then Trε−1x+Trε−1x+ε=Tr1=0 and so ∑x∈UTrε−1x=0.
Therefore,(41)∑x∈F22kFxhx=ε−1∑x∈F22kTrε−1xε−1x−1=ε−1∑x∈F22kTrxx−1=ε−1.
We complete the proof of Theorem4.
Now we consider the nonlinearity of the functionsF and obtain the following lower bound.Theorem 5.
Letk≥3 be an odd integer. For any ε,s∈F4, the nonlinearity of F satisfies NLF≥22k−1−2k−U, where U is as in Theorem 1.Proof.
By the definition of the Walsh transform of the functionF, we have, for any a,b∈F22k×F22k∗,(42)FWa,b=∑x∈F22k−1Trax+bFx=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx+ε−1+s=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1+Traε+bs.
IfTraε+bs=0, then(43)FWa,b=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1=∑x∈F22k−1Trax+bx−1.
And ifTraε+bs=1, then(44)FWa,b=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1+t+1=∑x∈F22k−1Trax+bx−1−2∑x∈U−1Trax+bx−1=∑x∈F22k−1Trbx−1+ax−2∑x∈U−1Trax+bx−1.
Lemma1 tells us that ∑x∈F22k−1Trbx−1+ax≤2k+1. Therefore, FWa,b≤2k+1+2U, which, according to the definition of NLF, implies that(45)NLF=22k−1−12maxa,b∈F22k×F22k∗FWa,b≥22k−1−2k−U.


### 4.2. Numerical Result of CCZ-Inequivalence ofFx

From the primary definition of CCZ-equivalence, it is difficult to check whether twon,n-functions are CCZ-equivalent. An alternative method to solve this problem is to compare their CCZ-invariant parameters (such as differential spectrum and extended Walsh spectrum).We compute the nonlinearity, the extended Walsh spectrum, and the differential spectrum of the constructed functions with different parameters. As we said in Remark4, we find at least 27 classes of CCZ-inequivalent differential 4-uniformity functions which are listed in Table 1. And as we remarked in Remark 5 (4), there are 2 CCZ-inequivalent differential 4-uniformity classes of functions, which are listed in Table 2. Moreover, CCZ-invariant parameters of the newly differential 6-uniformity functions from Theorem 3 are also computed and listed in Table 3. In these tables, we denote by NL the nonlinearity of a function and the multiset∗mt∗ the times of t appearing in this multiset which is m.It is obvious that all of the functions in Table2 are CCZ-inequivalent to those constructed in [11–13, 15, 26] since they have different nonlinearity. To compare our construction with that described in [14, 16–25], it is found that all of the functions in Table 2 are CCZ-inequivalent to them, since at least one of the extended Walsh spectrum and the differential spectrum is different. Moreover, in Table 3, all of the differential 6-uniformity permutations from Theorem 3 are CCZ-inequivalent to the previously constructed ones in [31–35] when k=3.


## 4.1. Algebraic Degree and Nonlinearity

The aim of this section is to prove that all functions we constructed have the optimal algebraic degree. For any given permutationF over F2n∗, the algebraic degree of Fx is at most n−1. As noticed in [23] that, for any n,1-function hx (or n-variable Boolean function) with deghx≤n−k−1, if Fx has algebraic degree at most k, one must have(38)Tr∑x∈F2naFxhx=∑x∈F2nTraFxhx=0,∀a∈F2n∗.It follows that the size of the setx∈F2nTrFxhx=0 must be even from the fact that the algebraic degree of TraFxhx is at most n−1. Hence, for a permutation Fx over F2n∗, if we can show that there exists some Boolean function hx with algebraic degree at most 1 such that(39)∑x∈F2nFxhx≠0,then we can conclude that the algebraic degree of F is at least n−1.Theorem 4.
Letk≥3 be an odd integer. For any ε,s∈F4, Fx as in (13) has the optimal algebraic degree 2k−1.Proof.
Whenε=0, Zha et al. [24] proved Theorem 4 as a special case. Now we turn to prove it for ε≠0. To end this, we only need to show that there exists some Boolean function hx with algebraic degree at most 1 such that∑x∈F2nFxhx≠0.
Letε≠0. Taking hx=Trε−1x, we know that it is of algebraic degree 1. By Trε−1x+ε=Trε−1x+Tr1 and Tr1=0, we have(40)∑x∈F22kFxhx=∑x∈UTrε−1xx+ε−1+s∑x∈UTrε−1x+∑x∈F22k\UTrε−1xx−1=∑x∈UTrε−1x+εx−1+∑x∈F22k\UTrε−1xx−1+s∑x∈UTrε−1x=∑x∈F22kTrε−1xx−1+s∑x∈UTrε−1x,where U is the same as in Theorem 1. For any x∈U, we have x+ε∈U. Then Trε−1x+Trε−1x+ε=Tr1=0 and so ∑x∈UTrε−1x=0.
Therefore,(41)∑x∈F22kFxhx=ε−1∑x∈F22kTrε−1xε−1x−1=ε−1∑x∈F22kTrxx−1=ε−1.
We complete the proof of Theorem4.
Now we consider the nonlinearity of the functionsF and obtain the following lower bound.Theorem 5.
Letk≥3 be an odd integer. For any ε,s∈F4, the nonlinearity of F satisfies NLF≥22k−1−2k−U, where U is as in Theorem 1.Proof.
By the definition of the Walsh transform of the functionF, we have, for any a,b∈F22k×F22k∗,(42)FWa,b=∑x∈F22k−1Trax+bFx=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx+ε−1+s=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1+Traε+bs.
IfTraε+bs=0, then(43)FWa,b=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1=∑x∈F22k−1Trax+bx−1.
And ifTraε+bs=1, then(44)FWa,b=∑x∈F22k\U−1Trax+bx−1+∑x∈U−1Trax+bx−1+t+1=∑x∈F22k−1Trax+bx−1−2∑x∈U−1Trax+bx−1=∑x∈F22k−1Trbx−1+ax−2∑x∈U−1Trax+bx−1.
Lemma1 tells us that ∑x∈F22k−1Trbx−1+ax≤2k+1. Therefore, FWa,b≤2k+1+2U, which, according to the definition of NLF, implies that(45)NLF=22k−1−12maxa,b∈F22k×F22k∗FWa,b≥22k−1−2k−U.


## 4.2. Numerical Result of CCZ-Inequivalence ofFx

From the primary definition of CCZ-equivalence, it is difficult to check whether twon,n-functions are CCZ-equivalent. An alternative method to solve this problem is to compare their CCZ-invariant parameters (such as differential spectrum and extended Walsh spectrum).We compute the nonlinearity, the extended Walsh spectrum, and the differential spectrum of the constructed functions with different parameters. As we said in Remark4, we find at least 27 classes of CCZ-inequivalent differential 4-uniformity functions which are listed in Table 1. And as we remarked in Remark 5 (4), there are 2 CCZ-inequivalent differential 4-uniformity classes of functions, which are listed in Table 2. Moreover, CCZ-invariant parameters of the newly differential 6-uniformity functions from Theorem 3 are also computed and listed in Table 3. In these tables, we denote by NL the nonlinearity of a function and the multiset∗mt∗ the times of t appearing in this multiset which is m.It is obvious that all of the functions in Table2 are CCZ-inequivalent to those constructed in [11–13, 15, 26] since they have different nonlinearity. To compare our construction with that described in [14, 16–25], it is found that all of the functions in Table 2 are CCZ-inequivalent to them, since at least one of the extended Walsh spectrum and the differential spectrum is different. Moreover, in Table 3, all of the differential 6-uniformity permutations from Theorem 3 are CCZ-inequivalent to the previously constructed ones in [31–35] when k=3.


## 5. Conclusions

In this paper, we constructed several classes of low differential uniformity permutations overF22k with k odd. All these functions have the optimal algebraic degree, and we get a lower bound of the high nonlinearity of Fx. Moreover, it has been checked by a computer program for k=3 that there are many new CCZ-inequivalent classes of differentially 4- and 6-uniform permutations in our construction. Precisely, all of the differential 6-uniformity permutations are CCZ-inequivalent with the known ones, and there are two new families of differential 4-uniformity permutations.



---

*Source: 7152657-2020-07-27.xml*