Generalized isotopic shift construction for APN functions

https://doi.org/10.1007/s10623-020-00803-1

Generalized isotopic shift construction for APN functions

Lilya Budaghyan¹·Marco Calderini¹ ·Claude Carlet^1,2·Robert Coulter³· Irene Villa¹

Received: 18 March 2020 / Revised: 24 June 2020 / Accepted: 8 September 2020

© The Author(s) 2020

Abstract

In this work we give several generalizations of the isotopic shift construction, introduced recently by Budaghyan et al. (IEEE Trans Inform Theory 66:5299–5309, 2020), when the initial function is a Gold function. In particular, we derive a general construction of APN functions which covers several unclassified APN functions forn =8 and produces fifteen new APN functions forn=9.

Keywords APN functions·Isotopic shift·Vectorial Boolean functions Mathematics Subject Classification 94A60·11T71·06E30

1 Introduction

Forna positive integer, letF2ⁿ be the finite field with 2ⁿelements. ByF₂n we denote the multiplicative group ofF2ⁿand, throughout the paper,ζdenotes one of its primitive elements,

Communicated by A. Pott.

Parts of this work were presented atWCC 2019: The Eleventh International Workshop on Coding and Cryptography.

B

[email protected] Robert Coulter

[email protected] Irene Villa [email protected]

1 Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway 2 LAGA, University of Paris 8, Saint-Denis, France

3 Department of Mathematical Sciences, University of Delaware, Newark, DE, USA

so thatF₂n = ζ = {1, ζ, ζ², ζ³, . . . , ζ²ⁿ⁻²}. An(n,n)-function is a map fromF2ⁿto itself.

Such function admits a unique representation as a univariate polynomial of degree at most 2ⁿ−1, that is

F(x)=

2ⁿ−1 j=0

ajx^j, aj∈F2ⁿ.

The kernel ofFis defined as ker(F)= {u∈F2ⁿ s.t.F(u)=0}.

The functionFis – linearifF(x)=_n−1

i=0 c_ix²ⁱ;

– affineif it is the sum of a linear function and a constant;

– DO(Dembowski-Ostrom)polynomialifF(x)=

0≤i<j<nai jx^2i+2j, withai j ∈F2ⁿ; – quadraticif it is the sum of a DO polynomial and an affine function.

A function F is calleddifferentiallyδ-uniform, forδ a positive integer, if for any pair (a,b) ∈F²₂n, witha =0, the equationF(x+a)−F(x) =badmits at mostδsolutions.

WhenFis used as an S-box inside a cryptosystem, the differential uniformity measures its contribution to the resistance to the differential attack [3]. The smaller isδ, the better is the resistance to this attack.

Over fields of characteristic 2, the solutions of the equationF(x+a)−F(x)=b, that is,F(x+a)+F(x)=b, go by pairs{x,x+a}, andδis even. The best resistance is then achieved by differentially 2-uniform functions. Such functions are also calledalmost perfect nonlinear; in short, APN. The simplest known example of APN function is Gold function, Gi(x)=x²ⁱ⁺¹, that is APN wheneveriis coprime withn.

APN functions have connections to optimal objects in other fields such as geometry, sequence design and combinatorics.

There are several equivalence relations of functions for which differential uniformity, and thus the APN property, is preserved. Two functionsFandFfromF2ⁿ to itself are called:

– affine equivalent ifF=A1◦F◦A2whereA1,A2:F2ⁿ →F2ⁿare affine permutations;

– EA-equivalent ifF=F+A, where the mapA:F2ⁿ →F2ⁿ is affine andFis affine equivalent toF;

– CCZ-equivalent [12] if there exists some affine permutationL ofF2ⁿ ×F2ⁿ such that the image of the graph of Fis the graph of F, that is,_L(G_F)= G_F, whereG_F = {(x,F(x)) : x ∈F2ⁿ}andG_F= {(x,F(x)) : x ∈F2ⁿ}.

CCZ-equivalence is the most general known equivalence relation for functions which pre- serves differential uniformity, while affine and EA-equivalences are its particular cases. We refer the reader to [5] and [11] for a more comprehensive overview on vectorial Boolean functions.

