# Bent and Permutational Properties of Budaghyan-Carlet Hexanomials

Authors: Tao Xie
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The set related to the existence of Budaghyan-Carlet
hexanomials is characterized. By investigating the component functions, it is also proved that none of Budaghyan-Carlet
hexanomials cannot be turned into a permutation by adding any linearized polynomial.
As a byproduct, a class of quadratic bent functions is obtained.


---

## Body

## 1. Introduction

For a positive integern, let F2n be the finite field with 2n elements and let F2n∗=F2n∖{0} be its multiplicative group. For a positive integer δ, a function F from F2n to itself is calleddifferentiallyδ-uniform if, for every (a,b)∈F2n∗×F2n, the equation F(x)+F(x+a)=b admits at most δ solutions in F2n [1]. The differentially 2-uniform functions are calledalmost perfect nonlinear (APN) functions, introduced in [1] as the class of functions having good resistance to differential cryptanalysis [2]. Recently, many constructions of APN functions were proposed (the reader is referred to the survey on APN polynomials [3] and references therein), and people also considered their applications in the topics such as finite geometries, cyclic codes, and sequences. Thus, it is interesting to find APN permutations since they are important candidates as cryptographically strong substitution boxes (S-boxes) of block ciphers [2]. However, the existence of APN permutations for even dimension n has been a long-standing question. Very recently, the first example of APN permutations over F26 was found in [4]. From the cryptographic point of view, it is also of great interest to study permutations with low differential uniformity. For instance, the inverse function over F28, a differentially 4-uniform permutation over F28, is applied to design the S-box of the Advanced Encryption Standard (AES) [5].For two positive integersl and k, a class ofBudaghyan-Carlet hexanomials(1)F1x=x2l+1+x2k+1+cx2k+l+1+c2kx2k+2l+dx2k+l+2l+x2k+l+2k,c,d∈F22k,d∉F2kover F22k is proposed in [6]. It is proved that if there exists an element c∈F22k such that the quadratic polynomial(2)Gx=x2l+1+cx2l+c2kx+1has no zero x∈F22k satisfying x2k+1=1, then F1(x) is a differentially 2s-uniform function, where s=gcd(l,k). In particular, the case s=1 gives a class of APN functions. Denote(3)Cl,k=c∈F22k∣Gxhas  no  zerox∈F22ksatisfyingx2k+1=1.Thus, the existence of low differential functions having a form as F1(x) depends on the nonempty property of C(l,k). To investigate this, a subset(4)Dl,k=c∈F22k∣Gxhas  no  zerosx∈F22kof C(l,k) is considered [6]. It was checked by a computer that D(l,k)≠∅ when 6≤2k≤500 and 3∤k. Moreover, at least 140 of the 166 checked cases satisfy D(l,k)≠∅ when 3∣k. Later on, it was proved that D(l,k)≠∅ if k is even such that 3∤k and gcd(l,2k)=1 [7]. This result was further improved by removing the condition 3∤k in [8]. In [9], it was demonstrated that C(l,k)≠∅ if and only if k>1 and l/k is not an odd integer. As a result, the existence of low differential functions F1(x) is completely characterized. In the case that C(l,k) is nonempty, in order to represent the differentially uniform function F1(x), it is important to determine what elements constitute the set C(l,k) and the cardinality of it. Under the condition that k is even, 3∤k, and gcd(l,2k)=1, there is an element of the form ωβ2k+2l+γ2k+2l in C(l,k), where ω∈F22k∗ has order 3 and the elements β,γ∈F22k satisfy γ2l+1+wβ2l+1+1=0 and γ2k-1≠β2k-1 [7]. When removing the condition 3∤k, an element of the form c=αα1+α2/α+1 in C(l,k) is found, where α∈F22k∖F2k is noncube and α1,α2 are the solutions of x2l+1=1+α-11-2k and y2l+1=1+α1-2k in F22k, respectively [8].To resist differential attack, it is desired to use permutations with low differential uniformity in block ciphers. It is well known that adding a linearized polynomial to a function does not change its differential uniformity. This motivates people to investigate the conditions such that the function of the formF(x)+L(x) is a permutation, where F(x) is a function with a low differential uniformity and L(x) is a linearized polynomial. The case that F(x) is a power function is discussed in [10–12]. When F(x) is a quadratic APN function on fields of even extensions, it is known that F(x)+L(x) can never be permutations. A natural question is that are there any linearized polynomials L(x) such that F1(x)+L(x) are permutations if the set C(l,k) is not empty and gcd(l,k) is small?This paper discusses the questions proposed above. The complementary set ofC(l,k) in F22k is described, and some properties of the cardinality of C(l,k) are also considered. Moreover, it is proved that the function F1 given by (1) cannot be turned into a permutation by adding any linearized polynomial for any positive integers l and k. As a byproduct, a class of quadratic bent functions is also obtained.The remainder of this paper is organized as follows. Section2 introduces some necessary concepts and results. In Section 3, the set C(l,k) is described and some properties of C(l,k) are studied. Section 4 investigates the permutation behavior of the function F1(x)+L(x) for a linearized polynomial L(x).


