Anne Canteaut
email: anne.canteaut@inria.fr.

Sébastien Duval
email: sebastien.duval@inria.fr.

Léo Perrin
email: leo.perrin@uni.lu.

A Generalisation of Dillon's APN Permutation with the Best Known Differential and Nonlinear Properties for all Fields of Size 2 4𝑘+2

Keywords: Boolean function, Sbox, APN, differential uniformity, nonlinearity

published or not. The documents may come     A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4k+2

I. INTRODUCTION

M ODERN block ciphers are designed based on a method- ology which guarantees that the cipher is resistant against all classical attacks. The differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], [START_REF]Differential cryptanalysis of DES-like cryptosystems[END_REF] and the linear cryptanalysis [START_REF] Matsui | Linear cryptoanalysis method for DES cipher[END_REF], [START_REF]The first experimental cryptanalysis of the data encryption standard[END_REF] are the two most prominent attacks against block ciphers, and a precise evaluation of their complexities has led to some design criteria on the so-called Sbox, i.e., on the nonlinear mapping used in the cipher. The differential uniformity of the Sbox [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF] and its nonlinearity respectively quantify its resistance to differential and linear attacks. These two design criteria are at the origin of a long line of work, including the search for infinite families of optimal permutations. Optimal permutations have been exhibited for more than twenty years when the number of variables is odd (e.g [START_REF] Nyberg | Provable security against differential cryptanalysis[END_REF], [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF]). In this case, the permutations with optimal nonlinearity are also APN, i.e., they have the lowest possible differential uniformity. But the situation is very different when the number of inputs is even, which is the case of practical interest. Indeed, in this case the values of the best differential uniformity and nonlinearity are unknown. For instance, it had been conjectured for many years that APN permutations of an even number of variables did not exist. This was disproved in 2009 by Dillon and his coauthors who exhibited an APN permutation of six variables [START_REF] Browning | An APN permutation in dimension six[END_REF]. However, the Dillon permutation is the only known example of an APN permutation depending on an even number of variables. It is unknown whether it can be generalised to any even number of inputs, or whether it is sporadic. In other words, the "(still) big APN problem" raised in [START_REF] Browning | An APN permutation in dimension six[END_REF] on the existence of an APN permutation of 𝑚 variables for 𝑚 even and greater than six is still unsolved.

Recently, Perrin et al. [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] exhibited a family of permutations acting on 2𝑛 variables, for any odd 𝑛 ≥ 3, with differential uniformity at most 4, and which includes the Dillon permutation for 𝑛 = 3. The novel idea in their work is the representation of the permutation of 2𝑛 variables as a bivariate polynomial over the field F 2 𝑛 . However, their simulations could not find any other APN permutation within this family than the one described by Dillon et al. The existence of an APN permutation of this form is left as an open problem at the end of [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF]. A second open problem mentioned in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] is the determination of the nonlinearity of these permutations, which is conjectured to be the same as the nonlinearity of the inverse mapping. Our work aims at solving these two open problems. More precisely, we define a new infinite family of permutations of 2𝑛 variables, 𝑛 odd, which generalises the functions introduced in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF]. This new family includes all permutations defined in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF], but also some other mappings which are not CCZ-equivalent to the previous ones. We show that all permutations in this family have the best known differential uniformity and nonlinearity for any number of variables of the form 𝑚 = 4𝑘 + 2, 𝑘 ≥ 1. Most notably, the differential uniformity of all permutations in this family is equal to 4, except for a single (up to equivalence) permutation of 6 variables which is CCZ-equivalent to the Dillon APN permutation. It is worth noticing that the nonlinearity of the subclass of permutations introduced by Perrin et al. has also been determined in an independent work by Fu and Feng [START_REF] Fu | Further results of the cryptographic properties on the butterfly structure[END_REF]. Therefore, our work solves all open questions raised in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] and provides new permutations with very good cryptographic properties and a compact description, which may be appropriate for some implementation purposes. One specificity of this family is that it is the only known general family of mappings with such cryptographic properties which includes the Dillon permutation. However, it does not contain any new APN permutation of an even number of variables besides the one exhibited by Dillon et al., therefore it does not solve the "big APN problem".

Organization of the paper: The cryptographic properties of Boolean functions investigated in the paper are defined in Section II. Then, in Section III, the new infinite family of functions studied in this work is described and some equivalences between the different elements are identified. Following the terminology introduced in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF], the functions within this family are named generalised butterflies. The rest of the paper studies their cryptographic properties: their nonlinearity is computed in Section IV, their differential uniformity is determined in Section V while Section VI investigates their algebraic degree.

II. BOOLEAN FUNCTIONS

This paper mainly focuses on vectorial functions with the same number of inputs and outputs, i.e., on functions 𝐹 from F 𝑚 2 into itself: 𝐹 :

F 𝑚 2 → F 𝑚 2
(𝑥 1 , . . . , 𝑥 𝑚 ) ↦ → 𝐹 (𝑥 1 , . . . , 𝑥 𝑚 ) = (𝑦 1 , . . . , 𝑦 𝑚 ) .

The components of the vectorial function 𝐹 are the Boolean functions corresponding to all linear combinations of its coordinates.

Alternatively, the vector space F 𝑚 2 can be identified with the finite field F 2 𝑚 . In this case, 𝐹 is seen as a univariate mapping from F 2 𝑚 into itself:

𝐹 : F 2 𝑚 → F 2 𝑚 𝑥 ↦ → 𝐹 (𝑥) = 𝑦 .
These two equivalent settings are related to two different notions of polynomials: a mapping from F 𝑚 2 into F 𝑚 2 can be uniquely represented by a collection of 𝑚 multivariate polynomials with binary coefficients corresponding to the algebraic normal forms of its coordinates. A mapping from F 2 𝑚 into F 2 𝑚 is represented by a unique univariate polynomial with coefficients in F 2 𝑚 . Therefore, we need to consider two different notions of degree.

Definition 1 (Univariate degree vs algebraic degree). Let 𝐹 be a function from F 𝑚 2 into F 𝑚 2 . The algebraic degree (aka multivariate degree) of 𝐹 is the maximal degree of the algebraic normal forms of its coordinates. The univariate degree of 𝐹 is the degree of the univariate polynomial in F 2 𝑚 [𝑋] representing 𝐹 when it is identified with a function from F 2 𝑚 into itself.

Obviously, these two notions are different: for instance, the cube function 𝑥 3 over F 2 𝑚 has univariate degree 3 and algebraic degree 2. More generally, the algebraic degree of the univariate polynomial 𝑥 ↦ → 𝑥 𝑒 of F 2 𝑛 is the Hamming weight of the binary expansion of 𝑒 [START_REF] Kyureghyan | Finite fields and their Applications -Character sums and polynomials[END_REF]Lemma 1.1].

In the rest of the paper, we will use the following notation.

Definition 2 (Derivative of a function). Let 𝐹 be a function from

F 𝑚 2 into F 𝑡 2 .
The derivative of 𝐹 with respect to 𝑎 ∈ F 𝑚 2 is the function

𝐷 𝑎 𝐹 : 𝑥 ∈ F 𝑚 2 ↦ → 𝐹 (𝑥 + 𝑎) + 𝐹 (𝑥) .
The resistance offered by a function to differential cryptanalysis is highly influenced by the following properties of its derivatives.

Definition 3 (Differential uniformity [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF]). Let 𝐹 be a function from

F 𝑚 2 into F 𝑡 2 . For any 𝑎 ∈ F 𝑚 2 and 𝑏 ∈ F 𝑡 2 , we define 𝛿(𝑎, 𝑏) = |{𝑥 ∈ F 𝑚 2 , 𝐷 𝑎 𝐹 (𝑥) = 𝑏}| . The multi-set {𝛿(𝑎, 𝑏), 𝑎 ∈ F 𝑚 2 ∖{0}, 𝑏 ∈ F 𝑡 2 }
is the differential spectrum of 𝐹 , and its maximum

𝛿 𝐹 = max 𝑎̸ =0,𝑏 𝛿(𝑎, 𝑏)
is the differential uniformity of 𝐹 . Definition 4 (Linearity of a function). Let 𝑓 be a Boolean function of 𝑚 variables. The Walsh coefficients of 𝑓 are the elements

̂ 𝑓 (𝑢) = ∑ 𝑥∈F 𝑚 2 (-1) 𝑓 (𝑥)+𝑢•𝑥 , 𝑢 ∈ F 𝑚 2
where 𝑢 • 𝑥 denotes the scalar product between 𝑥 and 𝑢. When 𝐹 is a vectorial Boolean function from F 𝑚 2 into F 𝑡 2 , the Walsh coefficients of 𝐹 are the Walsh coefficients of its components, i.e.,

̂ 𝐹 (𝑢, 𝑣) = ∑ 𝑥∈F 𝑚 2 (-1) 𝑣•𝐹 (𝑥)+𝑢•𝑥 , 𝑢 ∈ F 𝑚 2 , 𝑣 ∈ F 𝑡 2
and the multi-set composed of all Walsh coefficients ̂ 𝐹 (𝑢, 𝑣), 𝑣 ̸ = 0, is called the Walsh spectrum of 𝐹 .

The linearity of 𝐹 is the highest magnitude of its Walsh coefficients:

ℒ(𝐹 ) = max 𝑣∈F 𝑡 2 ∖{0} max 𝑢∈F 𝑚 2 | ̂ 𝐹 (𝑢, 𝑣)| .
Note that we can alternatively define the nonlinearity of 𝐹 as the lowest Hamming distance between a non-trivial component of 𝐹 and the set of all affine functions. Then, the nonlinearity can be computed as

𝒩 ℒ(𝐹 ) = 2 𝑚-1 - 1 2 ℒ(𝐹 ) .
Definition 5 (CCZ-equivalence [START_REF] Carlet | Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems[END_REF]). Two mappings 𝐹 and 𝐺 from F 𝑚 2 into itself are said to be CCZ-equivalent if there exists a linear permutation

𝐿 of F 2𝑚 2 such that {(𝑥, 𝐹 (𝑥)), ∀𝑥 ∈ F 𝑚 2 } = {𝐿(𝑥, 𝐺(𝑥)), ∀𝑥 ∈ F 𝑚 2 } .
CCZ-equivalence is the most relevant notion of equivalence with respect to the differential and linear properties of a mapping since it preserves both the differential and the Walsh spectra. It is worth noticing that neither the algebraic degree nor the fact that the mapping is a permutation is invariant under CCZ-equivalence.

III. GENERALISED BUTTERFLIES

A. Definition

Let 𝑚 = 2𝑛 be an even integer. In the paper, Boolean functions of 𝑚 variables are identified with functions from

F 2 𝑛 × F 2 𝑛 . Similarly, vectorial functions from F 𝑚 2 into F 𝑚 2
are identified with mappings from F 2 𝑛 × F 2 𝑛 to itself. It is worth noticing that the choice of the basis used for identifying F 2 𝑛 with F 𝑛 2 does not affect the cryptographic properties of the functions we are studying since different bases lead to functions which are affine-equivalent. In this setting, the scalar product between two elements (𝑥 1 , 𝑦 1 ) and (𝑥 2 , 𝑦 2 ) in F 2 𝑛 × F 2 𝑛 is defined as

Tr(𝑥 1 𝑥 2 ) + Tr(𝑦 1 𝑦 2 )
where Tr is the trace function on F 2 𝑛 , i.e., Tr(𝑥) = 𝑥 + 𝑥 2 + . . . + 𝑥 2 𝑛-1

. We now define the family of vectorial functions that will be studied in the paper. Definition 6 (Generalised Butterflies). Let 𝑅 be a bivariate polynomial of F 2 𝑛 such that 𝑅 𝑦 : 𝑥 ↦ → 𝑅(𝑥, 𝑦) is a permutation of F 2 𝑛 for all 𝑦 in F 2 𝑛 . The closed butterfly V 𝑅 is the function of (F 2 𝑛 ) 2 defined by

V 𝑅 (𝑥, 𝑦) = ( 𝑅(𝑥, 𝑦), 𝑅(𝑦, 𝑥) )
and the open butterfly H 𝑅 is the permutation of (F 2 𝑛 ) 2 defined by

H 𝑅 (𝑥, 𝑦) = ( 𝑅 𝑅 -1 𝑦 (𝑥) (𝑦), 𝑅 -1 𝑦 (𝑥) )
where 𝑅 𝑦 (𝑥) = 𝑅(𝑥, 𝑦) and 𝑅 -1 𝑦 (𝑅 𝑦 (𝑥)) = 𝑥 for any 𝑦, 𝑥. A representation of H 𝑅 is given in Figure 1a and one of V 𝑅 is given in Figure 1b.

𝑅 -1 𝑅 (a)
The open butterfly H𝑅 (bijective).

𝑅 𝑅

(b) The closed butterfly V𝑅.

Fig. 1: The butterfly constructions.

It can be easily checked that, for any choice of the keyed permutation 𝑅, the open butterfly H 𝑅 is an involution. Lemma 1. The permutation H 𝑅 and the function V 𝑅 of (F 2 𝑛 ) 2 are CCZ-equivalent.

Proof: The proof is identical to the proof of Lemma 2 in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF].

In this paper, we restrict ourselves to the case where 𝑅(𝑥, 𝑦) has univariate degree 3 as the butterflies first described in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] have such structure. Therefore, the differential uniformity and the linearity of the generalised butterflies will be computed only for the corresponding closed butterfly V 𝑅 since it has algebraic degree 2 only.

The following lemma describes all polynomials 𝑅 satisfying this degree condition which define a keyed permutation, as demanded by the butterfly definition. From a cryptographic point of view, the fact that 𝑅 corresponds to a keyed permutation can be viewed as an integral property, as noted in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF].

Lemma 2 (Degree Restriction). Let 𝑅 be a bivariate polynomial of F 2 𝑛 such that 𝑅 𝑦 : 𝑥 ↦ → 𝑅(𝑥, 𝑦) is a permutation for any 𝑦 and such that all terms in 𝑅 are non-linear terms with degree at most 3. Then 𝑅 can be described using two elements of F 2 𝑛 denoted 𝛼 and 𝛽 as 𝑅(𝑥, 𝑦) = (𝑥 + 𝛼𝑦) 3 + 𝛽𝑦 3 .

We denote butterflies based on such polynomials 𝑅 as V 𝛼,𝛽 and H 𝛼,𝛽 for closed and open butterflies respectively.

The proof of this lemma relies on the following theorem.

