# Class of Quadratic Almost Bent Functions That Is EA-Inequivalent to Permutations

Authors: Xinyang Zhang; Meng Zhou
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

The permutation relationship for the almost bent (AB) functions in the finite field is a significant issue. Li and Wang proved that a class of AB functions with algebraic degree 3 is extended affine- (EA-) inequivalent to any permutation. This study proves that another class of AB functions, which was developed in 2009, is EA-inequivalent to any permutation. This particular AB function is the first known quadratic class EA-inequivalent to permutation.


---

## Body

## 1. Introduction

Almost perfect nonlinear (APN) and almost bent (AB) functions and significant theoretical meanings have been extensively applied in finite field theory. The search for new APN (see Definition1) and AB (which also implies APN property) functions has become an interesting topic. Power functions have six known classes of APN functions, namely, Gold [1], Kasami [2], Welch [3, 4], Niho [4], Inverse, and Dobbertin [5]. Apart from power functions, APN function also has several known classes. Accordingly, [6–11] show that all results are quadratic functions (the meaning of degree is a little different, see Definitions 2 and 3).In the design of a block cipher, permutations overF2n with an even n are preferred due to hardware and software requirements. No APN permutation over F2n with an even n was determined until Dillon [12] in 2009. Thus, the Big APN problem emerged: Does such function exist? This problem is still open for n≥8. Berger et al. in [13] provided a significant solution for the Big APN problem: if the components of an APN function over F2n with an even n are plateaued, then a bent component exists, which is not permuted. This result is negative for quadratic functions because quadratic implies reaching a plateau [14]. If F2n is changed by an odd n, then the plateaued APN functions are equal to the AB functions based on the result of [3]. The AB functions are conjectured to be EA-equivalent (see Definition 4) to the permutations. In 2013, Li and Wang [15] proved that the infinite class in [7] is EA-inequivalent to any permutation.Definition 1.
F
(
x
) is called almost perfect nonlinear (APN) function on F2n if DaF(x)=F(x+a)-F(x) are 2−1 on F2n (i.e., DaF(x)=DaF(y) if and only if x=y or x+a=y) for all a∈F2n∖0. Almost bent (AB) function is a kind of APN function.Definition 2.
Every mappingF:F2n→F2n can be unique represented in the form F(x)=∑i=02n-1aixi, called the algebraic normal form (ANF) of mapping F. ANF is zero (i.e., ai=0 for any 0≤i≤2n-1) if and only if mapping is zero (i.e., F(x)=0 for any x).Definition 3.
Every0≤j≤2n-1 is equal to an n tuple j1⋯jn∈Z2n as j=∑k=1njk2n-k, called the n bits binary representation of j. Integer j and n tuple j1⋯jn will be regarded as the same from here. The degree of monomial xj on F2n is not j itself but the number of support supp⁡(j)={k:jk≠0}, called the weight of j and denoted as wt(j). The degree of mapping F:F2n→F2n is deg⁡F=max⁡{wt(i):ai≠0}, the highest degree of all nonzero monomials in its ANF. For example, linear mappings on F2n are in the form L(x)=∑i=0n-1lix2i. Trace mapping tr⁡(x)=∑i=0n-1x2i is a linear mapping only of values 0 or 1.Definition 4.
Two mappingsF′ and F over F2n are called extended affine- (EA-) equivalent if there are affine permutations A1, A2, and A over F2n such that F′=A1∘F∘A2+A and affine-equivalent if A=0.


## 2. Methods and Tools

Lemma 5.
F
(
x
) over F2n is EA-equivalent to permutation if and only if there is linear mapping L(x) such that F(x)+L(x) is permuted on F2n.Proof.
IfA1∘F∘A2+A is permuted, then A1-1∘(A1∘F∘A2+A)∘A2-1=F+A1-1∘A∘A2-1 is also permuted over F2n. A1-1∘A∘A2-1=∑i=0n-1lix2i+c denotes that F(x)+∑i=0n-1lix2i, thereby permuted over F2n.Circulation and cycle are introduced to identify and combine similar terms intr⁡(∑i=02n-1aixi).Definition 6.
Consider the circulation mappingg:Z2n→Z2n defined as g(j1j2⋯jn)=j2⋯jnj1, which means 2j when j≤2n-1-1 or 2j-2n+1 when j≥2n-1. c(j)={gi(j):i∈Z} is called the circulation orbit of j and its order c(j)=min⁡{i∈N∗:gi(j)=j} minimal positive period of j.The lemma below is obvious sincetr⁡(aixi) and tr⁡(ajxj) have no similar terms when i∉c(j).Lemma 7.
tr
⁡
(
∑
i
=
0
2
n
-
1
a
i
x
i
)
=
0 if and only if tr⁡(∑i∈c(j)aixi)=0 for every 0≤j≤2n-1.


## 3. Main Result and Proof