## 2. Preliminaries

For two positive integersm and n, a polynomial of the form L(x)=∑i=0maix2i with coefficients ai(0≤i≤m) in F2n is called alinearized polynomial over F2n. We use Tr⁡(·) to denote thetrace function from F2n to F2; that is,(5)Tr⁡x=x+x2+x22+⋯+x2n-1.For a Boolean functionf(x) from F2n to F2, itsWalsh transform is defined as(6)Wfω=∑x∈F2n-1fx+Tr⁡ωx,ω∈F2n.The Boolean function f(x) is calledbent if Wf(ω)=±2n/2 for all ω∈F2n.Lemma 1.
Letf(x)=x+1/x be a function defined over F2n∗. Then the following two statements hold:(i)
Iff(x)=f(y) for two elements x and y in F2n∗, then x=y or xy=1.(ii)
f(x)=0 if and only if x=1.Proof.
(i) Iff(x)=f(y) for x,y∈F2n∗, that is,(7)x+1x=y+1y,then(8)x2y+y=xy2+x,which implies(9)x+yxy+1=0.Therefore, x=y or xy=1.
(ii)f(x)=0 if and only if x+1/x=0, which is equivalent to x2=1.IfF(x) is a bijection from F2n to itself, then it is called apermutation of F2n. The following is a characterization of permutations.Lemma 2 (see [13, 14]).
A functionF:F2n→F2n is a permutation of F2n if and only if, for every γ∈F2n∗,(10)∑x∈F2n-1Tr⁡γFx=0.


## 3. Some Properties of the SetC(l,k)