Theorem 1 (Corollary 2.9 from [START_REF] Mollin | On permutation polynomials over finite fields[END_REF]). Let F 𝑞 have characteristic different from 3. Then 𝑓 : 𝑥 ↦ → 𝑎𝑥 3 +𝑏𝑥 2 +𝑐𝑥+𝑑 (𝑎 ̸ = 0) permutes F 𝑞 if and only if 𝑏 2 = 3𝑎𝑐 and 𝑞 ≡ 2 mod 3.

Proof of Lemma 2: Let 𝑅(𝑥, 𝑦) = 𝐴𝑥 3 + 𝐵𝑥 2 𝑦 + 𝐶𝑥𝑦 2 + 𝐷𝑦 3 + 𝐸𝑥𝑦.
Since 𝑥 ↦ → 𝑅(𝑥, 0) = 𝐴𝑥 3 must be a permutation, we deduce that 𝐴 ̸ = 0. A multiplication by a non-zero constant changes neither the degree nor the integral property. Therefore, we consider a normalised case where 𝐴 = 1. We need that 𝑥 ↦ → 𝑅(𝑥, 𝑦) is a permutation for any 𝑦. We are in characteristic 2 and, using the notation of Theorem 1, we always have that 𝑞 ≡ 2 mod 3 because 𝑛 is odd. Thus, in order to fulfill the integral condition, Theorem 1 imposes that (𝐵𝑦) 2 = 𝐶𝑦 2 + 𝐸𝑦 for all 𝑦. This implies that 𝐸 = 0 and 𝐵 2 = 𝐶. The polynomial can thus be written 𝑅(𝑥, 𝑦) = 𝑥 3 + 𝐵𝑥 2 𝑦 + 𝐵 2 𝑥𝑦 2 + 𝐷𝑦 3 which we factor into 𝑅(𝑥, 𝑦) = (𝑥 + 𝐵𝑦) 3 + (𝐵 3 + 𝐷)𝑦 3 . Simply setting 𝛼 = 𝐵 and 𝛽 = 𝐵 3 + 𝐷 gives us the lemma.

Remark 1. Lemma 2 excludes terms in 𝑥 2 , 𝑦 2 , 𝑥 and 𝑦 from 𝑅. Since such terms have algebraic degree 1, they could be added without changing the linearity and the differential properties of V 𝑅 , which is why we ignore them.

In this context, the results in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] can be interpreted as handling the particular case 𝛽 = 1. If 𝛼 = 1, the open butterflies and closed butterflies are functionally equivalent to the functions presented in Figure 2.

B. Equivalence Relations

As stated in Lemma 1, an open and a closed butterfly with identical parameters are CCZ-equivalent. There are other relations linking butterflies with each other.

• If the exponent is equal to 𝑒 = 3 × 2 𝑡 , the corresponding closed butterfly is affine-equivalent to the closed butterfly with the same 𝛼, 𝛽. Therefore, all results presented in the paper also hold when

𝑅(𝑥, 𝑦) = (𝑥 + 𝛼𝑦) 3×2 𝑡 + 𝛽𝑦 3×2 𝑡
for some 𝑡. • The closed butterflies V 𝛼,𝛽 and V 𝛼 2 ,𝛽 2 are affineequivalent as

V 𝛼 2 ,𝛽 2 (𝑥 2 , 𝑦 2 ) = (V 𝛼,𝛽 (𝑥, 𝑦)) 2 . 𝛽𝑥 3 𝑥 1/3 ⊕ ⊕ 𝛽𝑥 3 𝑥 3 ⊕ ⊕ (a) Open butterfly H 1,𝛽 . 𝛽𝑥 3 ⊕ 𝑥 1/3 ⊕ 𝛽𝑥 3 ⊕ (b) F 𝛽 (note F 𝛽 = H 1,𝛽 ). 𝛽𝑥 3 𝑥 3 𝛽𝑥 3 ⊕ ⊕ ⊕ (c) Closed butterfly V 1,𝛽 .
Fig. 2: The equivalence between H 1,𝛽 and F 𝛽 .

• For any 𝛼 ̸ = 1, the closed butterflies V 𝛼,𝛽 and V 𝛼,𝛽 ′ with 𝛽 ′ = 𝛽 -1 (1 + 𝛼) 6 are affine-equivalent. This equivalence is obtained by composing V 𝛼,𝛽 with the inverse of the linear permutation

𝐿 : (𝑥, 𝑦) ↦ → (𝑧 1 , 𝑧 2 ) = (𝛼𝑥 + 𝑦, 𝑥 + 𝛼𝑦) .
Indeed, V 𝛼,𝛽 ∘ 𝐿 -1 (𝑥, 𝑦) = (𝐴, 𝐵) with

𝐴 = 𝑧 3 2 + 𝛽 [ (1 + 𝛼) -2 (𝑧 1 + 𝛼𝑧 2 ) ] 3 = (1 + 𝛼) -6 [ (𝑧 1 + 𝛼𝑧 2 ) 3 + 𝛽 ′ 𝑧 3 2 ] 𝐵 = 𝑧 3 1 + 𝛽 [ (1 + 𝛼) -2 (𝑧 2 + 𝛼𝑧 1 ) ] 3 = (1 + 𝛼) -6 [ (𝑧 2 + 𝛼𝑧 1 ) 3 + 𝛽 ′ 𝑧 3 1
] .

• Let ⊗ be defined such that (𝑎, 𝑏) ⊗ (𝑐, 𝑑) = (𝑎𝑐, 𝑏𝑑) for any pairs (𝑎, 𝑏) and (𝑐, 𝑑) of (F 2 𝑛 ) 2 . Then the generalised butterflies exhibit the same multiplicative stability as those described in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF], namely:

V 𝛼,𝛽 ( (𝜆, 𝜆) ⊗ (𝑥, 𝑦) ) = (𝜆 3 , 𝜆 3 ) ⊗ V 𝛼,𝛽 (𝑥, 𝑦), and
H 𝛼,𝛽 ( (𝜆 3 , 𝜆) ⊗ (𝑥, 𝑦) ) = (𝜆 3 , 𝜆) ⊗ H 𝛼,𝛽 (𝑥, 𝑦).
Note that these multiplicative properties correspond to the so-called subspace property introduced in [START_REF] Browning | An APN permutation in dimension six[END_REF] and investigated in [START_REF] Göloglu | Almost perfect nonlinear trinomials and hexanomials[END_REF].

C. Cryptographic Properties

Main Theorem. The cryptographic properties of the generalised butterflies V 𝛼,𝛽 and H 𝛼,𝛽 , which are based on functions 𝑅 : (𝑥, 𝑦) ↦ → (𝑥 + 𝛼𝑦) 3 + 𝛽𝑦 3 with 𝛼, 𝛽 ̸ = 0 are as follows:

• the algebraic degree of V 𝛼,𝛽 is always equal to 2,

• if 𝑛 = 3, 𝛼 ̸ = 0, Tr (𝛼) = 0 and 𝛽 ∈ {𝛼 3 + 𝛼, 𝛼

1 + 𝛼𝛽 + 𝛼 4 = (𝛽 + 𝛼 + 𝛼 3 ) 2 .
In particular, there are no APN butterflies operating on more than 6 bits.

Open generalised butterflies with 𝛽 ̸ = (1+𝛼) 3 form a family of permutations operating on 2𝑛 bits with a linearity and a differential uniformity equal to the best known to be possible. Furthermore, the only known APN permutation on fields of even dimension is, up to affine-equivalence, a generalised butterfly as well.

The proof of this theorem is divided into several parts. Section IV treats the linearity, Section V the differential uniformity and Section VI the algebraic degree.

IV. ON LINEARITY

In this section, we compute the linearity of generalised butterflies. We extensively use the fact that closed butterflies are quadratic, i.e., have algebraic degree 2 since the Walsh spectrum of quadratic Boolean functions can be easily computed from some properties of the derivatives. First, this general principle is detailed in Section IV-A. This method is then applied to the particular case of closed butterflies in Section IV-B.

A. General method for computing the linearity Since V 𝛼,𝛽 has algebraic degree 2, its nonlinearity can be evaluated by computing the number of linear structures of its components, i.e., the number of constant derivatives of the components of the function. This relationship is described in the following proposition. Even if this result is wellknown in the area of sequence design and Boolean functions (see e.g. [START_REF] Macwilliams | The theory of error-correcting codes[END_REF]Chapter 15], [START_REF] Carlet | Boolean Models and Methods in Mathematics[END_REF]Proposition 15] or [17, Appendix A]), we give the proof for completeness.

Proposition 1. Let 𝑓 be a quadratic Boolean function of 𝑛 variables. Let LS(𝑓 ) denote the linear space of 𝑓 , i.e.,

LS(𝑓

) = {𝑎 ∈ F 𝑛 2 : 𝐷 𝑎 𝑓 (𝑥) = 𝜀, ∀𝑥 ∈ F 𝑛 2 }
where 𝜀 ∈ {0, 1}. Then, 𝑠 = dim LS(𝑓 ) has the same parity as 𝑛 and ℒ(𝑓 ) = 2 𝑛+𝑠 2 . Moreover, the Walsh coefficients of 𝑓 take 2 𝑛-𝑠 times the value ±2 𝑛+𝑠 2

and (2 𝑛 -2 𝑛-𝑠 ) times the value 0.

Proof: First, it is clear that LS(𝑓 ) is a linear subspace of

F 𝑛 2 . Moreover, since 𝐷 𝑎 𝑓 (𝑥) + 𝐷 𝑏 𝑓 (𝑥) = 𝐷 𝑎+𝑏 𝑓 (𝑥 + 𝑎),
only two situations can occur. Either 𝐷 𝑎 𝑓 = 0 for all 𝑎 ∈ LS(𝑓 ), or 𝐷 𝑎 𝑓 = 0 for exactly half of the elements in LS(𝑓 ).

In this second case, LS 1 (𝑓 ) = {𝑎 :

𝐷 𝑎 𝑓 = 1} is a coset of LS 0 (𝑓 ) = {𝑎 : 𝐷 𝑎 𝑓 = 0}
. Now, we use that the Walsh coefficients of 𝑓 are related to the weight of its derivatives (see e.g. [18, Lemma 1]), namely

( ̂ 𝑓 (𝑢) ) 2 = 2 𝑛 ∑ 𝑎∈F 𝑛 2 (-1) 𝑢•𝑎 ̂ 𝐷 𝑎 𝑓 (0) .
Because 𝑓 has algebraic degree 2, 𝐷 𝑎 𝑓 has algebraic degree 1 or is constant. If it has degree 1, then it is balanced, i.e.,

 𝐷 𝑎 𝑓 (0) = 0. It follows that  𝑓 (𝑢) 2 = 2 2𝑛 ⎛ ⎝ ∑ 𝑎∈LS0(𝑓 ) (-1) 𝑢•𝑎 - ∑ 𝑎∈LS1(𝑓 ) (-1) 𝑢•𝑎 ⎞ ⎠ . If LS 1 (𝑓 ) = ∅, ̂ 𝑓 (𝑢) 2 ∈ {0, 2 2𝑛+dim LS(𝑓 ) } .
Otherwise, LS 1 (𝑓 ) = 𝑏 + LS 0 (𝑓 ) for some 𝑏, implying that

 𝑓 (𝑢) 2 = 2 2𝑛 ( 1 + (-1) 𝑢•𝑏 ) ⎛ ⎝ ∑ 𝑎∈LS0(𝑓 ) (-1) 𝑢•𝑎 ⎞ ⎠ .
Then,

̂ 𝑓 (𝑢) 2 ∈ {0, 2 2𝑛+dim LS(𝑓 ) } .
The number of occurrences of the values 0 and ℒ(𝑓 ) in the Walsh spectrum is directly deduced from Parseval's relation.

Our proof also uses the following easy lemma, which is a special case of the more general result given in [19, Corollary 1]. Lemma 3. Let 𝑛 be an odd integer and 𝑎, 𝑏, 𝑐 be three elements of F 2 𝑛 which are not all equal to zero. Then, the equation

𝑎𝑋 16 + 𝑏𝑋 4 + 𝑐𝑋 = 0 has 1, 2 or 4 solutions in F 2 𝑛 . Proof: Let 𝑃 (𝑋) = 𝑎𝑋 16 + 𝑏𝑋 4 + 𝑐𝑋.
Since 𝑃 is a nonzero linearised polynomial with degree at most 16, its roots in F 2 𝑛 form a linear subspace of F 2 𝑛 , seen as vector space over F 2 . Then, 𝑃 has 2 𝑟 roots in F 2 𝑛 , with 0 ≤ 𝑟 ≤ 4. Since F 2 𝑛 is a subfield of F 2 2𝑛 , the roots of 𝑃 in F 2 𝑛 are also included in the set of all roots of 𝑃 in F 2 2𝑛 . Let 𝛽 ∈ F 4 𝑛 be such that 𝛽 2 + 𝛽 + 1 = 0. Then, for any 𝑥 ∈ F 2 𝑛 such that 𝑃 (𝑥) = 0, we have 𝑃 (𝛽𝑥) = 0 and 𝑃 (𝛽 2 𝑥) = 0, and none of these two other roots lie in F 2 𝑛 . Moreover, if 𝑥 and 𝑥 ′ are two distinct roots of 𝑃 in F 2 𝑛 , then {𝑥, 𝛽𝑥, 𝛽 2 𝑥, 𝑥 ′ , 𝛽𝑥 ′ , 𝛽 2 𝑥 ′ } are six distinct roots of 𝑃 in F 4 𝑛 . This implies that, if 𝑃 has seven nonzero roots in F 2 𝑛 , then it would have more than 16 roots in F 4 𝑛 which is impossible. Therefore, 𝑃 has at most 4 roots in F 2 𝑛 . B. Linearity of generalised butterflies Theorem 2. Let 𝑛 > 1 be an odd integer and (𝛼, 𝛽) be a pair of nonzero elements in F 2 𝑛 . Then the linearity of

V 𝛼,𝛽 over F 2 𝑛 × F 2 𝑛 is 2 𝑛+1 if 𝛽 ̸ = (1 + 𝛼) 3 . Moreover, the Walsh coefficients of V 𝛼,𝛽 belong to {0, ±2 𝑛 , ±2 𝑛+1 }. If 𝛽 = (1 + 𝛼) 3 , the linearity of V 𝛼,𝛽 is equal to 2 3𝑛+1 2
.

Proof: The linearity of V 𝛼,𝛽 is the maximal linearity of its nontrivial components, i.e., of the Boolean functions

𝑓 𝜆,𝜇 : (𝑥, 𝑦) ↦ → Tr(𝜆𝑅(𝑥, 𝑦)) + Tr(𝜇𝑅(𝑦, 𝑥))
for 𝜆, 𝜇 ∈ F 2 𝑛 , where Tr denotes the trace function from

