Differentially low uniform permutations from known 4-uniform functions

https://doi.org/10.1007/s10623-020-00807-x

Differentially low uniform permutations from known 4-uniform functions

Marco Calderini¹

Received: 1 March 2020 / Revised: 9 July 2020 / Accepted: 24 September 2020

© The Author(s) 2020

Abstract

Functions with low differential uniformity can be used in a block cipher as S-boxes since they have good resistance to differential attacks. In this paper we consider piecewise constructions for permutations with low differential uniformity. In particular, we give two constructions of differentially 6-uniform functions, modifying the Gold function and the Bracken–Leander function on a subfield.

Keywords Low differentially uniform·Boolean functions·Permutations·High nonlinearity

Mathematics Subject Classification 94A60·11T71·06E30

1 Introduction

Letnbe a positive integer, we will denote byF2ⁿ the finite field with 2ⁿ elements and its multiplicative group byF₂n. Permutation maps defined overF2ⁿ are used as the S-boxes of some symmetric cryptosystems. So, it is important to construct permutations with good cryptographic properties in order to design a cipher that can resist known attacks. In particular, among these properties we have a low differential and boomerang uniformity for preventing differential and boomerang attacks [1,36], high nonlinearity for avoiding linear cryptanalysis [25] and also not a too low algebraic degree to resist higher order differential attacks [21].

Over a field of even characteristic, the best differential uniformity of a function F is two. Functions achieving this value are called almost perfect nonlinear (APN). Many works have been done on the construction of APN functions (see for instance [4,8–11]). For odd values ofn there are known families of APN permutations; while forn even there exists only one example of APN permutation overF₂⁶ [7] and the existence of others remains an open problem. For ease of implementation, usually, the integernis required to be even in a

Communicated by C. Carlet.

B

1 Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway

Table 1 Primarily-constructed differentially 4-uniform permutations overF2ⁿ(neven) with the best known nonlinearity

Name F(x) deg Conditions In

Gold x²ⁱ⁺¹ 2 n=2k,kodd gcd(i,n)=2 [18]

Kasami x^22i−2i+1 i+1 n=2k,kodd gcd(i,n)=2 [20]

Inverse x²ⁿ⁻² n−1 n=2k,k≥1 [27]

Bracken–Leander x^22k+2k+1 3 n=4k,kodd [5]

Bracken–Tan–Tan ζx²ⁱ⁺¹+ζ^2mx^2−m+2m+i 2 n=3m,meven,m/2 odd,

gcd(n,i)=2, 3|m+i [6]

andζis a primitive element ofF2ⁿ

cryptosystem. Therefore, finding permutations with good cryptographic properties overF2ⁿ

withneven is an interesting research topic for providing more choices for the S-boxes.

The construction of low differentially uniform permutations with the highest nonlinearity overF2ⁿ (with n even) is a difficult task. In Table 1we give five families of primarily constructed differentially 4-uniform permutations with the best known nonlinearity. For all these primarily constructed permutations, but the Kasami function, the boomerang uniformity as been determined [3,12,26]. Note that amongst these functions, the Gold, Bracken–Leander and the Bracken–Tan–Tan functions have algebraic degrees 2 or 3.

In the last years, many works on permutations with low differential uniformity have been done. Several constructions of differentially 4-uniform permutations have been found by modifying the inverse function on some subsets ofF2ⁿ [28,29,31–34,37,39]. For example, some new constructions of differentially 4-uniform functions were obtained by shifting the inverse function on some subsets ofF2ⁿ[32,33]. While in [28,37,39] the authors change the inverse function on some subfields ofF2ⁿ. Moreover, all the functions constructed in those references were proved to have the optimal algebraic degree (n−1) and high nonlinearity.

For the case of 6-uniform permutations, in [2] the authors studied the differential spectra of some power functions. In [16], the authors study some particular sparse permutation polynomials showing, in particular, that we can obtain 6-uniform permutation polynomials of typex⁻¹+γTr(x^r). In [40], the authors give two examples of 6-uniform permutations modifying the Gold function.

