Christina Boura
email: christina.boura@uvsq.fr

Léo Perrin
email: leo.perrin@inria.fr

Shizhu Tian
email: shizhu.tian@inria.fr

Boomerang Uniformity of Popular S-box Constructions

Keywords: BCT, S-box, Feistel, MISTY, Lai-Massey

In order to study the resistance of a block cipher against boomerang attacks, a tool called the Boomerang Connectivity Table (BCT) for S-boxes was recently introduced. Very little is known today about the properties of this table especially for bijective S-boxes defined for n variables with n ≡ 0 mod 4. In this work we study the boomerang uniformity of some popular constructions used for building large S-boxes, e.g. for 8 variables, from smaller ones. We show that the BCTs of all the studied constructions have abnormally high values in some positions. This remark permits us in some cases to link the boomerang properties of an S-box with other well-known cryptanalytic techniques on such constructions while in other cases it leads to the discovery of new ones. A surprising outcome concerns notably the Feistel and MISTY networks. While these two structures are very similar, their boomerang uniformity can be very different.

Introduction

To evaluate the security level of a block cipher, cryptanalysts have designed multiple techniques that aim at searching for undesirable patterns. One such technique is the so-called differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] which looks for pairs (a, b) of input and output differences such that E k (x ⊕ a) ⊕ E k (x) = b, where E k is (a round-reduced version of) the studied block cipher.

Block ciphers-but also other symmetric primitives such as hash functions for example-are often built using the so-called S-boxes as the source of their non-linearity. These are small functions mapping n bits to m, specified by their lookup tables. Typical values of n and m would be n = m = 8 and n = m = 4. In order to study the resilience of a block cipher against differential attacks, we first study the differential properties of its S-boxes. To this end, a key tool is the Difference Distribution Table (DDT). It is a table defined for any function S : F n 2 → F m 2 which is of size 2 n × 2 m and such that δ S (a, b) = # {x ∈ F n 2 , S(x ⊕ a) ⊕ S(x) = b} for all a = 0. The maximal coefficient in the DDT of a function is called its differential uniformity and is denoted by δ S . If the S-boxes of a block cipher have a low differential uniformity, we can expect-and, depending on the properties of its diffusion layer, prove-that it does not have any high probability differential pattern.

Since its inception, many variants of the differential cryptanalysis have been designed. In particular, the boomerang attack [START_REF] Wagner | The boomerang attack[END_REF] considers both the encryption and the decryption functions at the same time by looking for pairs (a, b) such that

E k (x) = y E k (x ⊕ a) = y and E -1 k (y ⊕ b) = z E -1 k (y ⊕ b) = z ⊕ a
, where E k is the block cipher under consideration. In order to estimate the probability of such an event in an S-box-based block cipher, we need to use the DDT of its S-box. However, in order to properly take into account the coupling between the different encryptions, we also need to look at another table called the Boomerang Connectivity Table (BCT) introduced in [START_REF] Cid | Boomerang connectivity table: A new cryptanalysis tool[END_REF]. For a permutation S :

F n 2 → F n 2 , it is a 2 n × 2 n table of integers β S (a, b) defined as β S (a, b) = # x ∈ F n 2 , S -1 S(x) ⊕ b ⊕ S -1 S(x ⊕ a) ⊕ b = a .
The BCT coefficients are always equal to 2 n (the maximum) when a = 0 or b = 0. Thus, we define the boomerang uniformity of S, denoted β S , to be the maximum value of β S (a, b) for a = 0 and b = 0. As with the differential uniformity, the lower the boomerang uniformity the better. Note, that the boomerang uniformity could also be defined, by a slight modification, for non-bijective functions. However, for such functions the cryptographic interpretation of the property is not clear. As we are interested in this article in S-boxes used in practice, we only concentrate in the bijective case. Unlike the DDT, little is known about the BCT of even the most common cryptographic components. It is easy for example to prove (see e.g. [START_REF] Cid | Boomerang connectivity table: A new cryptanalysis tool[END_REF]) that for any function S, β S ≥ δ S and that for permutations S providing an optimal resistance to differential cryptanalysis, called Almost Perfect Nonlinear (APN) permutations, β S = δ S = 2. Then, Boura and Canteaut studied in [START_REF] Boura | On the boomerang uniformity of cryptographic sboxes[END_REF] the boomerang properties of the inverse mapping and of differentially 4-uniform quadratic power permutations of F 2 n . They showed that both families have an optimal boomerang uniformity when n ≡ 2 mod 4, where optimal means that the boomerang uniformity equals the differential uniformity and is 4 in both cases. However, besides these first results, determining the boomerang uniformity of other cryptographically relevant families of permutations or constructions remains an open problem.

In order to ease the implementation of their ciphers on constrained platforms, cryptographers often use specific block-cipher-like structures for their S-boxes. This technique permits the construction of large S-boxes from smaller, much cheaper ones. In this paper, we investigate the BCT of several such lightweight Sbox structures, notably the 3-round Feistel, Lai-Massey and (unbalanced) MISTY structures. These three classical constructions are depicted in Figures 1a,1b and 1c respectively. We then look at two 1-round structures: the 1-round SPN and the specific structure used in the FLY block cipher [START_REF] Karpman | The LITTLUN S-box and the FLY block cipher[END_REF]. For each of those structures, we derive a lower bound on the boomerang uniformity of S-boxes built using it. 1: The boomerang and differential uniformity of various 8-bit S-boxes. ( * ) The bound depends on the inner components of these constructions.

F 1 F 2 F 3 (a) 3-round Feistel.
Before going any further, we recall some basic properties of the BCT which were established in [START_REF] Boura | On the boomerang uniformity of cryptographic sboxes[END_REF][START_REF] Cid | Boomerang connectivity table: A new cryptanalysis tool[END_REF].

Proposition 1. Let S : F n 2 → F n 2
be a permutation. Then S has the same boomerang uniformity as S -1 and B•S•A, where A and B are affine permutations, and β S ≥ δ S . Furthermore, denote by S b the permutation

x → S -1 (S(x) ⊕ b). Then, β S (a, b) = # {x ∈ F n 2 , S b (x) ⊕ S b (x ⊕ a) = a} . (1)

3-round Feistel and Lai-Massey Networks

We study in this section the properties of the BCT of 3-round Feistel and Lai-Massey constructions and show that the boomerang uniformity of both is the worst one possible. The two proofs are similar and for this reason we provide here only the proof for the Lai-Massey one. In both cases, the results we derive are an inherent property of the structures used: even if the subcomponents are chosen so as to have excellent properties, the boomerang uniformity will be the worst possible.

The Feistel case