In this section, for any positive integersl and k, some properties of the set C(l,k) given by (3) are discussed.The setC(l,k) is described by characterizing its complementary set as follows.Proposition 3.
For any positive integersl and k, let(11)X0l=0∪α2k+1j∣j=0,1,…,2k-2,(12)Xrl=α-2l2k-1r∪α-2l2k-1r+α2k+1j+2l-1r∣j=0,1,…,2k-2for each integer r with 1≤r≤2k, where α is a primitive element of F22k. Then, we have(13)Cl,k=F22k∖⋃r=02kXrl.Proof.
To prove that (13) holds, it suffices to show that c∉C(l,k) if and only if c∈⋃r=02kXrl. By (3), c∉C(l,k) if and only if G(x)=x2l+1+cx2l+c2kx+1 has a zero satisfying x2k+1=1. Since α is a primitive element of F22k, the 2k+1 elements α(2k-1)r with 0≤r≤2k are exactly all solutions of x2k+1=1. Denote β=α2k-1; then, c∉C(l,k) if and only if c satisfies(14)Gβr=βr2l+1+cβr2l+c2kβr+1=0for some integer r with 0≤r≤2k.
For any positive integerl, denote Xrl=c∈F22k∣G(βr)=0, where the integer r satisfies 0≤r≤2k. Thus, an element c∈F22k belongs to X0l if and only if c satisfies c2k+c=0. Therefore, c is equal to 0 or α(2k+1)j where the integer j satisfies 0≤j≤2k-2. As a consequence, (11) holds. For each integer r with 1≤r≤2k, c∈Xrl if and only if c satisfies(15)c2k+βr2l-1c=β-r+βr2l.By a direct verification, the 2k elements α-2l(2k-1)r and α-2l(2k-1)r+α(2k+1)j+(2l-1)r with 0≤j≤2k-2 are exactly all solutions of (15). Thus, (12) holds.
The above analysis shows thatc∉C(l,k) if and only if c∈⋃r=02kXrl. Consequently, (13) holds.Proposition 4.
For two positive integersl and k with k>1, the set C(l,k) satisfies the following:(i)
C(l,k)=C(2k+l,k).(ii)
C(l,k)=C(2k-l,k) for l=1,2,…,k-1.Proof.
(i) By (11) and (12), we have X0l+2k=X0l and Xrl+2k=Xrl for each integer r with 1≤r≤2k. Thus, Claim (i) follows from (13).
(ii) To finish the proof of Claim (ii), by (13), it suffices to prove that, for an integer l with 1≤l≤k-1,(16)⋃r=02kXrl=⋃r=02kXr2k-l.Equation (11) implies X0l=X02k-l for l=1,2,…,k-1. In the sequel, we will show that there exists a permutation ρ of the set I2k=1,2,…,2k such that Xil=Xρ(i)2k-l for any i∈I2k and each l with 1≤l≤k-1.
For anyi∈I2k, there is a unique integer j∈I2k satisfying(17)2li≡-jmod⁡2k+1.Define ρ(i)=j and then ρ is a bijection from I2k to itself.
Letj=ρ(i); then, by (15) for each l=1,2,…,k-1,(18)Xil=c∈F22k∣c2k+β2l-1ic=1+β2l+1iβi,Xj2k-l=c∈F22k∣c2k+β22k-l-1jc=1+β22k-l+1jβj,where α is a primitive element of F22k and β=α2k-1. By (17), we have(19)22k-l-1j≡22k-l-1-2li≡2l-1imod⁡2k+1,which gives β(2l-1)i=β(22k-l-1)j. Again by (17), the facts β2li+2j=βj and β(2l+1)i+j=βi are obtained. As a consequence, we have βj+β(2l+1)i+j=βi+β2li+2j. By (19), we have (22k-l+1)j+i≡2li+2j(mod⁡2k+1). Thus, β(22k-l+1)j+i=β2li+2j and then βj+β(2l+1)i+j=βi+β(22k-l+1)j+i; that is, 1+β(2l+1)i/βi=1+β(22k-l+1)j/βj. Above analysis shows that Xil=Xj2k-l for each l with 1≤l≤k-1. This completes the proof.Proposition4 tells us that we only need to study the sets C(l,k) for a positive integer k and the integer l with 1≤l≤k and l=2k. When ⋃r=02kXrl is a proper subset of F22k, C(l,k) is nonempty. It is also of great interest to know the cardinality of the nonempty set C(l,k); however, for a general case the exact cardinality is difficult to calculate. For the special case of l=2k, it can be determined as follows.Proposition 5.
For any integerk>1, C(2k,k)=22k-1-2k.Proof.
By Proposition3, we have C(2k,k)=F22k∖⋃r=02kXr2k, where Xr2k=2k for 0≤r≤2k by (11) and (12). To prove C(2k,k)=22k-1-2k, it suffices to prove ⋃r=02kXr2k=22k-1+2k. To this end, we will prove two facts below.
Fact 1. Xr2k=X2k+1-r2k holds for each integer r with 1≤r≤2k-1.
Recall thatXr2k={c∈F22k∣G(βr)=0}, where G(x)=x2+(c+c2k)x+1 and β=α2k-1 for a primitive element α of F22k. Note that G(x-1)=x-2+(c+c2k)x-1+1=x-2G(x) holds for any x∈F22k∗; then, G(x)=0 if and only if G(x-1)=0 for any x∈F22k∗. In particular, G(β2k+1-r)=0 if and only if G(βr)=0 for each integer r satisfying 1≤r≤2k-1. Thus, Xr2k=X2k+1-r2k holds for each integer r with 1≤r≤2k-1.
Fact 2. Xi2k∩Xj2k=∅ holds for any two distinct integers i,j with 0≤i,j≤2k-1.
Otherwise, there exists an elementc0∈F22k such that c0∈Xi2k∩Xj2k for two distinct integers i,j with 0≤i, j≤2k-1. Then, we have(20)β2i+c0+c02kβi+1=0,β2j+c0+c02kβj+1=0.This implies(21)c0+c02k=βi+1βi=βj+1βj.By Lemma 1 and (21), we have f(β2k+1-i)=f(βi)=f(βj)=f(β2k+1-j). Again by Lemma 1, we have β2k+1-i=βj. This implies (2k+1)∣(i+j), which is impossible due to 1≤i+j≤2k. Thus, Xi2k∩Xj2k=∅.
With the above two facts, we have(22)⋃r=02kXr2k=⋃r=02k-1Xr2k=⋃r=02k-1Xr2k=2k1+2k-1,where the first equal sign holds due to Fact 1 and the second equal sign holds due to Fact 2. Hence, C2k,k=22k-2k(1+2k-1)=22k-1-2k. This finishes the proof.