In this paper, we investigate the piecewise construction as in [28,37,39] by modifying the image of other well-known 4-uniform permutations on some subfields ofF2ⁿ. In particular, we consider the case of the Gold and of the Bracken–Leander functions. We show that in these cases it is possible to obtain permutations with differential uniformity at most 6. Moreover, if we modify these functions using the inverse function (or a function equivalent to it) on a subfield ofF2ⁿ, then we can obtain permutations with algebraic degreen−1 (which is the highest possible) and high nonlinearity. These results extend those given in [40].

The paper is organized as follows. In Sect.2, we give some notations and preliminaries.

In Sect.3, we just give a result for obtaining 4-uniform permutation using the piecewise construction with APN permutations. In Sect.4, we report our study on the piecewise con- struction coming from the Gold and Bracken–Leander functions. We show that for these functions the construction can produce a permutation with differential uniformity at most 6.

Moreover, when we use the inverse function on the subfield, the obtained function has also algebraic degreen−1 and high nonlinearity. In the last section, we give some results on

the boomerang uniformity for some type of piecewise permutations. In particular, we give an upper bound on the boomerang uniformity of piecewise permutations obtained using a 4-uniform Gold function.

2 Preliminaries

Any functionFfromF2ⁿto itself can be represented as a univariate polynomial of degree at most 2ⁿ−1, that is

F(x)=

2ⁿ−1 i=0

aixⁱ.

The2-weightof an integer 0≤i ≤2ⁿ−1, denoted byw2(i), is the (Hamming) weight of its binary representation. It is well known that the algebraic degree of a functionFis given by

deg(F)=max{w2(i) | ai =0}.

Functions of algebraic degree 1 are calledaffine. Linear functions are affine functions with constant term equal to zero and they can be represented as L(x) = _n−1

i=0 a_ix²ⁱ. For any permutationF:F2ⁿ →F2ⁿit is well known that the algebraic degree can be at mostn−1.

For anym≥1 such thatm|nwe can define the (linear)trace functionfromF2ⁿtoF2^mby Trⁿ_m(x)=

n/m−1

i=0

x^{2i m}. Whenm=1 we will denote Trⁿ₁(x)by Tr(x).

For any functionF:F2ⁿ →F2ⁿ we denote theWalsh transformina,b∈F2ⁿ by WF(a,b)=

x∈F2n

(−1)Tr(ax+b F(x)).

WithWalsh spectrumwe refer to the set of all possible values of the Walsh transform.

The Walsh spectrum of a vectorial Boolean function F is strictly related to the notion of nonlinearity ofF, denoted byNL(F), indeed we have

NL(F)=2ⁿ⁻¹−1

2 max

a∈F2n,b∈F₂n

|WF(a,b)|.

Whennis odd, it has been proved thatNL(F) ≤2ⁿ⁻¹−2ⁿ⁻¹² ; forn even, the best known nonlinearity is 2ⁿ⁻¹−2ⁿ², and it is conjectured thatNL(F)≤2ⁿ⁻¹−2ⁿ². All the functions in Table1reach this value.

The concept of differential uniformity of a functionFis related to the number of solutions of the equationF(x+a)+F(x)=bfora∈F₂nandb∈F2ⁿ.

Definition 2.1 For a functionFfromF2ⁿ to itself, and anya∈F₂n andb∈F2ⁿ, we denote byδF(a,b)the number of solutions of the equationF(x+a)+F(x)=b. The maximum

δF= max

a∈F₂n,b∈F2nδF(a,b)

is called the differential uniformity ofF, and F is said to be differentiallyδF-uniform.

A function F is called almost perfect nonlinear (APN) ifδF =2. Note that the possible minimum value ofδF is 2, since ifx is a solution ofF(x+a)+F(x)=b, thenx+ais also a solution of the equation.

In [17], Cid et al. introduced the concept of Boomerang Connectivity Table for a permu- tationFoverF2ⁿ. Next, in [3] the authors introduced the notion of boomerang uniformity.

Definition 2.2 LetFbe a permutation overF2ⁿ, anda,binF2ⁿ. The Boomerang Connectivity Table (BCT) ofFis given by a 2ⁿ×2ⁿ tableT_F, in which the entry for the position(a,b) is given by

T_F(a,b)= |{x∈F2ⁿ : F⁻¹(F(x)+a)+F⁻¹(F(x+b)+a)=b}|.