Inspired by the notion ofisotopic equivalence, originally defined by Albert [1] in the study of presemifields and semifields, a new construction method for APN functions, called isotopic shift, was introduced in [6].

Given pa prime number, F ∈ Fpⁿ[x]a function, and L ∈ Fpⁿ[x]a linear map, the isotopic shiftofFbyLis defined as the map:

F_L(x)=F(x+L(x))−F(x)−F(L(x)). (1) As we have shown in [6], for the casep=2, an isotopic shift of an APN function can lead to APN functions CCZ-inequivalent to the original map. In particular, all existing quadratic APN functions overF₂⁶, which are 13 up to CCZ-equivalence, can be obtained fromx³by

isotopic shift. Moreover, a new family of quadratic APN functions, which generates a new APN function forn =9, is constructed by isotopic shift of Gold functions [6]. In [7], the isotopic shift construction has been investigated for the case of planar functions (p>2), i.e.

differentially 1-uniform functions. Also here, given a planar function, it is possible to obtain an inequivalent planar function from its isotopic shifts.

In the present paper we further study the isotopic shift construction over fields of even characteristic. Firstly, we verify that, overF2⁶, any quadratic APN map can be obtained as an isotopic shift of any other quadratic APN map. Then, we consider different generalizations of the isotopic shift construction when the initial function is a monomial with a Gold exponent.

In [6], we studied the APN property of the isotopic shift ofGi(x)= x²ⁱ⁺¹ overF2ⁿ, with n=km, given by

Gi,L(x)=x L(x)²ⁱ +x²ⁱL(x), (2) whereLis a 2^m-polynomial, that isL(x) = _k−1

i=0 Aix^{2i m} for some Ai ∈F2ⁿ. This con- struction provides a new APN function overF2⁹.

In the present work, we study the APN property ofx L1(x)²ⁱ +x²ⁱL2(x)where bothL1

andL₂ are 2^m-polynomials. From this construction, we obtain fifteen new APN functions forn=9. Moreover, we cover some of the functions in the lists given in [16] and [19] which are not contained in any of the known infinite families.

To show the inequivalence between some of the obtained maps, we introduce in Propo- sition3.2a new EA-invariant (such invariant was also noticed independently in [17]). Note that for quadratic APN functions, CCZ-equivalence coincides with EA-equivalence [23].

Finally, we consider the case when the isotopic shift ofGi(x)is obtained using a function Lnot necessarily linear. In this case we obtain that all the known power APN functions in odd dimension, except the Dobbertin function, can be obtained as the nonlinear shifts of Gold functions.

2 Further results on the isotopic linear shift overF2ⁿ

Before considering generalizations of the isotopic shift, we extend a result obtained in [6].

We have shown that, given a quadratic APN function F, if the isotopic shift F_L by a linear mapL is APN, then the map L is either a permutation or a 2-to-1 map. From the isotopic shifts of the Gold functionx³, with both choices forLbeing a permutation and a 2-to-1 map, we obtained (computationally) all the quadratic APN functions overF₂⁶ (up to EA-equivalence). That is, for any given quadratic APN functionF overF₂⁶ there exist a permutationL and a 2-to-1 map Lsuch that the isotopic shiftsG_1,L(x)andG_1,L(x)are EA-equivalent toF. The same result was computationally obtained for any quadratic APN map overF2⁶ listed in [16, Table 5] (see also [4]) in place of_G1. Up to EA-equivalence (and thus CCZ-equivalence) the list is complete and, since for two quadratic maps the EA- equivalence implies EA-equivalence of the isotopic shifts (see [6, Corollary 3.2]), we can state the following result.

Proposition 2.1 OverF2⁶ for any two quadratic APN maps F and G, there exist a linear permutation L and a linear 2-to-1 map Lsuch that FLand FL are EA-equivalent to G.

We conclude with the observation that the isotopic shift can lead to an APN function also starting from a non-APN function.

Remark 2.1 ConsiderF2⁶and the functionF(x)=x⁵, which is not APN. WithL(x)=ζx⁸ we construct the APN map

FL(x)=x⁴L(x)+x L(x)⁴=ζx¹²+ζ⁴x³³, whereFL(x)=M(x³)for the linear permutationM(x)=ζx⁴+ζ⁴x³².