## 4. Permutation Behavior of the FunctionF1(x)+L(x)

In this section, the permutation behavior of the functionF1(x)+L(x) is studied. Our investigations show that F1 cannot be turned into a permutation by adding any linearized polynomial.Proposition 6.
Letl,k be any positive integers and let F1(x) be a function on F22k defined by (1) with c,d∈F22k and d∉F2k. Then the Boolean function Tr⁡(λF1(x)) is bent for all λ∈F2k∗.Proof.
For eachλ∈F2k∗, to prove that Tr⁡(λF1(x)) is bent, it suffices to prove that the Walsh transform of Tr⁡(λF1(x)) takes values in the set {±2k}. By (6), we have(23)WTr⁡λF1xv=∑x∈F22k-1Tr⁡λF1x+vx,v∈F22k.Squaring it gives(24)WTr⁡λF1xv2=∑y∈F22k∑x∈F22k-1Tr⁡λF1y+λF1x+vy+vx.Assume that y=x+u for u∈F22k; then, for each fixed x∈F22k, u runs through F22k when y runs through F22k. Therefore, we have(25)WTr⁡λF1xv2=∑u∈F22k∑x∈F22k-1Tr⁡λF1x+u+λF1x+vx+u+vx=∑u∈F22k∑x∈F22k-1Tr⁡λF1x+u+λF1x+vu=∑u∈F22k-1Tr⁡λF1u+vu∑x∈F22k-1Tr⁡Δux,where Δu(x)=λ(F1(x+u)+F1(x)+F1(u)). By (1), we have(26)Δux=λu2lx+ux2l+u2kx+ux2k+cu2k+lx+ux2k+l+c2ku2lx2k+u2kx2l+du2lx2k+l+u2k+lx2l+u2kx2k+l+u2k+lx2k.Since Tr⁡(w+w2k)=0 for any w∈F22k, Tr⁡(Δu(x)) can be simplified as(27)Tr⁡Δux=Tr⁡λdu2lx2l+k+u2l+kx2l=Tr⁡λdu2lx2l+k+Tr⁡λdu2l+kx2l=Tr⁡λdu2lx2l+k+Tr⁡λ2kd2ku2lx2k+l=Tr⁡λd+λ2kd2ku2lx2l+k=Tr⁡λd+d2ku2lx2l+k,where the last equal sign holds due to λ∈F2k∗. Therefore,(28)WTr⁡λF1xv2=∑u∈F22k-1Tr⁡F1u+vu∑x∈F22k-1Tr⁡x2k+lλd+d2ku2l.Note that λ≠0 and d∈F22k∖F2k implies d+d2k≠0. Consequently, λ(d+d2k)u2l=0 if and only if u=0. Thus,(29)∑x∈F22k-1Tr⁡x2k+lλd+d2ku2l=0,ifu≠0,22k,ifu=0.Hence, WTr⁡(λF1(x))v2=22k and the proof is completed.By Proposition6, a class of quadratic bent functions is obtained, which is irrelevant to the case whether C(l,k) is nonempty or not. This fact together with Lemma 2 imply that F1(x) cannot be turned into a permutation by adding a linearized polynomial, because the functions having bent components cannot be permutations (neither their sum with a linearized polynomial).Theorem 7.
For a positive integerk, let F1(x) be the function defined by (1) with c,d∈F22k and d∉F2k. Then F1(x)+L(x) is not a permutation for any linearized polynomial L(x) over F22k.



---

*Source: 467020-2015-09-02.xml*