Moreover, the value βF= max

a,b∈F₂n

|{x∈F2ⁿ : F⁻¹(F(x)+a)+F⁻¹(F(x+b)+a)=b}|

is called the boomerang uniformity ofF, or we callFaboomerangβF-uniformfunction.

In [17], the authors show thatδF≤βFfor any functionF. Moreover,δF=2 if and only if βF=2. So, APN permutations offer an optimal resistance to both differential and boomerang attacks.

There are several equivalence relations of functions for which the differential uniformity and the Walsh spectrum (and in particular the nonlinearity) are preserved. Two functionsF andFfromF2ⁿ to itself are called:

– affine equivalentifF= A₁◦F◦A₂where the mappingsA₁,A₂ :F2ⁿ →F2ⁿare affine permutations;

– extended affine equivalent(EA-equivalent) if F = F+ A, where the mappings A : F2ⁿ →F2ⁿ is affine andFis affine equivalent toF;

– Carlet-Charpin-Zinoviev equivalent(CCZ-equivalent) if for some affine permutationL ofF2ⁿ ×F2ⁿ the image of the graph ofFis the graph of F, that is,L(GF) = G_F, whereG_F= {(x,F(x)) : x ∈F2ⁿ}andG_F = {(x,F(x)) : x ∈F2ⁿ}.

Obviously, affine equivalence is included in the EA-equivalence, and it is also well known that EA-equivalence is a particular case of CCZ-equivalence and every permutation is CCZ- equivalent to its inverse [14].

The algebraic degree is invariant for the affine equivalence and also for the EA-equivalence for nonlinear functions, but not for the CCZ-equivalence. The boomerang uniformity is preserved by affine equivalence and inverse transformation, but not from EA- and CCZ- equivalence in general [3].

Some secondary construction methods have been introduced to find new low differentially uniform functions from the known ones. For example, some constructions of differentially 4-uniform permutations overF2^2m, of degree m+1, by using Gold APN functions over F₂2m+1, were obtained by Li and Wang in [24], inspired by the idea introduced by Carlet in [13]. In [15], Carlet et al. give a construction of a differentially 4-uniform function over F2^2m from the inverse permutation overF2^2m−1. In the following we will denote the inverse function byx⁻¹(with 0⁻¹:=0).

The inverse function is APN overF2ⁿwhennis odd, and is differentially 4-uniform when nis even [27]. In the recent years, it has been found that a large number of differentially 4-uniform permutations can be obtained by modifying the inverse function on some subset ofF2ⁿ. Among these constructions we have

– The function

F₁(x)=

x⁻¹+1 ifx∈S x⁻¹ ifx∈/S

whereSis some specific subset ofF2ⁿ(neven). Some classes of differentially 4-uniform permutations of this form are given in [29,31,32,34,41]

– The function

F_t1,t2(x)=

t1x⁻¹+t2 ifx ∈F2^s

x⁻¹ ifx ∈/F2^s

wheren=smwithseven andn/sodd,t₁,t₂∈F2^s andt₁=0 [39].

– The function

F_α,β(x)=

β(x+1)⁻¹+α ifx∈F2^s

x⁻¹ ifx∈/F2^s

wheren=smwithseven andn/sodd,α, β ∈F2^sandβ=0 [28].

– The function

F_γ(x)=

(γx)⁻¹ ifx∈U x⁻¹ ifx∈/U

where Tr(γ )=Tr(γ⁻¹)=1 andUis some specific subset ofF2ⁿ(neven such thatn/2 is odd) [30].

– The function

F_γ(x)=

(γx)⁻¹ ifx ∈F2^s

x⁻¹ ifx ∈/F2^s

wheren=smwithseven andn/sodd for anyγ ∈F₂s, and with alsosodd if Tr(γ )=0 [37].

In the next sections, we will study the piecewise construction for the case of Gold and Bracken–Leander 4-uniform permutations and we will show that it is possible to obtain permutations with low differential uniformity.

3 Differentially 4-uniform piecewise functions from APN functions If we use APN permutations in the piecewise construction, then we can obtain a differentially 4-uniform function. This applies in particular to the case ofnodd for which some families of APN permutations are known.