IfDaF(x)=0 has no solution for any a∈F2n∖0, then F(x) is permuted. If a exists, such that aT(Ax+b)=1, then Ax+b=0 has no solution based on linear algebra. If DaF(x) is 2-1, then rank⁡A=n-1 and a, which satisfies aTA=0, is unique. Furthermore, a satisfies aTb=1.Iftr⁡(a3)=0, then tr⁡(a3Da-1(x3+tr(x9)+L(x)))=tr⁡(a3L(a-1)+1). If tr⁡(a3L(a-1))=0 when tr⁡(a3)=0, then tr⁡(a3)+1tr⁡(a3L(a-1))=0 for any a. Obviously, L(x)=b2x+bx2 and L(x)=tr⁡(bx) satisfy the identity. Theorem 8 will show that all kinds of L(x) satisfying the identity are the adding of the two kinds above.Theorem 8.
One assumes thatn≥9 and L(x)=∑i=0n-1lix2i over F2n. If tr⁡a3+1tr⁡(a3L(a-1))≡0, then(1)Lx=l1+b2x+l1+bx2+tr⁡bx.Proof.
Initially,(2)tr⁡a3+1tr⁡a3La-1=tr⁡a3tr⁡a3+1La-1=tr⁡∑i=0n-1a32i+1+a3La-1.
The exponents3(2i+1)+(-2j) and 3+(-2j) (plus negative will be denoted as minus for convenience) can be divided into the following orbits: 1:3-20, 3-21, 3(20+1)-21, 3(20+1)-22, 3(21+1)-20, 3(21+1)-23, 3(2n-1+1)-22, 3(2n-1+1)-2n-1.101⋯1:3-2j(2≤j≤n-1),  3(20+1)-2j(j=0 or 3≤j≤n-1),  3(2i+1)-2j(2≤i≤n-2,  j=i+2) or j=i+2 and 101 of 3(21+1)-22 and 3(2n-1+1)-21 and 1011 of 3(23+1)-24 and 3(2n-3+1)-21.10⋯011:3(2i+1)-2j(2≤i≤n-2,j=0,1,i,i+1), 100011 of 3(21+1)-2n-2 and 3(2n-1+1)-2n-3, 111 of 3(21+1)-21 and 3(2n-1+1)-20.101⋯10⋯011:3(2i+1)-2j,  4≤i≤n-2,  3≤j≤i-1 or i+3≤j≤n-1.10001⋯1:3(21+1)-2j and 3(2n-1+1)-2j with j unequal to n-2 and n-3. The condition n≥9 can distinguish this class from 10100011.The following equations were formulated based on Lemma7:(3)1:l01/2+l1+l11/4+l21/2+l01/8+l3+ln-11/4+l22=0101⋯1:lj+lj+11/2+lj+2+l22j=02≤j≤n-3101:ln-1+l01/2+l21/2+l1=01011:ln-2+ln-11/2+l0+l21/4+l41/4+l12=0100011:ln-2+ln-32+l41/4+l04+l61/4+l18=0111:l1+l02+l3+l14+l01/2+ln-22=010⋯011:l3+l08+l5+l116=0li+l02i+li+2+l12i+1=05≤i≤n-3101⋯10⋯011:li=ln+i-j2j=03≤i≤n-3,2≤j≤n-i-1.The last equation implies thatli=lj2i-j for all 3≤i,j≤n-1. We let b=ln-12; then li=b2i for all 3≤i≤n-1.We letj=n-3 in the second equation; thus, ln-3+ln-21/2+ln-1+l22n-3=ln-1+l22n-3=0. Therefore, l2=b4.Moreover,ln-1=b1/2 and l2=b4 are substituted into the third equation; thus, (l0+b)1/2=l1+b2.Therefore,L(x)=(l1+b2)2x+(l1+b2)x2+tr⁡(bx).x
3
+
tr
⁡
(
x
9
)
+
L
(
x
) cannot be permuted unless L(x) is in the form ax2+a2x+tr⁡(bx). Thus only x3+tr⁡(x9)+ax2+a2x+tr⁡(bx) should be considered. If y=x+a, then it is equal to y3+tr⁡(y9)+tr⁡(by+a8y+ay8)+a3+tr⁡(a9+ab), only different in a constant with y3+tr⁡(y9)+tr⁡(b′y), in which b′=b+a8+a1/8.Theorem 9.
x
3
+
tr
⁡
(
x
9
)
+
tr
⁡
(
b
x
) with n≥5 odd is not permuted.Proof.
x
3 is permuted on F2n because n is odd; its inverse is xt in which supp⁡(t)={1,3,…,n}. So the theorem is equal to x+tr⁡(x3)+tr⁡(bxt) which is not permuted. There is D1(x+tr⁡(x3)+tr⁡(bxt))=D1tr⁡(bxt)=tr⁡(b∑j∈Λxj), in which Λ={0≤j≤2n-1:supp⁡(j)⊂supp⁡(t)}. Every j with j1=jn=1 satisfies i∉c(j) if i∈Λ∖{j}, which means tr⁡(bxj) has no similar terms with tr⁡(bxi); and c(j)=n, which means the terms in tr⁡(bxj) are not similar to each other. Since j1 and jn will be adjacent after circulation, when j1=jn=1 there is Λ∩c(j)=j, which means bxj is not similar to other terms in tr⁡(b∑j∈Λxj). Thus ANF of tr⁡(b∑j∈Λxj) is not 1. According to Definitions 2 and 3, there exists x∈F2n such that tr⁡(bxt)=tr⁡(b(x+1)t). However, x+tr⁡(x3) is equal to x+1+tr⁡(x+1)3.


## 4. Conclusions

The AB class in [11] when n≥9 is EA-inequivalent to permutations. However, distinguishing whether the AB class is CCZ-equivalent to permutations is still unknown. Furthermore, the relationship of the permutations of the APN classes in [6, 8–10] and class with trm/n in [7] is unknown. The solution to these problems will be a significant topic in algebra and cryptography in the future.



---

*Source: 9627840-2017-08-13.xml*