F 2 𝑛 into F 2 .
Let us first determine the linearity of 𝑓 0,𝜇 . Since 𝑥 ↦ → 𝑅(𝑥, 𝑦) is a permutation for every fixed 𝑦, we deduce that 𝑓 0,𝜇 is balanced on any set (𝑎, F 2 𝑛 ), implying that it is balanced over F 2 2 𝑛 . The linearity of 𝑓 0,𝜇 is determined by the number of pairs (𝑎, 𝑏) such that 𝐷 (𝑎,𝑏) 𝑓 0,𝜇 is constant. We have

𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) + 𝑅(𝑦, 𝑥) = (𝛼 2 𝑏 + 𝑎(𝛼 3 + 𝛽))𝑥 2 + ((𝛼 3 + 𝛽)𝑎 2 + 𝛼𝑏 2 )𝑥 + (𝑏 + 𝛼𝑎)𝑦 2 + (𝑏 + 𝛼𝑎) 2 𝑦 + 𝑅(𝑏, 𝑎) .
Then, 𝐷 (𝑎,𝑏) 𝑓 0,𝜇 is equal to

Tr ( 𝑥 2 ( 𝜇(𝛼 2 𝑏 + 𝑎(𝛼 3 + 𝛽)) +𝜇 2 ((𝛼 3 + 𝛽) 2 𝑎 4 + 𝛼 2 𝑏 4 ) )) + Tr ( 𝑦 2 ( 𝜇(𝑏 + 𝛼𝑎) + 𝜇 2 (𝑏 + 𝛼𝑎) 4 )) + 𝑐, with 𝑐 ∈ F 2 implying that 𝐷 (𝑎,𝑏) 𝑓 0,𝜇 is constant if and only if (𝑎, 𝑏) satisfies { 𝜇(𝛼 2 𝑏 + 𝑎(𝛼 3 + 𝛽)) + 𝜇 2 ((𝛼 3 + 𝛽) 2 𝑎 4 + 𝛼 2 𝑏 4 ) = 0 𝜇(𝑏 + 𝛼𝑎) + 𝜇 2 (𝑏 + 𝛼𝑎) 4 = 0 .
Since 𝜇 ̸ = 0, the second equation implies that

𝑏 = 𝛼𝑎 + 𝛿 with 𝛿 ∈ {0, 𝜇 -1/3 } .
By replacing the value of 𝑏 in the first equation, we get

𝛽 2 𝑎 4 + 𝛽𝑎 = 𝛿 ′
where 𝛿 ′ can take two values including 0. Since 𝛽 ̸ = 0, we deduce that 𝑎 takes two different values when 𝛿 ′ = 0, and at most two values when 𝛿 ′ ̸ = 0. Then we get that the number of pairs (𝑎, 𝑏) satisfying these two equations is either 2 or 4.

We know from Proposition 1 that the dimension of the linear space is even, implying that 𝐷 (𝑎,𝑏) 𝑓 0,𝜇 is constant for four values (𝑎, 𝑏). Thus 𝑓 0,𝜇 has linearity exactly 2 𝑛+1 . Now, we focus on the case when 𝜆 ̸ = 0. Then there exists

𝜆 ′ ∈ F 2 𝑛 such that 𝜆 = 𝜆 ′3 because 𝑥 ↦ → 𝑥 3 is a permutation of F 2 𝑛 for any odd 𝑛. It follows that, for any nonzero 𝜆, 𝜆𝑅(𝑥, 𝑦) = (𝑥𝜆 ′ + 𝛼𝑦𝜆 ′ ) 3 + 𝛽(𝑦𝜆 ′ ) 3 = 𝑅(𝑥𝜆 ′ , 𝑦𝜆 ′ ) . Therefore, 𝑓 𝜆,𝜇 (𝑥, 𝑦) = Tr (𝜆𝑅(𝑥, 𝑦) + 𝜇𝑅(𝑦, 𝑥)) = Tr ( 𝑅(𝑥𝜆 ′ , 𝑦𝜆 ′ ) + 𝜇𝜆 -1 𝑅(𝑦𝜆 ′ , 𝑥𝜆 ′ ) ) = 𝑓 1,𝜇𝜆 -1 (𝑥𝜆 ′ , 𝑦𝜆 ′ ) .
We deduce that, for 𝜆 ̸ = 0, 𝑓 𝜆,𝜇 is linearly equivalent to 𝑓 1,𝜇𝜆 -1 , implying that these two functions have the same linearity. Therefore, we only need to compute the dimension of the linear space of the quadratic function 𝑓 1,𝜆 for all 𝜆 ∈ F * 2 𝑛 . Let 𝛾 = 𝛼 3 + 𝛽. Then, for any 𝑎 and 𝑏 in F 2 𝑛 , we have

𝐷 (𝑎,𝑏) 𝑓 1,𝜆 = Tr [ 𝑥 2 ( 𝑎 + 𝛼𝑏 + 𝜆(𝛾𝑎 + 𝛼 2 𝑏) )] + Tr [ 𝑥 ( (𝑎 + 𝛼𝑏) 2 + 𝜆(𝛾𝑎 2 + 𝛼𝑏 2 ) )] + Tr [ 𝑦 2 ( 𝛼 2 𝑎 + 𝛾𝑏 + 𝜆(𝛼𝑎 + 𝑏) )] + Tr [ 𝑦 ( 𝛼𝑎 2 + 𝛾𝑏 2 + 𝜆(𝛼𝑎 + 𝑏) 2 )] + 𝑓 1,𝜆 (𝑎, 𝑏) .
Then, we write

𝐷 (𝑎,𝑏) 𝑓 1,𝜆 = Tr(𝐴𝑥 2 ) + Tr(𝐵𝑦 2 ) + 𝑓 1,𝜆 (𝑎, 𝑏) implying that 𝐷 (𝑎,𝑏) 𝑓 1,𝜆 is constant if and only if ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 𝐴 = (1 + 𝜆𝛾) 2 𝑎 4 + (1 + 𝜆𝛾)𝑎 +(𝜆𝛼 + 𝛼 2 ) 2 𝑏 4 + (𝛼 + 𝜆𝛼 2 )𝑏 = 0 𝐵 = (𝛼 + 𝜆𝛼 2 ) 2 𝑎 4 + (𝛼 2 + 𝜆𝛼)𝑎 +(𝛾 + 𝜆) 2 𝑏 4 + (𝛾 + 𝜆)𝑏 = 0 (1)
We deduce that

𝐸 = (𝛼 + 𝜆𝛼 2 ) 2 𝐴 + (1 + 𝜆𝛾) 2 𝐵 = 𝑎(1 + 𝜆𝛾) [ (𝛼 + 𝜆𝛼 2 ) 2 + (1 + 𝜆𝛾)(𝛼 2 + 𝜆𝛼) ] +𝑏 4 [ (𝛼 + 𝜆𝛼 2 )(𝛼 2 + 𝜆𝛼) + (𝛾 + 𝜆)(1 + 𝜆𝛾) ] 2 +𝑏 [ (𝛼 + 𝜆𝛼 2 ) 3 + (1 + 𝜆𝛾) 2 (𝛾 + 𝜆) ] = 0 . (2)
Let us assume that 𝜆 ̸ = 𝛾 -1 (this case will be studied at the end of the proof). We first show that, if the coefficient of 𝑎 in (2) vanishes, then the coefficient of 𝑏 4 does not vanish, unless (𝛽, 𝜆) = ((1 + 𝛼) 3 , 1). Indeed, the coefficient of 𝑎 vanishes if and only if

𝜆 2 (𝛼 3 +𝛾)+𝜆(𝛼𝛾+1) = 𝜆 ( 𝜆𝛽 + (𝛼 4 + 𝛼𝛽 + 1) ) = 0 . (3)
There is then a single nonzero value of 𝜆 for which this coefficient vanishes, namely

𝜆 = 𝛽 -1 (𝛼 4 + 𝛼𝛽 + 1). (4)
The coefficient of 𝑏 4 vanishes if and only if

𝑋 = (𝛼 + 𝜆𝛼 2 )(𝛼 2 + 𝜆𝛼) + (𝛾 + 𝜆)(1 + 𝜆𝛾) = 𝜆 2 𝛽 + 𝜆(𝛼 3 + 𝛼 2 + 𝛼 + 1 + 𝛽) 2 + 𝛽 = 0 .
Therefore, this coefficient vanishes for the value of 𝜆 given by (4) if and only if

(𝛼 4 + 𝛼𝛽 + 1) 2 +(𝛼 4 + 𝛼𝛽 + 1)(𝛼 3 + 𝛼 2 + 𝛼 + 1 + 𝛽) 2 +𝛽 2 = 𝛼 ( 𝛽 + (1 + 𝛼) 3 ) 2 ( 𝛽 + (1 + 𝛼) 2 𝛼 ) = 0 .
Furthermore, this equation has two roots: 𝛽 = (1 + 𝛼) 3 (implying 𝜆 = 1, from ( 4)) and 𝛽 = (1 + 𝛼) 2 𝛼. This second case cannot occur since (4) then leads to 𝜆 = 𝛼 -1 and 𝛾 = 𝛼, which contradicts the hypothesis 𝜆 ̸ = 𝛾 -1 . Therefore, when (𝛽, 𝜆) ̸ = ((1 + 𝛼) 3 , 1), Equation ( 2) can be expressed either as 𝑈 𝑏 4 + 𝑉 𝑏 = 0 with 𝑈 ̸ = 0 or 𝑎 = 𝑈 𝑏 4 + 𝑉 𝑏 ,

where the first situation occurs if and only if (3) holds.

In the first case, we deduce at most 2 solutions for 𝑏, including 𝑏 = 0. We now replace 𝑏 by these two values in the first equation in [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]. We get that

(1 + 𝜆𝛾) 2 𝑎 4 + (1 + 𝜆𝛾)𝑎 = 𝛿
for two values of 𝛿. Using that 𝜆 ̸ = 𝛾 -1 , we deduce that there are at most two solutions 𝑎 for each value of 𝛿, implying that there are at most four pairs (𝑎, 𝑏) satisfying (1).

In the second case of ( 5), we replace 𝑎 by its expression in the first equation in [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]. This leads to

𝑏 16 𝑈 4 (1 + 𝜆𝛾) 2 + 𝑏 4 [ (𝜆𝛼 + 𝛼 2 ) 2 + 𝑉 4 (1 + 𝜆𝛾) 2 + 𝑈 (1 + 𝜆𝛾) ] + 𝑏 [ (𝛼 + 𝜆𝛼 2 ) + 𝑉 (1 + 𝜆𝛾) ] = 0 .
From Lemma 3, this equation has at most 4 solutions 𝑏, unless all its coefficients vanish. Therefore, the system has at most 4 solutions except when 𝑈 = 0 and

{ (𝜆𝛼 + 𝛼 2 ) + 𝑉 2 (1 + 𝜆𝛾) = 0 (𝛼 + 𝜆𝛼 2 ) + 𝑉 (1 + 𝜆𝛾) = 0 . (6)
These two relations hold only either when 𝑉 = 0, which implies 𝛼 = 𝜆 = 1, or when

{ 𝛼(1 + 𝜆𝛼) + 𝑉 (1 + 𝜆𝛾) = 0 (𝛼 + 𝜆) + 𝑉 (1 + 𝜆𝛼) = 0 .
When 𝑉 ̸ = 0, by multiplying the first equation by (1 + 𝜆𝛼) and the second one by (1 + 𝜆𝛾), we deduce that

𝛼(1 + 𝜆𝛼) 2 + (𝛼 + 𝜆)(1 + 𝜆𝛾) = 𝜆 2 𝛽 + 𝜆(𝛼 4 + 𝛼𝛽 + 1) = 0
which contradicts the fact that the second situation of (5) occurs, because the second case of (5) means that (3) does not hold.

When 𝑉 = 0, we deduce that 𝛼 = 𝜆 = 1. In this case, (1) corresponds to

{ (1 + 𝛾) 2 𝑎 4 + (1 + 𝛾)𝑎 = 0 𝛽 2 𝑏 4 + 𝛽𝑏 = 0 .
Using that 𝛽 = 1+𝛾 is nonzero, we deduce that this system of equations has at most 4 solutions (𝑎, 𝑏), because each equation has at most 2 solutions. We now need to handle the case 𝜆 = 𝛾 -1 . Then, the first equation in ( 1) equals

(𝛾 -1 𝛼 + 𝛼 2 ) 2 𝑏 4 + (𝛼 + 𝛾 -1 𝛼 2 )𝑏 = 0 .
The two coefficients of this equation cannot simultaneously vanish, unless

𝛾 = 𝛼 -1 = 𝛼 implying that 𝛼 = 𝛾 = 1 which is impossible since 𝛽 ̸ = 0.
Therefore, at most two values of 𝑏 (including 𝑏 = 0) satisfy this equation. Replacing 𝑏 by these two values in the second equation in (1) leads to

(𝛼 + 𝜆𝛼 2 ) 2 𝑎 4 + (𝛼 2 + 𝜆𝛼)𝑎 = 𝛿
for at most two values of 𝛿 (including 𝛿 = 0). Again the coefficients of 𝑎 4 and of 𝑎 cannot simultaneously vanish since 𝛼 = 𝛾 = 1 is impossible. This equation has at most two solutions for each value of 𝑏, leading to a total of at most 4 pairs (𝑎, 𝑏) solutions of (1). We have thus proved that, unless (𝛽, 𝜆) = ((1 + 𝛼) 3 , 1), (1) has at most four solutions, i.e. 𝑓 1,𝜆 has at most four constant derivatives. We eventually deduce from Proposition 1 that ℒ(𝑓 1,𝜆 ) ∈ {2 𝑛 , 2 𝑛+1 }. It follows that ℒ(V 𝛼,𝛽 ) = 2 𝑛+1 since it corresponds to the linearity of 𝑓 0,𝜆 . The last case is when (𝛽, 𝜆) = ((1+𝛼) 3 , 1). Then, (1+𝛾) = (𝛼 2 + 𝛼). It follows that ( 1) is equivalent to

(𝛼 2 + 𝛼) 2 (𝑎 + 𝑏) 4 + (𝛼 2 + 𝛼)(𝑎 + 𝑏) = 0 .
We deduce that 𝑎 + 𝑏 takes exactly two values, implying that there are exactly 2 𝑛+1 pairs (𝑎, 𝑏) solutions of (1). It follows that, for

𝛽 = (1 + 𝛼) 3 , ℒ(V 𝛼,𝛽 ) = 2 3𝑛+1 2
.

V. ON DIFFERENTIAL UNIFORMITY

In this section, we describe the differential properties of generalised butterflies. First, Section V-A is dedicated to Theorem 3, which shows that generalised butterflies V 𝛼,𝛽 and H 𝛼,𝛽 have differential uniformity at most 4, unless 𝛽 = (1 + 𝛼) 3 . Then, Theorem 4 and its immediate consequence, Corollary 1, give a necessary and sufficient condition on 𝛼 and 𝛽 for a generalised butterfly to be APN. This corollary is then used to show Proposition 2 which states that there are no APN butterflies if 𝑛 > 3. These results are presented and proved in Section V-B. Section V-C focuses on the special case 𝛼 = 𝛽 = 1, for which the generalised butterflies are equivalent to a 3-round Feistel network. In this case, we recover, with a different proof, a result from [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF], which states that the difference distribution tables of the corresponding butterflies do not contain the value 2. Finally, we show in Section V-D that the whole Walsh spectrum and difference distribution table of a generalised butterfly are determined by the number of bent components of the closed butterfly.

But first, we give a lemma playing a crucial role in these proofs. It allows to easily derive the maximum number of solutions of some particular degree-4 equations that appear several times in our proof. Since most proofs in this section rely on the number of solutions of univariate equations over F 2 𝑛 , the notion of degree that will be used always refers to the univariate degree. Proof: First of all, for any value of the constant 𝐶, the number of solutions of the equation is either zero or equal to the number of solutions of the linearised equation 𝑈 𝑧 4 + 𝑉 𝑧 2 + (𝑈 + 𝑉 )𝑧 = 0. We then only need to study the case 𝐶 = 0. Obviously, the number of solutions is always even as if 𝑧 is a solution then 𝑧 + 1 is too.

If 𝑈 = 𝑉 = 0 then the linearised equation does not involve 𝑧, meaning that all values of 𝑧 satisfy it. We now suppose that either 𝑈 ̸ = 0 or 𝑉 ̸ = 0.

If 𝑈 = 0 then the equation corresponds to 𝑉 𝑧(𝑧 + 1) = 0, implying that it has 2 solutions.

Let us now suppose that 𝑈 ̸ = 0. In this case, we can rewrite the equation as for any tuple (𝑎, 𝑏, 𝑐, 𝑑) of F 2 𝑛 with (𝑎, 𝑏) ̸ = (0, 0). We have

𝑈 𝑧(𝑧 + 1) ( 1
𝑅(𝑥, 𝑦)+𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = (𝑎𝑥 2 + 𝑎 2 𝑥) + 𝛼(𝑏𝑥 2 + 𝑎 2 𝑦) + 𝛼 2 (𝑏 2 𝑥 + 𝑎𝑦 2 ) + (𝛼 3 + 𝛽)(𝑏𝑦 2 + 𝑏 2 𝑦) + 𝑅(𝑎, 𝑏) . Let 𝑢 = 𝑎 + 𝛼𝑏. Then 𝑅(𝑥, 𝑦)+𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) =𝑢𝑥 2 + 𝑢 2 𝑥 + (𝛼 2 𝑢 + 𝑏𝛽)𝑦 2 + (𝛼𝑢 2 + 𝑏 2 𝛽)𝑦 + 𝑅(𝑎, 𝑏)
Similarly, for 𝑣 = 𝛼𝑎 + 𝑏, we have

𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) =(𝛼 2 𝑣 + 𝑎𝛽)𝑥 2 + (𝛼𝑣 2 + 𝑎 2 𝛽)𝑥 + 𝑣𝑦 2 + 𝑣 2 𝑦 + 𝑅(𝑏, 𝑎) ,
implying that we search for the solutions of

{ 𝑢𝑥 2 + 𝑢 2 𝑥 + (𝛼 2 𝑢 + 𝑏𝛽)𝑦 2 + (𝛼𝑢 2 + 𝑏 2 𝛽)𝑦 = 𝑐 ′ (𝛼 2 𝑣 + 𝑎𝛽)𝑥 2 + (𝛼𝑣 2 + 𝑎 2 𝛽)𝑥 + 𝑣𝑦 2 + 𝑣 2 𝑦 = 𝑑 ′ (7)
a) Special cases: We first focus on three special cases, namely 𝑏 = 𝛼 -1 𝑎, 𝛼𝑎, 0. The rest of the proof will be dedicated to the general case, when 𝑏 differs from these three values. We also consider a fourth special case corresponding to 𝛽 = (1 + 𝛼) 3 and 𝑏 = 𝑎.

• 𝑏 = 𝛼 -1 𝑎, or equivalently 𝑢 = 0. Note that neither 𝑎 nor 𝑏 vanishes, since it would imply 𝑎 = 𝑏 = 0, which has been excluded. In this case, (7) can be written as

{ (𝑏𝛽)𝑦 2 + (𝑏 2 𝛽)𝑦 = 𝑐 ′ (𝛼 2 𝑣 + 𝑎𝛽)𝑥 2 + (𝛼𝑣 2 + 𝑎 2 𝛽)𝑥 + 𝑣𝑦 2 + 𝑣 2 𝑦 = 𝑑 ′ .
Since 𝛽 ̸ = 0 and 𝑏 ̸ = 0, we deduce that the first equation has at most two solutions 𝑦 0 and 𝑦 1 . For each of these two solutions, the second equation has at most two solutions because the coefficients of 𝑥 2 and of 𝑥 cannot simultaneously vanish. Indeed

(𝛼 2 𝑣 + 𝑎𝛽) = (𝛼𝑣 2 + 𝑎 2 𝛽) = 0 (8)
implies that

𝑎 2 𝛽 = 𝛼𝑣 2 = 𝛼 2 𝑎𝑣 , leading to 𝛼𝑣(𝑣 + 𝑎𝛼) = 𝛼𝑣𝑏 = 0 ,
which is impossible since 𝑣 = 0 together with (8) would imply that 𝑎 = 0. Therefore, [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF] has at most four solutions when 𝑢 = 0. • 𝑏 = 𝛼𝑎, or equivalently 𝑣 = 0. This case is similar to the previous one. Indeed, (7) now corresponds to

{ 𝑢𝑥 2 + 𝑢 2 𝑥 + (𝛼 2 𝑢 + 𝑏𝛽)𝑦 2 + (𝛼𝑢 2 + 𝑏 2 𝛽)𝑦 = 𝑐 ′ 𝑎𝛽𝑥 2 + 𝑎 2 𝛽𝑥 = 𝑑 ′
Since 𝑎𝛽 ̸ = 0, the second equation has at most two solutions 𝑥 0 and 𝑥 1 . For each of these solutions, the first equation has at most two solutions for 𝑦 since the coefficients of 𝑦 2 and 𝑦 cannot simultaneously vanish.

Otherwise, we would have

𝑏 2 𝛽 = 𝛼𝑢 2 = 𝛼 2 𝑏𝑢 implying 𝛼𝑢𝑎 = 0. • 𝑏 = 0. Then, System (7) corresponds to { 𝑎𝑥 2 + 𝑎 2 𝑥 + 𝛼 2 𝑎𝑦 2 + 𝛼𝑎 2 𝑦 = 𝑐 ′ (𝛼 3 𝑎 + 𝑎𝛽)𝑥 2 + (𝛼 3 𝑎 2 + 𝑎 2 𝛽)𝑥 + 𝛼𝑎𝑦 2 + 𝛼 2 𝑎 2 𝑦 = 𝑑 ′ .
By summing the first equation and the second one multiplied by 𝛼, we get that

𝑦𝛼𝑎 2 (1 + 𝛼 2 ) = (𝑎 + 𝑎𝛼 4 + 𝑎𝛼𝛽)(𝑥 2 + 𝑎𝑥) + 𝑔
for some constant 𝑔. Let us first consider the case when 𝛼 = 1. Then, we get

𝑎𝛽(𝑥 2 + 𝑎𝑥) = 𝑔 .
Since 𝑎𝛽 ̸ = 0, this equation has at most two solutions 𝑥 0 and 𝑥 1 . Then, for each 𝑥 𝑖 , the first equation in the system provides at most two solutions for 𝑦, leading to at most four solutions (𝑥, 𝑦) for the whole system.

Let us now assume that 𝛼 ̸ = 1. Then, we replace 𝑦 by its value, i.e. 𝑦 = 𝜇(𝑥 2 + 𝑎𝑥) + 𝑔 ′ in the first equation of the system, and we get

𝛼 2 𝑎𝜇 2 𝑥 4 + [ 𝑎 + 𝛼 2 𝑎 3 𝜇 2 + 𝛼𝑎 2 𝜇 ] 𝑥 2 + [ 𝑎 2 + 𝛼𝑎 3 𝜇 ] 𝑥 = 𝑐 ′ , where 𝜇 = (1 + 𝛼 4 + 𝛼𝛽) 𝛼𝑎(1 + 𝛼 2 )
.

By replacing 𝑥 = 𝑎𝑥 ′ , we deduce that

𝑈 𝑥 ′4 + 𝑉 𝑥 ′2 + (𝑈 + 𝑉 )𝑥 ′ = 𝑐 ′ (9)
with

𝑈 = 𝛼 2 𝑎 5 𝜇 2 and 𝑉 = 𝑎 3 + 𝛼 2 𝑎 5 𝜇 2 + 𝛼𝑎 4 𝜇 .
This equation has at most four solutions 𝑥 𝑖 , and each 𝑥 𝑖 leads to a single 𝑦, implying that the whole system has at most four solutions. We now show that the whole system has at most two solutions for any 𝑎 ̸ = 0 for two values of 𝛽 only.

It is worth noticing that, since V 1,𝛽 cannot be APN because any three-round Feistel network has differential uniformity at least 4 [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF], 𝛼 = 1 can be excluded. If V 𝛼,𝛽 is APN, then the previous degree-4 equation ( 9) has at most two solutions for any 𝑎 ̸ = 0 and any 𝑐 ′ . We derive from Lemma 4 that this happens if and only if, for all 𝑎 ̸ = 0, 𝑈 = 0 and 𝑉 ̸ = 0 or 𝑈 = 𝑉 and 𝑈 ̸ = 0 or 𝑈 ̸ = 0 and Tr(𝑉 /𝑈 ) = 0 .

We first observe that 𝑉 ̸ = 0, otherwise 𝛼 2 𝑎 2 𝜇 2 + 𝛼𝑎𝜇 + 1 = 0 which would mean that (𝛼𝑎𝜇) is a root of 𝑋 2 + 𝑋 + 1 while this polynomial is irreducible over F 2 𝑛 , 𝑛 odd. Then, the first condition means that

𝜇 = (1 + 𝛼 4 + 𝛼𝛽) 𝛼𝑎(1 + 𝛼 2 ) = 0 or equivalently 𝛽 = 𝛼 -1 + 𝛼 3 .
The second condition corresponds to

𝛼𝑎𝜇 = 1 ⇔ 1 + 𝛼 4 + 𝛼𝛽 = 1 + 𝛼 2 ,
This condition is equivalent to

𝛽 = 𝛼 + 𝛼 3 .

The last condition corresponds to

Tr(𝑉 /𝑈 ) = Tr(1) + Tr

( 1 + 𝛼𝑎𝜇 𝑎 2 𝛼 2 𝜇 2 ) = 1 + Tr ( 1 𝑎 2 𝛼 2 𝜇 2 ) + Tr ( 1 𝑎𝛼𝜇 ) = 1 = 0 ,
which is impossible, Therefore, the only values of 𝛽 for which V 𝛼,𝛽 can be APN are 𝛽 = 𝛼 -1 + 𝛼 3 and 𝛽 = 𝛼 + 𝛼 3 . • 𝑏 = 𝑎 and 𝛽 = (1 + 𝛼) 3 . Note that 𝛽 = (1 + 𝛼) 3 ̸ = 0 implies that 𝛼 ̸ = 1. In this case, ( 7) is equal to

{ 𝑏(1 + 𝛼)𝑥 2 + 𝑏 2 (1 + 𝛼) 2 𝑥 + 𝑏(1 + 𝛼)𝑦 2 + 𝑏 2 (1 + 𝛼) 2 𝑦 = 𝑐 ′ 𝑏(1 + 𝛼)𝑥 2 + 𝑏 2 (1 + 𝛼) 2 𝑥 + 𝑏(1 + 𝛼)𝑦 2 + 𝑏 2 (1 + 𝛼) 2 𝑦 = 𝑑 ′ .
Thus, it has no solution if 𝑐 ′ ̸ = 𝑑 ′ . If 𝑐 ′ = 𝑑 ′ , it is equivalent to the single equation

(𝑥 + 𝑦) 2 + 𝑏(1 + 𝛼)(𝑥 + 𝑦) = 𝑐 ′ 𝑏 -1 (1 + 𝛼) -1 ,
since 𝛼 ̸ = 1 and 𝑏 ̸ = 0. Thus, either System (7) has no solution, or its solutions are of the form 𝑥+𝑦 = 𝜀 for two values of 𝜀, depending on (𝑏, 𝑐 ′ ). In particular, System (7) has exactly 2 𝑛+1 solutions when 𝑐 ′ = 𝑑 ′ = 0. b) General case: Let us now assume that 𝑢, 𝑣 and 𝑏 are all nonzero. We also suppose that 𝑎 = 𝑏 and 𝛽 = (1 + 𝛼) 3 do not hold simultaneously. Let ℓ 1 and ℓ 2 respectively denote two equations in [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF]. Then the following expression must constant:

𝑣ℓ 1 + 𝑢ℓ 2 = ( 𝑢𝑣(𝛼 2 + 1) + 𝑎𝑢𝛽 ) 𝑥 2 + ( 𝑢𝑣(𝑢 + 𝛼𝑣) + 𝑎 2 𝑢𝛽 ) 𝑥 + ( 𝑢𝑣(𝛼 2 + 1) + 𝑏𝑣𝛽 ) 𝑦 2 + ( 𝑢𝑣(𝛼𝑢 + 𝑣) + 𝑏 2 𝑣𝛽 ) 𝑦 = ( 𝑢𝑣(𝛼 2 + 1) + 𝑎𝑢𝛽 ) (𝑥 2 + 𝑎𝑥) + ( 𝑢𝑣(𝛼 2 + 1) + 𝑏𝑣𝛽 ) (𝑦 2 + 𝑏𝑦) ,
where the last equality comes from the fact that (𝑢 + 𝛼𝑣) = 𝑎(𝛼 2 + 1) and (𝛼𝑢 + 𝑣) = 𝑏(𝛼 2 + 1). We have obtained a relation of the form

𝜆 0 (𝑥 2 + 𝑎𝑥) + 𝜆 1 (𝑦 2 + 𝑏𝑦) = 𝜀 (10)
for some constant 𝜀. We first prove that 𝜆 0 and 𝜆 1 cannot simultaneously vanish. Let us first consider the case 𝛼 = 1.

Then 𝜆 0 = (𝑎 + 𝑏)𝑎𝛽 and 𝜆 1 = (𝑎 + 𝑏)𝑏𝛽 .

Since 𝑢 = 𝑎 + 𝑏 ̸ = 0, 𝑏 ̸ = 0 and 𝛽 ̸ = 0, 𝜆 1 does not vanish.

Let us now assume that 𝛼 ̸ = 1. Then we can write

𝛽 = (1 + 𝛼 2 )(𝛼 + 𝛽 ′ ) .
It follows that

𝜆 0 = 𝑢𝑣(𝛼 2 + 1) + 𝑎𝑢𝛽 = 𝑢(𝛼 2 + 1)(𝑏 + 𝑎𝛽 ′ ) 𝜆 1 = 𝑢𝑣(𝛼 2 + 1) + 𝑏𝑣𝛽 = 𝑣(𝛼 2 + 1)(𝑎 + 𝑏𝛽 ′ ) .
Then [START_REF] Fu | Further results of the cryptographic properties on the butterfly structure[END_REF] holds with

𝜆 0 = 𝑢(𝑏 + 𝑎𝛽 ′ ) and 𝜆 1 = 𝑣(𝑎 + 𝑏𝛽 ′ ) .
These two coefficients cannot simultaneously vanish: otherwise, it would lead to ′ = 𝑏 and 𝑏𝛽 ′ = 𝑎 implying that

𝑎𝑏𝛽 ′ = 𝑎 2 = 𝑏 2 and 𝛽 ′ = 1 ,
which has been excluded since it implies that 𝛽 = (1 + 𝛼) 3 and 𝑎 = 𝑏.

We now combine [START_REF] Fu | Further results of the cryptographic properties on the butterfly structure[END_REF] with one of the equations in [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF]. We need to consider two different cases:

• If 𝜆 0 = 0, then [START_REF] Fu | Further results of the cryptographic properties on the butterfly structure[END_REF], which can be written as

𝑦 2 + 𝑏𝑦 = 𝜀 ′ ,
has at most two solutions 𝑦 0 and 𝑦 1 . By replacing 𝑦 by these two values in the first equation in [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF], we get at most two solutions for for each 𝑦 𝑖 since 𝑢 ̸ = 0.

• If 𝜆 0 ̸ = 0, then (10) can be written as

𝑥 2 = 𝑎𝑥 + 𝜆 -1
0 𝜆 1 (𝑦 2 + 𝑏𝑦) + 𝜀 ′ . We replace 𝑥 2 by this expression in the first equation in [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF], and we get

(𝑢𝑎 + 𝑢 2 )𝑥 + (𝑢𝜆 -1 0 𝜆 1 + 𝛼 2 𝑢 + 𝑏𝛽)𝑦 2 +(𝑢𝜆 -1 0 𝜆 1 𝑏 + 𝛼𝑢 2 + 𝑏 2 𝛽)𝑦 = 𝑐 ′ .
The coefficient of 𝑥 does not vanish since 𝑢 = 𝑎 is equivalent to 𝑏 = 0. Then 𝑥 can be written as a degree-2 polynomial in 𝑦, i.e.

𝑥 = 𝜇 2 𝑦 2 + 𝜇 1 𝑦 + 𝜇 0 . (11)
By replacing 𝑥 by its value in [START_REF] Fu | Further results of the cryptographic properties on the butterfly structure[END_REF], we derive that

𝜆 1 (𝑦 2 + 𝑏𝑦) = 𝜆 0 ( 𝜇 2 2 𝑦 4 + 𝜇 2 1 𝑦 2 + 𝑎𝜇 2 𝑦 2 + 𝑎𝜇 1 𝑦 ) + 𝜀 ′′ leading to 𝜆 0 𝜇 2 2 𝑦 4 + ( 𝜆 1 + 𝜆 0 𝜇 2 1 + 𝜆 0 𝑎𝜇 2 ) 𝑦 2 +(𝜆 1 𝑏 + 𝜆 0 𝑎𝜇 1 ) 𝑦+𝜀 ′′ . ( 12
) Let us first assume that the three coefficients of 𝑦 4 , 𝑦 2 and 𝑦 do not simultaneously vanish. Then [START_REF] Carlet | Codes, Bent Functions and Permutations Suitable For DES-like Cryptosystems[END_REF] has at most four solutions, 𝑦 𝑖 , 0 ≤ 𝑖 < 4. Moreover, we know from [START_REF] Kyureghyan | Finite fields and their Applications -Character sums and polynomials[END_REF] that 𝑥 is entirely determined by 𝑦. It follows that System [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF] has at most four solutions (𝑥, 𝑦). Let us now suppose that all coefficients of (12) vanish. Then we have 𝜇 2 = 0 and 𝜆 1 + 𝜆 0 𝜇 2 1 = 0 and 𝜆 1 𝑏 + 𝜆 0 𝑎𝜇 1 = 0 . This may occur in one of the following two situations:

-𝜇 1 = 0 and 𝜆 1 = 0. Using that 𝜆 1 cannot vanish only when 𝛼 ̸ = 1, the definitions of 𝜆 1 and 𝜇 1 imply that 𝛼𝑢 2 + 𝑏 2 𝛽 = 0 and 𝑢(𝛼 2 + 1) + 𝑏𝛽 = 0 , leading to 𝛼𝑢 2 = 𝑢(𝛼 2 + 1)𝑏 i.e., 𝛼𝑎 + 𝑏 = 𝑣 = 0 which has been excluded. -𝑏𝜇 1 = 𝑎 and 𝑏 2 𝜆 1 = 𝑎 2 𝜆 0 . From the definition of 𝜇 2 , we deduce that 𝜇 2 = 0 together with this last relation implies that

0 = 𝑢𝜆 -1 0 𝜆 1 + 𝛼 2 𝑢 + 𝑏𝛽 = 𝑏 -2 ( 𝑢𝑎 2 + 𝑢𝛼 2 𝑏 2 + 𝑏 3 𝛽 ) = 𝑏 -2 (𝑢 3 + 𝑏 3 𝛽) i.e., 𝛽 = (𝑢𝑏 -1 ) 3 . ( 13
)
Since 𝜇 2 = 0 and 𝜇 1 = 𝑎𝑏 -1 , ( 11) can be written 𝑎𝑦 = 𝑏𝑥 + 𝜇 ′ 0 . By replacing 𝑎𝑦 by its value in the second equation of ( 7) multiplied by 𝑎 2 and with 𝐴 = 𝑣𝑏 2 + 𝛼 2 𝑎 2 𝑣 + 𝑎 3 𝛽 and 𝐵 = 𝑣 2 𝑎𝑏 + 𝛼𝑎 2 𝑣 2 + 𝑎 4 𝛽, we get

𝐴𝑥 2 + 𝐵𝑥 = 𝑑 ′′ ⇔ (𝑣 3 + 𝑎 3 𝛽)(𝑥 2 + 𝑎𝑥) = 𝑑 ′′ . ( 14
)
The coefficients of this equation do not vanish. Otherwise, combined with [START_REF] Mollin | On permutation polynomials over finite fields[END_REF], it would yield

𝑣 3 + 𝑎 3 𝛽 = (𝛼𝑎 + 𝑏) 3 + (𝑎 2 𝑏 -1 + 𝛼𝑎) 3 = 0 which implies 𝑏 = 𝑎 2 -1
i.e., 𝑎 = 𝑏 and 𝛽 = (𝛼 + 1) 3 which has been excluded. It follows that ( 14) has at most two solutions 𝑥 0 and 𝑥 1 . Since 𝑦 is entirely determined by 𝑥 (or constant), it follows that System (7) has at most two solutions in this case.

B. On APN Butterflies

We first derive a necessary and sufficient condition for a generalised butterfly to be APN in Theorem 4. Then, we simplify these conditions in Corollary 1. Finally, we show in Proposition 2 that this condition can only be satisfied if 𝑛 = 3.

Theorem 4 (APN Condition).

Let 𝛼 ̸ = 0, 1. A generalised butterfly with parameters 𝛼 and 𝛽 is APN if and only if:

𝛽 ∈ {𝛼+𝛼 3 , 𝛼 -1 +𝛼 3 } and Tr (𝒜 𝛼 (𝑒)) = 1, ∀ 𝑒 ̸ ∈ {0, 𝛼, 1/𝛼}, where 𝒜 𝛼 (𝑒) = 𝑒𝛼(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 .
Proof: Since we have proved in Section III-B that generalised butterflies with parameters (𝛼, 𝛽 0 ) and (𝛼, 𝛽 1 ) where 𝛽 1 = 𝛽 -1 0 (1+𝛼) 6 are affine-equivalent, we only need to prove the result for 𝛽 = 𝛼 + 𝛼 3 . As before, we need to count the number of solutions of { 𝑅(𝑥, 𝑦)

+ 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑 (15)
for any tuple (𝑎, 𝑏, 𝑐, 𝑑) of F 2 𝑛 with (𝑎, 𝑏) ̸ = (0, 0). Call

[ℓ 1 ] : 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 [ℓ 2 ] : 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑
This system is equivalent to

[ℓ 1 ] : 𝑎𝑥 2 +𝑎 2 𝑥+ 𝛼(𝑏𝑥 2 + 𝑎 2 𝑦) + 𝛼 2 (𝑏 2 𝑥 + 𝑎𝑦 2 ) + (𝛼 3 + 𝛽)(𝑏𝑦 2 + 𝑏 2 𝑦) = 𝑐 0 .
and

[ℓ 2 ] : 𝑏𝑦 2 + 𝑏 2 𝑦+ 𝛼(𝑎𝑦 2 + 𝑏 2 𝑥) + 𝛼 2 (𝑎 2 𝑦 + 𝑏𝑥 2 ) + (𝛼 3 + 𝛽)(𝑎𝑥 2 + 𝑎 2 𝑥) = 𝑑 0 .
As 𝛼 ̸ = 1, we can replace the lines ℓ 1 and ℓ 2 of this system by ℓ 1 + 𝛼ℓ 2 and 𝛼ℓ 1 + ℓ 2 to obtain a system with the exact same number of solutions. We obtain

[ℓ 1 ] :(𝑎𝑥 2 + 𝑎 2 𝑥)(1 + 𝛼𝛽 + 𝛼 4 ) + (𝛼 + 𝛼 3 )(𝑏𝑥 2 + 𝑎 2 𝑦) + (𝛼 3 + 𝛼 + 𝛽)(𝑏𝑦 2 + 𝑏 2 𝑦) = 𝑐 0 . [ℓ 2 ] :(𝑏𝑦 2 + 𝑏 2 𝑦)(1 + 𝛼𝛽 + 𝛼 4 ) + (𝛼 + 𝛼 3 )(𝑎𝑦 2 + 𝑏 2 𝑥) + (𝛼 3 + 𝛼 + 𝛽)(𝑎𝑥 2 + 𝑎 2 𝑥) = 𝑑 0 .
For 𝛽 = 𝛼 + 𝛼 3 , the system further simplifies using that 1 + 𝛼𝛽 + 𝛼 4 = (1 + 𝛼 2 ) and 𝛼 + 𝛼 3 + 𝛽 = 0:

{ (𝑎𝑥 2 + 𝑎 2 𝑥) + 𝛼(𝑏𝑥 2 + 𝑎 2 𝑦) = 𝑐 1 (𝑏𝑦 2 + 𝑏 2 𝑦) + 𝛼(𝑎𝑦 2 + 𝑏 2 𝑥) = 𝑑 1 . ( 16
)
We first consider the cases 𝑎 = 0 and 𝑏 = 0. Recall that 𝑎 = 𝑏 = 0 is excluded. If 𝑎 = 0, then the first line of the system is equivalent to

𝑥 = ( 𝑐 1 𝛼𝑏 ) 2 𝑛-1 .
Replacing 𝑥 by this value in the second line of System ( 16) yields a degree-2 equation in 𝑦 with nonzero coefficients since 𝑏 ̸ = 0, implying that ( 16) has at most two solutions (𝑥, 𝑦). The case 𝑏 = 0 is similar. We now suppose 𝑎 ̸ = 0 and 𝑏 ̸ = 0, which allows us to set 𝑥 = 𝑎𝑥 ′ and 𝑦 = 𝑏𝑦 ′ . In this context, System (16) has as many solutions as

{ 𝑎 3 (𝑥 ′2 + 𝑥 ′ ) + 𝛼𝑎 2 𝑏(𝑥 ′2 + 𝑦 ′ ) = 𝑐 1 𝑏 3 (𝑦 ′2 + 𝑦 ′ ) + 𝛼𝑎𝑏 2 (𝑦 ′2 + 𝑥 ′ ) = 𝑑 1 ,
which we rewrite using 𝑒 = 𝑎/𝑏 as

{ 𝑒(𝑥 ′2 + 𝑥 ′ ) + 𝛼(𝑥 ′2 + 𝑦 ′ ) = 𝑐 2 𝑒 -1 (𝑦 ′2 + 𝑦 ′ ) + 𝛼(𝑦 ′2 + 𝑥 ′ ) = 𝑑 2 . ( 17
)
Summing its lines yields

(𝑥 ′2 + 𝑥 ′ )(𝑒 + 𝛼) + (𝑦 ′2 + 𝑦 ′ )(𝑒 -1 + 𝛼) = 𝑐 2 + 𝑑 2 . If 𝑒 = 𝛼, then 𝑦 ′ is fixed to either 𝑦 ′ 0 or 𝑦 ′ 1 with 𝑦 ′ 0 + 𝑦 ′ 1 = 1.
The first line of the system implies in this case that 𝑥 ′ = 𝑦 ′ 𝑖 + 𝑐 2 /𝛼 as the terms in 𝑥 2 cancel each other, meaning that the system has at most two solutions. The case 𝑒 = 𝛼 -1 is similar. We now suppose 𝑒 ̸ = 𝛼, 𝛼 -1 .

The first line of System [START_REF] Canteaut | On cryptographic properties of the cosets of R(1, m)[END_REF] allows us to express 𝑦 ′ as a function of 𝑥 ′ :

𝑦 ′ = 𝑥 ′2 ( 𝑒 𝛼 + 1 ) + 𝑥 ′ 𝑒 𝛼 + 𝑐 2 𝛼 .
We replace 𝑦 ′ by this expression in the second line of ( 17) and obtain

𝑌 = 𝑦 ′2 ( 𝑒 -1 + 𝛼 ) + 𝑦 ′ 𝑒 -1 + 𝛼𝑥 ′ = ( 𝑥 ′2 ( 𝑒 𝛼 + 1 ) + 𝑥 ′ 𝑒 𝛼 ) 2 ( 𝑒 -1 + 𝛼 ) + ( 𝑥 ′2 ( 𝑒 𝛼 + 1 ) + 𝑥 ′ 𝑒 𝛼 ) 𝑒 -1 + 𝛼𝑥 ′ = 𝑥 ′4 ( 1 + 𝑒 𝛼 ) 2 (𝛼 𝑒 -1 ) + 𝑥 ′2 ( 𝑒 2 𝛼 2 (𝑒 -1 + 𝛼) + ( 𝑒 𝛼 + 1 ) 𝑒 -1 ) + 𝑥 ′ ( 1 𝛼 + 𝛼 ) = 𝑑 3
for some constant 𝑑 3 . If we let 𝑈 = (1 + 𝑒/𝛼) 2 (𝛼 + 1/𝑒) and 𝑉 = 𝑈 + 1/𝛼 + 𝛼, then the number of solutions of this equation can be computed using Lemma 4. First, 𝑈 ̸ = 0 and 𝑈 + 𝑉 ̸ = 0 as 𝛼 ̸ = 1. Therefore, the possible number of solutions is at most equal to 4 and is given by the trace of 𝑉 /𝑈 : if Tr (𝑉 /𝑈 ) = 0 then the equation has at most 2 solutions, otherwise it has 0 or 4 solutions. It holds that

𝑉 𝑈 = 1 + 𝛼 -1 + 𝛼 (𝑒 -1 + 𝛼)(1 + 𝑒𝛼 -1 ) 2 = 1 + 𝑒𝛼(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2
so the function is APN if and only if

Tr (𝒜 𝛼 (𝑒)) = 1, ∀𝑒 ̸ = 0, 𝛼, 1/𝛼, with 𝒜 𝛼 (𝑒) = 𝑒𝛼(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 .
The condition provided by Theorem 4 is sufficient to describe all APN generalised butterflies but it can be greatly simplified. This is stated in the following corollary.

Corollary 1. Let 𝛼 ̸ = 1, 𝛽 0 = 𝛼 3 + 𝛼 and 𝛽 1 = 𝛼 3 + 1/𝛼. A generalised butterfly with parameters 𝛼 and 𝛽 is APN if and only if 𝛽 = 𝛽 0 or 𝛽 1 and

Tr (𝒞 𝛼 (𝑣)) = 1, ∀ 𝑢 ̸ ∈ { 0, 1, 1/(1 + 𝛼 -2 ) } .
with

𝒞 𝛼 (𝑣) = ( 1 1 + 𝛼 -1 ) 4 1 𝑢 + 𝑢 3 .
Proof of Corollary 1: We know from Theorem 4 that a generalised butterfly with parameters 𝛼 and 𝛽 is APN if and only if 𝛽 ∈ {𝛽 0 , 𝛽 1 } and Tr (𝒜 𝛼 (𝑒)) = 1 for all 𝑒 not in {0, 𝛼, 1/𝛼}. Suppose that 𝛼 ̸ = 1 and let ℓ = (𝑒 + 𝛼)(1 + 𝛼) 2 . Then we can rewrite some of the expressions involved in 𝒜 𝛼 (𝑒) as follows:

𝑒(1+𝛼) 2 = ℓ+𝛼+𝛼 3 and (1+𝛼𝑒)(1+𝛼) 2 = 𝛼 ( ℓ + (1 + 𝛼) 4 𝛼 ) .
Recall that 𝛽 0 = 𝛼 + 𝛼 3 and 𝛽 1 = (𝛼 + 1) 4 /𝛼, so we can write:

𝒜 𝛼 (𝑒) = 𝑒𝛼(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 = 𝛼 𝑒(1 + 𝛼 2 ) (1 + 𝛼𝑒)(1 + 𝛼 2 ) ((𝛼+𝑒)(1+𝛼) 2 ) 2 (1+𝛼) 6 = (1 + 𝛼) 6 𝛼(ℓ + 𝛽 0 ) 𝛼(ℓ + 𝛽 1 )ℓ 2 = 𝛽 0 𝛽 1 ℓ 2 ℓ + 𝛽 0 ℓ + 𝛽 1 .
Let ℬ 𝛼 (𝑣) = 𝑣 2 (𝑣 + 1)/(𝑣 + 𝛽 0 /𝛽 1 ). Then the following equality holds:

ℬ 𝛼 ( 𝛽 0 ℓ ) = 𝛽 0 𝛽 1 ℓ 2 ℓ + 𝛽 0 ℓ + 𝛽 1 = 𝒜 𝛼 (𝑒) .
It is therefore sufficient to study the trace of ℬ 𝛼 . The condition 𝑒 ̸ ∈ {0, 𝛼, 𝛼 -1 } becomes ℓ ̸ ∈ {𝛽 0 , 0, 𝛽 1 } respectively and, equivalently, 𝛽 0 /ℓ ̸ ∈ {0, 1, 𝛽 0 /𝛽 1 }. As a consequence, the generalised butterfly with parameters 𝛼, 𝛽 is APN if and only if 𝛽 = 𝛽 0 or 𝛽 1 and

Tr (ℬ 𝛼 (𝑣)) = 1, ∀𝑣 ̸ ∈ { 0, 1, 𝛼 2 1 + 𝛼 2 } as 𝛽 0 /𝛽 1 = 𝛼 2 /(1 + 𝛼 2 )
. Finally, we note that the trace of ℬ 𝛼 (𝑣) can be simplified:

Tr (ℬ 𝛼 (𝑣)) = Tr ( 𝑣 2 1 + 𝑣 𝑣 + 𝛼 2 1+𝛼 2 ) = Tr ( 𝑣 2 + 𝑣 2 (1 + 𝛼 2 )𝑣 + 𝛼 2 ) = Tr ( 𝑣 + 𝑣 2 (1 + 𝛼 2 )𝑣 + 𝛼 2 ) = Tr ( (1 + 𝛼 2 )𝑣 2 + 𝛼 2 𝑣 + 𝑣 2 (1 + 𝛼 2 )𝑣 + 𝛼 2 ) = Tr ( 𝑣 2 + 𝑣 𝛾𝑣 + 1
) ,

where 𝛾 = 1 + 𝛼 -2 . We deduce the following:

Tr ( ℬ 𝛼 ( 𝑢 -1 𝛾 -1 )) = Tr ( ( 𝑢 -1 𝛾 -1 ) 2 + 𝑢 -1 𝛾 -1 𝑢 -1 + 1 ) = Tr ( ( 𝑢 -1 𝛾 -1 ) 2 𝑢 -1 + 1 + ( 𝑢 -1 𝛾 -1 ) 2 𝑢 -2 + 1 ) = Tr ( (𝑢 -3 + 𝑢 -2 )𝛾 -2 + 𝑢 -2 𝛾 -2 𝑢 -2 + 1 ) = Tr ( 𝛾 -2 𝑢 + 𝑢 3 ) . The condition 𝑢 -1 /𝛾 ̸ ∈ {0, 1, 𝛾 -1 } is equivalent to 𝑢 ̸ ∈ {0, 𝛾 -1 , 1}
, the same set as before. This proves the corollary.

We now show that the last condition in Corollary 1 can hold if 𝑛 = 3 only. In other words, APN generalised butterflies exist for 𝑛 = 3 only. The proof relies on the following lemma. Lemma 5. [START_REF] Berlekamp | On the solution of algebraic equations over finite fields[END_REF] The cubic equation 𝑥 3 + 𝑎𝑥 + 𝑏 = 0, where 𝑎 ∈ F 2 𝑛 and 𝑏 ∈ F * 2 𝑛 has a unique solution in F 2 𝑛 if and only if Tr(𝑎 3 /𝑏 2 ) ̸ = Tr(1). Proposition 2. Let 𝑛 > 1 be an odd integer, and

𝜆 ∈ F * 2 𝑛 . If Tr ( 𝜆 2 𝑥 + 𝑥 3 ) = 1, ∀ 𝑥 ̸ ∈ {0, 1, 𝜆} , (18)
then 𝑛 = 3.

Proof: Let 𝑧 in F * 2 𝑛 with Tr(𝑧) = 0. Then, there exists a unique 𝑥 ∈ F 2 𝑛 ∖ F 2 such that

1 𝑥 3 + 𝑥 = 𝑧 .
Indeed, since 𝑧 ̸ = 0, this equivalently means that

𝑥 3 + 𝑥 + 1 𝑧 = 0 .
We know from Lemma 5 that this equation has a unique solution when Tr(𝑧 2 ) = Tr(𝑧) = 0. Let us define 𝑧 𝜆 as

𝑧 𝜆 = 1 𝜆 3 + 𝜆 ,
and

𝒵 = {𝑧 ∈ F * 2 𝑛 ∖ {𝑧 𝜆 } : Tr(𝑧) = 0} .
Obviously, 𝒵 is either a hyperplane without 0 or a hyperplane without 0 and 𝑧 𝜆 (depending on the value of Tr(𝑧 𝜆 )). Then, Condition [START_REF]Propagation characteristics and correlation-immunity of highly nonlinear boolean functions[END_REF] implies that, for any 𝑧 ∈ 𝒵,

Tr(𝜆 2 𝑧) = 1 .
Suppose that 𝑛 ≥ 5. Then, 𝒵 contains at least (2 𝑛-1 -2) ≥ 14 elements and there exists at least two distinct elements 𝑧 0 and 𝑧 1 in 𝒵 such that 𝑧 0 + 𝑧 1 ∈ 𝒵. Therefore, these two elements must satisfy

Tr(𝜆 2 𝑧 0 ) = Tr(𝜆 2 𝑧 1 ) = Tr(𝜆 2 (𝑧 0 + 𝑧 1 )) = 1
which is impossible since

Tr(𝜆 2 (𝑧 0 + 𝑧 1 )) = Tr(𝜆 2 𝑧 0 ) + Tr(𝜆 2 𝑧 1 )
When 𝑛 = 3, the situation is different since the condition may be satisfied when 𝒵 contains 2 elements only, i.e. when Tr(𝑧 𝜆 ) = 0.

C. The Feistel case 𝛼 = 𝛽 = 1

In the case when 𝛼 = 𝛽 = 1, the generalised butterfly is equivalent to a 3-round Feistel network with round functions 𝑥 ↦ → 𝑥 3 , 𝑥 ↦ → 𝑥 1/3 and 𝑥 ↦ → 𝑥 3 . Theorem 4 in [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF] shows that, in this special case, the difference distribution table of the corresponding butterflies does not contain any 2. In other words, the number of solutions (𝑥, 𝑦) of

{ 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑
for any tuple (𝑎, 𝑏, 𝑐, 𝑑) of F 2 𝑛 with (𝑎, 𝑏) ̸ = (0, 0) is either 0 or 4. We now give an alternative proof of this result.

Proposition 3. [20, Theorem 4] For 𝛼 = 𝛽 = 1, the difference distribution tables of the butterflies V 1,1 and H 1,1 contain the values 0 and 4 only.

Proof: As in the proof of Theorem 3, we have to count the number of solutions of System [START_REF] Gold | Maximal recursive sequences with 3-valued recursive crosscorrelation functions[END_REF], which simplifies to

{ (𝑎 + 𝑏)𝑥 2 + (𝑎 + 𝑏) 2 𝑥 + 𝑎𝑦 2 + 𝑎 2 𝑦 = 𝑐 ′ 𝑏𝑥 2 + 𝑏 2 𝑥 + (𝑎 + 𝑏)𝑦 2 + (𝑎 + 𝑏) 2 𝑦 = 𝑑 ′ . (19)
• If 𝑎 = 0, the first line of the system equals 𝑏(𝑥 2 +𝑏𝑥) = 𝑐 ′ which has either 0 or 2 solutions, 𝑥 0 and 𝑥 1 (recall that 𝑎 and 𝑏 cannot simultaneously vanish). The second line of the system can be rewritten as

𝑏 ( (𝑥 + 𝑦) 2 + 𝑏(𝑥 + 𝑦) ) = 𝑑 ′
which has either 0 or 2 solutions, implying 𝑦 ∈ {𝑥 + 𝑧 0 , 𝑥 + 𝑧 1 }. Therefore, if the first line has two solutions, the second one has either 0 or 4 solutions. The case 𝑏 = 0 is similar. • If 𝑎 = 𝑏, the system is composed of two independent degree-2 equations, one in 𝑥 and the second one in 𝑦. If one of these equations has no solution, then the whole system does not have any solution. Otherwise, each equation has two solutions, and the system has 4 solutions. Replacing 𝑦 ′ = 𝑏𝑦, we equivalently obtain

𝑈 𝑦 ′4 + 𝑉 𝑦 ′2 + 𝑊 𝑦 ′ = 𝑏 -8 𝜀 ′ (21)
where the coefficients 𝑈 , 𝑉 and 𝑊 depend on 𝑒 = 𝑎/𝑏: D. Walsh spectrum and difference distribution tables of generalised butterflies

𝑈 = 𝑒 4 + 𝑒 2 + 1 = (𝑒 2 + 𝑒 + 1) 2 𝑉 = 𝑒 6 + 𝑒 5 + 𝑒 3 + 𝑒 + 1 = (𝑒 2 + 𝑒 + 1) 3 𝑊 = 𝑒 6 + 𝑒 5 + 𝑒 4 + 𝑒 3 + 𝑒 2 + 𝑒 = 𝑈 + 𝑉 .
Theorem 2 points out that, for 𝛽 ̸ = (1 + 𝛼) 3 , the nonzero components of V 𝛼,𝛽 are either bent, or their Walsh coefficients belong to {0, ±2 𝑛+1 }. Then, the whole multiset

{| H 𝛼,𝛽 (𝑢, 𝑣)|, 𝑢 ∈ F 2𝑛 2 , 𝑣 ∈ F 2𝑛 2 ∖ {0}} = {| ̂ V 𝛼,𝛽 (𝑢, 𝑣)|, 𝑢 ∈ F 2𝑛 2 , 𝑣 ∈ F 2𝑛 2 ∖
{0}} is entirely determined by the number 𝐵 of bent components of V 𝛼,𝛽 . Moreover, it is well-known that there is a one-toone correspondence between the squared Walsh transform of a vectorial function and its difference distribution table (see e.g. [START_REF] Chabaud | Links between differential and linear cryptoanalysis[END_REF], [START_REF] Blondeau | Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities[END_REF]). Therefore, different values of 𝐵 correspond to different difference distribution tables. Since all generalised butterflies have differential uniformity at most 4, the value of 𝐵 equivalently determines the number of occurrences of 4 in the difference distribution table of the mapping. This correspondence is detailed in the following proposition, which is a variant of Corollary 3 in [START_REF] Berger | On almost perfect nonlinear functions over F 𝑛 2[END_REF]. Proposition 4. Let 𝑚 be an even integer, and 𝐹 be a differentially 4-uniform mapping from F 𝑚 2 into itself such that its nonzero components are bent or have Walsh spectrum {0, ±2 𝑚 2 +1 }. Then, the number of 4 in the difference distribution table of 𝐹 is equal to

2 𝑚-2 (2 𝑚 -1) -3 × 2 𝑚-1 𝐵
where 𝐵 is the number of bent components of 𝐹 .

Most notably,

• 𝐹 is APN if and only if 𝐵 = 2(2 𝑚 -1)

3

; • The difference distribution table of 𝐹 does not contain any 2 if and only if 𝐵 = 0.

Proof: It is well-known [START_REF] Chabaud | Links between differential and linear cryptoanalysis[END_REF], [START_REF] Blondeau | Links between truncated differential and multidimensional linear properties of block ciphers and underlying attack complexities[END_REF] that the squared Walsh transform of 𝐹 is the Fourier transform of the mapping

(𝑎, 𝑏) ∈ F 𝑚 2 ×F 𝑚 2 ↦ → 𝛿(𝑎, 𝑏) = #{𝑥 ∈ F 𝑚 2 : 𝐹 (𝑥+𝑎)+𝐹 (𝑥) = 𝑏}.
A direct consequence is then the following result mentioned in [START_REF] Tan | Enhanced criteria on differential uniformity and nonlinearity of cryptographically significant functions[END_REF]Theorem 2] for instance:

∑ 𝜆∈F 𝑚 2 ∑ 𝜇∈F 𝑚 2 ̂ 𝐹 (𝜆, 𝜇) 4 = 2 2𝑚 ∑ 𝑎,𝑏∈F 𝑚 2 𝛿(𝑎, 𝑏) 2 .
Moreover, we have

∑ 𝜆∈F 𝑚 2 ̂ 𝐹 (𝜆, 𝜇) 4 = ⎧ ⎪ ⎨ ⎪ ⎩ 2 4𝑚 if 𝜇 = 0 2 3𝑚 if 𝐹 𝜇 is bent 2 3𝑚+2 otherwise.
It follows that

∑ 𝜆∈F 𝑚 2 ∑ 𝜇∈F 𝑚 2 ̂ 𝐹 (𝜆, 𝜇) 4 = 2 4𝑚 + 2 3𝑚 ( 2 𝑚+2 -4 -3𝐵 ) .
Let 𝐴 2 and 𝐴 4 respectively denote the number of occurrences of 2 and 4 in the difference distribution table of 𝐹 . We know that

∑ 𝑎∈F 𝑚 2 ∖{0} ∑ 𝑏∈F 2 𝑚 𝛿(𝑎, 𝑏) = 2𝐴 2 + 4𝐴 4 = (2 𝑚 -1)2 𝑚 .
We derive that

∑ 𝑎,𝑏∈F 𝑚 2 𝛿(𝑎, 𝑏) 2 = 2 2𝑚 + 4𝐴 2 + 16𝐴 4 = 2 2𝑚 + 2 𝑚+1 (2 𝑚 -1) + 8𝐴 4 .
Therefore We have seen in Proposition 3 that, when 𝛼 = 𝛽 = 1, the difference distribution tables of the corresponding butterflies do not contain any 2. The last item of the previous proposition shows that this situation corresponds to the case where V 𝛼,𝛽 has no bent component. In other words, the Walsh coefficients of V 1,1 and of H 1,1 over F 2 𝑛 × F 2 𝑛 take the values 0 and ±2 𝑛+1 only. This result, corresponding to Theorem 5 in [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF], is then a direct consequence of Proposition 3.

8𝐴 4 = 2 𝑚 ( 2 𝑚+2 -4 -3𝐵 -2 𝑚+1 -2 ) = 2 𝑚 ( 2
More generally, the whole Walsh spectrum and difference distribution table of generalised butterflies is derived by applying the previous proposition to V 𝛼,𝛽 .

Corollary 2 (Walsh and differential spectra of generalised butterflies). Let 𝛼 and 𝛽 be two nonzero elements in F 2 𝑛 such that 𝛽 ̸ = (1 + 𝛼) 3 . The Walsh spectrum of H 𝛼,𝛽 and V 𝛼,𝛽 , i.e., the multiset

{| H 𝛼,𝛽 (𝑢, 𝑣)|, 𝑢 ∈ F 2𝑛 2 , 𝑣 ∈ F 2𝑛 2 ∖ {0}} = {| ̂ V 𝛼,𝛽 (𝑢, 𝑣)|, 𝑢 ∈ F 2𝑛 2 , 𝑣 ∈ F 2𝑛 2 ∖ {0}} is given by ⃒ ⃒ ⃒ H 𝛼,𝛽 (𝑢, 𝑣) ⃒ ⃒ ⃒ = ⎧ ⎨ ⎩ 0, 3 × 2 2𝑛-2 (2 𝑛 -1)(2 𝑛 + 1 -𝐶) times 2 𝑛 , 2 2𝑛 (2 𝑛 -1)𝐶 times 2 𝑛+1 , 2 2𝑛-2 (2 𝑛 -1)(2 𝑛 + 1 -𝐶) times.
where (2 𝑛 -1)𝐶 is the number of bent components of V 𝛼,𝛽 .

The difference distribution table of both H 𝛼,𝛽 and V 𝛼,𝛽 contains the values 0, 2 and 4 with the following number of occurrences

𝛿(𝑎, 𝑏) = { 2, 2 2𝑛-2 (2 𝑛 -1) × 3𝐶 times 4, 2 2𝑛-3 (2 𝑛 -1)(2 𝑛+2 + 4 -3𝐶) times Proof:
The result is directly deduced from Proposition 4, using that the number of bent components of V 𝛼,𝛽 is of the form 𝐵 = (2 𝑛 -1)𝐶. Indeed, let 𝑓 𝜆,𝜇 , for 𝜆, 𝜇 in F 2 𝑛 , denote the components of V 𝛼,𝛽 , i.e., 𝑓 𝜆,𝜇 : (𝑥, 𝑦) ↦ → Tr(𝜆𝑅(𝑥, 𝑦)) + Tr(𝜇𝑅(𝑦, 𝑥)) .

We have seen in the proof of Theorem 2 that, for any 𝜇 ∈ F * 2 𝑛 , 𝑓 0,𝜇 is not bent, and that, for any nonzero 𝜆 ∈ F 2 𝑛 , 𝑓 𝜆,𝜇 is bent if and only if 𝑓 1,𝜆 -1 𝜇 is bent. We deduce that 𝐵 = (2 𝑛 -1)𝐶 where 𝐶 is the number of 𝜇 ∈ F 2 𝑛 such that 𝑓 1,𝜇 is bent. The Walsh spectrum of the generalised butterfly is then derived by using that all Walsh coefficients of a bent component are equal to ±2 𝑛 and, for a component with linearity 2 𝑛+1 , the Walsh transform takes 2 2𝑛-2 times the value ±2 𝑛+1 and (2 2𝑛 -2 2𝑛-2 ) times the value 0 (see Proposition 1).

The differential spectrum is deduced from Proposition 4: the number of 4 in the difference distribution table is

𝐴 4 = 2 𝑚-2 (2 𝑚 -1) -3 × 2 𝑚-1 𝐵 = 2 2𝑛-3 (2 𝑛 -1) ( 2 𝑛+1 + 2 -3𝐶 ) ,
and the number of 2 in the difference distribution table is

𝐴 2 = (2 2𝑛 -1)2 2𝑛-1 -2𝐴 4 = 2 2𝑛-2 (2 𝑛 -1) × 3𝐶 .
The values of 𝐶 for all H 𝛼,𝛽 of 2𝑛 variables, with 𝑛 ∈ {3, 5} are given in Tables I and II. We have checked by computer for 𝑛 ∈ {3, 5, 7, 9} that, when 𝛼 and 𝛽 vary in F * 2 𝑛 , 𝐶 takes the value 0 and all even values between ( 2 𝑛 +4 3 -2 (𝑛-1)/2 ) and ( 2 𝑛 +4 3 +2 (𝑛-1)/2 ). This implies that, for these values of 𝑛, the family of generalised butterflies contains mappings with (2 (𝑛-1)/2 + 2) different Walsh spectra (and therefore the same number of difference distribution tables).

It is also worth noticing that the family of generalised butterflies includes some mappings which are not CCZ-equivalent to the mappings in the family studied in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF]. Indeed, the case = 1 does not include all possible values for 𝐶.

We can also check, from the values of 𝐶, that most of the generalised butterflies are not CCZ-equivalent to previously known differentially 4-uniform permutations. For instance, Table I shows that the generalised butterflies of 6 variables have a difference distribution table with a number of 4 equal to one of the following four values: 𝐴 4 ∈ {0, 336, 672, 1008} .

While the last case corresponds to the same differential spectrum as the Gold and Kasami power permutations, the functions with the two intermediate values of 𝐴 4 cannot be CCZ-equivalent to a power function. Indeed, the only differentially 4-uniform power functions satisfy 𝐴 4 = 1008 (Gold and Kasami) or 𝐴 4 = 63 (inverse mapping). More generally, for any number of variables, none of the generalised butterflies is CCZ-equivalent to the inverse mapping since the formula of 𝐴 4 in the proof of Corollary 2 shows that 𝐴 4 is even, while the inverse mapping has an odd number of 4 in its difference distribution table. Similarly, it can be checked that the only permutation of F 6 2 with optimal nonlinearity constructed in [START_REF] Qu | Constructing differentially 4uniform permutations over F 2 2𝑘 via the switching method[END_REF] has another differential spectrum (see [START_REF] Qu | Constructing differentially 4uniform permutations over F 2 2𝑘 via the switching method[END_REF]Table II]). It is also worth noticing that the generalised butterflies of six variables have a higher nonlinearity than the functions constructed in [START_REF] Tang | Differentially 4-uniform bijections by permuting the inverse function[END_REF] and in [START_REF] Zha | Constructing new differentially 4-uniform permutations from the inverse function[END_REF].

VI. ON ALGEBRAIC DEGREE

It is well-known that, if all Walsh coefficients of a Boolean function 𝑓 of 𝑚 variables are divisible by 2 ℓ , then the algebraic degree of 𝑓 is at most (𝑚 + 1 -ℓ) (see e.g. [START_REF] Langevin | Covering radius of RM (1, 9) in RM (3, 9)[END_REF]Prop. 1.5]). Thus, we deduce from Theorem 2 that the algebraic degree

(1 + 𝛼𝛽 + 𝛼 4 ) 3 = 𝛽(𝛽 + 𝛼 + 𝛼 3 ) 3 .
The closed butterfly V 𝛼,𝛽 has algebraic degree 2.

Remark 2. The condition (1 + 𝛼𝛽 + 𝛼 4 ) 3 = 𝛽(𝛽 + 𝛼 + 𝛼 3 ) 3 can alternatively be written 𝑍(𝛼, 𝛽) = 0, where:

𝑍(𝛼, 𝛽) = 𝛽 4 + 𝛼𝛽 3 + 𝛼(𝛼 + 1) 6 𝛽 + (1 + 𝛼) 12 .
Furthermore, 𝑍 can be factorised as follows:

𝑍(𝛼, 𝛽) = 𝛽 4 + 𝛼𝛽 3 + 𝛼(𝛼 + 1) 6 𝛽 + (1 + 𝛼) 12 = ( 𝛽 2 + (1 + 𝛼) 6 ) ( 𝛽 2 + 𝛼𝛽 + (1 + 𝛼) 6 ) = ( 𝛽 2 + (1 + 𝛼) 6 ) ( 1 + 𝛼𝛽 + 𝛼 4 + (𝛽 + 𝛼 + 𝛼 3 ) 2 ) .
Hence, if 𝛽 ̸ = (1 + 𝛼) 3 then 𝑍(𝛼, 𝛽) = 0 if and only 1 + 𝛼𝛽 + 𝛼 4 = (𝛽 + 𝛼 + 𝛼 3 ) 2 . It follows that 𝑍(𝛼, 𝛽) is equal to 0 when 𝛽 = (1 + 𝛼) 3 and, if Tr(𝛼 -1 ) = 1, for two additional values of 𝛽. This includes the Feistel case, when 𝛼 = 𝛽 = 1.

Proof: Obviously, V 𝛼 (𝑥, 𝑦) has algebraic degree 2. We then focus on the generalised open butterfly H 𝛼,𝛽 . The right side of the output of such an open butterfly is equal to (𝑥 + 𝛽𝑦 3 ) 1/3 + 𝛼𝑦, where (𝑥, 𝑦) is the input. We deduce from Theorem 1 of [START_REF] Kyureghyan | On inverses of APN exponents[END_REF] (or equivalently from Proposition 5 of [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF]) that the inverse of 3 modulo (2 𝑛 -1) for odd 𝑛 is 1/3 ≡ (𝑛-1)/2 ∑ 𝑖=0 2 2𝑖 mod (2 𝑛 -1), which implies in particular that the algebraic degree of 𝑥 ↦ → 𝑥 1/3 is equal to (𝑛+1)/2. We deduce from this expression that the function 𝑡(𝑥, 𝑦) = (𝑥 + 𝛽𝑦 3 ) 1/3 is equal to ∏ (𝑛-1)/2

𝑖=0 (𝑥 + 𝛽𝑦 3 ) 2 2𝑘
. This sum can be developed as follows:

𝑡(𝑥, 𝑦) = (𝑥 + 𝛽𝑦 3 ) 1/3 to 𝛽 1/3 𝑦 and has degree 1. If 𝐽 = {𝑗} for some 𝑗, then the term is equal to 1) .

𝑇 = 𝑥 2 2𝑗 × 𝛽 1/3 𝑦 × (𝛽𝑦 3 ) 2 𝑛 -1-2 2𝑗 = 𝛽 1/3-2 2𝑗 × 𝑥 2 2𝑗 × 𝑦 (2 𝑛 -1)-(2 2𝑗+1 +2 2𝑗 -
If 𝑗 ̸ = (𝑛 -1)/2, then its algebraic degree is

1 + 𝑛 -𝑤𝑡(2 2𝑗+1 + 2 2𝑗 -1) = -2𝑗 .
If 𝑗 = (𝑛 -1)/2, then the term (omitting the constant factor) is equal to

𝑥 2 𝑛-1 × 𝑦 × 𝑦 2 𝑛 -1-(2 𝑛 -2 𝑛-1 ) = 𝑥 2 𝑛-1 𝑦 2 𝑛-1 -1 .
and has degree 𝑛. Therefore, 𝑡(𝑥, 𝑦) has two terms of degree 𝑛, corresponding to 𝑗 = 0 and 𝑗 = (𝑛 -1)/2 namely 𝑚 0 (𝑥, 𝑦) = 𝛽 -2/3 𝑥𝑦 2 𝑛 -3

and 𝑚 1 (𝑥, 𝑦) = 𝛽 (2 𝑛-1 -1)/3 𝑥 2 𝑛-1 𝑦 2 𝑛-1 -1

Thus, the right side of the output has an algebraic degree equal to 𝑛. The terms on the first line have degree at most 3. Let us focus on those of the second line and denote their sum 𝐿 ′ (𝑥, 𝑦). First, we can simplify this expression as follows:

𝐿 ′ (𝑥, 𝑦) 𝛼 = 𝐶 0 𝑦𝑡(𝑥, 𝑦) 2 + 𝐶 1 𝑦 2 𝑡(𝑥, 𝑦)

where 𝐶 0 = (𝛽 + 𝛼 + 𝛼 3 ) and 𝐶 1 = (1 + 𝛼𝛽 + 𝛼 4 ).

Since 𝑡(𝑥, 𝑦) has algebraic degree 𝑛, we deduce that 𝐿 ′ (𝑥, 𝑦) (and the left side of the output of H 𝛼,𝛽 ) has algebraic degree at most (𝑛 + 1), while the whole function has degree at least 𝑛 because of the right side. Moreover, this upper bound is reached if and only if the terms of degree (𝑛+1) in 𝐿 ′ (𝑥, 𝑦) do not cancel each other. The only terms in 𝐿 ′ (𝑥, 𝑦) which may have degree (𝑛 + 1) correspond to terms of degree 𝑛 in 𝑡(𝑥, 𝑦), namely (omitting the constant factors): 𝑦 2 𝑚 0 (𝑥, 𝑦) = 𝑥𝑦 2 𝑛 -1 , 𝑦 2 𝑚 1 (𝑥, 𝑦) = 𝑥 2 𝑛-1 𝑦 2 𝑛-1 +1 , 𝑦𝑚 0 (𝑥, 𝑦) 2 = 𝑥 2 𝑦 (2 𝑛 -1)-3 , 𝑦𝑚 1 (𝑥, 𝑦) 2 = 𝑥𝑦 2 𝑛 -1 .

Only the first and the last terms have degree (𝑛+1). Therefore, the term of degree (𝑛 + 1) in 𝐿 ′ (𝑥, 𝑦) is:

𝐶 0 𝑦𝑚 1 (𝑥, 𝑦) 2 +𝐶 1 𝑦 2 𝑚 0 (𝑥, 𝑦) =𝑥𝑦 2 𝑛 -1 ( 𝐶 0 𝛽 -1/3 +𝐶 1 𝛽 -2/3 ) =𝑥𝑦 2 𝑛 -1 𝛽 -1/3 ( 𝐶 0 +𝐶 1 𝛽 -1/3
) .

It follows that H 𝛼,𝛽 has algebraic degree (𝑛 + 1) if and only if 𝛽𝐶 3 0 ̸ = 𝐶 3 1 .

VII. CONCLUSION

We have solved the two open questions raised in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF] on the properties of butterflies. Moreover, a larger family of permutations of F 2𝑛 2 , for any odd 𝑛 ≥ 3, with differential uniformity 4 and linearity 2 𝑛+1 , has been described. Several functions with similar cryptographic properties have already been exhibited, e.g. in [START_REF] Qu | Constructing differentially 4uniform permutations over F 2 2𝑘 via the switching method[END_REF]- [START_REF] Zha | Constructing new differentially 4-uniform permutations from the inverse function[END_REF], [START_REF] Bracken | A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree[END_REF]- [START_REF] Peng | New explicit constructions of differentially 4uniform permutations via special partitions of F 2 2𝑘[END_REF]. However, the family of open butterflies presents two interesting characteristics. First, it has a reasonably simple representation which may be suitable for cryptographic applications (some specific cases can even be implemented as 3-round Feistel networks) which is also easier to handle for determining its cryptographic properties. A second specificity is that it is the only known such infinite family which includes the APN permutation exhibited by Dillon et al. Unfortunately, it does not contain any other APN permutation, implying that the "big APN problem" raised by Dillon remains open.

Lemma 4 .

 4 Let 𝑈, 𝑉 be elements of F 2 𝑛 with 𝑛 odd and let 𝑈 𝑧 4 + 𝑉 𝑧 2 + (𝑈 + 𝑉 )𝑧 = 𝐶 be some linearised degree-4 equation in 𝑧. It has:• 0 or 2 𝑛 solutions if 𝑈 = 𝑉 = 0, • 0 or 4 solutions if 𝑈 ̸ = 0, 𝑈 ̸ = 𝑉 and Tr (𝑉 /𝑈 ) = 1,• 0 or 2 solutions otherwise, that is if one of the following is true:-𝑈 = 0, 𝑉 ̸ = 0, -𝑈 ̸ = 0 and 𝑉 = 𝑈 , -𝑈 ̸ = 0 and Tr (𝑉 /𝑈 ) = 0,

  + 𝑉 /𝑈 + 𝑧(𝑧 + 1) ) = 0.Both 𝑧 = 0 and 𝑧 = 1 are obviously solutions. In fact, they are the only ones if 𝑉 = 𝑈 . Let us suppose that 𝑉 ̸ = 𝑈 . The term (𝑧 2 + 𝑧 + 1 + 𝑉 /𝑈 ) can be equal to 0 if and only if Tr (𝑉 /𝑈 ) = 1, meaning that the linearised equation has 2 solutions if Tr (𝑉 /𝑈 ) = 0 and 4 otherwise.A. The Non-APN CasesTheorem 3 (Differential uniformity). Let 𝑛 > 1 be an odd integer and (𝛼, 𝛽) be a pair of nonzero elements in F 2 𝑛 . If 𝛽 ̸ = (1+𝛼)3 , the generalised butterfly with parameters 𝛼 and 𝛽 has differential uniformity at most 4. Moreover, it has differential uniformity exactly 4 unless 𝛽 ∈ {(𝛼 + 𝛼 3 ), (𝛼 -1 + 𝛼 3 )}.If 𝛽 = (1 + 𝛼)3 , the generalised butterfly with parameters 𝛼 and 𝛽 has differential uniformity 2 𝑛+1 . Proof: In order to bound the differential uniformity of V 𝛼,𝛽 , we must bound the number of solutions (𝑥, 𝑦) of the following system: { 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑

Lemma 4 2 +

 42 then applies. Clearly 𝑈 ̸ = 0 since the polynomial 𝑋 2 +𝑋 +1 has no root in F 2 𝑛 when 𝑛 is odd. Also, 𝑈 ̸ = 𝑉 , otherwise 𝑒 2 + 𝑒 + 1 = 1 which is not possible since the cases 𝑒 ∈ {0, 1} (i.e., 𝑎 = 0 or 𝑎 = 𝑏) have been excluded. Then, Equation[START_REF] Berlekamp | On the solution of algebraic equations over finite fields[END_REF] has two solutions only if Tr(𝑉 /𝑈 ) = 0. But, 𝑒 + 1) = Tr(1) = 1 , implying that Equation (21) has 0 or 4 solutions 𝑦 𝑖 , and each 𝑦 𝑖 leads to a unique value of 𝑥. Therefore, the whole system has either 0 or 4 solutions.

3 ,

 3 The left side is equal to 𝐿(𝑥, 𝑦) which we can re-write using the function 𝑡(𝑥, 𝑦) = (𝑥 + 𝛽𝑦 3 ) 1/3 as𝐿(𝑥, 𝑦) = ( (𝛼 2 + 1)𝑦 + 𝛼𝑡(𝑥, 𝑦) ) 3 + 𝛽 ( 𝑡(𝑥, 𝑦) + 𝛼𝑦 ) 3 ,which we expand into𝐿(𝑥, 𝑦) = 𝑡(𝑥, 𝑦) 3 (𝛼 3 + 𝛽) + 𝑦 3 ( (𝛼 2 + 1) 3 + 𝛼 3 ) + 𝑦𝑡(𝑥, 𝑦) 2 ( (𝛼 2 + 1)𝛼 2 + 𝛽𝛼 ) + 𝑦 2 𝑡(𝑥, 𝑦) ( (𝛼 2 + 1) 2 𝛼 + 𝛽𝛼 2 ) .

  3 + 1/𝛼} then the butterflies are APN, have a linearity equal to 2 𝑛+1 and the algebraic degree of H 𝛼,𝛽 is equal to 𝑛 + 1;• if 𝛽 = (1+𝛼)3 then the differential uniformity is equal to 2 𝑛+1 , the linearity is equal to 2 (3𝑛+1)/2 and the algebraic degree of H 𝛼,𝛽 is equal to 𝑛; • otherwise, the differential uniformity is equal to 4, the linearity is equal to 2 𝑛+1 and the algebraic degree of H 𝛼,𝛽 is either 𝑛 or 𝑛 + 1. It is equal to 𝑛 if and only if

  • If 𝑎𝑏(𝑎 + 𝑏) ̸ = 0. Then, the first line ℓ 1 of (19) can be replaced by𝑏ℓ 1 + (𝑎 + 𝑏)ℓ 2 , leading to { 𝑎𝑏(𝑎 + 𝑏)𝑥 + (𝑎𝑏 + 𝑎 2 + 𝑏 2 )𝑦 2 + (𝑎 3 + 𝑏 3 + 𝑎𝑏 2 )𝑦 = 𝜀 𝑏𝑥 2 + 𝑏 2 𝑥 + (𝑎 + 𝑏)𝑦 2 + (𝑎 + 𝑏) 2 𝑦 = 𝑑 ′ .(20)We now multiply the second line by 𝑎 2 𝑏(𝑎 + 𝑏)2 and replace 𝑎𝑏(𝑎 + 𝑏)𝑥 by the value given by the first line and get 𝜀 ′ = 𝑦 4 (𝑎𝑏 + 𝑎 2 + 𝑏 2 ) 2 + 𝑦 2 ( 𝑎 6 + 𝑏 6 + 𝑎𝑏 5 + 𝑎 5 𝑏 + 𝑎 3 𝑏 3 ) 𝑏 + 𝑎 5 𝑏 2 + 𝑎 4 𝑏 3 + 𝑎 3 𝑏 4 + 𝑎 2 𝑏 5 + 𝑎𝑏 6 ) .

	+ 𝑦	(	𝑎 6

  and 𝐴 2 = 0 if and only if 𝐴 4 = 2 𝑚-2 (2 𝑚 -1), i.e., 𝐵 = 0.

	𝑚+1 -2 -3𝐵	)	,
	leading to the result. Most notably, 𝐹 is APN, i.e. 𝐴 4 = 0 if
	and only if
	2 𝑚+1 -2 -3𝐵 = 0 ,

TABLE I :

 I Value of 𝐶, i.e., number of bent components divided by (2 3 -1), of all H 𝛼,𝛽 for 𝛼 and 𝛽 in F * 2 3 where F 2 3 is defined by the primitive element 𝑎 such that 𝑎 3 + 𝑎 + 1 = 0. Let 𝛼 and 𝛽 be two nonzero elements in F 2 𝑛 . The generalised open butterfly H 𝛼,𝛽 has an algebraic degree equal to 𝑛 or 𝑛 + 1. It is equal to 𝑛 if and only if

	𝛼∖𝛽	1	𝑎	𝑎 2	𝑎 3	𝑎 4	𝑎 5	𝑎 6
	1	0	4	4	4	4	4	4
	𝑎	6	2	0	2	6	0	0
	𝑎 3	2	4	2	0	2	4	2
	of any generalised butterfly of 2𝑛 variables does not exceed
	(𝑛 + 1). We now show that this upper bound is actually tight
	for almost all values of (𝛼, 𝛽).
	Theorem 5.

TABLE II :

 II Value of 𝐶, i.e., number of bent components divided by (2 5 -1), of all H 𝛼,𝛽 for 𝛼 and 𝛽 in F * 2 5 where F 2 5 is defined by the primitive element 𝑎 such that 𝑎 5 + 𝑎 2 + 1 = 0. 𝛼∖𝛽 1 𝑎 𝑎 2 𝑎 3 𝑎 4 𝑎 5 𝑎 6 𝑎 7 𝑎 8 𝑎 9 𝑎 10 𝑎 11 𝑎 12 𝑎 13 𝑎 14 𝑎 14 𝑎 16 𝑎 17 𝑎 18 𝑎 19 𝑎 20 𝑎 21 𝑎 22 𝑎 23 𝑎 24 𝑎 25 𝑎 26 𝑎 27 𝑎 28 𝑎 29 𝑎 30

	0	0 16 16 12 16 12 12 8 16 12 12 12 12 12	8	12 16 12 12	8	12 12 12 12 12	8	12 12	8	12 12
	1 12 10 12 12 8 10 12 10 10 12 10	8		12 10 12 10 14 12 10 12 10 14	0	14 10 12 10 12 14 10
	3 14 8 10 10 14 12 8 10 12 12 12 12 10	8	12 14 10 10	8	14 14	8	10 12 14	0	14 12 10	8	14
	5 14 0 10 10 12 12 0 12 12 10 10	0	14 10 14 12 12 10 14 14 12 12 12 12 14 14 10 12 12 14 10
	7 12 12 14 16 0 16 14 12 12 12 8	10 10 14 14 10	0	10 14 12 12 14 10	0	10 14 14 10 10	8	12
	11 8 16 14 16 8 14 12 14 10 10 10 10 10 10 14 12 14	8	16 14 16	8	0	14 12 10	0	10 12 14	0
	15 12 14 10 16 12 8 12 10 10 10 0	10 10 10 12	8	12 16 10 14 12 14 10 12	8	10 10	8	12 10 14

ACKNOWLEDGMENT

The work of Léo Perrin is supported by the CORE ACRYPT project (ID C12-15-4009992) funded by the Fonds National de la Recherche (Luxembourg).

The work of Léo Perrin is supported by the CORE ACRYPT project (ID C12-15-4009992) funded by the Fonds National de la Recherche (Luxembourg).