Proposition 3.1 Let n = sm, with m odd. Let f be an APN permutation over F2^s and g∈F2^s[x]an APN permutation overF2ⁿ. Then, the function

F(x)= f(x)+(f(x)+g(x))(x^2s+x)²ⁿ⁻¹=

f(x) if x ∈F2^s

g(x) if x ∈/F2^s

is a differentially 4-uniform permutation.

Proof We need to check that for anya∈F₂n andb∈F2ⁿ the equation

F(x)+F(x+a)=b (1)

admits at most 4 solutions. First considera∈F₂s. Then we can have the equations f(x)+ f(x+a)=b

and

g(x)+g(x+a)=b

ifx ∈F2^s orx ∈/F2^s. In both cases we can have at most 2 solutions which implies that we can have at most 4 solutions for (1).

Whenais not inF2^s, then we can have two cases:

– a solutionxis inF2^sandx+anot;

– both the solutionsxandx+aare not inF2^s.

Let us count the solutions of first type, that is, we want to count the number of pairs in F2^s×(a+F2^s)which are solutions of our equation. To do that, we can count the number of solutions which belong toa+F2^s. Then, considerx∈a+F2^s, from (1) we obtain

g(x)+ f(x+a)=b. (2)

Raising (2) to the power 2^sand adding the result to (2) we have g(x)+g(x^2s)=b^2s+b,

recall thatg(x)^2s =g(x^2s)sinceg ∈F2^s[x]. Moreover, sincegis a permutation overF2ⁿ, forb ∈F2^s we have no solution of this type. Ifb ∈/ F2^s, then we havex^2s = x+cwhit c=a^2s+a=0. Thus, the equationg(x)+g(x^2s)=b^2s+badmits at most two solutionsx andx+c(recall thatgis APN overF2ⁿ). Sincex ∈a+F2^s, we have thatx+c∈a^2s+F2^s

anda^2s +F2^s ∩a+F2^s = ∅. Indeed, ifa^2s+F2^s ∩a+F2^s = ∅, thena^2s+a∈F2^s and thusa^22s =a, implyingF2^2s ⊆F2ⁿ, which is not possible. This implies that we can have at most one solution of (2) ina+F2^s. This leads to at most two solutions of (1).

For the second case, we have that (1) is given by g(x)+g(x+a)=b,

which admits at most 2 solutions. This implies that fora∈/F2^sEquation (1) admits at most

4 solutions.

Remark 3.1 Note that if in Proposition3.1one APN function is a permutation and the other one no, then the piecewise function is still differentially 4-uniform but it may not be a permutation. In particular, the restriction onmodd is necessary for havinggto be an APN permutation (see for instance [19]).

4 Differentially 6-uniform permutations from the Gold and Bracken–Leander functions

In this section we will study the piecewise construction for the case of Gold and the Bracken–

Leander function. Before considering these functions, we will give a general result on the differential uniformity of some piecewise functions.

Theorem 4.1 Let n=sm for some positive integers s and m. Let f and g be two polynomials with coefficients inF2^s, that is f,g∈F2^s[x], and g permutingF2ⁿ. Suppose that:

(H1) f is aδf-uniform function overF2^s; (H2) g is aδg-uniform function overF2ⁿ;

(H3) for any a ∈ F₂s and b∈ F2^s the equation g(x)+g(x+a) =b has no solution in F2ⁿ\F2^s.

Then, the function

F(x)= f(x)+(f(x)+g(x))(x^2s+x)²ⁿ⁻¹=

f(x) if x ∈F2^s

g(x) if x ∈/F2^s

is such that

δF(a,b)≤

max{δf, δg} if a∈F2^s

δg+2 if a∈/F2^s. Proof We need to check the number of solutions of the equation

F(x)+F(x+a)=b. (3)

Suppose thata ∈F₂s. Then, we can have that both the solutionsx andx+aare inF2^s or none is inF2^s. In the first case, (3) becomes

f(x)+ f(x+a)=b,

which has at mostδf solutions ifb∈F2^s and none whenb∈/F2^s. In the second case, we have the equation

g(x)+g(x+a)=b.