3 Generalized isotopic shift of Gold functions

In this section we generalize the isotopic shift construction for the case of Gold functions.

3.1 On the generalized linear shift overF2ⁿ

In [6], we showed that the isotopic shift can be a useful construction method for APN functions. Letn = km, wheremandk are any positive integers. AnF2^m-polynomial is a linear map given byL(x)=_k−1

j=0A_jx^{2j m}, for some A_j ∈F2ⁿ. The constructionG_i,L(x) as in (2) leads to a family of APN functions, providing, in particular, forn=9 (k,m =3) a new APN function and forn= 8 (k =4,m =2) a function equivalent tox⁹+Tr(x³), which is not contained in any infinite family.

In the following, we generalize the isotopic shift construction. This generalization provides further new APN functions, as it will be shown below.

Given two positive integersk,m, let us consider the finite fieldF2ⁿwithn=km. Denoting d = gcd(2^m−1,²₂^kmm−1⁻¹), let d be the positive integer with the same prime factors as d, satisfying gcd(2^m−1,₍₂²m^km−1)d⁻¹) = 1. Now, letU = ζ^d(2m−1)be the multiplicative subgroup ofF₂n of order₂km−1

2^m−1

/d. Note that it is possible to write every elementx∈F₂n

asx =utwithu∈Wandt ∈F₂m, whereW= {ζ^sy:y∈U, 0≤s≤d−1}. Indeed, let F₂mk = ζ, we havex=ζ^dz+j, for some integerszandjwhere 0≤ j ≤d−1. For ease of notation, setl= ₍₂²m^mk−⁻¹1)d. Since gcd(2^m−1,l)=1, for any suchz, there exist integersr andssuch thatz=r(2^m−1)+sl. Hence we have

x=ζ^dz+j=ζ^dr(2m−1)ζ^jζ^dsl=ut,

where, denotingy =ζ^dr(2m−1)∈U, we haveu= yζ^j ∈Wandt =ζ^dsl =ζ^{s(22mkm−1−1)} ∈ F₂^m. Since|{(u,t):u∈W,t∈F₂^m}| = |W|·|F₂^m| =(d|U|)·(2^m−1)=d·_d²(2^mkm−1−1)·(2^m− 1)=2^mk−1= |F₂mk|, two distinct elements inF₂mk cannot have the same representation, souandtare unique.

Then it is possible to obtain the following generalization of [6, Theorem 6.3].

Theorem 3.1 Let n = km for m > 1. Let L1(x) = _k−1

j=0Ajx^{2j m} and L2(x) = _k−1

j=0Bjx^{2j m}be twoF2^m-polynomials. Then, let i be such thatgcd(i,m)=1and F∈F2ⁿ[x] the function given by:

F(x)=x L₁(x)²ⁱ+x²ⁱL₂(x). (3) Then F is APN overF2ⁿ if and only if each of the following statements holds for anyv∈W :

– (^L1_v^(v))²ⁱ =^L2_v^(v);

– If u∈W\ {1}and(^L1_u^(uv)_v )²ⁱ = ^L2_v^(v), then(^L1_v^(v))²ⁱ = ^L2_u^(uv)_v ;

– If u∈W\ {1}and(^L1_uv^(uv))²ⁱ =^L2_v^(v), then^L1(v)2

i(uv)+L₂(uv)v²ⁱ L₁(uv)²ⁱv+L₂(v)(uv)²ⁱ ∈/F₂m.

Proof We need that, for anya∈F₂n, the functionΔa(x)=F(x+a)+F(x)+F(a)+F(0) is a 2-to-1 map, or equivalently, that ker(Δa(ax)) = {0,1}. As showed before, we can rewritea = st andx = uvwiths,u ∈ F₂m andt, v ∈ W. Hence, sinceL₁ andL₂ are F2^m-polynomials, we have:

Δa(ax)=L₁(a)²ⁱax+L₂(a)(ax)²ⁱ+L₁(ax)²ⁱa+L₂(ax)a²ⁱ

