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

Abstract

Whether there exist Almost Perfect Non-linear permutations (APN) operating on an even number of bits 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 $\mathbb {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 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 $\mathbb {F}_{2^{n}}$ can never be APN when n > 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.

1 Introduction

S(ubstitution)-boxes are core components in symmetric ciphers where they serve as the part providing confusion. In most cases, they are their only nonlinear components. In order for the algorithm to resist the two most prominent cryptanalytic techniques, namely differential [2, 3] and linear attacks [13], S-boxes should have a low differential uniformity [14] and a high nonlinearity [7].

Let F be a vectorial Boolean function from the vector space F2m (composed of all binary vectors of length m) to F2m. The nonlinearity of F, denoted by $\mathcal {NL}(F)$, is determined by the Walsh transform of F, defined as

$$W_{F}(u,v)=\sum\limits_{x\in\mathbb{F}_{2}^{m}}(-1)^{v\cdot F(x)+u\cdot x}, u,v\in\mathbb{F}_{2}^{m},$$

by the following relation

$$\mathcal{NL}(F)= 2^{m-1}-\frac{1}{2}\max\limits_{u,v\in\mathbb{F}_{2}^{m}, v \neq 0}|W_{F}(u,v)|.$$

We say that F is differentially δ-uniform if, for any nonzero a in ${\mathbb {F}_{2}^{m}}$ and $b\in {\mathbb {F}_{2}^{m}}$, the equation F(x) + F(x + a) = b has at most δ solutions in ${\mathbb {F}_{2}^{m}}$. The lower bound on the differential uniformity for functions on ${\mathbb {F}_{2}^{m}}$ is 2, and the functions that achieve this bound are called Almost Perfect Nonlinear (APN) [15]. That is, a function $F : {\mathbb {F}_{2}^{m}} \to {\mathbb {F}_{2}^{m}}$ is APN if the following equation

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

has at most two solutions for any $b \in \mathbb {F}_2^{m}$ and any nonzero $a \in \mathbb {F}_2^{m}$. An APN permutation over ${\mathbb {F}_{2}^{m}}$ would be an S-box providing optimal protection against differential attacks. Such components are easy to find for m odd: the Gold functions $x \mapsto x^{2^{i}+ 1}$ and the inverse mapping $x \mapsto x^{2^{m}-2}$, which are defined by identifying $\mathbb {F}_{2^{m}}$ with ${\mathbb {F}_{2}^{m}}$, 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 thebig APN problem.

Open Problem 1 (Big APN Problem)

Is there an APN permutation of $\mathbb {F}_{2^{m}}$ where m = 2n?

It has been an open problem in the field of vectorial Boolean functions since Nyberg introduced the differential uniformity in the early 90’s [14].

Some negative results are known. For instance, Hou proved in [10] that there are no APN permutations over $\mathbb {F}_{2^{4}}$ and that there are no APN permutations over $\mathbb {F}_{2^{2n}}$ with coefficients in $\mathbb {F}_{2^{n}}$. Also, an APN permutation over $\mathbb {F}_{2^{2n}}$ can be neither a monomial function nor a quadratic function [1].

The only known solution to this problem is a sporadic case found by Dillon et al. [4] for m = 6. At the time of writing, it remains the only known APN permutation over $\mathbb {F}_{2^{2n}}$. This solution was constructed by finding a permutation in the CCZ-equivalence class of a known quadratic APN function, namely the Kim mappingx↦x³ + x¹⁰ + gx²⁴ whereg is a root of the primitive polynomial used to define $\mathbb {F}_{2^{6}}$.

To try and use a similar approach, Yu et al. [17] designed a new matrix-based method to generate quadratic APN functions. They obtained 8157 new quadratic APN functions over $\mathbb {F}_{2^{8}}$. However, none of these APN functions are CCZ-equivalent to permutations.

In [16], Perrin et al. identified a specific structure called Open Butterfly which is affine-equivalent to Dillon et al.’s permutation. This structure is easily defined over higher dimensions, but, unfortunately, Canteaut et al. [5] proved that an even broader family of permutations containing the butterflies of Perrin et al. does not contain any APN permutations form > 6.

Several teams then studied other generalizations of the original butterfly of [16]. Firstly, it was shown in [8] 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 [11], and that this family of generalised butterflies contains some functions which are not CCZ-equivalent to the functions studied in [5]. 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 bounded from above by 6 so that Theorem 1 holds.

2 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.

2.1 Definition

In the remainder of the paper, we consider an even integer m = 2n which is not divisible by 4, i.e., n is always odd. Also, vectorial Boolean functions from F2m into F2m are identified with mappings from $\mathbb {F}_{2^{n}} \times \mathbb {F}_{2^{n}}$ to itself. It is worth noticing that the choice of the basis used for identifying $\mathbb {F}_{2^{n}}$ with F2n does not affect the cryptographic properties of the functions we are studying since different bases lead to functions which are affine-equivalent (see the definition in Section 2.2).

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

Definition 1 (Generalised Butterflies)

Let R be a bivariate polynomial of $\mathbb {F}_{2^{n}}$ such that R_y :x ↦ R(x, y) is a permutation of $\mathbb {F}_{2^{n}}$ for all y in $\mathbb {F}_{2^{n}}$. The closed butterfly V_R is the function of $(\mathbb {F}_{2^{n}})^{2}$ defined by

$$ \mathsf{V}_{R}(x, y) = \left( R(x, y), R(y, x) \right) $$

and the open butterflyH_R is the permutation of $(\mathbb {F}_{2^{n}})^{2}$ defined by

$$ \mathsf{H}_{R}(x, y) = \left( R_{R_{y}^{-1}(x)}(y) , R_{y}^{-1}(x) \right) $$

where R_y(x) = R(x,y) and $R_{y}^{-1}\left (R_{y}(x)\right ) = x$ for any x, y. A representation of H_R is given in Fig. 1a and one of V_R is given in Fig. 1b.

Fig. 1

The butterfly constructions

It can be easily checked that, for any choice of the keyed permutationR, the open butterfly H_R 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 [16].

• In [16], Perrin et al. found that Dillon et al.’s permutation is affine equivalent toH_R with R_y(x) = (x + αy)³ + y³, for n = 3, where Tr (α) = 0. They showed that such structures always have algebraic degree n + 1 and a differential uniformity at most equal to 4 whenever α ≠ 0 and n is odd. However, they left their nonlinearity as an open problem along with the existence of APN permutations forn > 3 among them.

• Canteaut et al. [5] considered the broader class of polynomials R_y(x) = (x + αy)³ + βy³ which, up to equivalence, contains all R of degree 3 such thatR_y is always a permutation. They showed that it is always differentially 4-uniform (except for some sporadic cases) and that it could only be APN when n = 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. [8] instead chose to look at different exponents, i.e. at $R_{y}(x) = (x + \alpha y)^{2^{i}+ 1} + y^{2^{i}+ 1}$ with gcd(i, n) = 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 is always a permutation.

• Li et al. [11] investigated the broadest class of butterflies, namely those with $R_{y}(x) = (x + \alpha y)^{2^{i}+ 1} + \beta y^{2^{i}+ 1}$ with gcd(i, n) = 1. They showed that, except in some sporadic cases, the nonlinearity of such constructions is the best known to be possible and the differential uniformity is 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

$$R_{y}(x) = (x + \alpha y)^{2^{i}+ 1} + \beta y^{2^{i}+ 1}$$

with gcd(i, n) = 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.

2.2 Equivalence Relations

To begin with, we recall some basic notations of equivalence relations between vectorial Boolean functions. Two functions F₁, F₂ from F2m into F2m are E(xtended) A(ffine)-equivalent if there exist two affine permutations A₁, A₂ from F2m into F2m and an affine function A₃ from F2m into F2m such that

$$ F_{1}(x)=A_{1}(F_{2}(A_{2}(x)))+A_{3}(x). $$

If (A₃) is the all-zero function, then we say that (F₁) and (F₂) are affine equivalent. A more general framework is introduced by considering the graphs of the functions [6]. Two functions F₁, F₂ from F2m into F2m are called CCZ-equivalent (after Carlet, Charpin and Zinoviev) if there exists an affine permutation $\mathcal {L}$ over $\mathbb {F}_{2}^{2m}$ such that

$$ \mathcal{L}\left( \left\{ (x, F_{1}(x)): x \in \mathbb{F}_2^{m} \right\} \right) = \left\{ (x, F_{2}(x)): x \in \mathbb{F}_2^{m} \right\}. $$

Both the differential uniformity and the nonlinearity are invariant under EA-equivalence and under CCZ-equivalence. In particular, all functions CCZ-equivalent to an APN function are APN themselves.

In the following we denote the generalised closed butterflies asV_{α, β} : (x, y)↦ (R_y(x), R_x(y))), where $R_{y}(x) = (x + \alpha y)^{2^{i}+ 1} + \beta y^{2^{i}+ 1}$. As in the case studied in [5], the following relations hold.