From (H3) we have no solution inF2ⁿ \F2^s ifb∈F2^s. Ifb∈/F2^s we can have at mostδg

solutions. Then, fora∈F₂s we have at mostδ=max{δf, δg}solutions for Equation (3) for anyb.

Consider, now,a∈/F2^s. We can have two cases:

(i) a solutionxis inF2^s andx+anot;

(ii) both the solutionsxandx+aare not inF2^s.

We want to count the number of pairs(x,x+a)inF2^s ×(a+F2^s)which are solutions of Equation (3). Without loss of generality, we can supposex∈a+F2^s. Then (3) becomes

g(x)+ f(x+a)=b. (4)

From this, raising (4) by 2^sand adding the result to (4), we obtain the equationg(x)^2s+g(x)= b^2s+b. Denoting byy=g(x), we obtain

y^2s +y=b^2s+b.

The solutions of this last equation are the elements of the cosetb+F2^s. Since we supposed that x ∈ a +F2^s andg permutesF2ⁿ we need to check how many elements we have ing(a+F2^s)∩(b+F2^s), where g(a+F2^s) := {g(x) : x ∈ a+F2^s}. Suppose that

|g(a+F2^s)∩(b+F2^s)| ≥ 2. Then, there existz₁,z₂, w1, w2 ∈F2^s such thatb+z₁ = g(a+w1),b+z₂=g(a+w2)andz₁=z₂,w1=w2. Thus,

g(a+w1)+g(a+w2)=z₁+z₂.

Denoting byx=a+w1anda=w1+w2, we obtain that g(x)+g(x+a)=z₁+z₂.

Thus we would have a solutionx ∈/ F2^s for the equation g(x)+g(x+a) = z₁+z₂, which is not possible by (H3). Therefore,|g(a+F2^s)∩(b+F2^s)| ≤ 1, implying that in F2^s×(a+F2^s)we have at most one pair(x,x+a)which can be solutions of (3).

For the second case we have the equation

g(x)+g(x+a)=b,

which admits at mostδgsolutions for anyb. Then, in total for the casea∈/F2^s Equation (3)

admits at mostδg+2 solutions.

It is easy to note that if also f permutesF2^s, thenFis a permutation overF2ⁿ.

Remark 4.1 Note that Proposition3.1and Theorem4.1use a similar analysis. However, the proof of Proposition3.1relies strictly on the APN property ofgfor the casex ∈F2^s and x+a ∈/F2^s and not on Condition (H3). So we cannot include the result of Proposition3.1 into Theorem4.1.

Remark 4.2 When the functiongin Theorem4.1is a power function, i.e.g(x)=x^d, Con- dition (H3) can be checked only fora=1. Indeed, for any nonzeroawe have that studying

x^d+(x+a)^d =b is equivalent to study

x a

d

+x a +1

d

= b a^d.

Thus, for the case of Gold and Bracken–Leander functions we need to check if the equation x^d+(x+1)^d =bhas no solution inF2ⁿ\F2^s wheneverbis inF2^s.

For the Gold function we have the following.

Lemma 4.1 Let n=sm with s even and m odd. Let k be such thatgcd(k,n)=2. For any b∈F2^s the equation

x^2k+x =b does not admit any solution x inF2ⁿ\F2^s.

Proof Suppose that there existsb ∈F2^s for which the equation admits a solutionx ∈/ F2^s. Then, we have thatx^2k+x =x^2k+s+x^2s, which also implies(x^2s+x)^2k =x^2s+x. Then, x^2s +x ∈F2ⁿ ∩F₂^k =F4 ⊂F2^s. Sincemis odd andx ∈/F2^s this is not possible. Indeed, x^2s+x ∈F2^simplies(x^2s+x)^2s =x^2s+xand thusx^22s =x, and thenx ∈F2ⁿ∩F₂^2s =F2^s.

Thus, we have immediately the following result.

Theorem 4.2 Let n = sm with s even such that s/2and m are odd. Let k be such that gcd(k,n)=2and f be a permutation at most differentially 6-uniform overF2^s. Then

F(x)= f(x)+(f(x)+x^2k+1)(x^2s+x)²ⁿ⁻¹=

f(x) if x∈F2^s