=s²ⁱL₁(t)²ⁱst·uv+s L₂(t)s²ⁱt²ⁱ ·u²ⁱv²ⁱ+s²ⁱu²ⁱL₁(tv)²ⁱst+su L₂(tv)s²ⁱt²ⁱ

=us²ⁱ⁺¹[(L1(t)²ⁱtv+L2(tv)t²ⁱ)+u²ⁱ⁻¹(L2(t)t²ⁱv²ⁱ +L1(tv)²ⁱt)].

Without loss of generality we can assume thats=1. So,Fis APN overF2ⁿ if and only if u=0 oru=v=1 are the only solutions toΔt(uvt)=0 for anyt ∈U.

Ifv=1, then

Δt(t x)=u(L1(t)²ⁱt+L2(t)t²ⁱ)[1+u²ⁱ⁻¹].

Since gcd(i,m)=1,x²ⁱ⁻¹is a permutation overF2^m and thus ker(Δt(t x))= {0,1}if and only if ^L1(t)2

i

t²ⁱ = ^L2_t^(t).

Assume now thatv=1. Then, ifL2(t)t²ⁱv²ⁱ +L1(tv)²ⁱt=0, we have:

Δt(t x)=u[(L₁(t)²ⁱtv+L₂(tv)t²ⁱ)].

This implies^L1(t)2

i

t²ⁱ = ^L2_tv^(tv).

IfL₂(t)t²ⁱv²ⁱ +L₁(tv)²ⁱt=0, then

[(L1(t)²ⁱtv+L2(tv)t²ⁱ)+u²ⁱ⁻¹(L2(t)t²ⁱv²ⁱ +L1(tv)²ⁱt)] =0 impliesu²ⁱ⁻¹ = ^{L1(t)2itv+L2(tv)t2i}

L2(t)t²ⁱv²ⁱ+L1(tv)²ⁱt. Sincex²ⁱ⁻¹ is a permutation overF2^m this equation admits a solution different from zero if and only if ^L1(t)2

itv+L2(tv)t²ⁱ

L2(t)t²ⁱv²ⁱ+L1(tv)²ⁱtis contained inF₂m. The obtained APN function (3) is of the form

F(x)=(A²₀ⁱ+B₀)x²ⁱ⁺¹+ k−1

j=1

[A²_jⁱx^{2i+j m+1}+B_jx^{2j m+2i}].

Let us see now necessary conditions on the linear functionsL₁andL₂forFto be APN.

Proposition 3.1 Let n,L1,L2and F be as in Theorem3.1. If F is APN overF2ⁿ, then the following statements hold:

(i) ker(L1(x)+r x)∩ker(L2(x)+r²ⁱx)= {0}for any r ∈F2ⁿ; (ii) |ker(L1(x)²ⁱ +r x)∩ker(L2(x)+w²ⁱx²ⁱ)| ≤2for any r, w∈F2ⁿ; (iii) Ifker(L1)∩ker(L2(x)+x)= {0}, thenker(L1(x)+x)∩ker(L2)= {0};

(iv) ker(L₁(x)+r x^2j)∩ker(L₂(x)+r²ⁱx^(2j−1)2i+1)= {0}for any r ∈F2ⁿ and j≥0.

Proof For any nonzeroa, we define the functionΔa(x)=F(x+a)+F(x)+F(a)+F(0) and, witht∈F2^m, we have

Δa(x)=a L1(x)²ⁱ +x L1(a)²ⁱ+x²ⁱL2(a)+a²ⁱL2(x), Δa(at)=(t+t²ⁱ)(a L₁(a)²ⁱ +a²ⁱL₂(a)).

Suppose there exists a non-zeroa∈ker(L1(x)+r x)∩ker(L2(x)+r²ⁱx). We clearly have aF2^m ⊆ker(Δa), but sincem>1, this contradicts|ker(Δa)| =2. This establishes (i).

For (ii), suppose{0,a,b} ⊂ker(L1(x)²ⁱ +r x)∩ker(L2(x)+w²ⁱx²ⁱ). Then Δa(b)=a(r b)+b(r a)+a²ⁱ(w²ⁱb²ⁱ)+b²ⁱ(w²ⁱa²ⁱ)=0.