• If the exponent is equal to e = (2ⁱ + 1) × 2^t, the corresponding closed butterfly is affine-equivalent to the closed butterfly with e = 2ⁱ + 1 and the same α, β. Therefore, all results presented in the paper also hold when

  $$R(x, y) = (x + \alpha y)^{(2^{i}+ 1)\times 2^{t}} + \beta y^{(2^{i}+ 1) \times 2^{t}}$$

  for some t.

• The closed butterflies V_{α, β} and $\mathsf {V}_{\alpha ^{2}, \beta ^{2}}$ are affine-equivalent as

  $$\mathsf{V}_{\alpha^{2}, \beta^{2}}\circ L_{1}(x,y)=\mathsf{V}_{\alpha^{2}, \beta^{2}}(x^{2}, y^{2})=L_{1}\circ\mathsf{V}_{\alpha, \beta}(x, y)$$

  where L₁(x, y) = (x², y²) is a linear permutation.

• For any α ≠ 1 and β ≠ 0, the closed butterflies V_{α, β} and $\mathsf {V}_{\alpha , \beta ^{\prime }}$ with $\beta ^{\prime }= \beta ^{-1} (1+\alpha )^{2(2^{i}+ 1)}$ are affine-equivalent.

  This equivalence is obtained by composing V_{α, β} with the inverse of the linear permutation

  $$L:(x,y) \mapsto (z_{1},z_{2})=(\alpha x + y, x + \alpha y) .$$

  Indeed,

  $$ \begin{array}{@{}rcl@{}} \mathsf{V}_{\alpha, \beta} \circ L^{-1}(z_{1},z_{2}) &=& \left( z_{2}^{2^{i}+ 1} + \beta \left[(1+\alpha)^{-2} (z_{1} + \alpha z_{2})\right]^{2^{i}+ 1} ,\right.\\ &&\quad\left. z_{1}^{2^{i}+ 1} + \beta \left[(1+\alpha)^{-2} (z_{2} + \alpha z_{1})\right]^{2^{i}+ 1} \right), \end{array} $$

  which is obtained by substituting (x + αy) = z₂ and y = (1 + α)^− 2(z₁ + αz₂) in R_y(x), and (αx + y) = z₁ and x = (1 + α)^− 2(αz₁ + z₂) in R_x(y). With $\beta ^{\prime }= \beta ^{-1} (1+\alpha )^{2(2^{i}+ 1)}$, we deduce that

  $$ \begin{array}{@{}rcl@{}} &&\mathsf{V}_{\alpha, \beta} \circ L^{-1}(z_{1},z_{2})\\ &=& \left( \beta(1+\alpha)^{-2(2^{i}+ 1)} \left[\beta^{\prime} z_{2}^{2^{i}+ 1} + (z_{1}+\alpha z_{2})^{2^{i}+ 1} \right],\right.\\ &&\quad\left. \beta(1+\alpha)^{-2(2^{i}+ 1)} \left[\beta^{\prime} z_{1}^{2^{i}+ 1} + (z_{2}+\alpha z_{1})^{2^{i}+ 1}\right]\right)\\ & = & \left( \beta(1+\alpha)^{-2(2^{i}+ 1)} R^{\prime}_{z_{2}}(z_{1}), \beta(1+\alpha)^{-2(2^{i}+ 1)} R^{\prime}_{z_{1}}(z_{2})\right), \end{array} $$

  where $R^{\prime }_{y}(x)= (x + \alpha y)^{2^{i}+ 1} + \beta ^{\prime } y^{2^{i}+ 1}$.

3 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 [9]). Letn be odd andibe suchthati < nand gcd(i,n) = 1. Let$\mathcal {S}_{k}$for any integerk bedefined as

$$\mathcal{S}_{k}=\{a\neq0, x^{2^{i}+ 1}+x=a has exactly k solutions\}.$$

Then$\mathcal {S}_{k}$is empty unless k ∈ {0, 1, 3}, in which case it has the following sizes:

$$ \begin{array}{@{}rcl@{}} |\mathcal{S}_{0}|&=&\frac{2^{n}+ 1}{3};\\ |\mathcal{S}_{1}|&=&2^{n-1}-1;\\ |\mathcal{S}_{3}|&=&\frac{2^{n-1}-1}{3}. \end{array} $$

Furthermore, if xis such that$x^{2^{i}+ 1}+x+a = 0$then$x^{2^{i}+ 1}+x+a = 0$has exactly 1 solution if and only if Tr ((1 +x^− 1)^τ) = 1, where τ(2ⁱ − 1) ≡ 1 mod (2ⁿ − 1).It is worth noticing that τis well-defined since$\gcd (i,n)= 1$.

The second proposition is an adaptation of Lemma 4 of [5] to the case where the exponents are 2ⁱ and 2²ⁱ rather than 2 and 4 respectively.

Proposition 2

LetU, Vbe elementsof$\mathbb {F}_{2^{n}}$withn odd.For any constant$C\in \mathbb {F}_{2^{n}}$, the linearised equation in z

$$Uz^{2^{2i}} + Vz^{2^{i}} + (U+V)z = C$$

with gcd(i,n) = 1 has

• 0 or 2ⁿsolutions ifU = V = 0,

• 0 or 4 solutions if U ≠ 0, U ≠ Vand$\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 0$,