x^2k+1 if x∈/F2^s

is a differentially 6-uniform permutation overF2ⁿ.

Proof Lemma4.1implies that we have no solution inF2ⁿ\F2^s ofx^2k+(x+1)^2k=bwhen

b∈F2^s. Then, we have our claim from Theorem4.1.

For the Gold function it was considered in [40] the case of changing its image on the subfieldF4composing the function with the cycle(1, ω, ω²), whereω²=ω+1; or modifying it using f(x)=x^2k+1+1 over a subfieldF2^s, withs/2 odd. Theorem4.2generalizes the results given in [40].

Also for the case of Bracken–Leander function it is possible to prove a similar result as in Lemma4.1.

Lemma 4.2 Let n=4k=sm with k and m odd. For any b∈F2^s the equation

x^22k+2k+x^22k+1+x^2k+1+x^22k+x^2k+x =b (5) does not admit any solution x inF2ⁿ\F2^s.

Proof The proof is obtained following similar steps to those used in [5, Theorem 1] for proving the differential 4-uniformity of the mapx^22k+2k+1.

Denoting by Tr^4k_k the trace map fromF2^4ktoF2^k, since

Tr^4k_k (x^22k+2k+x^22k+1+x^2k+1+x^22k+x^2k)=0,

from (5) we obtain Tr^4k_k (x)=x^23k+x^22k+x^2k+x=Tr^4k_k (b)=cand thusx^22k+x^2k= x^23k+x+c. From this, Eq. (5) can be rewritten as

x^22k+2k+x(x^23k+x+c)+x^23k=c+b (6) Now, using always the fact thatx^23k+x^22k+x^2k+x =c, we have that raising (6) to the power 2^2kand adding the result to Eq. (6) we obtain

(x+x^22k)²+(c+1)(x+x^22k)=b^22k+b+c=b. (7) Note that, sinceb∈F2^s then alsoc∈F2^s andb∈F2^s.

Now, suppose thatc=1, then Eq. (7) becomes x+x^22k =b²⁻¹ =b. Thus, we can substitutex^22k =x+bin Eq. (5) obtaining

x²+b(x+x^2k)+x^2k=b+b. (8) If we raise (8) by 2^kand we add it to (8), we have

(x+x^2k)²+(b+b^2k+1)(x+x^2k)=b^2k+1+b+b^2k+b^2k. Noting thatb+b^2k=(x+x^22k)+(x+x^22k)^2k =c=1 we have

x+x^2k =(b^2k+1+b^2k+b+b^2k)²⁻¹ =t.

Now, substitutingx^2k =x+tin (8) we obtain the equation x²+x =b+b+bt+t.

Sinceb+b+bt+t ∈F2^swe have thatx²+x=x^2s+1+x^2s. Therefore,x^2s+x ∈F2 ⊂F2^s. This is not possible since it would implyx=x^22s andx ∈F2ⁿ∩F₂^2s =F2^s. Then, ifc=1 we cannot have solutionsx ∈/F2^s.

Consider now,c=1. Substitutingx=(c+1)yin (7) we obtain (c+1)²[(y+y^22k)²+(y+y^22k)] =b.

Note thatc∈F2^k∩F2^sand then ifx∈/F2^s so doy. Now, we have thaty+y^22kis a solution of the equationz²+z=b/(c+1)². Then,y+y^22k =tort+1 for somet ∈F2^s ∩F2^2k

(note thatb∈F2^s and we cannot have solution inF2ⁿ\F2^s forz²+z=b).

Ify+y^22k =tthen we can substitutey^22k =y+tin Eq. (5) giving

(c+1)²((y+y^2k)t+y²)+(c+1)(y^2k+t)=b. (9) Adding Eq. (9) to itself raised by 2^kwe get

(c+1)²(y+y^2k)²+ [(c+1)²(t+t^2k)+(c+1)](y+y^2k)

+(c+1)²t^2k+1+(c+1)t^2k+b+b^2k=0. (10) Sincex =(c+1)ywe havec=Tr^4k_k (x)=(c+1)Tr^4k_k (y)and Tr^4k_k (y)=t^2k+t. Therefore, t^2k+t=c/(c+1)and