A popular way to construct large S-boxes from smaller ones is by using the Feistel construction. This scheme was used for constructing the 8-bit S-boxes of multiple ciphers including ZUC [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128[END_REF], and Scream [START_REF] Grosso | SCREAM & iSCREAM Side-Channel Resistant Authenticated Encryption with Masking[END_REF]. All use 3 rounds. This number of rounds is the smallest allowing the overall structure to have good properties. In particular, if only 2 are used, a part of the output depends linearly on a part of the input. A 3-round Feistel network has the worst possible boomerang uniformity, no matter the choice of the inner functions. Proposition 2 (whose proof will be given in the full version) formalizes this statement.

Proposition 2. Let S : F n 2 ×F m 2 → F n 2 ×F m
2 be a 3-round Feistel network and let F 1 , F 2 and F 3 be its inner functions as depicted in Fig. 1a, with

F 1 , F 3 : F m 2 → F n 2 and F 2 : F n 2 → F m 2 . Then, for any b ∈ F n 2 × F m 2 , β S (b, b) = β S = 2 n+m .
The property corresponding to Proposition 2 was known before. In fact, this property was recently used by Biryukov et al. for performing guess and determine attacks against Feistel networks [START_REF] Biryukov | Cryptanalysis of Feistel networks with secret round functions[END_REF]. We deduce that the knowledge of the BCT can help the cryptanalyst in contexts different from boomerang attacks. We discuss such applications later in Section 5.

The Lai-Massey case

We consider a variant of the structure depicted in Fig. 1b where the last application of the linear orthomorphism σ is removed for two reasons. First, the S-box of the cipher Fox is built in this way. Second, this version yields a simpler proof but, since σ is linear and since the boomerang uniformity is constant in an affine-equivalence class, the result still holds if the last σ is present.

Proposition 3. Let S : (F n 2 ) 2 → (F n 2 ) 2 be a 3-round Lai-Massey structure. Let F 1 , F 2 , F 3 : F n 2 → F n 2
be its inner functions and let σ be a linear permutation. For any nonzero a ∈ F n 2 , consider a 1 = (a, a) and b = (σ(a), σ(a)) ∈ (F n 2 ) 2 . Then,

β S (a 1 , b) = β S = 2 2n . F 1 σ F 2 σ F 3 σ(a) σ(a) F 3 σ -1 F 2 σ -1 F 1 ℓ0 r0 r1 ℓ1 r2 ℓ2 r3 ℓ3 r ′ 0 ℓ ′ 0 r ′ 1 r ′ 2 r ′ 3 ℓ ′ 1 ℓ ′ 2 ℓ ′ 3 S S -1
Fig. 2: The function S b (x) = S -1 (S(x, y) + b), where S is a 3-round Lai-Massey construction where the last application of σ is omitted.

Proof. Let b ∈ (F n 2 ) 2 be of the form b = (σ(a), σ(a)) ∈ (F n 2 ) 2
where a is nonzero. Furthermore, let S b be as defined in Eq. ( 1) (see Fig. 2). Our aim is to prove that

S b (x, y) + S b ((x, y) + (a, a)) = (a, a), for all (x, y) ∈ (F n 2 ) 2 . ( 2
)
The remainder of the proof consists in checking Eq. ( 2) by developing the expression of S b .

Begin with the input ( 0 , r 0 ) = (x, y) ∈ F 2n 2 and denote

A 1 (x, y) = A 1 = x + y, A 2 (x, y) = A 2 = σ(x) + y + F 1 (A 1 ) + σ(F 1 (A 1 )), A 3 (x, y) = A 3 = σ(σ(x + F 1 (A 1 )) + F 2 (A 2 )) + y + F 1 (A 1 ) + F 2 (A 2 ), T (x, y) = T = F 2 (A 2 ) + F 2 (A 2 + σ(a) + a), B 1 (x, y) = B 1 = A 1 + σ -1 (a) + σ(a) + T + σ -1 (T ).
The output ( i , r i ) of the i-th round, i = 1, 2, 3 of S, is detailed below:

( 1 , r 1 ) = (σ(x + F 1 (A 1 )), y + F 1 (A 1 )) , ( 2 , r 2 ) = (σ(σ(x + F 1 (A 1 )) + F 2 (A 2 )), y + F 1 (A 1 ) + F 2 (A 2 )) , ( 3 , r 3 ) = (σ(σ(x + F 1 (A 1 )) + F 2 (A 2 )) + F 3 (A 3 ), y + F 1 (A 1 ) + F 2 (A 2 ) + F 3 (A 3 )) .
Denote by ( 0 , r 0 ) = ( 3 , r 3 ) + (σ(a), σ(a)) the input of S -1 . Similarly, we have

( 1 , r 1 ) = (a + σ(x + F 1 (A 1 )) + F 2 (A 2 ), σ(a) + y + F 1 (A 1 ) + F 2 (A 2 )) , ( 2 , r 2 ) = σ -1 (a) + x + F 1 (A 1 ) + σ -1 (T ), σ(a) + y + F 1 (A 1 ) + T , ( 3 , r 3 ) = ((σ -1 (a) + x + F 1 (A 1 ) + F 1 (B 1 ) + σ -1 (T ), σ(a) + y + F 1 (A 1 ) + F 1 (B 1 ) + T ).
As A 1 (x + a, y + a) = A 1 (x, y) and A 2 (x + a, y + a) = A 2 (x, y) + σ(a) + a, it holds that T (x + a, y + a) = T (x, y) and B 1 (x + a, y + a) = B 1 (x, y). Therefore, Eq. ( 2) holds and we deduce the proposition.

BCTs of 3-round MISTY Networks

The MISTY network mimicks a structure used in the MISTY cipher [START_REF] Matsui | New block encryption algorithm MISTY[END_REF]. While it might ressemble a Feistel network it requires all three inner functions to be bijective in order for the whole function to be a permutation. As we will show, the MISTY structure also differs from the Feistel one via its BCT: the boomerang uniformity of a 3-round MISTY structure depends on the specifics of the subfunctions used.

Though the results are similar in both cases, the case where the branches are of the same size (balanced) and of different sizes (unbalanced) require different analyses which we provide in Sections 3.1 and 3.2 respectively.

3-round Balanced MISTY Networks

Proposition 4. Let S : (F n 2 ) 2 → (F n 2 ) 2 be a 3-round balanced MISTY network and let F 1 , F 2 and F 3 be its inner functions as depicted in Fig. 1c, with F 1 , F 2 , F 3 :

F n 2 → F n 2 bijective. Then, β S ≥ 2 n β F2 . F 1 F 2 F 3 b 1 b 1 F -1 3 F -1 2 F -1 1 S S -1
β S (a, b) = # {(x, y) ∈ F n 2 × F n 2 | S b (x, y) + S b (x + a 1 , y) = (a 1 , 0)}
, where S b is as depicted in Fig. 3. Since b = (b 1 , b 1 ), it can be simplified into

S b (x, y) = F -1 2 (F 2 (x) + b 1 ), F -1 1 (F -1 2 (F 2 (x) + b 1 ) + F 1 (y) + x) so we deduce S b (x, y) + S b (x + a 1 , y) = F -1 2 (F 2 (x) + b 1 ) + F -1 2 (F 2 (x + a 1 ) + b 1 ), F -1 1 F -1 2 (F 2 (x) + b 1 ) + F 1 (y) + x + F -1 1 F -1 2 (F 2 (x + a 1 ) + b 1 ) + F 1 (y) + x + a 1 . (3)
We now show that β S (a, b) = 2 n |A|, where

A = x ∈ F n 2 | F -1 2 (F 2 (x) + b 1 ) + F -1 2 (F 2 (x + a 1 ) + b 1 ) = a 1 .
For any x ∈ A, the right hand side of S b (x, y) + S b (x + a 1 , y) can be simplified:

F -1 1 F -1 2 (F 2 (x) + b 1 ) + F 1 (y) + x + F -1 1 F -1 2 (F 2 (x + a 1 ) + b 1 ) + F 1 (y) + x + a 1 = F -1 1 F -1 2 (F 2 (x) + b 1 ) + F 1 (y) + x + F -1 1 F -1 2 (F 2 (x) + b 1 ) + F 1 (y) + x = 0 .
As |A| = β F2 (a 1 , b 1 ) = β F2 , we conclude that the boomerang uniformity of a 3-round balanced MISTY network is lower bounded by 2 n β F2 .

Remark 1. We give here the minimal bounds for a 3-round MISTY network, for some popular choices of n. All functions F 1 , F 2 and F 3 are supposed bijective. n = 4 As proved in [START_REF] Boura | On the boomerang uniformity of cryptographic sboxes[END_REF], the minimal boomerang uniformity for a permutation of F 4 2 is 6. Therefore, by choosing F 2 , with β F2 = 6, we get that β S ≥ 96. As we will argue in Section 5 this is a high value for an 8-bit S-box. n = 3 APN permutations exist for n = 3. Using one as F 2 , we obtain β S ≥ 16.

Proposition 5. Let S : (F n 2 ) 2 → (F n 2 ) 2 be a 3-round MISTY network with inner functions F 1 , F 2 and F 3 . If F 1 or F 3 is an affine permutation, then β S = 2 2n .
The proof of this proposition will be given in the full version of this paper.

3-round Unbalanced MISTY Networks

In practice, all known MISTY constructions are unbalanced. More specifically, they use branches of n -1 and n + 1 bits. This is the case for the original MISTY1 cipher [START_REF] Matsui | New block encryption algorithm MISTY[END_REF], where some inner components follow a 3-round construction with one 7-bit and one 9-bit branch. It is also the case of the 8-bit S-box of Fantomas [START_REF] Grosso | LS-designs: Bitslice encryption for efficient masked software implementations[END_REF], where a 3-bit and a 5-bit branch are used. One reason for this is that an unbalanced 3-round MISTY structure can potentially achieve a better differential uniformity than a balanced one. For example, Canteaut et al. showed in [START_REF] Canteaut | Construction of lightweight S-boxes using Feistel and MISTY structures[END_REF] that for n = 4, a 2n-bit permutation S following a balanced MISTY structure has δ S ≥ 16, while by taking a 3-bit and a 5-bit branch it is possible to find a permutation S with δ S = 8. Another reason is that taking branches of an odd length of bits permits to use APN permutations for the inner components-as was indeed done in MISTY1.

We studied the boomerang uniformity of 3-round unbalanced MISTY networks. Our arguments differ slightly depending on whether the widest branch is on the left or on the right. Let m be the size of the smallest branch and n the size of the biggest one. If S 1 is the construction with F 2 applying to the smallest branch and S 2 is the other one then we get that

β S1 ≥ 2 n β F2 and β S2 ≥ 2 m β F2| F m 2 .
Both proofs will appear in an extended version of this abstract.

Non-iterative constructions

Until now, we have only considered 3-round constructions. However, S-box designers sometimes choose non-iterative structures. In this section, we look at 1-round SPN (as used e.g. in Midori [START_REF] Banik | Midori: A block cipher for low energy[END_REF]) and at the ad hoc Lai-Massey like structure used by the Littlun S-Box of the block cipher FLY [START_REF] Karpman | The LITTLUN S-box and the FLY block cipher[END_REF]. It is composed of a single Lai-Massey round followed by an S-box layer (see Fig. 4a). While Littlun is such that F 1 = F 2 = F 3 , we do not make this assumption.

The following straightforward proposition deals with the properties of a 1-round SPN. Proposition 6. Let F 1 , F 2 be n-bit permutations and let S : (F n 2 ) 2 → (F n 2 ) 2 be such that S(x 1 , x 2 ) = (F 1 (x 1 ), F 2 (x 2 )). Then we have Let us now consider the Littlun construction. If F 1 is an affine permutation, then the corresponding Littlun-like S-box is a 1-round SPN structure which has thus the worst possible boomerang uniformity. If not, the following proposition relates its boomerang uniformity to that of its subcomponents. Proposition 7. Let S be a generalised-Littlun structure with n-bit permutations F 1 , F 2 and F 3 (see Fig. 4a). Then β S ≥ 2 n max{β F2 , β F3 }.

β S ((a 1 , a 2 ), (b 1 , b 2 )) = β F1 (a 1 , b 1 ) × β F2 (a 2 , b 2 ) , so that in particular β S = β S ((a, 0), (0, b)) = 2 2n . F 1 F 2 F 3 (a) Littlun S-box. F 1 F 2 F 3 b 2 b 1 F -1 3 F -1 2 F 1 S S -1 (
Proof. We define the two following functions H and G over (F n 2 ) 2 :

H(x, y) = (x + F 1 (x + y), y + F 1 (x + y)) and G(x, y) = (F 2 (x), F 3 (y)) .
Both H and G are permutations of (F n 2 ) 2 , H is an involution, and

S(x, y) = (G • H)(x, y). we claim that β S (a, b) ≥ β G (a, b), for a = (a 1 , a 1 ), a 1 = 0 and b = (b 1 , b 2 ). Indeed, β S (a, b) = # X ∈ (F n 2 ) 2 | H(G -1 (G(H(X) + a) + b)) + H(G -1 (G(H(X) + b))) = a = # Y ∈ (F n 2 ) 2 | H(G -1 (G(Y + a) + b)) + H(G -1 (G(Y ) + b)) = a = # Y ∈ (F n 2 ) 2 | H(G -1 (G(Y ) + b) + G -1 (G(Y ) + b)) +G -1 (G(Y + a) + b)) + H(G -1 (G(Y ) + b)) = a ≥ # Y ∈ (F n 2 ) 2 | G -1 (G(Y ) + b) + G -1 (G(Y + a) + b) = a = β G (a, b) . By applying Proposition 6 to β G (a, b) with a = (a 1 , a 1 ), b (b 1 , b 2 ), we obtain that β S (a, b) = 2 n β F2 (a 1 , b 1 ) when b 2 = 0 and β S (a, b) = 2 n β F2 (a 1 , b 2 ) when b 1 = 0. We deduce that β S ≥ 2 n max(β F2 , β F3 ).

Conclusion

Our results on the BCT and on the boomerang uniformity of permutations with various structures have several consequences. First, by the fact that β S = 2 if and only if S is APN, we can immediately see that 3-round Feistel, Lai-Massey and MISTY structures can never be APN.

As mentioned in Section 2.1, the consequences in terms of cryptanalysis can also extend further than boomerang attacks. The guess and determine of Biryukov et al. [START_REF] Biryukov | Cryptanalysis of Feistel networks with secret round functions[END_REF] uses a property equivalent to the fact that the boomerang uniformity of a 3-round Feistel network is always maximal. We can therefore expect the same attack to work against Lai-Massey structures. Interestingly, our results show that it is possible to construct a 3-round MISTY structure immune against the existence of such probability 1 patterns, meaning that they seem to offer some inherent resilience against these attacks. Not only are our results regarding Feistel and Lai-Massey structures very similar, the arguments we used to derive them are also very close-independently of the choice of the linear mapping σ. While the similarity between these two structures makes intuitive sense, we find it interesting to see it displayed in such a clear manner.

We have encountered several cases: for 3-round Lai-Massey, 3-round Feistel and 1-round SPN, the boomerang uniformity is maximal regardless of the subcomponents used. In the 3-round MISTY case, the boomerang uniformity is bounded by the differential uniformity of its subfunction and, in the Littlun case, it is bounded by the boomerang uniformity of its subfunction.

Finally, another application of our results lies in S-box reverse-engineering [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF]. In this context, the aim is to recover the hidden structure of an S-box using only its lookup table. If an S-box has non-trivial differential and linear properties but a boomerang uniformity equal to 2 n then we can suspect that it is a 3-round Lai-Massey or Feistel structure. Since the boomerang uniformity is preserved under the composition with an affine permutation, this test would work even if the S-box structure is obfuscated by such permutations-as is the case for instance in the S-box of ZUC [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128[END_REF].

We generated 1000 different permutations for various block sizes n and obtained averages of A n with A 4 = 11.9, A 6 = 16.5, A 8 = 20.3, A 10 = 24.0 . This shows that a maximal boomerang uniformity is an extremely rare event indicative of a very strong structure. In fact, the non-maximal but still very high boomerang uniformity of the 3-round MISTY and Littlun structures can also be leveraged to identify such potentially hidden structures.

  3-round Lai-Massey.

  3-round MISTY.

Fig. 1 :

 1 Fig. 1: The structures investigated in this paper.

Fig. 3 :

 3 Fig. 3: The function S b (x) = S -1 (S(x) + b), for x ∈ F n 2 × F n 2 and b = (b1, b1) where S is a 3-round balanced MISTY structure.

  b) The function S (x) = S -1 (S(x, y) + b), where S is the Littlun S-box.

Fig. 4 :

 4 Fig. 4: Analysis of the Littlun structure

  Table 1 presents the differential and boomerang uniformity of several S-boxes from the literature. It also contains the lower bounds derived in this paper.

	Rounds	S-box Struct.	Cipher	Ref.	δS	βS	Lower bound
		Feistel	Scream	[6, 11]	8	256	256
	3	MISTY-like	Fantomas	[10]	16	160	64 ( * )
		Lai-Massey	Fox	[14]	16	256	256
	1	SPN Lai-Massey-like	Midori FLY	[1] [12]	64 16	256 256	256 256 ( * )
	Table


Anne Canteaut

Léo Perrin

Shizhu Tian

If a Generalised Butterfly is APN then it Operates on 6 Bits

Keywords: Boolean function, Sbox, APN, Differential uniformity, Butterflies

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bit is the so-called Big APN Problem. It has been solved in the 6-bit case by Dillon et al. in 2009 but, since then, the general case has remained an open problem. In 2016, Perrin et al. discovered the butterfly structure which contains Dillon et al.'s permutation over F 2 6 . Later, Canteaut et al. generalised this structure and proved that no other butterflies with exponent 3 can be APN. Recently, Yongqiang et al. further generalized the structure with Gold exponent and obtained more differentially 4-uniform permutations with the optimal nonlinearity. However, the existence of more APN permutations in their generalization was left as an open problem.

In this paper, we adapt the proof technique of Canteaut et al. to handle all Gold exponents and prove that a generalised butterfly with Gold exponents over F 2 2𝑛 can never be APN when 𝑛 > 3. More precisely, we prove that such a generalised butterfly being APN implies that the branch size is strictly smaller than 5. Hence, the only APN butterflies operate on 3-bit branches, i.e. on 6 bits in total.

Introduction

S(ubstitution)-boxes are core components in symmetric ciphers where they serve as the confusion part. In most cases, they are their only nonlinear components. In order for the algorithm to resist the two most prominent cryptanalysis techniques, namely differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] and linear attacks [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], S-boxes should have a low differential uniformity [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF] and a high nonlinearity [START_REF] Chabaud | Links between differential and linear cryptanalysis[END_REF].

Let 𝐹 be a function from F 𝑚 2 into F 𝑚 2 . We say that 𝐹 is differentially 𝛿-uniform if, for any nonzero 𝑎 in F 𝑚 2 and 𝑏 ∈ F 𝑚 2 , the equation 𝐹 (𝑥) + 𝐹 (𝑥 + 𝑎) = 𝑏 has at most 𝛿 solutions in F 𝑚 2 . The lower bound for functions on F 𝑚 2 is 2, and the functions that achieve this bound are called Almost Perfect Nonlinear (APN) [START_REF] Nyberg | Provable security against differential cryptanalysis (rump session)[END_REF]. That is, a function 𝐹 : F 𝑚 2 → F 𝑚 2 is APN if the following equation has at most two solutions: 𝐹 (𝑥) + 𝐹 (𝑥 + 𝑎) = 𝑏 for any 𝑏 ∈ F 𝑚 2 and any 𝑎 ∈ F 𝑚 2 such that 𝑎 ̸ = 0. An APN permutation over F 𝑚 2 would be an S-box providing optimal protection against differential attacks. Such components are easy to find for 𝑚 odd: the Gold functions 𝑥 ↦ → 𝑥 2 𝑖 +1 and the inverse mapping 𝑥 ↦ → 𝑥 2 𝑚 -2 , which are defined by identifying F 2 𝑚 with F 𝑚 2 , are APN permutations in this case. However, the very existence of APN permutations operating on an even number of bits is an open problem nicknamed the big APN problem.

Open Problem 1 (Big APN Problem). Is there an APN permutation of F 2 𝑚 where 𝑚 = 2𝑛? It has been an open problem in the field of vectorial Boolean functions since Nyberg introduced the differential uniformity in the early 90's [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF].

Some negative results are known. For instance, Hou proved in [START_REF] Hou | Affinity of permutations of F 2 𝑛[END_REF] that there are no APN permutations over F 2 4 and that there are no APN permutations over F 2 2𝑛 with coefficients in F 2 𝑛 . Also, an APN permutation over F 2 2𝑛 cannot neither be a monomial function nor a quadratic function [START_REF] Thierry | On almost perfect nonlinear functions over F 𝑛 2[END_REF].

The only known solution to this problem is a sporadic case found by Dillon et al. [START_REF] Browning | An APN permutation in dimension six[END_REF] for 𝑚 = 6. At the time of writing, it remains the only known APN permutation over F 2 2𝑛 . This solution was constructed by finding a permutation in the CCZ-equivalence class of a known quadratic APN function, namely the Kim mapping 𝑥 ↦ → 𝑥 3 + 𝑥 10 + 𝑔𝑥 24 where 𝑔 is a root of the primitive polynomial used to define F 2 6 .

To try and use a similar approach, Yu et al. [START_REF] Yu | A matrix approach for constructing quadratic APN functions[END_REF] designed a new matrix-based method to generate quadratic APN functions. They obtained 8157 new quadratic APN functions over F 2 8 . However, none of these APN functions are CCZ-equivalent to permutations.

In [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF], Perrin et al. identified a specific structure called Open Butterfly which is affineequivalent to Dillon et al.'s permutation. This structure is easily defined over higher dimensions, but, unfortunately, Canteaut et al. [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF] proved that an even broader family of permutations containing the butterflies of Perrin et al. did not contain any APN permutations for 𝑚 > 6.

Several teams then studied other generalizations of the original butterfly of [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF]. Firstly, it was shown in [START_REF] Fu | Differentially 4-uniform permutations with the best known nonlinearity from butterflies[END_REF] that changing the exponent from 3 to 2 𝑖 + 1 in the construction of Perrin et al. still yielded differentially 4-uniform permutations. Then, Li et al. showed that the generalization of Canteaut et al. had the same properties [START_REF] Li | On the generalization of butterfly structure[END_REF], and that this family of generalised butterflies contains some functions which are not CCZ-equivalent to the functions studied in [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF]. In each case, the authors established that such generalizations have a differential uniformity at most equal to 4 except in some sporadic cases but they left the existence of APN permutations among them as an open problem. In this paper, we answer this question by proving the following theorem.

Theorem 1. If a generalised butterfly is APN then it operates on 6 bits.

In other words, natural quadratic generalizations of the initial structure of Perrin et al. do not provide any new solutions to the big APN problem.

The remainder of the paper is our proof of this theorem. First, we formally describe generalized butterflies and some of their basic properties in Section 2. Then, in Section 3, we present some useful propositions, both new ones and from the literature, which will be used further in the paper. Our proof then operates in two high level steps. In Section 4, we establish a necessary criterion for a butterfly to be APN which we call the refined trace condition. Then, in Section 5, we show that this condition implies that the block size is upperbounded by 6 so that Theorem 1 holds.

Generalised Butterflies

In this section, we formally define the generalisation of the butterfly structure we consider in this paper and establish some of its most basic properties.

Definition

In the remainder of the paper, we consider an even integer 𝑚 = 2𝑛 which is not divisible by 4, i.e., 𝑛 is always odd. Also, vectorial Boolean 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.

We now define the family of vectorial functions that will be studied in the paper.

Definition 1 (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 𝑅 .

Figure 1: The butterfly constructions.

It can be easily checked that, for any choice of the keyed permutation 𝑅, the open butterfly H 𝑅 is an involution and, as such, a permutation.

Several particular cases of this structure have been presented in the literature. They consist in iterative generalizations of the first butterfly structure which was introduced in [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF].

• In [START_REF] Perrin | Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem[END_REF], Perrin et al. found that Dillon et al.'s permutation is affine equivalent to H 𝑅 with 𝑅 𝑦 (𝑥) = (𝑥 + 𝛼𝑦) 3 + 𝑦 3 , for 𝑛 = 3, where Tr (𝛼) = 0. They showed that such structures always have algebraic degree 𝑛 + 1 and a differential uniformity at most equal to 4 whenever 𝛼 ̸ = 0 and 𝑛 is odd. However, they left their nonlinearity as an open problem along with the existence of APN permutations for 𝑛 > 3 among them.

• Canteaut et al. [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF] considered the broader class of polynomials 𝑅 𝑦 (𝑥) = (𝑥 + 𝛼𝑦) 3 + 𝛽𝑦 3 which, up to equivalence, contains all 𝑅 of degree 3 such that 𝑅 𝑦 is always a permutation. They showed that it was always differentially 4 (except for some sporadic cases) and that it could only be APN when 𝑛 = 3. They also showed that the nonlinearity of butterflies was always equal to the best known one (except for some sporadic cases). Their results are trivially generalized to exponents of the form 3 × 2 𝑖 .

• Fu et al. [START_REF] Fu | Differentially 4-uniform permutations with the best known nonlinearity from butterflies[END_REF] instead chose to look at different exponents, i.e. at 𝑅 𝑦 = (𝑥 + 𝛼𝑦) 2 𝑖 +1 + 𝑦 2 𝑖 +1 with gcd(𝑖, 𝑛) = 1. They showed that, again, such structures were always differentially 4-uniform and always have the best nonlinearity known to be possible. They also proved that the closed butterfly with 𝛼 = 1 was always a permutation.

• Li et al. [START_REF] Li | On the generalization of butterfly structure[END_REF] investigated the broadest class of butterflies, namely those with 𝑅 𝑦 = (𝑥 + 𝛼𝑦) 2 𝑖 +1 + 𝛽𝑦 2 𝑖 +1 with gcd(𝑖, 𝑛) = 1. They showed that, except in some sporadic cases, the nonlinearity of such constructions was the best known to be possible and the differential uniformity was at most 4. However, they left the existence of APN functions among them as an open problem.

In this paper, we focus on the broadest definition, i.e. on the case where

𝑅 𝑦 = (𝑥 + 𝛼𝑦) 2 𝑖 +1 + 𝛽𝑦 2 𝑖 +1
with gcd(𝑖, 𝑛) = 1. As Li et al. already proved that such structures yield the best known nonlinearity and differential uniformity, we focus only on whether they can be APN or not.

Equivalence Relations

To begin with, we recall some basic notations of equivalence relations among vectorial Boolean functions. Two functions

𝐹 1 , 𝐹 2 from F 𝑚 2 into F 𝑚 2 are E(xtended) A(ffine)-equivalent if there exist two affine permutations 𝐴 1 , 𝐴 2 from F 𝑚 2 into F 𝑚 2 and an affine function 𝐴 3 from F 𝑚 2 into F 𝑚 2 such that 𝐹 1 (𝑥) = 𝐴 1 (𝐹 2 (𝐴 2 (𝑥))) + 𝐴 3 (𝑥) .
A more general framework is introduced by considering the graphs of the functions [START_REF] Carlet | Codes, bent functions and permutations suitable for DES-like cryptosystems[END_REF]. Two functions 𝐹 1 , 𝐹 2 from F 𝑚 2 into F 𝑚 2 are called CCZ-equivalent (after Carlet, Charpin and Zinoviev) if there exists an affine permutation ℒ over F 2𝑚 2 such that

ℒ ({ (𝑥, 𝐹 1 (𝑥)), ∀𝑥 ∈ F 𝑚 2 }) = { (𝑥, 𝐹 2 (𝑥)), ∀𝑥 ∈ F 𝑚 2 }
Both the differential uniformity and the nonlinearity are invariant under both EA-equivalence and CCZ-equivalence. In particular, all functions CCZ-equivalent to an APN function are APN themselves.

As in the case studied in [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF], the generalised butterflies with 𝑅 𝑦 (𝑥) = (𝑥 + 𝛼𝑦) 2 𝑖 +1 + 𝛽𝑦 2 𝑖 +1 are linked by the following relations.

• If the exponent is equal to 𝑒 = (2 𝑖 + 1) × 2 𝑡 , the corresponding closed butterfly is affineequivalent to the closed butterfly with 𝑒 = 2 𝑖 + 1 and the same 𝛼, 𝛽. Therefore, all results presented in the paper also hold when

𝑅(𝑥, 𝑦) = (𝑥 + 𝛼𝑦) (2 𝑖 +1)×2 𝑡 + 𝛽𝑦 (2 𝑖 +1)×2 𝑡
for some 𝑡.

• The closed butterflies V 𝛼,𝛽 and V 𝛼 2 ,𝛽 2 are affine-equivalent as

V 𝛼 2 ,𝛽 2 (𝑥 2 , 𝑦 2 ) = (V 𝛼,𝛽 (𝑥, 𝑦)) 2 .
• For any 𝛼 ̸ = 1, the closed butterflies V 𝛼,𝛽 and

V 𝛼,𝛽 ′ with 𝛽 ′ = 𝛽 -1 (1 + 𝛼) 2(2 𝑖 +1) are affine- equivalent.
This equivalence is obtained by composing V 𝛼,𝛽 with the inverse of the linear permutation

𝐿 : (𝑥, 𝑦) ↦ → (𝑧 1 , 𝑧 2 ) = (𝛼𝑥 + 𝑦, 𝑥 + 𝛼𝑦) .
Indeed,

V 𝛼,𝛽 ∘ 𝐿 -1 (𝑥, 𝑦) = ( 𝑧 2 𝑖 +1 2 + 𝛽 [ (1 + 𝛼) -2 (𝑧 1 + 𝛼𝑧 2 ) ] 2 𝑖 +1 , 𝑧 2 𝑖 +1 1 + 𝛽 [ (1 + 𝛼) -2 (𝑧 2 + 𝛼𝑧 1 ) ] 2 𝑖 +1 ) = ( (1 + 𝛼) -2(2 𝑖 +1) [ (𝑧 1 + 𝛼𝑧 2 ) 2 𝑖 +1 + 𝛽 ′ 𝑧 2 𝑖 +1 2 ] , (1 + 𝛼) -2(2 𝑖 +1) [ (𝑧 2 + 𝛼𝑧 1 ) 2 𝑖 +1 + 𝛽 ′ 𝑧 2 𝑖 +1 1 ]) .

Useful Results

Several steps of our reasoning require counting the number of solutions of an equation. The following two propositions allow us to predict this number for two simple equations.

The first is a well known result established by Helleseth and Kholosha in 2008.

Proposition 1. (Theorem 1 in [START_REF] Helleseth | On the equation 𝑥 2 𝑙 +1 + 𝑥 + 𝑎 = 0 over 𝐺𝐹 (2 𝑘 )[END_REF]). Let 𝑛 be odd and 𝑖 be such that 𝑖 < 𝑛 and gcd(𝑖, 𝑛) = 1.

Let 𝒮 𝑘 for any integer 𝑘 be defined as

𝒮 𝑘 = {𝑎 ̸ = 0, 𝑥 2 𝑖 +1 + 𝑥 = 𝑎 ℎ𝑎𝑠 𝑒𝑥𝑎𝑐𝑡𝑙𝑦 𝑘 𝑠𝑜𝑙𝑢𝑡𝑖𝑜𝑛𝑠}
Then 𝒮 𝑘 is empty unless 𝑘 ∈ {0, 1, 3} and the non-empty ones have the following sizes:

|𝒮 0 | = 2 𝑛 + 1 3 |𝒮 1 | = 2 𝑛-1 -1 |𝒮 3 | = 2 𝑛-1 -1 3 . Furthermore, if 𝑥 is such that 𝑥 2 𝑖 +1 + 𝑥 + 𝑎 = 0 then 𝑥 2 𝑖 +1 + 𝑥 + 𝑎 = 0 has exactly 1 solution if and only if Tr ( (1 + 𝑥 -1 ) 𝜏 ) = 1 where 𝜏 (2 𝑖 -1) ≡ 1 mod (2 𝑛 -1).
The second proposition is an adaptation of Lemma 4 of [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF] to the case where the exponents are 2 𝑖 and 2 2𝑖 rather than 2 and 4 respectively. • 0 or 2 solutions otherwise, that is if one of the following is true:

-𝑈 = 0, 𝑉 ̸ = 0, -𝑈 ̸ = 0 and 𝑉 = 𝑈 , -𝑈 ̸ = 0 and Tr (( 1 + 𝑉 𝑈 ) 𝜏 ) = 1,
where 𝜏 (2 𝑖 -1) ≡ 1 mod (2 𝑛 -1).

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

𝑈 𝑧 2 2𝑖 + 𝑉 𝑧 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. We consider each case separately.

• 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, 𝑉 ̸ = 0 then the equation corresponds to 𝑉 𝑧(𝑧 2 𝑖 -1 + 1) = 0, implying that it has 2 solutions since gcd(𝑖, 𝑛) = 1.

• Let us now suppose that 𝑈 ̸ = 0. In this case, we can rewrite the equation as

𝑈 𝑧(𝑧 2 𝑖 -1 + 1) ( 1 + 𝑉 /𝑈 + (𝑧 2 𝑖 + 𝑧) 2 𝑖 -1 ) = 0.
Both 𝑧 = 0 and 𝑧 = 1 are obviously solutions. In fact, they are the only ones if 𝑉 = 𝑈 so that the equation has 0 or 2 solutions in this case. Let us now suppose that 𝑉 ̸ = 𝑈 . In this case, the equation

( 1 + 𝑉 /𝑈 + (𝑧 2 𝑖 + 𝑧) 2 𝑖 -1
) = 0 can be rewritten as Finally, an a priori complex trace will appear further in this paper. The following lemma establishes that it is in fact constant.

𝑧 2 𝑖 + 𝑧 + ( 1 + 𝑉 𝑈 ) 𝜏 = 0.
Lemma 1. Let 𝑛 be an odd integer and 𝑖 < 𝑛 with gcd(𝑖, 𝑛) = 1. For any 𝛼, 𝛽 ∈ F * 2 𝑛 , we define

ℬ 𝛼,𝛽 = (𝛼 + 𝛼 2 𝑖+1 -1 ) 2 𝑖 -1 × 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖+1 -1 + 𝛼 2 𝑖 𝛽 𝛼 2 2𝑖+1 +2 𝑖 + 𝛼 2 𝑖 + 𝛼 2 2𝑖 𝛽 2 𝑖 .
Then, for all 𝛼, 𝛽 ̸ = 0, we have that Tr

( ℬ 𝜏 𝛼,𝛽 ) = 0 where 𝜏 (2 𝑖 -1) ≡ 1 mod (2 𝑛 -1).
Proof. We note that ℬ 𝛼,𝛽 is equal to

ℬ 𝛼,𝛽 = (𝛼 + 𝛼 2 𝑖+1 -1 ) 2 𝑖 -1 × 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖+1 -1 + 𝛼 2 𝑖 𝛽 𝛼 2 2𝑖+1 +2 𝑖 + 𝛼 2 𝑖 + 𝛼 2 2𝑖 𝛽 2 𝑖 = (𝛼 + 𝛼 2 𝑖+1 -1 ) 2 𝑖 -1 𝛼 2 𝑖 ( 𝛼 2 𝑖 +1 + 𝛼 2 𝑖 -1 + 𝛽 ) 𝛼 2 2𝑖 ( 𝛼 2 2𝑖 +2 𝑖 + 𝛼 2 𝑖 -2 2𝑖 + 𝛽 2 𝑖 ) = ( 𝛼 + 𝛼 2 𝑖+1 -1 𝛼 2 𝑖 ) 2 𝑖 -1 𝛼 2 𝑖 +1 + 𝛼 2 𝑖 -1 + 𝛽 ( 𝛼 2 𝑖 +1 + 𝛼 1-2 𝑖 + 𝛽 ) 2 𝑖 = ( 𝛼 1-2 𝑖 + 𝛼 2 𝑖 -1 ) 2 𝑖 -1 𝛼 2 𝑖 +1 + 𝛼 2 𝑖 -1 + 𝛽 ( 𝛼 2 𝑖 +1 + 𝛼 1-2 𝑖 + 𝛽 ) 2 𝑖 ,
which we simplify using

𝜆 𝛼 = 𝛼 2 𝑖 -1 + 𝛼 1-2 𝑖 and 𝑄 𝛼 (𝛽) = 𝛼 2 𝑖 +1 + 𝛼 1-2 𝑖 + 𝛽 by writing ℬ 𝛼,𝛽 = 𝜆 2 𝑖 -1 𝛼 × 𝜆 𝛼 + 𝑄 𝛼 (𝛽) 𝑄 𝛼 (𝛽) 2 𝑖 = ( 𝜆 𝛼 𝑄 𝛼 (𝛽) ) 2 𝑖 + ( 𝜆 𝛼 𝑄 𝛼 (𝛽) ) 2 𝑖 -1
.

The trace of (

(1 + 𝑞) 2 𝑖 + (1 + 𝑞) 2 𝑖 -1
) 𝜏 is equal to 0 for any 𝑞. Indeed, we have

(1 + 𝑞) 2 𝑖 + (1 + 𝑞) 2 𝑖 -1 = (1 + 𝑞) 2 𝑖 +1 + (1 + 𝑞) 2 𝑖 1 + 𝑞 = 𝑞 2 𝑖 +1 + 𝑞 1 + 𝑞 = 𝑞(𝑞 + 1) 2 𝑖 -1 ,
from which we deduce that

( (1 + 𝑞) 2 𝑖 + (1 + 𝑞) 2 𝑖 -1 ) 𝜏 = 𝑞 𝜏 (1 + 𝑞) = 𝑞 𝜏 + 𝑞 𝜏 +1 .
We note that 2 𝑖 𝜏 ≡ 𝜏 + 1 mod (2 𝑛 -1) and deduce that

Tr (( (1 + 𝑞) 2 𝑖 + (1 + 𝑞) 2 𝑖 -1 ) 𝜏 ) = Tr ( 𝑞 𝜏 + 𝑞 2 𝑖 𝜏 ) = 0 .
As a consequence, since

Tr ( ℬ 𝜏 𝛼,𝛽 ) = Tr (( ( 𝜆 𝛼 𝑄 𝛼 (𝛽) ) 2 𝑖 + ( 𝜆 𝛼 𝑄 𝛼 (𝛽) ) 2 𝑖 -1 ) 𝜏 ) , we have that Tr ( ℬ 𝜏 𝛼,𝛽
) = 0 for any 𝛼, 𝛽 ̸ = 0.

4 Necessary Condition for a Generalized Butterfly to be APN

We first show that, in order for a generalized butterfly to be APN, it is necessary that 𝛽 takes some very specific values.

Proposition 3 (Condition on 𝛽). Let 𝑛 > 1 be an odd integer, (𝛼, 𝛽) be a pair of nonzero elements in F 2 𝑛 and 𝑖 > 0 be an integer such that gcd(𝑖, 𝑛) = 1. If the generalised butterfly with parameters 𝛼, 𝛽 and exponent 2 𝑖 + 1 is APN then

𝛽 ∈ { (𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 ), (𝛼 -2 𝑖 +1 + 𝛼 2 𝑖 +1 ) } .
Proof. In order to bound the differential uniformity of V 𝛼,𝛽 , we must bound the number of solutions (𝑥, 𝑦) of the following system: and

𝑅(𝑦, 𝑥) + 𝑅(𝑦, 𝑥 + 𝑎) = (𝛼𝑎) 2 𝑖 (𝑦 + 𝛼𝑥) + (𝛼𝑎)(𝑦 + 𝛼𝑥) 2 𝑖 + (𝛼𝑎) 2 𝑖 +1 + 𝛽 ( 𝑎 2 𝑖 𝑥 + 𝑎𝑥 2 𝑖 + 𝑎 2 𝑖 +1 )
so that the original system can be re-written into

{ 𝑎𝑥 2 𝑖 + 𝑎 2 𝑖 𝑥 + 𝛼 2 𝑖 𝑎𝑦 2 𝑖 + 𝛼𝑎 2 𝑖 𝑦 = 𝑐 ′ (𝛼 2 𝑖 +1 𝑎 + 𝑎𝛽)𝑥 2 𝑖 + (𝛼 2 𝑖 +1 𝑎 2 𝑖 + 𝑎 2 𝑖 𝛽)𝑥 + 𝛼𝑎𝑦 2 𝑖 + 𝛼 2 𝑖 𝑎 2 𝑖 𝑦 = 𝑑 ′ . (1)
By summing the first equation and the second one multiplied by 𝛼 2 𝑖 -1 , we get that

𝑦𝑎 2 𝑖 (𝛼 + 𝛼 2 𝑖+1 -1 ) = (𝛼 2 𝑖+1 𝑎 + 𝑎 + 𝛼 2 𝑖 -1 𝑎𝛽)(𝑥 2 𝑖 + 𝑎 2 𝑖 -1 𝑥) + 𝑔
for some constant 𝑔. If 𝛼 = 1 then the corresponding open butterfly is functionally equivalent to a 3-round Feistel network (see [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF]). Thus, we can use the results of [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF] to deduce that the differential uniformity in this case is at least equal to 4 and thus that the corresponding butterflies are not APN. We thus assume that 𝛼 ̸ = 1. In this case, we replace 𝑦 by its value

𝑦 = (1 + 𝛼 2 𝑖+1 + 𝛼 2 𝑖 -1 𝛽) 𝑎 2 𝑖 -1 (𝛼 + 𝛼 2 𝑖+1 -1 ) (𝑥 2 𝑖 + 𝑎 2 𝑖 -1 𝑥) + 𝑔 ′
in the first equation of System (1). We get

𝛼 2 𝑖 𝑎𝜇 2 𝑖 𝑥 2 2𝑖 + [ 𝑎 + 𝛼 2 𝑖 𝑎 2 2𝑖 -2 𝑖 +1 𝜇 2 𝑖 + 𝛼𝑎 2 𝑖 𝜇 ] 𝑥 2 𝑖 + [ 𝑎 2 𝑖 + 𝛼𝑎 2 𝑖+1 -1 𝜇 ] 𝑥 = 𝑐 ′′ ,
where

𝜇 = (1 + 𝛼 2 𝑖+1 + 𝛼 2 𝑖 -1 𝛽) 𝑎 2 𝑖 -1 (𝛼 + 𝛼 2 𝑖+1 -1
) .

Using the substitution 𝑥 = 𝑎𝑥 ′ , we obtain that

𝑈 𝑥 ′2 2𝑖 + 𝑉 𝑥 ′2 𝑖 + (𝑈 + 𝑉 )𝑥 ′ = 𝑐 ′′ (2)
with

𝑈 = 𝛼 2 𝑖 𝑎 2 2𝑖 +1 𝜇 2 𝑖 and 𝑉 = 𝑎 2 𝑖 +1 + 𝛼 2 𝑖 𝑎 2 2𝑖 +1 𝜇 2 𝑖 + 𝛼𝑎 2 𝑖+1 𝜇 .
Using Proposition 2, 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 4 solutions for some 𝑎 ̸ = 0 except for two specific values of 𝛽. Recall that we exclude the case 𝛼 = 1. If V 𝛼,𝛽 is APN, then Equation ( 2) must have at most two solutions for any 𝑎 ̸ = 0 and any 𝑐 ′′ . We derive from Proposition 2 that this happens if and only if, for all 𝑎 ̸ = 0, 𝑈 = 0 and 𝑉 ̸ = 0 or 𝑈 = 𝑉 and 𝑈 ̸ = 0 or 𝑈 ̸ = 0 and Tr

( ( 1 + 𝑉 𝑈 ) 𝜏 ) = 1 .
We first observe that 𝑉 ̸ = 0, otherwise

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

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

𝛼𝑎 2 𝑖 -1 𝜇 = 1 ⇔ 1 + 𝛼 2 𝑖+1 + 𝛼 2 𝑖 -1 𝛽 = 1 + 𝛼 2 𝑖+1 -2 , which is equivalent to 𝛽 = 𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 .
The last condition corresponds to

1 = Tr ( ( 1 + 𝑉 𝑈 ) 𝜏 ) = Tr (( 𝑎 2 𝑖 +1 + 𝛼𝑎 2 𝑖+1 𝜇 𝛼 2 𝑖 𝑎 2 2𝑖 +1 𝜇 2 𝑖 ) 𝜏 )
We simplify the fraction on the right-hand side as follows:

𝑎 2 𝑖 +1 + 𝛼𝑎 2 𝑖+1 𝜇 𝛼 2 𝑖 𝑎 2 2𝑖 +1 𝜇 2 𝑖 = 1 + 𝑎 2 𝑖 -1 𝛼𝜇 𝑎 2 2𝑖 -2 𝑖 𝛼 2 𝑖 𝜇 2 𝑖 = 𝛼 2 𝑖+1 +1 +𝛼 2 𝑖+1 -1 +𝛼 2 𝑖 𝛽 𝛼+𝛼 2 𝑖+1 -1 ( 𝛼+𝛼 2 𝑖+1 +1 +𝛼 2 𝑖 𝛽 𝛼+𝛼 2 𝑖+1 -1 ) 2 𝑖 = ℬ 𝛼,𝛽 ,
where

ℬ 𝛼,𝛽 = 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖+1 -1 + 𝛼 2 𝑖 𝛽 𝛼 + 𝛼 2 𝑖+1 -1 ( 𝛼 + 𝛼 2 𝑖+1 -1 𝛼 + 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖 𝛽 ) 2 𝑖 = (𝛼 + 𝛼 2 𝑖+1 -1 ) 2 𝑖 -1 × 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖+1 -1 + 𝛼 2 𝑖 𝛽 (𝛼 + 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖 𝛽) 2 𝑖 = (𝛼 + 𝛼 2 𝑖+1 -1 ) 2 𝑖 -1 × 𝛼 2 𝑖+1 +1 + 𝛼 2 𝑖+1 -1 + 𝛼 2 𝑖 𝛽 𝛼 2 2𝑖+1 +2 𝑖 + 𝛼 2 𝑖 + 𝛼 2 2𝑖 𝛽 2 𝑖 .
We have established in Lemma 1 that Tr(ℬ 𝜏 𝛼,𝛽 ) is always equal to 0, implying that Tr

( ( 1 + 𝑉 𝑈 ) 𝜏 ) = 0 . Therefore, if V 𝛼,𝛽 is APN then 𝛽 = 𝛼 -2 𝑖 +1 + 𝛼 2 𝑖 +1 or 𝛽 = 𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 .
We then show that, for the two particular values of 𝛽 that we consider, the corresponding butterfly is APN if and only if a specific trace is constant on F 2 𝑛 except on 3 particular values.

Proposition 4 (Trace Condition). Let 𝛼 ̸ = 0, 1. A generalised butterfly with parameters 𝛼 and 𝛽 is APN if and only if:

𝛽 ∈ {𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 , 𝛼 -2 𝑖 +1 + 𝛼 2 𝑖 +1 } and Tr (𝒜 𝛼 (𝑒) 𝜏 ) = 1, ∀ 𝑒 ̸ ∈ {0, 𝛼, 1/𝛼} , where 𝒜 𝛼 (𝑒) = 𝛼 2 𝑖 -1 × 𝑒𝛼(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 𝑖 .
Proof. Since we have proved in Section 2.2 that generalised butterflies with parameters (𝛼, 𝛽 0 ) and (𝛼, 𝛽 1 ) where 𝛽 1 = 𝛽 -1 0 (1 + 𝛼) 2(2 𝑖 +1) are affine-equivalent, we only need to prove the result for 𝛽 = 𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 .

As before, we need to count the number of solutions of

{ 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑 (3)
for any tuple (𝑎, 𝑏, 𝑐, 𝑑) of F 2 𝑛 with (𝑎, 𝑏) ̸ = (0, 0). We develop each line of this system and obtain

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

{ (𝑎 + 𝛼𝑏)(1 + 𝛼 2 𝑖+1 -2 )𝑥 2 𝑖 + 𝑎 2 𝑖 (1 + 𝛼 2 𝑖+1 -2 )𝑥 + 𝑎 2 𝑖 𝛼(1 + 𝛼 2 𝑖+1 -2 )𝑦 = 𝑐 1 (𝛼𝑎 + 𝑏)(1 + 𝛼 2 𝑖+1 -2 )𝑦 2 𝑖 + 𝑏 2 𝑖 (1 + 𝛼 2 𝑖+1 -2 )𝑦 + 𝑏 2 𝑖 𝛼(1 + 𝛼 2 𝑖+1 -2 )𝑥 = 𝑑 1 , i.e., { (𝑎 + 𝛼𝑏)𝑥 2 𝑖 + 𝑎 2 𝑖 𝑥 + 𝑎 2 𝑖 𝛼𝑦 = 𝑐 2 (𝛼𝑎 + 𝑏)𝑦 2 𝑖 + 𝑏 2 𝑖 𝑦 + 𝑏 2 𝑖 𝛼𝑥 = 𝑑 2 ,
which can be rewritten as

{ (𝑎𝑥 2 𝑖 + 𝑎 2 𝑖 𝑥) + 𝛼(𝑏𝑥 2 𝑖 + 𝑎 2 𝑖 𝑦) = 𝑐 2 (𝑏𝑦 2 𝑖 + 𝑏 2 𝑖 𝑦) + 𝛼(𝑎𝑦 2 𝑖 + 𝑏 2 𝑖 𝑥) = 𝑑 2 . ( 4
)
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

𝑥 = ( 𝑐 2 𝛼𝑏 ) 2 𝑛-𝑖 .
Replacing 𝑥 by this value in the second line of System ( 4) yields an equation in 𝑦 with nonzero coefficients of the form 𝑏𝑦 2 𝑖 + 𝑏 2 𝑖 𝑦 = 𝑐 3 . Since gcd(𝑖, 𝑛) = 1, this equation has at most two solutions, implying that (4) 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 (4) has as many solutions as

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

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

(𝑥 ′2 𝑖 + 𝑥 ′ )(𝑒 + 𝛼) + (𝑦 ′2 𝑖 + 𝑦 ′ )(𝑒 -1 + 𝛼) = 𝑐 3 + 𝑑 3 . If 𝑒 = 𝛼, then 𝑦 ′ is fixed to either 𝑦 ′ 0 or 𝑦 ′ 1 with 𝑦 ′ 0 + 𝑦 ′ 1 = 1.
The first line of the system implies in this case that 𝑥 ′ = 𝑦 ′ 𝑖 + 𝑐 3 /𝛼 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 (5) allows us to express 𝑦 ′ as a function of 𝑥 ′ :

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

( 𝑒 -1 + 𝛼 ) 𝑦 ′2 𝑖 + 𝑒 -1 𝑦 ′ + 𝛼𝑥 ′ = ( 𝑒 -1 + 𝛼 ) (( 𝑒 𝛼 + 1 ) 𝑥 ′2 𝑖 + 𝑒 𝛼 𝑥 ′ + 𝑐 3 𝛼 ) 2 𝑖 + 𝑒 -1 (( 𝑒 𝛼 + 1 ) 𝑥 ′2 𝑖 + 𝑒 𝛼 𝑥 ′ + 𝑐 3 𝛼 ) + 𝛼𝑥 ′ = (𝑒 -1 + 𝛼) ( 𝑒 𝛼 + 1 ) 2 𝑖 𝑥 ′2 2𝑖 + ( (𝑒 -1 + 𝛼) 𝑒 2 𝑖 𝛼 2 𝑖 + 𝑒 -1 ( 𝑒 𝛼 + 1 ) ) 𝑥 ′2 𝑖 + ( 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 Proposition 2. 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 (1

+ 𝑉 /𝑈 ) 𝜏 : if Tr (( 1 + 𝑉 𝑈 ) 𝜏 ) = 1
then the equation has at most 2 solutions, otherwise it has 0 or 4 solutions. It holds that

1 + 𝑉 𝑈 = 𝛼 -1 + 𝛼 (𝑒 -1 + 𝛼)(1 + 𝑒𝛼 -1 ) 2 𝑖 = 𝛼 2 𝑖 -1 𝑒(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 𝑖 so the function is APN if and only if Tr (𝒜 𝛼 (𝑒) 𝜏 ) = 1, ∀𝑒 ̸ = 0, 𝛼, 1/𝛼, with 𝒜 𝛼 (𝑒) = 𝛼 2 𝑖 -1 × 𝑒(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 𝑖 .
The trace condition provided by Proposition 4 is sufficient to describe all APN generalised butterflies but it can be greatly simplified. This is stated in the following proposition which presents the refined trace condition.

Proposition 5 (Refined Trace Condition). Let 𝛼 ∈ F 2 𝑛 ∖ {0, 1}, with 𝑛 odd. The generalised butterfly with parameters 𝛼 and 𝛽 = 𝛼 2 𝑖 -1 + 𝛼 2 𝑖 +1 is APN if and only if:

Tr(𝐹 𝐷 (𝑡) 𝜏 ) = 1, ∀𝑡 / ∈ {0, 1, 𝐷} where 𝐹 𝐷 (𝑡) = 𝑡 + 𝑡 2 𝑖 +1 𝑡 + 𝐷 ,
and

𝐷 = 1/(1 + 𝛼 2 ).
Proof. Based on Proposition 4, we only have to prove that the number of 𝑒 / ∈ {0, 𝛼, 1/𝛼} such that Tr(𝒜 𝛼,𝑖 (𝑒) 𝜏 ) = 1 is equal to the number of 𝑡 / ∈ {0, 1, 𝐷} such that Tr(𝐹 𝐷 (𝑡) 𝜏 ) = 1. Using that 2 𝑖 𝜏 ≡ 1 + 𝜏 mod (2 𝑛 -1), the term 𝒜 𝛼,𝑖 (𝑒) 𝜏 can be re-written as follows

𝒜 𝛼,𝑖 (𝑒) 𝜏 = ( 𝛼 2 𝑖 -1 𝑒(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) 2 𝑖 ) 𝜏 = 𝛼 𝑒 𝜏 (1 + 𝛼) 2𝜏 (1 + 𝛼𝑒) 𝜏 (𝛼 + 𝑒) 2 𝑖 𝜏 = 𝛼 𝑒 𝜏 (1 + 𝛼) 2𝜏 (1 + 𝛼𝑒) 𝜏 (𝛼 + 𝑒) 𝜏 +1 = 𝛼 𝛼 + 𝑒 ( 𝑒(1 + 𝛼) 2 (1 + 𝛼𝑒)(𝛼 + 𝑒) ) 𝜏 .
We further simplify this expression by reusing the change of variable introduced in [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF], namely

ℓ = (𝑒 + 𝛼)(1 + 𝛼) 2
which implies in particular that, for 𝛾 0 = 𝛼 + 𝛼 3 and 𝛾 1 = 𝛼 -1 + 𝛼 3 :

• 𝑒 ̸ ∈ {0, 𝛼, 1/𝛼} is equivalent to ℓ ̸ ∈ {𝛾 0 , 0, 𝛾 1 },

• 𝑒(1 + 𝛼) 2 = ℓ + 𝛾 0 , and

• (1 + 𝛼𝑒)(1 + 𝛼) 2 = 𝛼(ℓ + 𝛾 1 ).
We deduce:

𝒜 𝛼,𝑖 (𝑒) 𝜏 = 𝛼 ( 𝑒(1 + 𝛼) 2 (1 + 𝛼𝑒)(1 + 𝛼 2 )(𝛼 + 𝑒)(1 + 𝛼 2 ) / (1 + 𝛼) 4 ) 𝜏 1 𝛼 + 𝑒 = 𝛼 ( ℓ + 𝛾 0 𝛼(ℓ + 𝛾 1 ) ℓ (1 + 𝛼 4 ) ) 𝜏 1 + 𝛼 2 ℓ = 𝛾 0 ( 𝛾 1 (ℓ + 𝛾 0 ) (ℓ + 𝛾 1 )ℓ ) 𝜏 1 ℓ .
As a sanity check, if we let 𝜏 = 1, we can see that we obtain

𝒜 𝛼,𝑖 (𝑒) = 𝛾 0 𝛾 1 ℓ 2 × ℓ + 𝛾 0 ℓ + 𝛾 1
which is exactly the equation Canteaut et al. derived on page 7585 of [START_REF] Canteaut | A generalisation of Dillon's APN permutation with the best known differential and nonlinear properties for all fields of size 2 4𝑘+2[END_REF].

We further let 𝛾 1 /𝑣 = ℓ and note that 𝛾 0 /𝛾 1 = (1 + 𝛼 -2 ) -1 = 𝐶. As a consequence, the condition ℓ ̸ ∈ {𝛾 0 , 0, 𝛾 1 } becomes 𝑣 ̸ ∈ {1/𝐶, 0, 1} and we can write:

𝒜 𝛼,𝑖 (𝑒) 𝜏 = 𝛾 0 ( 𝛾 2 1 𝑣 -1 + 𝛾 0 𝛾 1 (𝛾 1 𝑣 -1 + 𝛾 1 )𝛾 1 𝑣 -1 ) 𝜏 𝑣/𝛾 1 = 𝛾 0 /𝛾 1 ( 𝑣 -1 + 𝛾 0 /𝛾 1 (𝑣 -1 + 1)𝑣 -1 ) 𝜏 𝑣 = 𝐶 ( 𝑣 -1 + 𝐶 (𝑣 -1 + 1)𝑣 -1 ) 𝜏 𝑣 = 𝐶 ( 𝑣 + 𝐶𝑣 2 1 + 𝑣 ) 𝜏 𝑣 = 𝐶 ( 𝑣 + 𝐶𝑣 2 1 + 𝑣 𝑣 2 𝑖 -1 ) 𝜏 = 𝐶 ( 𝑣 2 𝑖 + 𝐶𝑣 2 𝑖 +1 1 + 𝑣 ) 𝜏 .
We now let 𝑣 = (𝑡 + 1)/𝐶, so that 𝑣 ̸ ∈ {1/𝐶, 0, 1} becomes 𝑡 ̸ ∈ {0, 1, 𝐷} where 𝐷 = 1 + 𝐶 = 1 + 1/(1 + 𝛼 -2 ) = 1/(1 + 𝛼 2 ). Thus, we can write:

𝑣 2 𝑖 + 𝐶𝑣 2 𝑖 +1 = (𝑡 + 1) 2 𝑖 𝐶 -2 𝑖 + 𝐶(𝑡 + 1) 2 𝑖 +1 𝐶 -2 𝑖 -1 = 𝐶 -2 𝑖 (𝑡 2 𝑖 + 1 + 𝑡 2 𝑖 +1 + 𝑡 2 𝑖 + 𝑡 + 1) = 𝐶 -2 𝑖 (𝑡 2 𝑖 +1 + 𝑡)
and 𝑣 + 1 = 𝐶 -1 (𝑡 + 1 + 𝐶). The expression then becomes

𝒜 𝛼,𝑖 (𝑒) 𝜏 = 𝐶 ( 𝐶 -2 𝑖 (𝑡 + 𝑡 2 𝑖 +1 ) 𝐶 -1 (𝑡 + 1 + 𝐶) ) 𝜏 = ( 𝑡 + 𝑡 2 𝑖 +1 𝑡 + 𝐷 ) 𝜏 = 𝐹 𝐷 (𝑡) 𝜏 ,
so we can conclude that the number of 𝑒 ̸ ∈ {0, 𝛼, 1/𝛼} such that Tr (𝒜 𝛼,𝑖 (𝑒) 𝜏 ) = 1 is equal to the number of 𝑡 ̸ ∈ {0, 1, 𝐷} such that Tr (𝐹 𝐷 (𝑡) 𝜏 ) = 1.

The Necessary Condition Needs a Small Branch Size

In what follows, we prove the last step of our reasoning: if a butterfly is APN then 𝑛 ≤ 3. This statement is given by the following proposition that we prove below.

Proposition 6. If the refined trace condition of Proposition 5 holds then 𝑛 ≤ 3.

Proof. Suppose that the trace condition holds for some 𝐷, 𝑖 and 𝛼. Then we have

Tr (𝐹 𝐷 (𝑥) 𝜏 ) = 1, ∀𝑥 ̸ ∈ {0, 1, 𝐷}
with 𝐹 𝐷 (𝑥) = (𝑥 2 𝑖 +1 + 𝑥)/(𝑥 + 𝐷) and 𝐷 = 1/(1 + 𝛼 2 ). Let Im(𝐹 𝐷 ) be defined by

Im(𝐹 𝐷 ) = { 𝑐 ∈ F 2 𝑛 , ∃𝑥 ∈ F 2 𝑛 ∖{0, 1, 𝐷}, 𝐹 𝐷 (𝑥) = 𝑐 } .
Since 𝐹 𝐷 is a well-defined function, we have

⋃ 𝑐∈Im(𝐹 𝐷 ) { 𝑥 ∈ F 2 𝑛 ∖{0, 1, 𝐷}, 𝐹 𝐷 (𝑥) = 𝑐 } = F 2 𝑛 ∖{0, 1, 𝐷} so that ∑ 𝑐∈Im(𝐹 𝐷 ) ⃒ ⃒ { 𝑥 ∈ F 2 𝑛 ∖{0, 1, 𝐷}, 𝐹 𝐷 (𝑥) = 𝑐 }⃒ ⃒ = 2 𝑛 -3 .
As 𝐹 𝐷 (0) = 𝐹 𝐷 (1) = 0 and since these are the only two preimages of 0 under 𝐹 𝐷 , we have that 0 ̸ ∈ Im(𝐹 𝐷 ) when the input varies in F 2 𝑛 ∖{0, 1, 𝐷} and we can therefore simplify this expression into ∑

𝑐∈Im(𝐹 𝐷 ) * ⃒ ⃒ { 𝑥 ∈ F 2 𝑛 ∖{𝐷}, 𝐹 𝐷 (𝑥) = 𝑐 }⃒ ⃒ = 2 𝑛 -3 . (6)
Let us rewrite this sum using another expression of 𝑐.

Suppose that 𝑐 = 𝐹 𝐷 (𝑥) for some 𝑥 ̸ ∈ {0, 1, 𝐷}. Then 𝑥 2 𝑖 +1 + 𝑥 = 𝑐(𝑥 + 𝐷), or, equivalently,

𝑥 2 𝑖 +1 + 𝑥(𝑐 + 1) + 𝐷𝑐 = 0 . If c = 1.
In this case, the system is equivalent to 𝑥 2 𝑖 +1 + 𝐷 = 0. Thus, 1 has exactly one preimage in F 2 𝑛 ∖{0, 1, 𝐷}.

If c ̸ = 1. We then have that 𝑐 = 𝐹 𝐷 (𝑥) if and only if 𝑥 2 𝑖 +1 + (𝑐 + 1)𝑥 + 𝑐𝐷 = 0. Substituting 𝑥 with 𝐷 yields 𝐷 2 𝑖 = 1, which is impossible as this is equivalent to 𝛼 = 0. Hence, the condition 𝐹 𝐷 (𝑥) = 𝑐 already implies 𝑥 ̸ = 𝐷. Using 𝑥 = 𝑢(1 + 𝑐) 2 𝑛-𝑖 , we rewrite this equation into

𝑢 2 𝑖 +1 (1 + 𝑐) 2 𝑛-𝑖 (2 𝑖 +1) + 𝑢(1 + 𝑐) 2 𝑛-𝑖 +1 + 𝐷𝑐 = 0
which, after a division by (1 + 𝑐) 2 𝑛-𝑖 +1 , is seen to be equivalent to

𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (𝑐) = 0 , where 𝑔 𝐷 (𝑐) = 𝑐𝐷 (1 + 𝑐) 2 𝑛-𝑖 +1 . We deduce that ⃒ ⃒ { 𝑥 ∈ F 2 𝑛 ∖{0, 1, 𝐷}, 𝐹 𝐷 (𝑥) = 𝑐 }⃒ ⃒ = ⃒ ⃒ { 𝑢 ∈ F 2 𝑛 , 𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (𝑐) = 0 }⃒ ⃒ when 𝑐 ̸ = 1.
As a consequence, we can rewrite Equation ( 6) as

2 𝑛 -3 = ⃒ ⃒ { 𝑢 ∈ F 2 𝑛 , 𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (1) = 0 }⃒ ⃒ + ∑ 𝑐∈Im(𝐹 𝐷 )∖{0,1} ⃒ ⃒ { 𝑢 ∈ F 2 𝑛 , 𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (𝑐) = 0 }⃒ ⃒ which is equivalent to 2 𝑛 -4 = ∑ 𝑐∈Im(𝐹 𝐷 )∖{0,1} ⃒ ⃒ { 𝑢 ∈ F 2 𝑛 , 𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (𝑐) = 0 }⃒ ⃒ . (7)
Because of Proposition 1, we have that 𝑢 2 𝑖 +1 + 𝑢 + 𝑔 𝐷 (𝑐) = 0 has exactly 1 or 3 solutions. Indeed, it cannot have 0 solution since it is equivalent to 𝐹 𝐷 ( 𝑢(1 + 𝑐) 2 𝑛-𝑖 ) = 𝑐 which, by definition of 𝑐, has at least one solution. Thus, 𝑔 𝐷 (𝑐) ∈ 𝒮 1 ∪ 𝒮 3 , where 𝒮 1 and 𝒮 3 are defined as in Proposition 1.

Let 𝑇 be the set defined as

𝑇 = { 𝑔 𝐷 (𝑐), 𝑐 ∈ Im(𝐹 𝐷 )∖{0, 1} } .
Then ( 7) can be re-written as In order to figure out the number of 𝑏 corresponding to a given 𝑎 ′ , we will apply Proposition 1. To this end, we compute the following trace: This trace has to be equal to 1 under our assumption that the refined trace condition holds. Thus, using Proposition 1, we deduce that any given 𝑎 ′ = 𝑐 (𝑐+1) 2 𝑛-𝑖 +1 corresponds to a unique 𝑏 = 1 (𝑐+1) 2 𝑛-𝑖 and, therefore, that |𝑇 | = |Im(𝐹 𝐷 )∖{0, 1}|. We define 𝑖 1 = ⃒ ⃒ 𝑇 ∩ 𝒮 1 ⃒ ⃒ and 𝑖 3 = ⃒ ⃒ 𝑇 ∩ 𝒮 3 ⃒ ⃒ . From (8), we know that 2 𝑛 -4 = 𝑖 1 + 3𝑖 3 . The values of 𝑖 1 and 𝑖 3 are upperbounded by the sizes of 𝒮 1 and 𝒮 3 respectively which are given by Proposition 1: 𝑖 1 ≤ 2 𝑛-1 -1 and 𝑖 3 ≤ (2 𝑛-1 -1)/3. Furthermore, 𝑖 1 + 𝑖 3 = |𝑇 | = |Im(𝐹 𝐷 )∖{0, 1}| and, since we have assumed that the trace of 𝐹 𝐷 (𝑥) 𝜏 is constant and equal to 1, the size of the image of 𝐹 𝐷 is upperbounded by 2 𝑛-1 , which we decrement because we remove 1 from Im(𝐹 𝐷 ). We deduce that

2 𝑛 -4 = ⃒ ⃒ 𝑇 ∩ 𝒮 1 ⃒ ⃒ + 3 × ⃒ ⃒ 𝑇 ∩ 𝒮 3 ⃒ ⃒ . (8)
𝑖 1 ≤ 2 𝑛-1 -1 𝑖 3 ≤ (2 𝑛-1 -1)/3 𝑖 1 + 𝑖 3 ≤ 2 𝑛-1 -1 𝑖 1 + 3𝑖 3 = 2 𝑛 -4 .
It holds that 𝑖 1 + 3𝑖 3 = (𝑖 1 + 𝑖 3 ) + 2𝑖 3 which we can upperbound by 2 𝑛-1 -1 + 2(2 𝑛-1 -1)/3, a quantity equal to 2 𝑛-1 -1 + 2(2 𝑛-1 -1) 3 = 3(2 𝑛-1 -1) + 2(2 𝑛-1 -1) 3 = 6 × 2 𝑛-1 -2 𝑛-1 -5 3 = 2 𝑛 -2 𝑛-1 + 5 3 .

As a consequence, if (2 𝑛-1 + 5)/3 > 4 then we have a contradiction because 𝑖 1 + 3𝑖 3 would then be both equal to 2 𝑛 -4 and strictly smaller than 2 𝑛 -4. This inequality can be re-written as follows:

(2 𝑛-1 + 5)/3 > 4 ⇔ 2 𝑛-1 > 7 .

Thus, if the refined trace conditions then we have a contradiction whenever 2 𝑛-1 > 7 or, equivalently, 𝑛 > 3. We conclude that the refined trace condition implies 𝑛 ≤ 3.

Conclusion

Since generalised butterflies defined in [START_REF] Li | On the generalization of butterfly structure[END_REF] have very good differential uniformity and nonlinearity, and, moreover, contain the only known APN permutation, it was natural to hope there would be APN permutations among them. However, we give a negative answer to this question: through a rigorous proof, we confirm that all APN generalised butterflies operate on 6 bits. In other words, all APN generalised butterflies were already known.

Proposition 2 .

 2 Let 𝑈, 𝑉 be elements of F 2 𝑛 with 𝑛 odd. The linearised equation in 𝑧 𝑈 𝑧 2 2𝑖 + 𝑉 𝑧 2 𝑖 + (𝑈 + 𝑉 )𝑧 = 𝐶 with gcd(𝑖, 𝑛) = 1 has • 0 or 2 𝑛 solutions if 𝑈 = 𝑉 = 0, • 0 or 4 solutions if 𝑈 ̸ = 0, 𝑈 ̸ = 𝑉 and Tr (( 1 + 𝑉 𝑈 ) 𝜏 ) = 0,

{

  𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦 + 𝑏) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦 + 𝑏, 𝑥 + 𝑎) = 𝑑 for any tuple (𝑎, 𝑏, 𝑐, 𝑑) of F 2 𝑛 with (𝑎, 𝑏) ̸ = (0, 0) and where 𝑅(𝑥, 𝑦) = (𝑥 + 𝛼𝑦) 2 𝑖 +1 + 𝛽𝑦 2 𝑖 +1 .In order to derive the necessary condition on 𝛽 given by this proposition, we simply need to consider the case 𝑏 = 0. In this case, the system becomes { 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦) = 𝑐 𝑅(𝑦, 𝑥) + 𝑅(𝑦, 𝑥 + 𝑎) = 𝑑 where 𝑅(𝑥, 𝑦) + 𝑅(𝑥 + 𝑎, 𝑦) = (𝑥 + 𝛼𝑦)𝑎 2 𝑖 + (𝑥 + 𝛼𝑦) 2 𝑖 𝑎 + 𝑎 2 𝑖 +1

1 (

 1 Let us now show that |𝑇 | = |Im(𝐹 𝐷 )∖{0, 1}|. Let 𝑎 ′ = 𝑐 (𝑐+1) 2 𝑛-𝑖 +1 and let us investigate the number of 𝑐 ∈ Im 𝐹 𝐷 that correspond to the same 𝑎 ′ . Note that 𝑐 (𝑐 + 1) 2 𝑛-𝑖 +1 = 1 (𝑐 + 1) 2 𝑛-𝑖 +1 + 1 (𝑐 + 1) 2 𝑛-𝑖 , and, by the substitution 𝑏 = 𝑐+1) 2 𝑛-𝑖 , we get 𝑏 2 𝑖 +1 + 𝑏 + 𝑎 ′ = 0 .

  2 𝑛-𝑖 +1 + 𝑥 2 𝑛-𝑖 𝑥 2 𝑛-𝑖 + 𝐷 2 𝑛-𝑖 2 𝑛-𝑖 +1 + 𝑥 2 𝑛-𝑖 𝑥 2 𝑛-𝑖 + 𝐷 2 𝑛-𝑖 ) 2 𝑖 𝜏 ) = Tr ( ( 𝑥 2 𝑖 +1 + 𝑥 𝑥 + 𝐷 ) 𝜏 ) = Tr(𝐹 𝐷 (𝑥) 𝜏 ) .

Acknowledgements. The work of Léo Perrin was supported by the Fondation Sciences Mathématiques de Paris. The work of Shizhu Tian was supported by the National Science Foundation of China (No. 61772517, 61772516).


Ternary Syndrome Decoding with Large Weight

Rémi Bricout 1,2 André Chailloux 2 Thomas Debris-Alazard 1,2 Matthieu Lequesne 1,2 1 Sorbonne Université, UPMC Univ Paris 06 2 Inria, Paris

The Syndrome Decoding Problem Syndrome Decoding -SD(q, R, W ) Instance: H ∈ F (n-k)×n q of full rank, s ∈ F n-k q (usually called the syndrome).

Output: e ∈ F n q such that |e| = w and eH = s, where k = Rn , w = W n and |e| = |{i : e i = 0}|.

Binary vs. Ternary case

Depending on R and W , the complexity of the SD problem can greatly vary. Let us fix a value R, and let W GV denote the Gilbert-Varshamov bound. For W ∈ 0, 1 2 , there exist three regimes. 1 W ≈ W GV . There is a small number of solutions. This is the regime where the problem is the hardest and where it is the most studied.

2 W W GV . There are exponentially many solutions and this makes the problem simpler. When W reaches 1-R 2 , the problem can be solved in average polynomial time.

3 W W GV . In this regime, we have with high probability a unique solution. However, the search space, i.e. the set of vectors e st. |e| = W n is much smaller.

Decoding in Large Weight

Symetry. SD(2, R, W ) and SD(2, R, 1 -W ) are equivalent.

However, this argument is no longer valid for q ≥ 3. The problem has a quite different behavior in small and large weights. The goal of this work is to study the complexity of the SD problem for q = 3 and W > 0.5.

From SD to Subset Sum

Most algorithms designed to solve the SD problem follow the same framework, which can be generalized for the non-binary case. Let (H, s) be the instance that we want to solve. Let us introduce and p, two parameters of the system.

1 Apply a random permutation π on the columns of H. 2 Perform a partial Gaussian elimination on the rows of H π using the first n -k -columns. Let S ∈ F (n-k)×(n-k) q be the matrix corresponding to this operation and introduce two matrices

H ∈ F (n-k-)×(k+ ) q and H ∈ F ×(k+ ) q such that SH π = 1 n-k-H 0 H .
The problem can be rewritten as follows.

H

Reduction Lemma

If we have an algorithm that solves SS(3, k + , , L, ∅) then we have an algorithm that solves SSNZC(3, k + , , L, k + ) with the same complexity.

The Subset Sum Problem

Subset Sum problem -SS(q, n, m, L, p)

Instance: n vectors x i ∈ F m q for 1 ≤ i ≤ n, a target s ∈ F m q . Output: L solutions (b (j) 1 , . . . , b (j) n ) ∈ {0, 1} n for 1 ≤ j ≤ L, such that for all j, n i=1 b (j) i x i = s and |b (j) | = p.
We denote SSNZC(q, n, m, L, p) the problem when we look for solutions with b (j)

i ∈ F q . We denote SS(q, n, m, L, ∅) the problem without any constraint on the weight.

Wagner's algorithm

Wagner's algorithm [START_REF] Wagner | A generalized birthday problem[END_REF] is an algorithm to solve SS(2, n, , L, ∅).

For some parameters, it finds L solution in time O(L). It can easily be adapted to solve the SS problem in the ternary case. The algorithm works as follows:

divide the vectors x 1 , . . . , x n in 2 a stacks of size n/2 a ; for each stack, compute a list L p of L random linear combinations of the vectors in the stack ; merge the lists two by two: from L p and L p+1 create the list {y p + y p+1 : y i ∈ L i and the last /a bits of y p + y p+1 are 0s.} ; repeat a -1 times.

Smoothing Wagner's Algorithm

Wagner's algorithm shows how to find L solutions in time O(L) for L = 3 /a . The smaller L is, the better the algorithm performs. So the idea is to take the largest integer a such that 3 /a < 2 (k+ )/2 a . But this induces a discontinuity in the complexity. We propose a refinement of the theorem that reduces the discontinuity. Our best algorithm uses a tree on seven levels. It uses Wagner's left-right splits at the top and at the bottom of the tree and representations on the intermediate levels.

Using Representations

New Parameters for Wave

Wave [START_REF] Debris-Alazard | Wave: A new code-based signature scheme[END_REF] is a new code-based signature scheme. It uses a hashand-sign approach and follows the GPV paradigm. Wave is the firts cryptographic scheme on the ternary SD problem with large weight. Forging a signature in the Wave scheme amounts to solving the ternary SD problem (more exactly the Decoding One Out of Many version of the problem). We provide new parameters for Wave so that the scheme resists attacks using our algorithms.

Hardest Instances

We now focus on the parameters where the problem is the hardest. We compared the performance of 3 standard algorithms: Prange's algorithm, Dumer's algorithm and the BJMM algorithm on binary SD problem with our equivalents for the ternary SD problem. We performed a case study and showed that the hardest case is reached for R ≈ 0.36907 and W = 1. The ternary SD problem appears significantly harder than the binary one. But the input matrices have elements in F 3 and not F 2 , so matrices of the same dimension contain more information. To get rid of this bias, we define the following metric. What is the smallest input size for which the algorithms need at least 2 128 operations to decode? The input matrix

H ∈ F n(1-R)×n 3 is represented in systematic form. Algorithm q = 2 q = 3

Conclusion

Strong difference between the cases q = 2 and q ≥ 3. Two algorithms to solve the Syndrome Decoding problem in this new regime : a q-ary version of Wagner's approach and a second algorithm making use of representations. Application: new parameters for the Wave signature scheme.

Study of ths hardest case: complexity of SD in large weight is higher than in small weight.

This work opens many new perspectives. It seems there are many cases in code-based cryptography, from encryption schemes to signatures, where this problem could replace the binary SD problem to get smaller key sizes.

Figure 1 :

 1 Figure 1: Asymptotic complexity of Prange's ISD algorithm for R = 0.5.

π e = s ⇐⇒ SH π e = Ss ⇐⇒ 1

 1 To solve the problem, we will try to find a solution (e , e ) to the above system such that |e | = p and |e | = w -p.

Figure 2 :

 2 Figure 2: Wagner's algorithm with a = 2.

  When looking for vectors b, Wagner's algorithm looks for b in the form b = b 1 + b 2 , where the second half of b 1 and the first half of b 2 are only zeros, as on Figure 3 (1). As in the BJMM algorithm [2], the idea of representations is to remove this constraint and replace it by a less restrictive one. Here, we fix the number of 0s, 1s and 2s in b 1 and b 2 . This allows more possibilities to write b as the sum of two vectors (2).

Figure 3 :

 3 Figure 3: Same vector (1) using left-right split and (2) using representations.

Figure 4 :Figure 5 :

 45 Figure 4: Wagner tree for a = 7. Yellow lists correspond to representations and blue lists to left-right splits.

Algorithm q = 2 q

 2 = 3 and W > 0.5 Prange 0.121 (R = 0.454) 0.369 (R = 0.369) Dumer/Wagner 0.116 (R = 0.447) 0.269 (R = 0.369) BJMM/our algorithm 0.102 (R = 0.427) 0.247 (R = 0.369)

  and W > 0.5 Prange 275 (R = 0.384) 44 (R = 0.369) Dumer/Wagner 295 (R = 0.369) 83 (R = 0.369) BJMM/our algorithm 374 (R = 0.326) 99 (R = 0.369)

Table 1 :

 1 Best exponents with associated rates.

Table 2 :

 2 Minimum input sizes (in Kbits) for a time complexity of 2 128 .

Compute a set S of solutions of H e = s such that |e | = p. This is an instance of the Subset Sum problem.

Take a vector e ∈ S and let e = s -H e . If |e | = w -p, e = (e , e ) is a solution for inputs H π and s, which can be turned into a solution of the initial problem.


Hauke Straehler-Pohl

Anette Bagger

Laura Black

Anna Chronaki

David Kollosche

la diffusion de documents scientifiques de niveau

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction to the work of TWG10: Diversity and Mathematics Education: Social, Cultural and Political Challenges

Introduction to the work of TWG10: Diversity and Mathematics Education: Social, Cultural and Political Challenges

Hauke Straehler-Pohl 1 , Anette Bagger 2 , Laura Black 3 , Anna Chronaki 4 and David Kollosche 5

1 Freie Universität Berlin, Germany; h.straehler-pohl@fu-berlin.de 2 Örebrö Universitet, Sweden; anette.bagger@oru.se 3 University of Manchester, United Kingdom; laura.black@manchester.ac.uk 4 University of Thessaly, Greece; chronaki@uth.gr 5 Pädagogische Hochschule Vorarlberg, Austria; david.kollosche@ph-vorarlberg.ac.at

Scope and Focus

Thematic working group 10 is interested in discussing mathematics education within the realms of culture, society and the political. TWG10 builds on the premise that mathematics education is always more than the encounter between an individual and an object. Such encounters are embedded within wider contexts than just classroom settings. They are shaped by the social, cultural and political contexts in which they take place. Being social, cultural and political encounters themselves, they reflexively contribute to constituting the wider context in which they are embedded. Research in this group is characterized by an effort to reflect its own double-role in not only analysing but also shaping the possibilities of seeing and inventing mathematics education practices.

The call for papers invited participants to address how diversity affects possibilities in mathematics education. The group's work was based on a broad understanding of diversity, including: 1) Diversity as expressed in terms of attributes of people, such as gender, ethnicity, language, socioeconomic status, social class, (dis)abilities, needs, achievement, life opportunities; 2) diversity as expressed in terms of ways of perceiving the world and giving structure to it, such as aspirations, worldviews, ideologies, school systems, and governance structures; 3) diversity in relation to the variety of sites where mathematics education takes place, such as schools, homes, workplaces, after-school organisations, communities; and finally, 4) diversity in relation to who is doing the research and who is being researched, posing methodological issues of an ethical nature. Diversity thus also refers to the wide variety of doing mathematics education research within the realms of culture, society and the political. As all these multiple diversities intersect, the group made an effort to develop reflexive approaches. The group invited to explore, deconstruct and even reinvent the concept of diversity.

Organisation of TWG 10's work

Understanding research as a practice that is situated within the realm of the cultural, the social, and the political has implications for practicing research in situ. We strived to organize the group to work in a way that 1) cultivates a change of perspectives and fosters reflexivity and 2) creates consciousness about the power relations underlying TWG10's work as a community of practice.

The introduction in the first session gave a brief overview about the controversies that have unfolded within the TWG in previous CERMEs, highlighting that controversies do not only occur between (groups of) scholars but also occur within individuals or within allegedly homogeneous "camps". Fostering controversy was intended to counteract dichotomization and facilitate the deconstruction of binaries.

The development of reflexivity was sought by following the principle of peer presentation, namely that authors do not present their own paper, but give a short (5 minutes) presentation of a colleague's paper. This peer presentation included a description of the main ideas from the perspectives adopted in the paper and the formulation of questions from the presenter's own perspective that opened up subsequent whole-group discussion (15 minutes). In addition, two sessions each involved, firstly, a small group breakout discussion (30 minutes) and, secondly, a synthesis (30 minutes) to support participants in drawing connections between contributions. In an attempt to make poster contributions visible to the whole group, posters were also presented. However, since the poster presentations were not followed by discussions, this procedure did not only make visible the posters, but also visualized and potentially stabilized the hierarchical distinction between papers and posters.

The papers discussed

In order to encourage and also facilitate drawing connections between papers, they were grouped in thematic pairs before the conference. As any classification does, this grouping highlighted some connections while displacing others. In the 1 st session the contributions of Wright and Black et al. critically sounded out possibilities of practicing progressive pedagogy in favour of underprivileged students. In the thematic pair on democratic experiences, Daher sought for ways of assessing democratic practices using a quantitative analysis of questionnaires, and Sachdeva took a closer look on how students experience learner autonomy in mathematics classes. In the first half of the 2nd session, Maheux et al. invited us to consider school mathematics as a possible reference for mathematics itself, hence disrupting traditional understandings of mathematics, where professional mathematics is often seen as the reference for school mathematics. Salazar reported on how students of colour developed a practice of mathematics in problem solving activities similar to the practice of professional mathematicians, thereby disrupting institutional racism in traditional school mathematics. In the second half of the session, Cabral et al. proposed Solidarity Assimilation Methodology not only as a way of disrupting traditional pedagogy, but also as a way of subverting the recurrent mode of capital accumulation embodied in assessment practices. Bagger et al.

analysed how a neoliberal regime of assessment has expanded into the domain of preschool-class education in the Swedish context. The first half of the 3 rd session was devoted to the connections between mathematics and life. Aizikovitsh-Udi reported on a teaching unit that aimed at explicitly teaching critical thinking skills. Yolçu problematized the forms of responsibilisation, reason and rationality in a course on "mathematical applications" in Turkey. In the second half, the contributions of Kollosche and of Lüssenhop et al. focused on language diversity, the former proposing guidelines for analysing and developing teaching materials, the latter exploring the practices of teachers in international preparatory classes for refugees. In the 4 th session, Makramalla et al. explored the gaps between the "mathematical ideologies" of the Egyptian curriculum, of the teachers and of the teachers' practices, yielding the potential for change within the contextual power dynamics operating in Egypt. Foyn confronted an emerging public discourse in Norway on disadvantaging boys with data from a longitudinal study, highlighting the need to nuance the debate and not lose track of the discourses that still disadvantage girls. Critically reflecting the power relations between the researcher and her/his informants, Lembrer raised methodological questions concerning the use of photo-elicitation for data-collection in the context of early years mathematics education. Kara et al. presented their research on the relation between students' social backgrounds and their problem-solving competencies. Nordkild et al. reported on a culturally sensitive teaching unit in Finland. The unit was developed by students with a Sami background to teach geometry to peers from their own culture. The first half of the 5 th session was devoted to mathematics teacher education. Povey reflected on the potential of her own teaching practice as an embodied case of a "living education theory" to serve the aims of social justice. Dexel et al. showed how a course on inclusive mathematics teaching for pre-service teachers fostered a potential-related perspective on diversity within teacher-students. This potential-related perspective on diversity was further developed in the second half by Padilla et al. who proposed the conjunction of interdisciplinarity, culturally sustaining pedagogies and pandisability cultures as a point of departure for co-creating diverse mathematics learning contexts. The need for such co-creation was empirically consolidated by Nieminen who reconstructed discourses of otherness in self-reports of university students with special needs. The 6 th session zoomed in on the mathematics student. Both the contributions of Röj-Lindberg et al. and Doğan reconstructed students' perspectives. The former did so through a longitudinal study that provided insight into why some students develop negative identifications with mathematics despite the reform-related efforts of their teachers. The latter turned the focus on a popular Turkish social medium, where almost a thousand users reported on their moments of farewell to mathematics and constructed it as an individual and subject-related fate. The last thematic pair focused on students' identities. Taking an intersectional approach, Sabbah et al. investigated how categories of gender, ethnicity and religion play out in the formation of agency and identity in female Arab students entering university mathematics in Israel. Gebremichael explored in an Ethiopian context how students perceive the relevance of mathematics and how this is closely linked to the development of identity. His analysis also sheds light on how little Ethiopian mathematics education is attuned to Ethiopian society's needs and the possible historical reasons for this.

Common conclusions

All contributions and discussions were characterized by a strong openness to perspectives and methods that are not yet established within the field of mathematics education, but belong to the state of the art in the corresponding disciplines of reference. This interdisciplinary character was consistently appreciated. It also led participants to collectively question the "nature" of mathematics: How do we define it? What are legitimate sources of reference? Who decides what is legitimate? The group agreed that these questions must remain undecided. Another issue that found unrestricted approval was the necessity of bringing theory and practice together, not only rejecting theory for theory's sake but in a similar manner rejecting excessively inductive empirical research. This commitment to (social) theory is related to the critical spirit that participants saw as common ground, binding the group together. Work in this group is largely concerned with a critique of the status quo. This critique may concern educational institutions or the societies we live in more broadly. Group members were united in the desire to change systems, whilst at the same time being aware that they are part of these systems themselves. This insight resulted in a self-critical attitude when it comes to assessing the ethical ramifications and also the generalisability of research. The self-critical attitude expressed itself in the fact that participants consensually cherished TWG work as an opportunity of "decentring oneself", an opportunity to experience their own perspective as one among legitimate alternatives, thereby allowing a reflection about each perspective's social, cultural, and political foundations. It was also expressed in a deep concern for the power relations that pervade instances of mathematics learning and teaching as well as research practice and the dynamics within the working group itself.

Open questions / controversy

While the participants all agreed on conceptualizing power as simultaneously having both restricting "negative" as well as empowering "positive" effects, the group remained undecided about the normative ramifications related to identifying power relations. For example, the group addressed the question of whether there is a boundary between acceptable and unacceptable values. What would a strictly horizontal organisation of values imply? If we do not privilege some values over others, how can we, then, talk back to and fight against socially accepted forms of oppression and violence? Related to the question of equality of values is the question about the role and function that we assign to schools: Is it their task to adapt to students' backgrounds? Or is it exactly their task to treat students irrespective of their background, or at least help them to transcend their backgrounds? Reflecting the political and moral underpinnings of each of the participants' stance certainly created tensions within the group. Some participants may identify with dissolving tensions to one side or the other, a third part of participants may identify with the contradiction inherent in the tension itself. While the group agrees that it is a collective task to deal with these contradictions and tensions, there may be different normative stances on how this should be done: Once power relations within the group surface, should the use of power be regulated? Can the group benefit in the future from explicit rules so that "privileged" participants develop techniques to govern themselves, re-distributing power to the "non-privileged"? Or would this suffocate the attempt to embrace controversy, finally leading to synchronization of perspectives and thereby jeopardizing the cherished opportunity of decentring oneself? Another controversial issue was the role of utopia in our research: Is utopia the generator of change that allows us to think of something in rupture with what exists? Or is utopia actually preventing change to materialize by outsourcing change into some displaced "alternative reality"? Finally, identifying all these controversies led to commonly posing the question: How much diversity can a thematic working group on "diversity" productively handle?

Future tasks

The group identified a need to ensure the productivity of diversity and saw the danger of losing depth in the discussion. Depth, here, applies both to the scientific quality as well as to the social quality of mutual intellectual engagement. Two ideas that found approval were 1) the reformulation and specification of the group's theme and 2) a stronger focusing and specification of the group's call for papers. Concerning the theme, the group agreed that even though diversity adequately described the spirit of the group, it factually did not serve anymore as the thematic pivot. It is a designated task for the future TWG-leaders to maintain this spirit of diversity. However, the contributions rarely addressed diversity explicitly. The group suggested to exclude diversity from the title, nevertheless making sure that the call maintains the thematic inclusion of diversity as a theme (among others). Further, the call should more explicitly demand authors to interrelate "the micro" and "the macro" which also implies a stronger attentiveness to social, cultural and political theory. If the next group-leaders should, however, decide to keep diversity in the title, there is a need to sharpen the call for papers in that direction. In order to develop in any of these directions, the group requires a clearer and more concise focus in order to maintain its scientific and intellectual productivity.