• 0 or 2 solutions otherwise, that is if one of the following is true:

  • U = 0, V ≠ 0,

  • U ≠ 0 and V = U,

  • U ≠ 0 and$\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 1$,

where τ(2ⁱ − 1) ≡ 1 mod (2ⁿ − 1).

Proof

First of all, for any value of the constant C, the number of solutions of the equation is either zero or equal to the number of solutions of the linearised equation $Uz^{2^{2i}} + Vz^{2^{i}} + (U+V)z = 0$. We then only need to study the case C = 0. Obviously, the number of solutions is always even as if z is a solution then z + 1 is a solution too.

We consider each case separately.

• If U = V = 0 then the linearised equation does not involve z, meaning that all values of z satisfy it. We now suppose that either U ≠ 0 or V ≠ 0.

• If U = 0, V ≠ 0 then the equation corresponds to $Vz(z^{2^{i}-1}+ 1)= 0$, implying that it has 2 solutions since gcd(i, n) = 1.

• Let us now suppose that U ≠ 0. In this case, we can write

  $$ \begin{array}{@{}rcl@{}} Uz^{2^{2i}} + Vz^{2^{i}} + (U+V)z & = & U (z^{2^{i}} +z)^{2^{i}} + (U+V) z^{2^{i}} + (U+V)z \\ & = & U (z^{2^{i}} +z) \left( (z^{2^{i}} +z)^{2^{i}-1} + \frac{U+V}{U}\right)\\ & = & U z (z^{2^{i}-1}+ 1)\left( (z^{2^{i}}+z)^{2^{i}-1} + 1 + V/U \right) , \end{array} $$

  implying that the equation corresponds to

  $$U z (z^{2^{i}-1}+ 1)\left( (z^{2^{i}}+z)^{2^{i}-1} + 1 + V/U \right) = 0 .$$

  Both z = 0 and z = 1 are obviously solutions. In fact, they are the only ones if V = U so that the equation has 0 or 2 solutions in this case. Let us now suppose that V ≠U. In this case, the equation $\left ((z^{2^{i}}+z)^{2^{i}-1}+ 1 + V/U\right )= 0$ can be rewritten as

  $$z^{2^{i}}+z+\left( 1+\frac{V}{U}\right)^{\tau}= 0.$$

  This equation has two solutions when $\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 0$ while it has no solution when $\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 1$, meaning that the linearised equation has 2 solutions if $\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 1$ and 4 otherwise.

□

Finally, an a priori complicated trace will appear further in this paper. The following lemma establishes that it is in fact constant.

Lemma 1

Letnbe an odd integer andi < nwith gcd(i,n) = 1. For any$\alpha , \beta \in \mathbb {F}_{2^{n}}^{*}$,we define

$$ \mathcal{B}_{\alpha,\beta} = (\alpha + \alpha^{2^{i + 1}-1})^{2^{i}-1} \times \frac{\alpha^{2^{i + 1}+ 1} + \alpha^{2^{i + 1}-1} + \alpha^{2^{i}}\beta} {\alpha^{2^{2i + 1} + 2^{i}} + \alpha^{2^{i}} + \alpha^{2^{2i}}\beta^{2^{i}}} . $$

Then, for all α, β ≠ 0, we have that $\text {Tr}\left (\mathcal { B}_{\alpha , \beta }^{\tau } \right ) = 0$ where τ(2ⁱ − 1) ≡ 1 mod (2ⁿ − 1).

Proof

We note that $\mathcal {B}_{\alpha ,\beta }$ is equal to

$$ \begin{array}{ll} \mathcal{B}_{\alpha,\beta} &= (\alpha + \alpha^{2^{i + 1}-1})^{2^{i}-1} \times \frac{\alpha^{2^{i + 1}+ 1} + \alpha^{2^{i + 1}-1} + \alpha^{2^{i}}\beta} {\alpha^{2^{2i + 1} + 2^{i}} + \alpha^{2^{i}} + \alpha^{2^{2i}}\beta^{2^{i}}} \\ &= (\alpha + \alpha^{2^{i + 1}-1})^{2^{i}-1} \frac{\alpha^{2^{i}}\left( \alpha^{2^{i}+ 1} + \alpha^{2^{i}-1} + \beta \right)} {\alpha^{2^{2i}}\left( \alpha^{2^{2i} + 2^{i}} + \alpha^{2^{i}-2^{2i}} + \beta^{2^{i}}\right)} \\ &= \left( \frac{\alpha + \alpha^{2^{i + 1}-1}}{\alpha^{2^{i}}}\right)^{2^{i}-1} \frac{\alpha^{2^{i}+ 1} + \alpha^{2^{i}-1} + \beta} {\left( \alpha^{2^{i} + 1} + \alpha^{1-2^{i}} + \beta\right)^{2^{i}}} \\ &= \left( \alpha^{1-2^{i}} + \alpha^{2^{i}-1}\right)^{2^{i}-1} \frac{\alpha^{2^{i}+ 1} + \alpha^{2^{i}-1} + \beta} {\left( \alpha^{2^{i} + 1} + \alpha^{1-2^{i}} + \beta\right)^{2^{i}}} , \end{array} $$

which we simplify using $\lambda _{\alpha } = \alpha ^{2^{i}-1} + \alpha ^{1-2^{i}}$ and $Q_{\alpha }(\beta ) = \alpha ^{2^{i} + 1} + \alpha ^{1-2^{i}} + \beta$ by writing

$$ \mathcal{B}_{\alpha,\beta} = \lambda_{\alpha}^{2^{i}-1} \times \frac{\lambda_{\alpha} + Q_{\alpha}(\beta)}{Q_{\alpha}(\beta)^{2^{i}}} = \left( \frac{\lambda_{\alpha}}{Q_{\alpha}(\beta)} \right)^{2^{i}} + \left( \frac{\lambda_{\alpha}}{Q_{\alpha}(\beta)} \right)^{2^{i}-1} . $$

The trace of $\left ((1+q)^{2^{i}} + (1+q)^{2^{i}-1} \right )^{\tau }$ is equal to 0 for any q. Indeed, the case q = 0 is trivial, and for q ≠ 0, we have

$$ (1+q)^{2^{i}} + (1+q)^{2^{i}-1} = \frac{(1+q)^{2^{i}+ 1} + (1+q)^{2^{i}}}{1+q} = \frac{q^{2^{i}+ 1} + q}{1+q} = q (q + 1)^{2^{i}-1} , $$

from which we deduce that

$$ \left( (1+q)^{2^{i}} + (1+q)^{2^{i}-1}\right)^{\tau} = q^{\tau}(1 + q) = q^{\tau} + q^{\tau+ 1} . $$

We note that 2ⁱτ ≡ τ + 1 mod (2ⁿ − 1) and deduce that

$$ \text{Tr}\left( \left( (1+q)^{2^{i}} + (1+q)^{2^{i}-1}\right)^{\tau} \right) = \text{Tr}\left( q^{\tau} + q^{2^{i}\tau} \right) = 0 . $$

As a consequence, since

$$ \text{Tr}\left( \mathcal{B}_{\alpha,\beta}^{\tau} \right) = \text{Tr}\left( \left( \left( \frac{\lambda_{\alpha}}{Q_{\alpha}(\beta)} \right)^{2^{i}} + \left( \frac{\lambda_{\alpha}}{Q_{\alpha}(\beta)} \right)^{2^{i}-1} \right)^{\tau} \right) , $$