Next supposea∈ker(L₁)∩ker(L₂(x)+x). Then we haveΔa(x)=a(L₁(x)+x)²ⁱ+ a²ⁱL2(x). Clearly anyb∈ker(L1(x)+x)∩ker(L2)satisfiesΔa(b)=0. Since f is APN, ker(Δa)= {0,a}, so that ker(L1(x)+x)∩ker(L2)⊂ {0,a}. However, ker(L1)∩ker(L1(x)+

x)= {0}, so that no non-zero element ofF2ⁿ can lie in both ker(L1)∩ker(L2(x)+x)and ker(L₁(x)+x)∩ker(L₂). This establishes (iii).

For (iv), supposea∈ker(L1(x)+r x^2j)∩ker(L2(x)+r²ⁱx^(2j−1)2i+1)is non-zero. Then for anyt∈F2^m we have

Δa(ta)=(t+t²ⁱ)(a L₁(a)²ⁱ +a²ⁱL₂(a))

=(t+t²ⁱ)(ar²ⁱa^2j2i +a²ⁱr²ⁱa^(2j−1)2i+1)=0,

so thataF2^m ⊆ker(Δa), a contradiction.

3.2 The casen=8

Applying the construction of Theorem3.1in dimension 8 withk=4 andm=2, restricting the coefficients ofL1andL2to the subfieldF₂⁴ we obtained several APN functions given in [16, Table 9] and one in [19, Table 6] which have not been previously identified as a part of any APN family. The functions mentioned are listed in Table1.

The following results were obtained forn=8.

– Considering generalized isotopic shifts ofx³it is possible to obtain maps EA-equivalent to nos. 1.2, 1.5, 1.7, 1.8, 1.10, 1.11, 1.12, 1.16, 1.17, 3.1 in Table 9 [16] and to no. 9 in Table 6 of [19].

– Considering generalized isotopic shifts of x⁹ it is also possible to obtain maps EA- equivalent to no. 1.3 Table 9 [16].

Remark 3.1 The function no. 9 in Table 6 [19] has the same CCZ-invariants (Γ-rank,Δ-rank andMGF) as the function number 1.9 in Table 9 of [16] (we note that the value of theΓ-rank given in [19] is not correct, indeed this function hasΓ-rank = 14034).

Since two quadratic APN functions are CCZ-equivalent if and only if they are EA- equivalent [23], the CCZ-inequivalence between these two functions can be obtained by checking another invariant with respect to the EA-equivalence that we shall introduce in the next subsection.

Table 1 APN polynomials overF2⁸derived from Theorem3.1

Functions Equiv. to no. in Table 9 in [16]

ζ¹³⁶x⁶⁶+ζ⁸⁵x³³+ζ⁸⁵x¹⁸+ζ¹⁰²x⁹+ζ²²¹x⁶+x³ No. 9 in Table 6 in [19]

ζ¹⁰²x⁶⁶+ζ²⁰⁴x⁹+x³ 1.2

ζ¹⁵³x¹²⁹+ζ²⁰⁴x⁶⁶+ζ¹⁷⁰x³³+ζ⁸⁵x¹⁸+ζ²⁰⁴x⁶+x³ 1.5 ζ¹⁰²x¹²⁹+ζ¹⁵³x⁶⁶+ζ¹⁷⁰x³³+ζ²²¹x¹⁸+ζ²²¹x⁹+ζ¹⁸⁷x⁶+x³ 1.7

x⁶⁶+ζ⁸⁵x³³+x¹⁸+x⁹+x³ 1.8

ζ²⁰⁴x¹²⁹+ζ¹⁷⁰x⁶⁶+ζ¹⁵³x³³+ζ⁸⁵x¹⁸+ζ¹⁵³x⁹+ζ¹⁷x⁶+x³ 1.10

ζ²⁰⁴x⁶⁶+x³³+x¹⁸+ζ¹⁵³x⁹+x³ 1.11