(c+1)²((y+y^2k)²+(y+y^2k))

+(c+1)²t^2k+1+(c+1)t^2k+b+b^2k =0. (11) Note that also consideringy+y^22k =t+1 we would obtain the same equation.

Now, from (11) we have thaty+y^2k =rorr+1 for somer∈F2^s. Ify^2k =y+rtheny^22k =y+r+r^2k and, substituting in (5), we obtain

(c+1)²((y+r+r^2k)(y+r)+(y+r+r^2k)y+(y+r)y)+(c+1)(y+r^2k)= (c+1)²y²+(c+1)y+(c+1)²(r^2k+1+r²)+(c+1)r^2k=b which is the same as

x²+x+(c+1)²(r^2k+1+r²)+(c+1)r^2k =b, and thenx²+x=dfor somed∈F2^s, which is not possible as seen above.

Ify^2k =y+r+1, then we would obtain

x²+x+(c+1)²(r^2k+1+r^2k+r²+r)+(c+1)(r+1)^2k =b.

Then, Eq. (5) does not admit solutions inF2ⁿ\F2^s whenb∈F2^s. Theorem 4.3 Let n=4k=sm, with k, m odd and s even. Let f be a permutation at most differentially 6-uniform overF2^s. Then

F(x)= f(x)+(f(x)+x^22k+2k+1)(x^2s+x)²ⁿ⁻¹=

f(x) if x∈F2^s

x^22k+2k+1 if x∈/F2^s

is a differentially 6-uniform permutation overF2ⁿ.

Proof From Lemma4.2we have thatx^22k+2k+1+(x+1)^22k+2k+1 =bhas no solution in F2ⁿ\F2^s whenb∈F2^s. So the claim follows from Theorem4.1.

From Theorems4.2and4.3we obtain a general construction for piecewise functions with differential uniformity at most 6. In the following, we will show that using a functionf which is affine equivalent to the inverse function we can obtain a permutation of maximal degree n−1 with high nonlinearity.

We, first, give the following result.

Lemma 4.3 Let F be a function defined overF2ⁿ. Then, F in its polynomial representation has a term of algebraic degree n−1if and only if there exists a linear monomial x^2j such that

x∈F2n F(x)x^2j =0.

Proof We note that for anyi≤2ⁿ−1 and j≤n−1 we have

w2(i)+1≥w2(i+2^j)≥deg(x^i+2j mod x²ⁿ−x).

Indeed, let us consider the first inequality. If 2^jis not in the binary expansion ofi, that is i=_n−1

k=0b_k2^kwithb_j =0, thenw2(i+2^j)=w2(i)+1. Ifb_j =1, then, denoting byh= min{n,k : j+1≤k≤n−1,bk=0}, we havei+2^j =_j−1

k=0bk2^k+2^h+_n−1

k=h+1bk2^k, implyingw2(i+2^j)=w2(i)−(h− j)+1< w2(i)+1.

For the second inequality, we have that ifi+2^j ≤2ⁿ−1, thenw2(i+2^j)=deg(x^i+2j modx²ⁿ−x)=deg(x^i+2j). Ifi+2^j>2ⁿ−1, then it means thati=_j−1

k=0bk2^k+_n−1

k=j2^k andi+2^j =2ⁿ+j−1

k=0b_k2^k. So, denoting byh =min{j,k : 0≤k ≤ j−1,b_k =0}, we have

x^i+2j modx²ⁿ −x =x·x^k=0j−1bk2k =x^2h+

_j−1 k=h+1b_k2^k, and sow2(i+2^j)≥deg(x^{2h+k=h+1j−1 bk2k}).

Thus, since for any functionGwe have

x∈F2n G(x)=0 if and only if deg(G)=n, we obtain that ifw2(i) <n−1, then

x∈F2n x^i+2j =0.

Now, consider the functionF. We can writeF(x)=cx²ⁿ⁻¹+_n−1

k=0akx^2n−1−2k+G(x), where deg(G)≤n−2. Note that for anyk=0, ...,n−1 and 0≤ j ≤n−1, we have

x^{2n−1−2k+2j} modx²ⁿ −x ≡

⎧⎪

⎨

⎪⎩