we have that $\text {Tr}\left (\mathcal {B}_{\alpha ,\beta }^{\tau } \right )= 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 β)

Letn > 1 be an odd integer, (α, β) be a pair of nonzero elements in$\mathbb {F}_{2^{n}}$andi > 0be an integer such that$\gcd (i, n)= 1$. If the generalised butterfly with parametersα, βand exponent 2ⁱ + 1 is APN then

$$ \beta \in \left\{(\alpha^{2^{i}-1}+\alpha^{2^{i}+ 1}), (\alpha^{-2^{i}+ 1}+\alpha^{2^{i}+ 1})\right\} . $$

Proof

In order to bound the differential uniformity of V_{α, β}, we must bound the number of solutions (x,y) of the following system

$$ \left\{\begin{array}{ll} R(x, y) + R(x + a, y + b) = c \\ R(y, x) + R(y + b, x + a) = d \end{array}\right. $$

for any tuple (a, b, c, d) of $\mathbb {F}_{2^{n}}$ with (a, b)≠(0,0) and where $R(x, y) = (x + \alpha y)^{2^{i}+ 1} + \beta y^{2^{i}+ 1}$.

In order to derive the necessary condition on β given by this proposition, we simply need to consider the caseb = 0. In this case, the system becomes

$$ \left\{\begin{array}{ll} R(x, y) + R(x + a, y) = c \\ R(y, x) + R(y, x + a) = d \end{array}\right. $$

where

$$ R(x, y) + R(x + a, y) = (x + \alpha y)a^{2^{i}} + (x + \alpha y)^{2^{i}} a + a^{2^{i}+ 1} $$

and

$$ \begin{array}{@{}rcl@{}} R(y, x) + R(y, x + a) &=& (\alpha a)^{2^{i}}(y + \alpha x) + (\alpha a)(y + \alpha x)^{2^{i}} + (\alpha a)^{2^{i}+ 1} \\ &&+ \beta \left( a^{2^{i}}x + a x^{2^{i}} + a^{2^{i}+ 1} \right) \end{array} $$

so that the original system can be re-written into

$$ \left\{\begin{array}{ll} a x^{2^{i}} + a^{2^{i}} x + \alpha^{2^{i}} a y^{2^{i}} + \alpha a^{2^{i}} y = c^{\prime} \\ (\alpha^{2^{i}+ 1} a+ a \beta) x^{2^{i}} + (\alpha^{2^{i}+ 1} a^{2^{i}}+a^{2^{i}} \beta) x + \alpha a y^{2^{i}} + \alpha^{2^{i}} a^{2^{i}} y = d^{\prime} . \end{array}\right. $$

(1)

By summing the first equation and the second one multiplied by $\alpha ^{2^{i}-1}$, we get that

$$y a^{2^{i}} (\alpha+\alpha^{2^{i + 1}-1}) = (\alpha^{2^{i + 1}}a + a + \alpha^{2^{i}-1}a\beta) (x^{2^{i}}+a^{2^{i}-1}x) + g$$

for some constant g. If α = 1 then the corresponding open butterfly is functionally equivalent to a 3-round Feistel network (see [5]). Thus, we can use the results of [12] 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 y by its value

$$y=\frac{(1+\alpha^{2^{i + 1}}+\alpha^{2^{i}-1}\beta)}{a^{2^{i}-1}(\alpha+\alpha^{2^{i + 1}-1})}(x^{2^{i}}+a^{2^{i}-1}x) +g^{\prime}$$

in the first equation of System (1). We get

$$\alpha^{2^{i}} a \mu^{2^{i}} x^{2^{2i}} + \left[a+ \alpha^{2^{i}} a^{2^{2i}-2^{i}+ 1} \mu^{2^{i}} + \alpha a^{2^{i}} \mu\right] x^{2^{i}} + \left[a^{2^{i}}+\alpha a^{2^{i + 1}-1} \mu\right]x = c^{\prime\prime} ,$$

where

$$\mu = \frac{(1+\alpha^{2^{i + 1}}+\alpha^{2^{i}-1}\beta)}{a^{2^{i}-1}(\alpha+\alpha^{2^{i + 1}-1})} .$$

Using the substitution x = ax′, we obtain that

$$ U x^{\prime 2^{2i}} + V x^{\prime 2^{i}} + (U+V)x^{\prime} = c^{\prime\prime} $$

(2)

with

$$U =\alpha^{2^{i}}a^{2^{2i}+ 1}\mu^{2^{i}} \text{ and} V = a^{2^{i}+ 1}+ \alpha^{2^{i}} a^{2^{2i}+ 1} \mu^{2^{i}} + \alpha a^{2^{i + 1}} \mu .$$

Using Proposition 2, this equation has at most four solutions x_i, and each x_i leads to a single y, implying that the whole system has at most four solutions.

We now show that the whole system has 4 solutions for some a ≠ 0 except for two specific values of β. Recall that we exclude the case α = 1. If V_α,β is APN, then (2) must have at most two solutions for any a ≠ 0 and any c^″. We derive from Proposition 2 that this happens if and only if, for all a ≠ 0,

$$U = 0 \text{ and\ } V \neq 0$$

or

$$U=V \text{ and\ } U \neq 0$$

or

$$U\neq 0 \text{and} \text{Tr}\left( \left( 1+\frac{V}{U}\right)^{\tau}\right)= 1 .$$

We first observe that V ≠ 0, otherwise

$$\alpha^{2^{i}} a^{2^{2i}-2^{i}} \mu^{2^{i}} + \alpha a^{2^{i}-1}\mu + 1 = 0$$

which would mean that $(\alpha a^{2^{i}-1} \mu )$ is a root of $X^{2^{i}}+X + 1$. It follows that $(\alpha a^{2^{i}-1} \mu )$ is a solution of $(X + 1)^{2^{i}+ 1}=X^{2^{i}+ 1}$, a contradiction since $x \mapsto x^{2^{i}+ 1}$ is a permutation because $\gcd (n,i)= 1$ and n is odd. Then, the first condition means that

$$\mu = \frac{(1+\alpha^{2^{i + 1}}+\alpha^{2^{i}-1}\beta)}{a^{2^{i}-1}(\alpha+\alpha^{2^{i + 1}-1})}= 0 ,$$

or equivalently

$$\beta = \alpha^{-2^{i}+ 1} + \alpha^{2^{i}+ 1} .$$

The second condition corresponds to

$$\alpha a^{2^{i}-1} \mu = 1 \Leftrightarrow 1 + \alpha^{2^{i + 1}} + \alpha^{2^{i}-1} \beta = 1 + \alpha^{2^{i + 1}-2} ,$$

which is equivalent to

$$\beta = \alpha^{2^{i}-1} + \alpha^{2^{i}+ 1} .$$

The last condition corresponds to

$$ 1 = \text{Tr}\left( \left( 1+\frac{V}{U}\right)^{\tau}\right) = \text{Tr}\left( \left( \frac{a^{2^{i}+ 1} + \alpha a^{2^{i + 1}} \mu}{\alpha^{2^{i}}a^{2^{2i}+ 1}\mu^{2^{i}}}\right)^{\tau}\right). $$

We simplify the fraction on the right-hand side as follows:

$$ \begin{array}{@{}rcl@{}} \frac{a^{2^{i}+ 1} + \alpha a^{2^{i + 1}} \mu}{\alpha^{2^{i}}a^{2^{2i}+ 1}\mu^{2^{i}}} &=& \frac{1+ a^{2^{i}-1}\alpha \mu}{a^{2^{2i}-2^{i}}\alpha^{2^{i}}\mu^{2^{i}}} \\ &=& \frac{\frac{\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i + 1}-1}+\alpha^{2^{i}}\beta}{\alpha+\alpha^{2^{i + 1}-1}}}{(\frac{\alpha+\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i}}\beta}{\alpha+\alpha^{2^{i + 1}-1}})^{2^{i}}} \\ &=& \mathcal{B_{\alpha,\beta}} , \end{array} $$