ζ¹⁷⁰x¹²⁹+ζ²⁰⁴x⁶⁶+ζ¹⁷x³³+ζ⁶⁸x¹⁸+ζ²²¹x⁹+ζ²⁰⁴x⁶+x³ 1.12 ζ²³⁸x¹²⁹+ζ²⁰⁴x⁶⁶+ζ¹¹⁹x³³+ζ⁶⁸x¹⁸+ζ⁸⁵x⁹+ζ¹¹⁹x⁶+x³ 1.16 ζ¹⁷x¹²⁹+ζ⁸⁵x⁶⁶+ζ³⁴x³³+ζ³⁴x¹⁸+ζ¹⁸⁷x⁹+ζ¹⁸⁷x⁶+x³ 1.17 ζ¹⁷x¹²⁹+ζ²³⁸x⁶⁶+ζ¹⁵³x³³+ζ⁸⁵x¹⁸+ζ²³⁸x⁹+ζ¹⁰²x⁶+x³ 3.1 ζ¹⁵³x¹²⁹+ζ²²¹x⁷²+ζ¹⁷⁰x³³+ζ¹⁰²x²⁴+x¹²+x⁹+ζ¹³⁶x³ 1.3 All are either new or correspond to the known but unclassified cases

3.3 A new EA-equivalence invariant

Let S(F) = {b ∈ F2ⁿ : ∃a ∈ F2ⁿ s.t.WF(a,b) = 0}, where WF(a,b) =

x∈F2n(−1)Tr(ax+b F(x)) is the Walsh coefficient of F in a andb. This set was used in [8] to study some relations between the CCZ-equivalence and the EA-equivalence.

It is easy to check that:

– ifF(x)=F(x)+L(x)withLlinear, thenb∈S(F)if and only ifb∈S(F). – IfF(x)=A₁◦F◦A₂(x)withA₁,A₂affine permutations, thenb∈S(F)if and only

ifA¯^∗₁(b)∈S(F), whereA¯^∗₁is the adjoint operator of the linear map A1(x)+A1(0).

From this we have the following.

Proposition 3.2 Let N_i be the number of theF2-vector subspaces ofF2ⁿ contained in S(F) of dimension i . Then, the values N_i for i=1, ...,n are EA-invariant.

Proof IfFis EA-equivalent toF, then there existA1,A2affine permutations andLlinear such thatF(x)= A1◦F◦A2(x)+L(x). From the arguments above, denoting A¯1(x)= A₁(x)+A₁(0)we have thatS(F)= ¯A^∗(S(F)). Remark 3.2 We computed the valuesNifor the two functions and we gotN1=86,N2=340 andN3 = 4 for the new function, andN1 = 86,N2 = 340 and N3 = 8 for the function number 1.9. Thus from Proposition3.2we have that the two functions are not EA-equivalent.

Remark 3.3 Note that whennis odd, a quadratic APN functionFis Almost Bent (i.e. for all b∈F₂nwe have{WF(a,b) : a∈F2ⁿ} = {0,±2^(n+1)/2}), which impliesS(F)=F2ⁿ. Thus, such invariant cannot be used for testing the CCZ-equivalence of quadratic APN functions in the casenodd.

Remark 3.4 In fact, this EA-invariant was tackled independently by Gölo˘glu and Pavl˚u in [17]. In their work, they focused on plateaued functions and looked at the subspaces in the set{b : WF(0,b)= ±2^n/2}(neven). For plateaued functions, this set coincides withS(F).

3.4 The casen=9

For the casek = m = 3 we consider the generalized linear shift as in (3) with L₁ and L2having coefficients in the subfieldF₂³. In Table2we list all known APN functions for n=9, as reported in [6, Table 1]. In Table3, we list all new APN functions obtained from Theorem3.1. We can observe that the family of Theorem3.1covers the only known example of APN function forn=9, function 8.1 of Table 11 in [16], which has not been previously identified as a part of an APN family. Hence, currently, we do not have any known example of APN functions forn=9 which would not be covered by an APN family. Note that this latter function was not obtained from the approach studied in [16] (it does not belong to a switching class of a previously known APN map). Finally, Table3indicates 15 new APN functions all obtained from Theorem3.1. In both tables we include, for each function, the CCZ-invariantsΓ-rank,Δ-rank and|MGF|.

The CCZ-inequivalence of some of these functions was obtained by checking with MAGMA the equivalence of some linear code which can be associated to an APN func- tion (see [4]).

3.5 Isotopic shifts with nonlinear functions