x²ⁿ⁻¹ ifj=k

x^{(2n−1)−(2k−1+...+2j)} ifj<k x^{2j−1+...+2k} ifj>k. Letk¯=min{k : a_k=0}, we have that

x∈F2n

F(x)x^2k¯=c

x∈F2n

x^2k¯+a_k¯

x∈F2n

x²ⁿ⁻¹+

k¯−1

k=0

x∈F2n

akx^{2k−1¯ +...+2k}

+ n−1 k=¯k+1

x∈F2n

a_kx^{2n−1−(2k−1+...+2k¯)}+

x∈F2n

G(x)x^2k¯ =a_k¯. Thus, ifF(x)has a term of algebraic degreen−1, that is, there existsa_k=0, then we can find a monomialx^2j for which

x∈F2n F(x)x^2j =0.

Vice versa, from above we have that if, by contradiction,F(x) =cx²ⁿ⁻¹+G(x), with deg(G)≤n−2, then

x∈F2n F(x)x^2j =c

x∈F2nx^2j +

x∈F2n G(x)x^2j =0 for any j.

Remark 4.3 IfFis a permutation, Lemma4.3gives a necessary and sufficient condition for having deg(F)=n−1. Moreover, it is possible to generalize Lemma4.3also for the case deg(F)=n−t, using monomialsx^d withw2(d)=t. This result is similar to that given in [28,33], where the authors use ann-variables Boolean function to give a sufficient condition for having deg(F)=n−1. In particular, they show that if there exists a Boolean function h(x)of degreen−ksuch that

x∈F2n F(x)h(x)=0, then deg(F)≥k.

Corollary 4.1 Let n = sm with s even such that s/2and m are odd. Let k be such that gcd(k,n)=2and f(x)= A1◦I nv◦A2(x), where I nv(x)=x⁻¹and A1,A2are affine permutations overF2^s. Then

F(x)= f(x)+(f(x)+x^2k+1)(x^2s+x)²ⁿ⁻¹=

f(x) if x∈F2^s

x^2k+1 if x∈/F2^s

is a differentially 6-uniform permutation overF2ⁿ. Moreover, if s > 2then the algebraic degree of F is n−1.

Proof We need to prove only that the degree of Fisn−1. From Lemma4.3, since f(x) is affine-equivalent to the inverse function overF2^s, there exists a monomialh(x)=x^2j in F2^s[x](with j≤s−1) such that

x∈F2s

f(x)h(x)=0.

Thus, sincex^2k+1has algebraic degree equal to 2<s−1 overF2ⁿ and also overF2^s, we obtain

x∈F2n

F(x)h(x)=

x∈F2s

f(x)h(x)+

x∈F2n

x^2k+1h(x)+

x∈F2s

x^2k+1h(x)

=

x∈F2s

f(x)h(x)=0.

Then, we have a term of degreen−1 in the polynomial representation of F(x), implying

deg(F)=n−1 sinceFis a permutation.

Remark 4.4 Whens=2, we have thatx^2k+1has algebraic degrees−1=1 overF2^s, and we could obtain a permutationF(x)= f(x)+(f(x)+x^22k+2k+1)(x^2s+x)²ⁿ⁻¹of degree less thann−1 (an example is provided forn=6 andn=10 in Tables2and3).

Similarly we have the following construction using the Bracken–Leander function.

Corollary 4.2 Let n =4k =sm with k, m odd and s even. Let f(x)= A₁◦I nv◦A₂(x), where I nv(x)=x⁻¹and A1,A2are affine permutations overF2^s. Then

F(x)= f(x)+(f(x)+x^22k+2k+1)(x^2s+x)²ⁿ⁻¹=

f(x) if x∈F2^s

x^22k+2k+1 if x∈/F2^s

is a differentially 6-uniform permutation overF2ⁿ. Moreover, if s >4thendeg(F)=n−1.

Remark 4.5 Fors=4, we have thatx^22k+2k+1has algebraic degrees−1=3 overF2^s, and we could obtain a permutationF(x)= f(x)+(f(x)+x^22k+2k+1)(x^2s+x)²ⁿ⁻¹of degree less thann−1 (we will provide an example forn=12 in Table4).