where

$$ \begin{array}{@{}rcl@{}} \mathcal{B_{\alpha,\beta}}&=&\frac{\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i + 1}-1}+\alpha^{2^{i}}\beta}{\alpha+\alpha^{2^{i + 1}-1}}\left( \frac{\alpha+\alpha^{2^{i + 1}-1}}{\alpha+\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i}}\beta}\right)^{2^{i}}\\ &=&(\alpha+\alpha^{2^{i + 1}-1})^{2^{i}-1} \times \frac{\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i + 1}-1}+\alpha^{2^{i}}\beta}{(\alpha+\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i}}\beta)^{2^{i}}}\\ &=&(\alpha+\alpha^{2^{i + 1}-1})^{2^{i}-1} \times \frac{\alpha^{2^{i + 1}+ 1}+\alpha^{2^{i + 1}-1}+\alpha^{2^{i}}\beta}{\alpha^{2^{2i + 1}+ 2^{i}}+\alpha^{2^{i}}+\alpha^{2^{2i}}\beta^{2^{i}}} . \end{array} $$

We have established in Lemma 1 that $\text {Tr}(\mathcal {B}_{\alpha ,\beta }^{\tau })$ is always equal to 0, implying that

$$\text{Tr}\left( \left( 1+\frac{V}{U}\right)^{\tau}\right) = 0 .$$