In this section we consider the case when the function used in the shift is not necessarily linear.

In [6], it has been proved that, in even dimension, an isotopic shift of the Gold function with a linear function defined overF2[x]cannot be APN. In the following, we show that for any quadratic functionFin even dimension, we cannot obtain APN functions by shiftingF with a polynomial whose coefficients belong toF2.

Proposition 3.3 For two integers k and m let n = km and q = 2^k. Consider a function F∈F2ⁿ[x]of the form

F(x)=

i<j

bi jx^qi+qj +

i

bix²ⁱ+c,

If n is even or k>1, then any isotopic shift F_Lwith L∈F₂^k[x]cannot be APN. In particular, this holds for any quadratic function F∈F2ⁿ[x]with n even and L∈F2[x].

Proof ForFandLas outlined, we have

FL(x)=

i<j

bi j[x^qiL(x)^qj +x^qjL(x)^qi] +c

andL(x^q)= L(x)^q. Note that for anyx ∈F2^k,FL(x)=c. Fora ∈F2ⁿ, we setΔa(x)= FL(x+a)+FL(x)+FL(a)+FL(0).

Ifk>1, thenΔa(x)=0 for allx,a∈F₂^k, so thatFLis not APN. IfF4= {0,1, α, α+ 1} ⊆F2ⁿ, then considerΔ_α(x). ClearlyΔ_α(0)=0, while it is easily observed thatΔ_α(α+

Table2PreviouslyknownCCZ-inequivalentAPNpolynomialsoverF29andtheirrelationtopreviouslyknownfamiliesofAPNfunctions FunctionsFamiliesno.Table11in[16]Γ-rankΔ-rank|MGF| x3Gold1.1384708729·29·511 x5Gold2.1414948729·29·511 x17Gold3.1384708729·29·511 x13Kasami4.15867630869·511 x241Kasami6.16172634829·511 x19Welch5.16089439569·511 x255Inverse7.1130816930242·9·511 Tr 9 1939(x)+x[9]1.2478909209·2 Tr

9 318939(x+x)+x[10]1.3484289309·2 Tr 9 3361839(x+x)+x[10]1.4484609449·2 3104381369x+x+ζx–8.1486089383·7·2 33712942466217103439ζx+ζx+ζx+ζx+ζx[6]–485969443·7·2

Table3APNpolynomialsoverF29derivedfromTheorem3.1 GiFunctionEq.toknownonesΓ-rankΔ-rank|MGF| i=1x129+ζ146x66+x17+ζ365x10+x3eq.toAPNfunctionin[6]4859694429·3·7 i=1ζ219x129+ζ292x66+ζ292x17+ζ219x10+x3new4850693629·3·7 i=1ζ365x129+ζ292x66+ζ365x17+ζ73x10+x3new4861093829·3·7 i=1ζ365x129+ζ365x66+ζ146x17+ζ365x10+x3new4861293829·3·7 i=1ζ365x129+ζ219x66+ζ292x17+ζ73x10+x3new4854892829·3·7 i=1ζ73x129+ζ365x66+ζ73x17+ζ73x10+x3new4854892829·3·7 i=1ζ365x129+ζ438x66+ζ292x10+x3new4850693629·3·7 i=1ζ365x129+x66+ζ438x10+x3new4860492829·3·7 i=1ζ73x129+ζ292x66+x10+x3new4856494229·3·7 i=1ζ73x129+x66+ζ219x17+x3new4860492829·3·7 i=2ζ146x257+ζ438x68+ζ438x12+x5new4854693829·3·7 i=2ζ146x257+ζ365x33+ζ365x12+x5eq.to8.14860893829·3·7 i=2ζ73x257+ζ146x68+x33+x5new4856494229·3·7 i=2ζ365x257+ζ438x68+ζ365x33+ζ438x12+x5new4859494429·3·7 i=2ζ146x257+ζ219x68+ζ73x33+x12+x5new4852093229·3·7 i=2ζ73x257+ζ219x68+ζ365x33+x5new4860293829·3·7 i=4ζ292x3+ζ146x80+ζ73x24+x17new4852093229·3·7 All,exceptforthefirstone,areeitherneworcorrespondtotheoneknownbutunclassifiedcase