Therefore, if V_{α, β} is APN then $\beta = \alpha ^{-2^{i}+ 1} + \alpha ^{2^{i}+ 1}$ or $\beta = \alpha ^{2^{i}-1} + \alpha ^{2^{i}+ 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 $\mathbb {F}_{2^{n}}$ except on 3 particular values.

Proposition 4 (Trace Condition)

Letα ≠ 0, 1. A generalised butterfly with parametersαandβis APN if and only if

$$ \forall e \not\in \{ 0, \alpha, 1/\alpha \},\text{Tr}\left( \mathcal{A}_{\alpha}(e)^{\tau} \right) = 1 \text{ and } \beta \in \{\alpha^{2^{i}-1} + \alpha^{2^{i}+ 1} , \alpha^{-2^{i}+ 1}+\alpha^{2^{i}+ 1}\}, $$

where τ(2ⁱ − 1) ≡ 1 mod (2ⁿ − 1) and

$$ \mathcal{A}_{\alpha}(e) =\alpha^{2^{i}-1} \times \frac{e(1 + \alpha)^{2}}{(1+\alpha e)(\alpha + e)^{2^{i}}} . $$

Proof

Since we have proved in Section 2.2 that generalised butterflies with parameters (α, β₀) and (α,β₁) where $\beta _{1}= \beta _{0}^{-1} (1+\alpha )^{2(2^{i}+ 1)}$ are affine-equivalent, we only need to prove the result for $\beta = \alpha ^{2^{i}-1} + \alpha ^{2^{i}+ 1}$.

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

$$ \left\{\begin{array}{ll} R(x, y) + R(x + a, y + b) = c \\ R(y, x) + R(y + b, x + a) = d \end{array}\right. $$

(3)

for any tuple (a, b, c, d) of $\mathbb {F}_{2^{n}}$ with (a, b) ≠ (0, 0). We develop each line of this system and obtain

$$ \left\{\begin{array}{ll} (a+b\alpha)x^{2^{i}} + (a+b\alpha)^{2^{i}}x + (\alpha^{2^{i}}a+\alpha^{2^{i}-1}b)y^{2^{i}} + (\alpha a^{2^{i}}+\alpha^{2^{i}-1}b^{2^{i}})y= c_{0} \\ (\alpha^{2^{i}}b+\alpha^{2^{i}-1}a)x^{2^{i}} + (\alpha b^{2^{i}}+\alpha^{2^{i}-1}a^{2^{i}})x + (\alpha a+b)y^{2^{i}} + (\alpha a+b)^{2^{i}}y= d_{0} . \end{array}\right. $$

As α ≠ 1, we can replace the linesℓ₁ and ℓ₂ of this system by $\ell _{1} + \alpha ^{2^{i}-1} \ell _{2}$ and $\alpha ^{2^{i}-1}\ell _{1} + \ell _{2}$ to obtain a system with the exact same number of solutions. We obtain

$$ \left\{\begin{array}{ll} (a+\alpha b)(1+\alpha^{2^{i + 1}-2})x^{2^{i}}+a^{2^{i}}(1+\alpha^{2^{i + 1}-2})x+a^{2^{i}}\alpha(1+\alpha^{2^{i + 1}-2})y = c_{1} \\ (\alpha a+b)(1+\alpha^{2^{i + 1}-2})y^{2^{i}}+b^{2^{i}}(1+\alpha^{2^{i + 1}-2})y+b^{2^{i}}\alpha(1+\alpha^{2^{i + 1}-2})x = d_{1} , \end{array}\right. $$

i.e.,

$$ \left\{\begin{array}{ll} (a+\alpha b)x^{2^{i}}+a^{2^{i}}x+a^{2^{i}}\alpha y = c_{2} \\ (\alpha a+b)y^{2^{i}}+b^{2^{i}}y+b^{2^{i}}\alpha x = d_{2} , \end{array}\right. $$

which can be rewritten as

$$ \left\{\begin{array}{ll} (ax^{2^{i}} + a^{2^{i}}x) + \alpha(bx^{2^{i}}+a^{2^{i}} y) = c_{2} \\ (by^{2^{i}} + b^{2^{i}}y) + \alpha(ay^{2^{i}}+b^{2^{i}} x) = d_{2} . \end{array}\right. $$

(4)

We first consider the cases a = 0 and b = 0. Recall that a = b = 0 is excluded. If a = 0, then the first line of the system is equivalent to

$$x = \left( \frac{c_{2}}{\alpha b}\right)^{2^{n-i}} .$$

Replacing x by this value in the second line of System (4) yields an equation in y with nonzero coefficients of the form $by^{2^{i}} + b^{2^{i}}y=c_{3}$. Since gcd(i, n) = 1, this equation has at most two solutions, implying that (4) has at most two solutions (x, y). The caseb = 0 is similar.

We now suppose a ≠ 0 and b ≠ 0, which allows us to set x = ax′ and y = by′. In this context, System (4) has as many solutions as

$$ \left\{\begin{array}{ll} a^{2^{i}+ 1}(x^{\prime 2^{i}} + x^{\prime}) + \alpha a^{2^{i}}b(x^{\prime 2^{i}}+y^{\prime}) = c_{2} \\ b^{2^{i}+ 1}(y^{\prime 2^{i}} + y^{\prime}) + \alpha ab^{2^{i}}(y^{\prime 2^{i}}+x^{\prime}) = d_{2} , \end{array}\right. $$

which we rewrite using e = a/b as

$$ \left\{\begin{array}{ll} e(x^{\prime 2^{i}} + x^{\prime}) + \alpha (x^{\prime 2^{i}}+y^{\prime}) = c_{3}\\ e^{-1}(y^{\prime 2^{i}} + y^{\prime}) + \alpha (y^{\prime 2^{i}}+x^{\prime}) = d_{3} . \end{array}\right. $$

(5)

Summing its lines yields

$$ (x^{\prime 2^{i}} + x^{\prime}) (e+\alpha) + (y^{\prime 2^{i}} + y^{\prime})(e^{-1}+\alpha) = c_{3} + d_{3} . $$

If e = α, then the equation holds for precisely two values $y_{0}^{\prime }$ and $y_{1}^{\prime }$ which satisfy $y_{0}^{\prime } + y_{1}^{\prime } = 1$. The first line of the system implies in this case that $x^{\prime } = y_{i}^{\prime } + c_{3}/\alpha$ as the terms in $x^{2^{i}}$ cancel each other, meaning that the system has at most two solutions. The case e = α^− 1 is similar. We now suppose e ≠ α, α^− 1.

The first line of System (5) allows us to express y′ as a function of x′:

$$ y^{\prime} = \left( \frac{e}{\alpha} + 1\right)x^{\prime 2^{i}} + \frac{e}{\alpha}x^{\prime} + \frac{c_{3}}{\alpha} . $$

We replace y′ by this expression in the second line of (5) and obtain

$$ \begin{array}{ll} &\left( e^{-1} + \alpha \right)y^{\prime 2^{i}} + e^{-1}y^{\prime} + \alpha x^{\prime} \\ = & \left( e^{-1} + \alpha \right)\left( \left( \frac{e}{\alpha} + 1\right)x^{\prime 2^{i}} + \frac{e}{\alpha}x^{\prime} + \frac{c_{3}}{\alpha} \right)^{2^{i}} + e^{-1} \left( \left( \frac{e}{\alpha} + 1\right)x^{\prime 2^{i}} + \frac{e}{\alpha}x^{\prime} + \frac{c_{3}}{\alpha}\right)+ \alpha x^{\prime} \\ = & (e^{-1}+\alpha )\left( \frac{e}{\alpha}+ 1\right)^{2^{i}}x^{\prime 2^{2i}} + \left( (e^{-1} + \alpha)\frac{e^{2^{i}}}{\alpha^{2^{i}}} + e^{-1}\left( \frac{e}{\alpha}+ 1\right) \right)x^{\prime 2^{i}}+ \left( \frac{1}{\alpha} + \alpha\right)x^{\prime}\\ = & d_{3}^{\prime} , \end{array} $$

for some constant $d_{3}^{\prime }$. If we let $U = (1 + e/\alpha )^{2^{i}}(\alpha + 1/e)$ and V = U + 1/α + α, then the number of solutions of this equation can be computed using Proposition 2. First, U ≠ 0 and U + V ≠ 0 as α ≠ 1. Therefore, the possible number of solutions is at most equal to 4 and is given by the trace of (1 + V/U)^τ: if $\text {Tr}\left (\left (1+\frac {V}{U}\right )^{\tau }\right )= 1$ then the equation has at most 2 solutions, otherwise it has 0 or 4 solutions. It holds that

$$ \begin{array}{ll} 1+\frac{V}{U} &= \frac{\alpha^{-1} + \alpha}{(e^{-1} + \alpha)(1 + e \alpha^{-1})^{2^{i}}} \\ &= \alpha^{2^{i}-1}\frac{e(1 + \alpha)^{2}}{(1+\alpha e)(\alpha + e)^{2^{i}}} \end{array} $$

so the function is APN if and only if

$$ \text{Tr}\left( \mathcal{A}_{\alpha}(e)^{\tau} \right) = 1, \forall e \neq 0, \alpha, 1/\alpha, \text{with } \mathcal{A}_{\alpha}(e) = \alpha^{2^{i}-1} \times \frac{e(1 + \alpha)^{2}}{(1+\alpha e)(\alpha + e)^{2^{i}}} . $$

□

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$\alpha \in \mathbb {F}_{2^{n}} \setminus \{0, 1\}$,withnodd. The generalised butterfly with parametersαand$\beta =\alpha ^{2^{i}-1} + \alpha ^{2^{i}+ 1}$isAPN if and only if:

$$ \text{Tr}(F_{D}(t)^{\tau})= 1, \forall t\notin\{0,1,D\} \text{ where} F_{D}(t)=\frac{t+t^{2^{i}+ 1}}{t+D} , $$

τ(2ⁱ − 1) ≡ 1 mod (2ⁿ − 1) and D = 1/(1 + α²).

Proof

Let $F_{D}(t)=\frac {t+t^{2^{i}+ 1}}{t+D}$. Based on Proposition 4, we only have to prove that the number ofe∉{0, α,1/α} such that $\text {Tr}(\mathcal {A}_{\alpha ,i}(e)^{\tau })= 1$ is equal to the number of t∉{0,1, D} such that Tr(F_D(t)^τ) = 1. Using that 2ⁱτ ≡ 1 + τ mod (2ⁿ − 1), the term $\mathcal {A}_{\alpha ,i}(e)^{\tau }$ can be re-written as follows

$$ \begin{array}{ll} \mathcal{A}_{\alpha,i}(e)^{\tau} &= \left( \alpha^{2^{i}-1} \frac{e(1+\alpha)^{2}}{(1 + \alpha e)(\alpha + e)^{2^{i}}}\right)^{\tau} \\ &= \alpha \frac{e^{\tau}(1+\alpha)^{2\tau}}{(1 + \alpha e)^{\tau}(\alpha + e)^{2^{i}\tau}} \\ &= \alpha \frac{e^{\tau}(1+\alpha)^{2\tau}}{(1 + \alpha e)^{\tau}(\alpha + e)^{\tau+ 1}} \\ &= \frac{\alpha}{\alpha + e} \left( \frac{e(1+\alpha)^{2}}{(1 + \alpha e)(\alpha + e)}\right)^{\tau} . \end{array} $$

We further simplify this expression by reusing the change of variable introduced in [5], namely

$$ \ell = (e + \alpha)(1+\alpha)^{2} $$

which implies in particular that, for γ₀ = α +α³ and γ₁ = α^− 1 + α³:

• e ∉ {0, α, 1/α} is equivalent to ℓ∉{γ₀,0, γ₁},

• e(1 + α)² = ℓ + γ₀, and

• (1 + αe)(1 + α)² = α(ℓ + γ₁).

We deduce:

$$ \begin{array}{ll} \mathcal{A}_{\alpha,i}(e)^{\tau} &= \alpha \left( \frac{e(1+\alpha)^{2}}{(1 + \alpha e)(1+\alpha^{2}) (\alpha + e)(1+\alpha^{2}) / (1+\alpha)^{4}}\right)^{\tau}\frac{1}{\alpha + e} \\ &= \alpha \left( \frac{\ell + \gamma_{0}}{\alpha(\ell + \gamma_{1}) \ell} (1+\alpha^{4}) \right)^{\tau}\frac{1+\alpha^{2}}{\ell} \\ &= \gamma_{0} \left( \frac{\gamma_{1}(\ell + \gamma_{0})}{(\ell + \gamma_{1}) \ell} \right)^{\tau}\frac{1}{\ell} . \end{array} $$

As a sanity check, if we let τ = 1, we can see that we obtain

$$ \mathcal{A}_{\alpha,i}(e) = \frac{\gamma_{0}\gamma_{1}}{\ell^{2}} \times \frac{\ell + \gamma_{0}}{\ell + \gamma_{1}} $$

which is exactly the equation Canteaut et al. derived on page 7585 of [5].

We further let γ₁/v =ℓ, which is well-defined since v ≠ 0. We note that γ₀/γ₁ = (1 + α^− 2)^− 1 =:C (where this notation does not correspond to any previously defined value). As a consequence, it can be checked that, whenℓ varies in $\mathbb {F}_{2^{n}} \setminus \{ \gamma _{0}, 0, \gamma _{1} \}$, then v takes all values in $\mathbb {F}_{2^{n}} \setminus \{ 1/C, 0, 1 \}$. We can then write:

$$ \begin{array}{ll} \mathcal{A}_{\alpha,i}(e)^{\tau} &= \gamma_{0} \left( \frac{{\gamma_{1}^{2}}v^{-1} + \gamma_{0}\gamma_{1}}{(\gamma_{1}v^{-1} + \gamma_{1}) \gamma_{1}v^{-1}} \right)^{\tau}v/\gamma_{1} \\ &= \gamma_{0}/\gamma_{1} \left( \frac{v^{-1} + \gamma_{0}/\gamma_{1}}{(v^{-1} + 1) v^{-1}} \right)^{\tau}v \\ &= C \left( \frac{v^{-1} + C}{(v^{-1} + 1) v^{-1}} \right)^{\tau}v \\ &= C \left( \frac{v + Cv^{2}}{1 + v} \right)^{\tau}v \\ &= C \left( \frac{v + Cv^{2}}{1 + v}v^{2^{i}-1} \right)^{\tau} \\ &= C \left( \frac{v^{2^{i}} + Cv^{2^{i}+ 1}}{1 + v} \right)^{\tau} . \end{array} $$

We now let v = (t + 1)/C, so thatv∉{1/C,0,1} becomes t∉{0,1, D} where D = 1 + C = 1 + 1/(1 + α^− 2) = 1/(1 + α²). Thus, we can write:

$$ \begin{array}{ll} v^{2^{i}} + Cv^{2^{i}+ 1} &= (t + 1)^{2^{i}}C^{-2^{i}} + C (t + 1)^{2^{i}+ 1} C^{-2^{i}-1} \\ &= C^{-2^{i}}(t^{2^{i}} + 1 + t^{2^{i}+ 1} + t^{2^{i}} + t + 1) \\ &= C^{-2^{i}}(t^{2^{i}+ 1} + t) \end{array} $$

and v + 1 = C^− 1(t + 1 + C). The expression then becomes

$$ \mathcal{A}_{\alpha,i}(e)^{\tau} = C \left( \frac{C^{-2^{i}}(t + t^{2^{i}+ 1})}{C^{-1}(t + 1 + C)} \right)^{\tau} = \left( \frac{t + t^{2^{i}+ 1}}{t + D} \right)^{\tau} = F_{D}(t)^{\tau} , $$

so we can conclude that the number of e∉{0, α,1/α} such that $\text {Tr}\left (\mathcal {A}_{\alpha ,i}(e)^{\tau } \right ) = 1$ is equal to the number of t∉{0,1, D} such that Tr (F_D(t)^τ) = 1. □

5 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 n ≤ 3. This statement is given by the following proposition that we prove below.

Proposition 6

If the refined trace condition of Proposition 5 holds thenn ≤ 3.

Proof

Suppose that the refined trace condition holds for some D, i andα. Then we have □

$$ \text{Tr}\left( F_{D}(x)^{\tau} \right) = 1, \forall x \not\in \{ 0, 1, D \} $$

with $F_{D}(x) = (x^{2^{i}+ 1}+x)/(x + D)$ and D = 1/(1 + α²). Let Im(F_D) be defined by

$$ \text{Im}(F_{D}) = \left\{ c \in \mathbb{F}_{2^{n}}, \exists x \in \mathbb{F}_{2^{n}} \backslash \{ 0,1,D \}, F_{D}(x) = c \right\} . $$

Since F_D is a well-defined function, we have

$$ \bigcup\limits_{c \in \text{Im}(F_{D})} \left\{ x \in \mathbb{F}_{2^{n}}\backslash \{ 0, 1, D \}, F_{D}(x) = c \right\} = \mathbb{F}_{2^{n}}\backslash \{ 0, 1, D \} $$

so that

$$ \sum\limits_{c \in \text{Im}(F_{D})} \left| \left\{ x \in \mathbb{F}_{2^{n}}\backslash \{0, 1, D \}, F_{D}(x) = c \right\} \right| = 2^{n}-3 . $$

As F_D(0) = F_D(1) = 0 and since these are the only two preimages of 0 under F_D, we have that 0∉Im(F_D) when the input varies in $\mathbb {F}_{2^{n}}\backslash \{ 0, 1, D \}$ and we can therefore simplify this expression into

$$ \sum\limits_{c \in \text{Im}(F_{D})\backslash\{0\}} \left| \left\{ x \in \mathbb{F}_{2^{n}}\backslash \{ D \}, F_{D}(x) = c \right\} \right| = 2^{n}-3 . $$

(6)

Let us rewrite this sum using another expression of c.

Suppose that c = F_D(x) for some x∉{0,1, D}. Then $x^{2^{i}+ 1} + x = c(x + D)$, or, equivalently,

$$ x^{2^{i}+ 1} + x(c + 1) + Dc = 0 . $$

If c = 1 In this case, the equation is equivalent to $x^{2^{i}+ 1} + D = 0$. Thus, c = 1 has exactly one preimage in $\mathbb {F}_{2^{n}} \backslash \{ 0, 1, D \}$ since $\gcd (i,n)= 1$ (and hence $x \mapsto x^{2^{i}+ 1}$ is a permutation).

If c ≠ 1 We then have that c = F_D(x) if and only if $x^{2^{i}+ 1} + (c + 1)x + c D = 0$. Substituting x with D yields $D^{2^{i}} = 1$, which is impossible as this is equivalent to α = 0. Hence, the condition F_D(x) = c already impliesx ≠ D. Using $x = u (1+c)^{2^{n-i}}$, we rewrite this equation into

$$ u^{2^{i}+ 1}(1+c)^{2^{n-i}(2^{i}+ 1)} + u(1+c)^{2^{n-i}+ 1} + Dc = 0 $$

which, after a division by $(1+c)^{2^{n-i}+ 1}$, is seen to be equivalent to

$$ u^{2^{i}+ 1} + u + g_{D}(c) = 0 , \text{ where} \ g_{D}(c) = \frac{cD}{(1+c)^{2^{n-i}+ 1}} . $$

We deduce that

$$ \left| \left\{ x \in \mathbb{F}_{2^{n}}\backslash \{0, 1, D \}, F_{D}(x) = c \right\} \right| = \left|\left\{ u \in \mathbb{F}_{2^{n}}, u^{2^{i}+ 1}+u+g_{D}(c)= 0 \right\} \right| $$

when c ≠ 1.

As a consequence, we can rewrite (6) as

$$ \begin{array}{@{}rcl@{}} 2^{n}-3 &=& \left|\{x \in \mathbb{F}_{2^{n}} \backslash \{ 0,1,D \}, F_{D}(x)= 1\} \right| \\ &&+ \sum\limits_{c \in \text{Im}(F_{D}) \backslash \{0, 1 \}} \left| \left\{ u \in \mathbb{F}_{2^{n}}, u^{2^{i}+ 1}+u+g_{D}(c)= 0 \right\} \right| \end{array} $$

which is equivalent to

$$ 2^{n}-4 = \sum\limits_{c \in \text{Im}(F_{D}) \backslash \{0, 1 \}} \left|\left\{ u \in \mathbb{F}_{2^{n}}, u^{2^{i}+ 1}+u+g_{D}(c)= 0 \right\} \right| . $$

(7)

Because of Proposition 1, we have that $u^{2^{i}+ 1} + u + g_{D}(c) = 0$ has exactly 1 or 3 solutions. Indeed, it cannot have 0 solution since it is equivalent to $F_{D}\left (u(1+c)^{2^{n-i}}\right ) = c$ which, by definition of c, has at least one solution. Thus, $g_{D}(c) \in \mathcal {S}_{1} \cup \mathcal {S}_{3}$, where ₁ and ₃ are defined as in Proposition 1.

Let T be the set defined as

$$ T=\left\{g_{D}(c), c\in\text{Im}(F_{D}) \backslash \{0, 1 \}\right\} . $$

Then (7) can be re-written as

$$ 2^{n}-4 = \left| T\cap \mathcal{S}_{1} \right| + 3 \times \left| T \cap \mathcal{S}_{3} \right| . $$

(8)

Let us now show that |T| = |Im(F_D)∖{0,1}|. Let $a^{\prime }=\frac {c}{(c + 1)^{2^{n-i}+ 1}}$ and let us investigate the number of c ∈Im(F_D) that correspond to the same a′. Note that

$$\frac{c}{(c + 1)^{2^{n-i}+ 1}}=\frac{1}{(c + 1)^{2^{n-i}+ 1}}+\frac{1}{(c + 1)^{2^{n-i}}} ,$$

and, by the substitution $b=\frac {1}{(c + 1)^{2^{n-i}}}$, we get

$$b^{2^{i}+ 1}+b+a^{\prime}= 0 .$$

In order to figure out the number of b corresponding to a given a′, we will apply Proposition 1. To this end, we compute the following trace:

$$ \begin{array}{@{}rcl@{}}&&\text{Tr}\left( (1+b^{-1})^{\tau}\right)\\ =&&\text{Tr}\left( \left( 1+(c + 1)^{2^{n-i}}\right)^{\tau}\right)\\ =&&\text{Tr}\left( \left( 1+\left( \frac{x^{2^{i}+ 1}+D}{x+D}\right)^{2^{n-i}}\right)^{\tau}\right)\\ =&&\text{Tr}\left( \left( \frac{x^{2^{n-i}+ 1}+x^{2^{n-i}}}{x^{2^{n-i}}+D^{2^{n-i}}}\right)^{\tau}\right)\\ =&&\text{Tr}\left( \left( \frac{x^{2^{n-i}+ 1}+x^{2^{n-i}}}{x^{2^{n-i}}+D^{2^{n-i}}}\right)^{2^{i}\tau}\right)\\ =&&\text{Tr}\left( \left( \frac{x^{2^{i}+ 1}+x}{x+D}\right)^{\tau}\right)\\ =&&\text{Tr}(F_{D}(x)^{\tau}) . \end{array} $$

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 $a^{\prime }=\frac {c}{(c + 1)^{2^{n-i}+ 1}}$ corresponds to a unique $b=\frac {1}{(c + 1)^{2^{n-i}}}$ and, therefore, that |T| = |Im(F_D)∖{0, 1}|.

We define

$$ i_{1} = \left| T\cap \mathcal{S}_{1} \right| \text{ and\ } i_{3} = \left| T \cap \mathcal{S}_{3} \right| . $$

From (8), we know that 2ⁿ − 4 =i₁ + 3i₃. The values of i₁ and i₃ are upperbounded by the sizes of $\mathcal {S}_{1}$ and $\mathcal {S}_{3}$ respectively which are given by Proposition 1: i₁ ≤ 2^n− 1 − 1 and i₃ ≤ (2^n− 1 − 1)/3. Furthermore, i₁ + i₃ = |T| = |Im(F_D)∖{0,1}| and, since we have assumed that the trace ofF_D(x)^τ is constant and equal to 1, the size of the image of F_D is upperbounded by 2^n− 1, which we decrement because we remove 1 from Im(F_D). We deduce that

$$ \begin{array}{@{}rcl@{}} i_{1} &\leq& 2^{n-1}-1 \\ i_{3} &\leq& (2^{n-1}-1)/3 \\ i_{1} + i_{3} &\leq& 2^{n-1}-1 \\ i_{1} + 3i_{3} &=& 2^{n}-4 . \end{array} $$

It holds that i₁ + 3i₃ = (i₁ + i₃) + 2i₃ which we can upperbound by 2^n− 1 − 1 + 2(2^n− 1 − 1)/3, a quantity equal to

$$ \begin{array}{ll} 2^{n-1}-1 + \frac{2(2^{n-1}-1)}{3} &= \frac{3 (2^{n-1}-1) + 2(2^{n-1}-1)}{3} \\ &= \frac{6 \times 2^{n-1} - 2^{n-1} - 5}{3} \\ &= 2^{n} - \frac{2^{n-1} + 5}{3} . \end{array} $$

As a consequence, if (2^n− 1 + 5)/3 > 4 then we have a contradiction becausei₁ + 3i₃ would then be both equal to 2ⁿ − 4 and strictly smaller than 2ⁿ − 4. This inequality can be re-written as follows:

$$ \frac{2^{n-1}+ 5}{3} > 4 \Leftrightarrow 2^{n-1} > 7 . $$

Thus, if the refined trace condition holds then we have a contradiction whenever 2^n− 1 > 7 or, equivalently, n > 3. We conclude that the refined trace condition impliesn ≤ 3.

6 Conclusion

Since generalised butterflies defined in [11] have very good differential uniformity and nonlinearity, and, moreover, contain the only known APN permutation, it was natural to wonder whether 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.