The Number of Almost Perfect Nonlinear Functions Grows Exponentially

Abstract

Almost perfect nonlinear (APN) functions play an important role in the design of block ciphers as they offer the strongest resistance against differential cryptanalysis. Despite more than 25 years of research, only a limited number of APN functions are known. In this paper, we show that a recent construction by Taniguchi provides at least $\frac{\varphi (m)}{2}\left\lceil \frac{2^m+1}{3m} \right\rceil$ inequivalent APN functions on the finite field with ${2^{2m}}$ elements, where $\varphi$ denotes Euler’s totient function. This is a great improvement of previous results: for even m, the best known lower bound has been $\frac{\varphi (m)}{2}\left( \lfloor \frac{m}{4}\rfloor +1\right)$; for odd m, there has been no such lower bound at all. Moreover, we determine the automorphism group of Taniguchi’s APN functions.

1 Introduction

A function $f:\mathbb {F}_{2^n} \rightarrow \mathbb {F}_{2^n}$ is called almost perfect nonlinear (APN) if the equation

$$\begin{aligned} f(x+a)+f(x)=b \end{aligned}$$

has exactly 0 or 2 solutions for any $b\in \mathbb {F}_{2^n}$ and any nonzero $a\in \mathbb {F}_{2^n}$. APN functions were introduced in 1994 by Nyberg [28]. She defined them as the mappings with the highest resistance to differential cryptanalysis, which is one of the most important cryptanalyst tools for block ciphers and was introduced in 1991 by Biham and Shamir [3]. APN functions and other functions with low differential uniformity are widely used in the design of symmetric key cryptographic algorithms such as the S-boxes in nonlinear layers of block ciphers. For instance, in the hardware-oriented MISTY ciphers [27], the 16-bit state is split into two parts of different odd lengths on which two APN permutations are used; in the AES algorithm [15], an affine transformation of the inverse function over $\mathbb {F}_{2^8}$ which has differential 4-uniformity was chosen as the S-box. Blondeau and Nyberg [4] provide an overview of theoretical results and applications of APN functions in cryptography.

APN functions are also strongly connected with coding theory and finite geometry. In particular, quadratic APN functions are equivalent to a special type of dimensional dual hyperovals; see the work by Yoshiara [31], Edel [21], and Dempwolff and Edel [16] for more details.

Since their introduction, APN functions have been studied intensively. For an extended overview of these functions, we refer to the survey by Pott [29]. For a long time, only very few APN functions were known, all of which power functions of the form $x \mapsto x^d$. In 2006, Edel et al.  [20] reported the first two examples of non-power APN functions on $\mathbb {F}_{2^{10}}$ and $\mathbb {F}_{2^{12}}$. Since then, quite a few infinite families of non-power APN functions have been found. A recent list of them was given by Budaghyan et al. [10, Table 3].

Except for some sporadic examples, every known non-power APN function is equivalent to a quadratic APN function that can be written in the form $\sum _{0\le i<j\le n-1}\alpha _{i,j} x^{2^i+2^j}+\sum _{0\le i \le n-1}\beta _i x^{2^i} +\gamma$ with $\alpha _{i,j},\beta _i,\gamma \in \mathbb {F}_{2^n}$ for $i,j = 0, \dots , n-1$ and not all $\alpha _{i,j}=0$. By equivalent, we mean there exists a CCZ-equivalence transformation between functions over $\mathbb {F}_{2^n}$. This equivalence relation was introduced in 1998 by Carlet et al. [14], it preserves the APN property, and it is the most general equivalence relation of functions from $\mathbb {F}_{2^n}$ to $\mathbb {F}_{2^n}$.

When n is odd, several known APN functions are also permutations on $\mathbb {F}_{2^n}$. The most fascinating problem regarding APN functions is to find APN permutations on $\mathbb {F}_{2^{n}}$ where n is even. So far, only one such function is known: it was found by Browning et al. [7] on $\mathbb {F}_{2^6}$. This sporadic example is also equivalent to a quadratic APN function.

A very basic and natural question concerning APN functions is the following.

Question 1

How many CCZ-inequivalent APN functions on $\mathbb {F}_{2^n}$ exist for a given n?

Despite its simplicity, this question has not been satisfactorily answered yet. By checking the known APN functions, see Sect. 3, we first notice that all the power APN functions only provide very few inequivalent examples. Little is known, however, about the number of inequivalent non-power APN functions as it is, in general, a very hard problem to prove the non-equivalence of two functions. Only for small dimensions, this problem can be solved computationally; for larger dimensions, one has to solve it theoretically. Studying a special family of non-power APN functions introduced by Pott and the second author [33], the present authors [26] recently presented a first benchmark to answer Question 1 for certain fields: they showed that there are at least $\frac{1}{2}\varphi (m)\left( \lfloor m/4\rfloor +1\right)$ inequivalent APN functions on $\mathbb {F}_{2^{2m}}$ with m even, where $\varphi$ is Euler’s totient function.

In this paper, we considerably improve this lower bound and extend it to $\mathbb {F}_{2^{2m}}$ for any $m \ge 2$. We investigate a family of APN functions defined on $\mathbb {F}_{2^{2m}}$ for any $m\ge 2$ that has been found by Taniguchi [30]. By completely determining the equivalence of members among this family, we show that the number of inequivalent APN functions on $\mathbb {F}_{2^{2m}}$ is at least

$$\begin{aligned} \frac{\varphi (m)}{2}\left\lceil \frac{2^m+1}{3m} \right\rceil . \end{aligned}$$

As a corollary, our results enable us to determine the automorphism group of the Taniguchi APN functions.

The paper is organized as follows. In Sect. 2, we introduce all necessary definitions and notations. In Sect. 3, we give an overview of the known classes of APN functions and introduce the constructions by Taniguchi [30] and Pott and the second author [33]. Afterwards, we solve the equivalence problem for the Taniguchi APN functions and present their automorphism group in Sect. 4. In Sect. 5, we use these results to establish the aforementioned lower bound on the total number of inequivalent APN functions on $\mathbb {F}_{2^{2m}}$. To conclude, we point out several open problems regarding APN functions in Sect. 6.

2 Preliminaries

In this section, we present all the definitions and basic results needed to follow the paper. Denote by $\mathbb {F}_{2}^n$ the n-dimensional vector space over the finite field $\mathbb {F}_2$ with two elements. A function from $\mathbb {F}_2^n$ to $\mathbb {F}_2^m$ is called a vectorial Boolean function if $m \ge 2$ or simply a Boolean function if $m=1$. In this paper, we will only consider vectorial Boolean functions from $\mathbb {F}_2^n$ to $\mathbb {F}_2^n$, we say functions on $\mathbb {F}_2^n$. In most cases, we identify the n-dimensional vector space $\mathbb {F}_2^n$ over $\mathbb {F}_{2}$ with the finite field $\mathbb {F}_{2^n}$ with $2^n$ elements. This will allow us to use finite field operations and notations. Note that any function on the finite field $\mathbb {F}_{2^n}$ can be written as a univariate polynomial mapping of degree at most $2^n-1$. Furthermore, denote by $\mathbb {F}_{2^n}^*$ the multiplicative group of $\mathbb {F}_{2^n}$.

Besides our definition given above, there are several equivalent definitions of almost perfect nonlinear functions. We refer to Budaghyan [9] and Pott [29] for an extended overview of these functions. In this paper, we will only consider quadratic APN functions. We define this term using the coordinate function representation of a function on $\mathbb {F}_2^n$.

Definition 1

Let $f : \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n$ be a vectorial Boolean function defined by n Boolean coordinate functions $f_1, \dots , f_n: \mathbb {F}_2^n \rightarrow \mathbb {F}_2$ that are given in their algebraic normal form, that is,

$$\begin{aligned} f(x_1,\dots ,x_n) = \begin{pmatrix} f_1(x_1, \dots , x_n)\\ \vdots \\ f_n(x_1, \dots , x_n) \end{pmatrix}. \end{aligned}$$

The maximal degree of the coordinate functions $f_1, \dots , f_n$ is called the algebraic degree of f. We call a function of algebraic degree 2 quadratic and a function of algebraic degree 1 affine. If f is affine and has no constant term, we call f linear.

In polynomial mapping representation, any quadratic function f on $\mathbb {F}_{2^n}$ can be written in the form

$$\begin{aligned} f(x) = \sum _{\begin{array}{c} i,j = 0 \\ i < j \end{array}}^{n-1}\alpha _{i,j} x^{2^i+2^j} + \sum _{i = 0}^{n-1}\beta _i x^{2^i} + \gamma , \end{aligned}$$

and any affine function $f : \mathbb {F}_{2^n} \rightarrow \mathbb {F}_{2^n}$ can be written as

$$\begin{aligned} f(x) = \sum _{i=0}^{n-1}\beta _i x^{2^i} + \gamma . \end{aligned}$$

If f is affine and $\gamma = 0$, then f is linear. Similar terms are used to describe polynomials over $\mathbb {F}_{2^n}$. Denote by $\mathbb {F}_{2^n}[X]$ the univariate polynomial ring over $\mathbb {F}_{2^n}$. A polynomial of the form

$$\begin{aligned} P(X) = \sum _{i\ge 0}\alpha _i X^{2^i} \end{aligned}$$

is called a linearized polynomial. Note that there is a one-to-one correspondence between linear functions on $\mathbb {F}_2^n$ and linearized polynomials in $\mathbb {F}_{2^n}[X] / (X^{2^n}-X)$. In the same way as for univariate polynomials, we define a linearized polynomial in the multivariate polynomial ring $\mathbb {F}_{2^n}[X_1,\dots , X_r]$ as a polynomial of the form

$$\begin{aligned} P(X_1,\dots ,X_r) = \sum _{j=1}^{r} \left( \sum _{i\ge 0}\alpha _{i,j} X_j^{2^i}\right) . \end{aligned}$$

We will use such polynomials to study the equivalence of APN functions. In this paper, we are interested in inequivalent APN functions. There are several notions of equivalence between vectorial Boolean functions that preserve the APN property. We list them in the following definition.

Definition 2

Two functions $f,g : \mathbb {F}_{2^n} \rightarrow \mathbb {F}_{2^n}$ are called

• Carlet–Charpin–Zinoviev equivalent (CCZ-equivalent), if there is an affine permutation C on $\mathbb {F}_{2^n} \times \mathbb {F}_{2^n}$ such that

  $$\begin{aligned} C(G_f) = G_g, \end{aligned}$$

  where $G_f = \{(x,f(x)) : x \in \mathbb {F}_{2^n}\}$ is the graph of f,

• extended affine equivalent (EA-equivalent) if there exist three affine functions $A_1,A_2,A_3 : \mathbb {F}_{2^n} \rightarrow \mathbb {F}_{2^n}$, where $A_1$ and $A_2$ are permutations, such that

  $$\begin{aligned} f(A_1(x)) = A_2(g(x)) + A_3(x), \end{aligned}$$

• extended linearly equivalent (EL-equivalent) if they are EA-equivalent and $A_1,A_2$ and $A_3$ are linear,

• affine equivalent if they are EA-equivalent and $A_3(x) = 0$,

• linearly equivalent if they are EL-equivalent and $A_3(x)=0$.

In the case of EL- or linear equivalence, we usually write L, N, M instead of $A_1,A_2,A_3$ to underline the linearity of these functions. CCZ-equivalence is the most general known notion of equivalence that preserves the APN property. Obviously, linear equivalence implies affine equivalence, and affine equivalence implies EA-equivalence. Similarly, linear equivalence implies EL-equivalence, and EL-equivalence implies EA-equivalence. Moreover, it is well known that EA-equivalence implies CCZ-equivalence, but, in general, the converse is not true. For quadratic APN functions, however, Yoshiara [32] proved that also the converse holds.

Proposition 2.1

[32, Theorem 1] Let f and g be quadratic APN functions on a finite field $\mathbb {F}_{2^n}$ with $n \ge 2$. Then, f is CCZ-equivalent to g if and only if f is EA-equivalent to g.

In this paper, Proposition 2.1 will allow us to prove the CCZ-inequivalence of certain quadratic APN functions by showing that they are EA-inequivalent.

We characterize some of the mappings that define an equivalence of two functions in the sense of Definition 2 in more detail. Let f, g be functions on $\mathbb {F}_{2^n}$, and denote their graphs by $G_f$ and $G_g$, respectively. We call an affine permutation C on $\mathbb {F}_{2^n} \times \mathbb {F}_{2^n}$ such that $C(G_f) = G_g$ a CCZ-mapping from g to f. Similarly to [12], we define an EL-mapping $C_{EL} =(L,M,N)$ from g to f as a linear CCZ-mapping from g to f satisfying

$$\begin{aligned} f(L(x)) = N(g(x)) + M(x), \end{aligned}$$

where L, N are linear permutations on $\mathbb {F}_{2^n}$ and M is a linear map on $\mathbb {F}_{2^n}$. Such an EL-mapping $C_{EL}$ from g to f may be represented as a formal matrix

$$\begin{aligned} C_{EL} = \begin{bmatrix}L &{}0\\ M&{} N\end{bmatrix} \end{aligned}$$

corresponding to the calculation

$$\begin{aligned} \begin{bmatrix} L &{} 0\\ M &{} N \end{bmatrix} \begin{bmatrix} x\\ g(x)\end{bmatrix} = \begin{bmatrix} L(x)\\ N(g(x))+M(x)\end{bmatrix} = \begin{bmatrix} y\\ f(y) \end{bmatrix}. \end{aligned}$$

We, moreover, define an EA-mapping $C_{EA} = (L,M,N,a,b)$ from g to f as a CCZ-mapping from g to f whose linear part is an EL-mapping. It is characterized by L, M, N as above and two elements $a,b \in \mathbb {F}_{2^n}$ such that

$$\begin{aligned} f(L(x) + a) = N(g(x)) + M(x) + b. \end{aligned}$$

(1)

Of particular interest are equivalence mappings from f to f, that are mappings preserving the graph of f.

Definition 3

For a function $f: \mathbb {F}_{2^n} \rightarrow \mathbb {F}_{2^n}$ with graph $G_f$, we call an affine permutation $\mathcal {A}$ on $\mathbb {F}_{2^n} \times \mathbb {F}_{2^n}$ with $\mathcal {A}(G_f) = G_f$ an automorphism of f. We denote the set of all such mappings by $\hbox {Aut}(f)$. If $\mathcal {A}$ is an EA-mapping, we say that $\mathcal {A}$ is an EA-automorphism of f, and we denote the set of all EA-automorphisms by $\hbox {Aut}_{EA}(f)$. Analogously, if $\mathcal {A}$ is an EL-mapping, we say that $\mathcal {A}$ is an EL-automorphism of f, and we denote the set of all EL-automorphisms by $\hbox {Aut}_{EL}(f)$.

Note that $\hbox {Aut}(f), \hbox {Aut}_{EA}(f)$ and $\hbox {Aut}_{EL}(f)$ each form a group under composition, see [12], and $\hbox {Aut}_{EL}(f)$ is a subgroup of $\hbox {Aut}_{EA}(f)$, which in turn is a subgroup of $\hbox {Aut}(f)$. Hence, we simply call $\hbox {Aut}(f)$ the automorphism group of f, and we call $\hbox {Aut}_{EA}(f)$ and $\hbox {Aut}_{EL}(f)$ the automorphism group of f under EA- or EL-equivalence, respectively.

All the functions we study in this paper are quadratic and have no constant term. We show that if any two such functions f and g are EA-equivalent, they are also EL-equivalent.

Proposition 2.2

Suppose f and g are EA-equivalent quadratic functions on $\mathbb {F}_2^n$ with $f(0) = g(0) = 0$, and denote by $C_{EA}=(L,M,N,a,b)$ an EA-mapping from g to f. Define a mapping $D_{f,L,a}$ on $\mathbb {F}_2^n$ as

$$\begin{aligned} D_{f,L,a}(x) = f(L(x)+a) + f(L(x)) + f(a). \end{aligned}$$

Then, $b = f(a)$, the functions f and g are EL-equivalent, and $C_{EA}$ uniquely defines an EL-mapping $C_{EL} = (L,M+D_{f,L,a},N)$ from g to f.

Proof

Recall that $C_{EA}$ satisfies (1). As f is quadratic, it is easy to confirm that $D_{f,L,a}$ is linear for $a \ne 0$ and zero for $a = 0$. Combining (1) with the definition of $D_{f,L,a}$, we obtain

$$\begin{aligned} f(L(x)) = N(g(x)) + M(x) + D_{f,L,a}(x) + b + f(a). \end{aligned}$$

As $f(0) = g(0) = 0$ and $L,N,M,D_{f,L,a}$ have no constant part either, it follows that $b = f(a)$, which implies

$$\begin{aligned} f(L(x)) = N(g(x)) + M(x) + D_{f,L,a}(x). \end{aligned}$$

Consequently, $C_{EA}$ corresponds to an EL-mapping $C_{EL}$ from g to f of the shape

$$\begin{aligned} \begin{bmatrix}L&{}0\\ M + D_{f,L,a}&{}N \end{bmatrix}, \end{aligned}$$

that is uniquely determined by $C_{EA}$. $\square$

With the help of Proposition 2.2, we can also establish a connection between the automorphism groups $\hbox {Aut}_{EA}(f)$ and $\hbox {Aut}_{EL}(f)$ of a quadratic function f with no constant part. Proposition 2.3 may be well-known. We need the definition of a semidirect product first. Let G be a group with identity element e. Let H and N be two subgroups of G. If N is normal, $G=NH$ and $N\cap H=\{e\}$, then we say G is a semidirect product of N and H and write

$$\begin{aligned} G= N\rtimes H. \end{aligned}$$

Proposition 2.3

Let f be a quadratic function on $\mathbb {F}_{2^n}$ with $f(0) = 0$. Then,

$$\begin{aligned} \hbox {Aut}_{EA}(f) = T_f \rtimes \hbox {Aut}_{EL}(f), \end{aligned}$$

where $T_f$ is isomorphic to the additive group $(\mathbb {F}_{2^n},+)$ of $\mathbb {F}_{2^n}$.

Proof

By Proposition 2.2, every EA-automorphism of f given by (L, M, N, a, b) can be uniquely written as the composition of an EL-automorphism $\varphi$ of the shape

$$\begin{aligned} \varphi : \begin{bmatrix} x\\ y \end{bmatrix} \mapsto \begin{bmatrix} L &{} 0\\ \tilde{M} &{} N \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix}, \end{aligned}$$

(2)

where $\tilde{M}=M + D_{f,L,a}$ for $D_{f,L,a}$ as defined in Proposition 2.2, and a map $\tau _a$ of the shape

$$\begin{aligned} \tau _a: \begin{bmatrix} x\\ y \end{bmatrix} \mapsto \begin{bmatrix} I &{} 0\\ D_{f,I,a} &{} I \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} + \begin{bmatrix} a\\ f(a) \end{bmatrix}, \end{aligned}$$

where I is the identity map on $\mathbb {F}_{2^n}$.

Note that the set of all $\varphi$ is $\hbox {Aut}_{EL}(f)$. Clearly, $\tau _a$ is also an EA-automorphism of f mapping (x, f(x)) to $(x+a, f(x+a))$ for any $x\in \mathbb {F}_{2^n}$. The set of all $\tau _a$ with $a\in \mathbb {F}_{2^n}$ forms a subgroup $T_f$ of $\hbox {Aut}_{EA}(f)$, which is isomorphic to $(\mathbb {F}_{2^n}, +)$. Hence $\hbox {Aut}_{EA}(f) = T_f \hbox {Aut}_{EL}(f)$. Moreover, it is obvious that the identity map on $\mathbb {F}_{2^n} \times \mathbb {F}_{2^n}$ is the unique common element of $T_f$ and $\hbox {Aut}_{EL}(f)$

It remains to show that $T_f$ is a normal subgroup of $\hbox {Aut}_{EA}(f)$. We do so by verifying that

$$\begin{aligned} \tau _{a} \circ \varphi =\varphi \circ \tau _{L^{-1}(a)}. \end{aligned}$$

(3)

A similar result was given by Dempwolff and Edel [16, Lemma 2.5]. The left-hand side of (3), $\tau _a\circ \varphi$, is exactly the EA-automorphism (L, M, N, a, b) we decomposed above. The right-hand side of (3), $\varphi \circ \tau _{L^{-1}(a)}$, maps (x, f(x)) to

$$\begin{aligned} \varphi \circ \tau _{L^{-1}(a)} \begin{bmatrix} x\\ f(x) \end{bmatrix}&= \begin{bmatrix} L &{} 0\\ \tilde{M} &{} N \end{bmatrix} \begin{bmatrix} x+L^{-1}(a)\\ f(x+L^{-1}(a)) \end{bmatrix}\nonumber \\&= \begin{bmatrix} L(x)+a\\ N(f(x+L^{-1}(a))) +\tilde{M}(x+L^{-1}(a)) \end{bmatrix}. \end{aligned}$$

(4)

We consider

$$\begin{aligned} N(f(x+L^{-1}(a))) +\tilde{M}(x+L^{-1}(a)). \end{aligned}$$

(5)

Adding $N(f(x)) + N(f(L^{-1}(a)))$ twice and using the definition of $\tilde{M}$, (5) equals

$$\begin{aligned}&N(f(x)) + M(x) +N(f(L^{-1}(a))+ M(L^{-1}(a))\\&\quad +D_{f,L,a}(x) +N(f(x+L^{-1}(a)))+N(f(x))+N(f(L^{-1}(a))) +D_{f,L,a}(L^{-1}(a)). \end{aligned}$$

First, note that $D_{f,L,a}(L^{-1}(a))=0$. Second, as we have $f(L(x)) = N(f(x)) +M(x) +D_{f,L,a}(x)$ by the definition of $\varphi$, it follows that

$$\begin{aligned}&N(f(x+L^{-1}(a))) + N(f(x)) + N(f(L^{-1}(a)))\\&\quad = f(L(x)+a) + f(L(x)) + f(a) = D_{f,L,a}(x). \end{aligned}$$

Third, using the same reasoning as before and recalling that $D_{f,L,a}(L^{-1}(a))=0$, we have

$$\begin{aligned} N(f(L^{-1}(a))+ M(L^{-1}(a))=f(a)+D_{f,L,a}(L^{-1}(a))=f(a). \end{aligned}$$

Consequently, we obtain

$$\begin{aligned} N(f(x+L^{-1}(a))) +\tilde{M}(x+L^{-1}(a)) = N(f(x)) + M(x) + f(a), \end{aligned}$$

which, considering (4), means that $\varphi \circ \tau _{L^{-1}(a)}$ also describes the EA-automorphism (L, M, N, a, b). Therefore, by definition, $\hbox {Aut}_{EA}(f)= T_f \rtimes \hbox {Aut}_{EL}(f)$. $\square$

We remark that Proposition 2.3 enables us to determine the automorphism group $\hbox {Aut}_{EA}(f)$ under EA-equivalence of any quadratic function f on $\mathbb {F}_{2^n}$, also if $f(0) \ne 0$. To obtain $\hbox {Aut}_{EA}(f)$, we only have to apply a conjugation of a translation on $\hbox {Aut}_{EA}(f+f(0))$, which we can determine with Proposition 2.3.

Regarding the automorphism groups of quadratic APN functions, we may say even more: the following lemma follows from Yoshiara’s [32] proof of Proposition 2.1 in combination with a result by Dempwolff and Edel [16, Theorem 4.10].

Lemma 2.4

Let f be a quadratic APN function on the finite field $\mathbb {F}_{2^n}$, where $n \ge 4$. Then,

$$\begin{aligned} \hbox {Aut}(f) = \hbox {Aut}_{EA}(f). \end{aligned}$$

We close this section by introducing the general framework we use to study the equivalence of functions in the remainder of this paper. We will mostly consider functions on finite fields of even extension degree. Such functions can be represented in a bivariate description as a map on $\mathbb {F}_{2^m}^2 = \mathbb {F}_{2^m}\times \mathbb {F}_{2^m}$ with two coordinate functions. As all the functions we study are quadratic and have no constant term, we may use Proposition 2.1 in combination with Proposition 2.2 to study their CCZ-equivalence by focusing on EL-mappings. We describe EL-equivalence as follows: Two functions $f,g : \mathbb {F}_{2^m}^2 \rightarrow \mathbb {F}_{2^m}^2$, where

$$\begin{aligned} f(x,y) = (f_1(x,y), f_2(x,y))&\text {and}&g(x,y) = (g_1(x,y), g_2(x,y)) \end{aligned}$$

for coordinate functions $f_1,f_2,g_1,g_2 : \mathbb {F}_{2^m}^2 \rightarrow \mathbb {F}_{2^m}$, are EL-equivalent, if there exist linear functions $L,N,M : \mathbb {F}_{2^m}^2 \rightarrow \mathbb {F}_{2^m}^2$, where L and N are bijective, such that

$$\begin{aligned} f(L(x,y)) = N(g(x,y)) + M(x,y). \end{aligned}$$

Write

$$\begin{aligned} L(x,y) = (L_A(x,y), L_B(x,y))&\text {and}&M(x,y) = (M_A(x,y), M_B(x,y)) \end{aligned}$$

for linear functions $L_A, L_B, M_A, M_B : \mathbb {F}_{2^m}^2 \rightarrow \mathbb {F}_{2^m}$ and

$$\begin{aligned} N(x,y) = \left( N_1(x) + N_3(y),\ N_2(x) + N_4(y)\right) \end{aligned}$$

for linear functions $N_1, \dots , N_4 : \mathbb {F}_{2^m}\rightarrow \mathbb {F}_{2^m}$. In terms of these newly defined functions, f and g are EL-equivalent if both

$$\begin{aligned} f_1(L_A(x,y), L_B(x,y))&= N_1(g_1(x,y)) + N_3(g_2(x,y)) + M_A(x,y), \end{aligned}$$

(6)

$$\begin{aligned} f_2(L_A(x,y), L_B(x,y))&= N_2(g_1(x,y)) + N_4(g_2(x,y)) + M_B(x,y) \end{aligned}$$

(7)

hold. They are linearly equivalent if $M(x,y) = 0$.

Equations (6) and (7) will form the general framework in the proof of our main theorem.

3 Known Classes of APN Functions

In this section, we give a short overview of the currently known APN functions. In Table 1, we present the known APN power functions. This list is conjectured to be complete. APN power functions and their equivalence relations are very well studied. It is well known that the classes in Table 1 are in general CCZ-inequivalent. Moreover, it is, for example, known that Gold functions are inequivalent for different values of i; see Budaghyan et al. [11].

Table 1 List of known APN power functions $x \mapsto x^d$ [29, Table 3]

As far as non-power APN functions are concerned, the situation becomes much less clear than for power functions. Several infinite families of non-power APN functions have been found, but only for few of them their equivalence relations are known. This includes equivalence relations both between functions from different classes as well as between functions coming from the same class. A current list of known families of APN functions that are CCZ-inequivalent to power functions was recently given by Budaghyan et al. [10, Table 3]. This list contains 13 distinct classes, all of which are quadratic.

In the present paper, we study the family (F12) from this list. It was introduced by Taniguchi [30] who used a criterion developed by Carlet [13] to prove the APN property of his functions. In Theorem 3.1, we restate Taniguchi’s [30] construction in bivariate representation. Its univariate form can be found in the list by Budaghyan et al. [10].

Theorem 3.1

[30, Theorem 3] Let $m \ge 2$ and k be positive integers such that $\gcd (k,m) = 1$. Let $\alpha , \beta \in \mathbb {F}_{2^m}$ and $\beta \ne 0$. Then, the function $f_{k,\alpha ,\beta }: \mathbb {F}_{2^{2m}}\rightarrow \mathbb {F}_{2^{2m}}$, where

$$\begin{aligned} f_{k,\alpha ,\beta }(x,y) = \left( x^{2^{2k}(2^k+1)} + \alpha x^{2^{2k}} y^{2^k} + \beta y^{2^k+1},\ xy\right) \end{aligned}$$

is APN if and only if the polynomial $X^{2^k+1} + \alpha X + \beta \in \mathbb {F}_{2^m}[X]$ has no root.

We remark that the Taniguchi APN functions from Theorem 3.1 are quadratic. In the following lemma we specify the case $\alpha = 0$.

Lemma 3.2

A Taniguchi function $f_{k,0,\beta }$ on $\mathbb {F}_{2^{2m}}$ is APN if and only if m is even and $\beta$ is a non-cube in $\mathbb {F}_{2^m}^*$.

Proof

According to Theorem 3.1, the function $f_{k,0,\beta }$ is APN if and only if the polynomial $P(X) \in \mathbb {F}_{2^m}[X]$, where $P(X) = X^{2^k+1} + \beta$, has no root. Recall that m and k are coprime. Hence,

$$\begin{aligned} \gcd (2^k+1,2^m-1) = {\left\{ \begin{array}{ll} 1, &{}\text {if } m\text { is odd},\\ 3, &{}\text {if } m\text { is even}. \end{array}\right. } \end{aligned}$$

Consequently, if m is odd, P(X) is a permutation polynomial and, thus, always has a root. If m is even, however, then P(X) has a root if and only if $\beta$ is a cube. $\square$

The following lemma provides insight on the total number of Taniguchi APN functions for given m and k—without considering equivalence—by giving the number of admissible $\beta \in \mathbb {F}_{2^m}^*$. This result is due to Bluher [5, Theorem 5.6] who proved it in a more general setting. In the specific form of the present paper, the result was also obtained by Helleseth and Kholosha [23].

Lemma 3.3

Let k, m be coprime integers such that $0< k < m$. The number of $\beta \in \mathbb {F}_{2^m}^*$ such that the polynomial $X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$ is $\frac{2^m-1}{3}$ if m is even and $\frac{2^m+1}{3}$ if m is odd.

In Theorem 3.4, we present another family of APN functions, which is closely related to Taniguchi’s [30] construction from Theorem 3.1. It was introduced by Pott and the second author [33], and Anbar et al. [1] showed that the conditions on the parameters are not only sufficient but also necessary. The equivalence problem of these APN functions was recently solved by the present authors [26].

Theorem 3.4

[33, Corollary 2] and [1, Proposition 3.5] Let m be an even integer and let k, s be integers, $0 \le k,s \le m$, such that $\gcd (k,m)=1$. Let $\alpha \in \mathbb {F}_{2^m}^*$. The function $g_{k,s,\alpha }:\mathbb {F}_{2^{2m}}\rightarrow \mathbb {F}_{2^{2m}}$ defined as

$$\begin{aligned} g_{k,s,\alpha }(x,y) = \left( x^{2^k+1} + \alpha y^{2^s(2^k+1)},\ xy\right) \end{aligned}$$

is APN if and only if s is even and $\alpha$ is a non-cube.

In the following Lemma 3.5 and Theorem 3.6, we restate two results by the present authors [26] about the equivalence between Pott–Zhou APN functions that we will need to study the equivalence relations between Taniguchi APN functions in Sect. 4.

Lemma 3.5

[26, Lemma 5.1] Let $m \ge 2$ be an even integer. Let $k,\ell$ be integers coprime to m such that $0< k,\ell < m$, and let s, t be even integers with $0 \le s,t \le m$. Let $\alpha , \alpha ' \in \mathbb {F}_{2^m}^*$ be non-cubes. The two APN functions $g_{k,s,\alpha },g_{\ell ,t,\alpha '}$ on $\mathbb {F}_{2^{2m}}$ from Theorem 3.4 are linearly equivalent

• (a) if $k = \ell$ and $s=t$, no matter which non-cubes $\alpha$ and $\alpha '$ we choose,

• (b) if $k \equiv \pm \ell \pmod {m}$ and $s \equiv \pm t\pmod {m}$.

Theorem 3.6

[26, Theorem 1.1] Let $m \ge 4$ be an even integer. Let $k,\ell$ be integers coprime to m such that $0< k,\ell < \frac{m}{2}$, let s, t be even integers with $0 \le s,t \le \frac{m}{2}$, and let $\alpha ,\alpha ' \in \mathbb {F}_{2^m}^*$ be non-cubes. Two Pott–Zhou APN functions $g_{k,s,\alpha }, g_{\ell ,t,\alpha '}$ on $\mathbb {F}_{2^{2m}}$ from Theorem 3.4, are CCZ-equivalent if and only if $k = \ell$ and $s = t$.

4 On the Equivalence of Taniguchi APN Functions

In this section, we study the equivalence problem of the Taniguchi APN functions on $\mathbb {F}_{2^{2m}}$, which were introduced in Theorem 3.4. We will answer the question for which values of the parameters $k,\alpha ,\beta$ two Taniguchi APN functions $f_{k,\alpha ,\beta }$ are CCZ-inequivalent.

As we have pointed out before, Taniguchi APN functions are quadratic. Moreover, they have no constant term. Hence, by Proposition 2.1 and Proposition 2.2, two Taniguchi APN functions are CCZ-equivalent if and only if they are EL-equivalent, and, by Lemma 2.4, their automorphism groups under CCZ- and EA-equivalence are the same. We begin by studying the case $\alpha = 0$. Recall from Lemma 3.2 that $f_{k,0,\beta }$ is APN if and only if m is even and $\beta$ is a non-cube.

Proposition 4.1

Let $m \ge 2$ be an even integer, and let $0< k < \frac{m}{2}$ such that k and m are coprime. Let $\beta , \gamma \in \mathbb {F}_{2^m}^*$ be non-cubes. The Taniguchi APN function $f_{k,0,\beta }$ on $\mathbb {F}_{2^{2m}}$ from Theorem 3.1 is linearly equivalent to the Pott–Zhou APN function $g_{k,2k,\gamma }$ on $\mathbb {F}_{2^{2m}}$ from Theorem 3.4.

Proof

If $\beta$ is a non-cube in $\mathbb {F}_{2^{2m}}^*$, then $\frac{1}{\beta }$ is as well. From Lemma 3.5 (a), we know that the Pott–Zhou APN function $g_{k,2k,\gamma }$ is linearly equivalent to $g_{k,2k,\frac{1}{\beta }}$. We will show that $f_{k,0,\beta }$ is linearly equivalent to $g_{k,2k,\frac{1}{\beta }}$.

By (6) and (7) and the explanations below, the two functions $f_{k,0,\beta }$ and $g_{k,2k,\frac{1}{\beta }}$ are linearly equivalent if there exist bijective mappings L, N on $\mathbb {F}_{2^m}^2$, represented by linearized polynomials $L_A(X,Y), L_B(X,Y) \in \mathbb {F}_{2^m}[X,Y]$ and $N_1(X),\dots ,N_4(X) \in \mathbb {F}_{2^m}[X]$, respectively, such that the two equations

$$\begin{aligned} L_A(x,y)^{2^{2k}(2^k+1)} + \beta L_B(x,y)^{(2^k+1)}&= N_1(x^{2^k+1} + \tfrac{1}{\beta } y^{2^{2k}(2^k+1)}) + N_3(xy),\\ L_A(x,y)L_B(x,y)&= N_2(x^{2^k+1}+ \tfrac{1}{\beta } y^{2^{2k}(2^k+1)}) + N_4(xy) \end{aligned}$$

hold for all $x,y \in \mathbb {F}_{2^m}$. The functions $f_{k,0,\beta }$ and $g_{k,2k,\frac{1}{\beta }}$ are linearly equivalent by

$$\begin{aligned} L_A(X,Y)&= Y, L_B(X,Y)=X,\nonumber \\ N_1(X)&= \beta X, N_2(X)=N_3(X)=0, N_4(X) = X. \end{aligned}$$

Consequently, $f_{k,0,\beta }$ is linearly equivalent to $g_{k,2k,\gamma }$. $\square$

From Proposition 4.1, we immediately obtain the following results.

Corollary 4.2

Let $m \ge 4$.

• (a) Two Taniguchi APN functions $f_{k,0,\beta }$ and $f_{-k,0,\beta }$ on $\mathbb {F}_{2^{2m}}$ are CCZ-equivalent.

• (b) Two Taniguchi APN functions $f_{k,0,\beta }$ and $f_{\ell ,0,\beta '}$ on $\mathbb {F}_{2^{2m}}$ where $0< k,\ell < \frac{m}{2}$ are CCZ-equivalent if and only if $k = \ell$.

Proof

Statement (a) follows from Proposition 4.1 in combination with Lemma 3.5 (b). Statement (b) follows from Proposition 4.1 in combination with Theorem 3.6. $\square$

We remark that for $m = 2$, all Taniguchi APN functions, no matter if $\alpha$ is zero or not, are CCZ-equivalent to the Gold APN function $x \mapsto x^3$. From now on, we focus on the case $\alpha \ne 0$. In the following Lemma 4.3, we summarize several results about polynomials of the shape $X^{2^k+1} + X + \beta$ that we need to solve the equivalence problem of the Taniguchi APN functions.

Lemma 4.3

Let $m \ge 2$ and $k < m$ be positive integers, and let $\alpha , \beta \in \mathbb {F}_{2^m}^*$.

• (a) The polynomial $P(X) = X^{2^k+1} + \alpha X + \beta$ has no root in $\mathbb {F}_{2^m}$ if and only if $P'(X)=X^{2^k+1} + X + \frac{\beta }{\alpha ^{2^{-k}+1}}$ has no root in $\mathbb {F}_{2^m}$ .

• (b) The polynomial $P(X) = X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$ if and only if $P'(X)=X^{2^k+1} + X + {\beta }^{2^{i}}$ has no root in $\mathbb {F}_{2^m}$ for $i \in \{0, \dots , m-1\}$.

• (c) The polynomial $P(X) = X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$ if and only if $P'(X)=X^{2^k+1} + X + {\beta }$ has no root in $\mathbb {F}_{2^m}$.

Proof

• (a) Substitute X by $\alpha ^{2^{-k}}X$ in P(X) to obtain $\alpha ^{2^{-k}+1}X^{2^k+1} + \alpha ^{2^{-k}+1}X + \beta$. Factoring out $\alpha ^{2^{-k}+1}$ gives the result.

• (b) For any $i \in \{0,\dots , m-1\}$ we can transform P(X) into $P'(X)$ by applying the automorphism $x\mapsto x^{2^{i}}$ on the coefficients of P(X).

• (c) We can transform $P'(X)$ into P(X) using the substitution $X\mapsto (X+1)^{2^k}$. $\square$

We now focus on the equivalence relations between Taniguchi APN functions. Proposition 4.4 (a) was also observed by Taniguchi [30, Proposition 2].

Proposition 4.4

Let $m \ge 2$ be an integer. Let k be an integer coprime to m such that $0< k <m$, and let $\alpha , \beta \in \mathbb {F}_{2^m}^*$. Then, the following pairs of Taniguchi APN functions on $\mathbb {F}_{2^{2m}}$ from Theorem 3.1 are linearly equivalent:

• (a) $f_{k,\alpha ,\beta }$ and $f_{k,1,\frac{\beta }{\alpha ^{2^{-k}+1}}}$,

• (b) $f_{k,1,\beta ^{2^i}}$ and $f_{k,1,\beta }$ for $i \in \{0,\dots ,m-1\}$,

• (c) $f_{-k,1,\beta }$ and $f_{k,1,\beta }$.

Proof

It follows from Lemma 4.3 that all the functions in Proposition 4.4 are APN.

By (6) and (7) and the explanations below, two Taniguchi APN functions $f_{k,\alpha ,\beta }$ and $f_{\ell ,\alpha ',\beta '}$ are linearly equivalent if there exist invertible mappings L, N on $\mathbb {F}_{2^m}^2$, represented by linearized polynomials $L_A(X,Y), L_B(X,Y) \in \mathbb {F}_{2^m}[X,Y]$ and $N_1(X),\dots ,N_4(X) \in \mathbb {F}_{2^m}[X]$, respectively, such that the two equations

$$\begin{aligned}&L_A(x,y)^{2^{2k}(2^k+1)} + \alpha L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k} +\beta L_B(x,y)^{(2^k+1)} \\&\quad = N_1(x^{(2^\ell +1)2^{2\ell }} + \alpha ' x^{2^{2\ell }} y^{2^\ell } + \beta ' y^{2^\ell +1}) + N_3(xy),\\&L_A(x,y)L_B(x,y) = N_2(x^{(2^\ell +1)2^{2\ell }} + \alpha ' x^{2^{2\ell }} y^{2^\ell } + \beta ' y^{2^\ell +1}) + N_4(xy) \end{aligned}$$

hold for all $x,y \in \mathbb {F}_{2^m}$. We will give such polynomials for (a)–(c). As we have $N_2(X) = N_3(X) = 0$ in all three cases, we will not restate these polynomials in every case.

• (a) The functions $f_{k,\alpha ,\beta }$ and $f_{k,1,\frac{\beta }{\alpha ^{2^{-k}+1}}}$ are linearly equivalent by

  $$\begin{aligned} L_A(X,Y)&= X,&L_B(X,Y)&=\tfrac{1}{\alpha ^{2^{-k}}}Y,&N_1(X)&=X,&N_4(X)&= \tfrac{1}{\alpha ^{2^{-k}}}X. \end{aligned}$$

• (b) The functions $f_{k,1,\beta ^{2i}}$ and $f_{k,1,\beta }$ are linearly equivalent by

  $$\begin{aligned} L_A(X,Y)&= X^{2^i},&L_B(X,Y)&=Y^{2^i},&N_1(X)&= X^{2^i},&N_4(X)&= X^{2^i}. \end{aligned}$$

• (c) We first show that $f_{-k,1,\beta }$ and $f_{k,\frac{1}{\beta },\frac{1}{\beta }}$ are equivalent. This can be seen choosing

  $$\begin{aligned} L_A(X,Y)&= Y^{2^{3k}},&L_B(X,Y)&=X^{2^{3k}},&N_1(X)&= \beta X,&N_4(X)&= X^{2^{3k}}. \end{aligned}$$

  Using (a), it follows that $f_{k,\frac{1}{\beta },\frac{1}{\beta }}$ is linearly equivalent to $f_{k,1,\beta ^{2^{-k}}}$, which, by (b), is linearly equivalent to $f_{k,1,\beta }$.

$\square$

Next, we present our main theorem. We remark that it only holds for $m \ge 3$ as for $m = 2$, all Taniguchi APN functions are CCZ-equivalent to the Gold APN function $x \mapsto x^3$. According to Proposition 4.4, for $m \ge 3$, every Taniguchi APN function $f_{k,\alpha ,\beta }$, where $\alpha \ne 0$, is linearly equivalent to a Taniguchi APN function $f_{\ell ,1,\beta '}$, where $0< \ell < \frac{m}{2}$. Hence, we will only consider functions $f_{k,1,\beta }$ where $0< k < \frac{m}{2}$ in our theorem. Note that the structure of the proof of Theorem 4.5 is similar to the structure of the proof of Theorem 3.6 by the present authors [26]. To keep the paper self-contained we will restate some parts that also appear in [26].

Theorem 4.5

Let $m \ge 3$ be an integer, and let $k,\ell$ be integers, $0< k,\ell < \frac{m}{2}$, coprime to m. Let $\beta , \beta ' \in \mathbb {F}_{2^m}^*$ such that the polynomials $X^{2^k+1} + X + \beta$ and $X^{2^\ell +1} + X + \beta '$ have no roots in $\mathbb {F}_{2^m}$. Two Taniguchi APN functions $f_{k,1,\beta }, f_{\ell ,1,\beta '}$ on $\mathbb {F}_{2^{2m}}$, where

$$\begin{aligned} f_{k,1,\beta } = (x^{2^{2k}(2^k+1)} + x^{2^{2k}}y^{2^k} + \beta y^{2^k+1},\ xy) \end{aligned}$$

and

$$\begin{aligned} f_{\ell ,1,\beta '} = (x^{2^{2\ell }(2^\ell +1)} + x^{2^{2\ell }}y^{2^\ell } + \beta ' y^{2^\ell +1},\ xy), \end{aligned}$$

are CCZ-equivalent if and only if $k = \ell$ and $\beta ' = \beta ^{2^i}$ for some $i \in \{0,\dots ,m-1\}$.

Proof

We have shown in Proposition 4.4 that $f_{k,1,\beta }$ and $f_{k,1,\beta ^{2^i}}$ are linearly equivalent and thereby CCZ-equivalent. We will now show the converse: if $f_{k,1,\beta }$ and $f_{\ell ,1,\beta '}$ are CCZ-equivalent, then $k=\ell$ and $\beta ' = \beta ^{2^i}$ for some $i \in \{0,\dots ,m-1\}$.

For $m = 3$ and $m = 4$, the result can be easily confirmed. If $m=3$, then $k=1$ and, according to Lemma 3.3, there are three distinct $\beta \in \mathbb {F}_{2^3}^*$ such that $X^3+X+\beta$ has no root in $\mathbb {F}_{2^3}$. Clearly, if $\beta$ meets this condition, then $\beta ^2$ and $\beta ^4$ do as well. Consequently, for $m = 3$, all three Taniguchi APN functions belong to the same equivalence class. If $m=4$, then $k=1$ and there are five distinct $\beta \in \mathbb {F}_{2^4}^*$ such that $X^3+X+\beta$ has no root, namely 1 and $\beta , \beta ^2, \beta ^4, \beta ^8$ for some $\beta \ne 1$. Hence, for $m=4$, there exist two equivalence classes: $f_{1,1,1}$ and $f_{1,1,\beta }$, where $\beta \ne 1$. The existence of these two classes was also observed by Taniguchi [30], who computed the $\Gamma$-ranks for these functions.

For the remainder of the proof, let $m\ge 5$. Assume $f_{k,1,\beta }$ and $f_{\ell ,1,\beta '}$ are CCZ-equivalent. By Propositions 2.1 and 2.2, this implies that the functions are also EL-equivalent. Hence, analogously to the proof of Proposition 4.4, there exist linearized polynomials $L_A(X,Y), L_B(X,Y), M_A(X,Y), M_B(X,Y) \in \mathbb {F}_{2^m}[X,Y]$ and $N_1(X), \dots , N_4(X) \in \mathbb {F}_{2^m}[X]$, where

$$\begin{aligned} L(X,Y) = (L_A(X,Y), L_B(X,Y)) \end{aligned}$$

and

$$\begin{aligned} N(X,Y) = (N_1(X) + N_3(Y),\ N_2(X) + N_4(Y)) \end{aligned}$$

are invertible, such that the equations

$$\begin{aligned}&L_A(x,y)^{2^{2k}(2^k+1)} \,+ \, L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k} +\beta L_B(x,y)^{2^k+1} \nonumber \\&\quad = N_1(x^{(2^\ell +1)2^{2\ell }} + x^{2^{2\ell }} y^{2^\ell } + \beta ' y^{2^\ell +1}) + N_3(xy) + M_A(x,y), \end{aligned}$$

(8)

$$\begin{aligned}&L_A(x,y)L_B(x,y) = N_2(x^{(2^\ell +1)2^{2\ell }} + x^{2^{2\ell }} y^{2^\ell } + \beta ' y^{2^\ell +1}) + N_4(xy) + M_B(x,y) \end{aligned}$$

(9)

hold for all $x,y \in \mathbb {F}_{2^m}$. We write $L_A(X,Y) = L_1(X) + L_3(Y)$ and $L_B(X,Y) = L_2(X) + L_4(Y)$ for linearized polynomials $L_1(X), \dots , L_4(X) \in \mathbb {F}_{2^m}[X]$. Hence,

$$\begin{aligned} L(X,Y) = \left( L_1(X)+L_3(Y),\ L_2(X) + L_4(Y)\right) . \end{aligned}$$

Write

$$\begin{aligned} L_1(X)&= \sum _{i=0}^{m-1} a_i X^{2^i}, L_2(X) = \sum _{i=0}^{m-1} b_i X^{2^i}, \\ L_3(Y)&= \sum _{i=0}^{m-1} \overline{a}_i Y^{2^i}, L_4(Y) = \sum _{i=0}^{m-1} \overline{b}_i Y^{2^i}. \end{aligned}$$

Analogously, define linearized polynomials $M_1(X), \dots , M_4(X) \in \mathbb {F}_{2^m}[X]$ such that

$$\begin{aligned} M(X,Y) = (M_1(X) + M_3(Y), M_2(X) + M_4(Y)). \end{aligned}$$

For the remainder of the proof, let $x,y \in \mathbb {F}_{2^m}$. We first prove the following claim.

Claim. If $f_{k,1,\beta }$ and $f_{\ell ,1,\beta '}$ are EL-equivalent, then $k=\ell$ and each of the linearized polynomials $L_1(X), L_2(X), L_3(Y), L_4(Y)$ is a monomial or zero.

We will prove the result for $y=0$ and obtain statements for $L_1(X)$ and $L_2(X)$. Using the same approach with $x=0$, identical statements can be obtained for $L_3(Y)$ and $L_4(Y)$. Let $y=0$. Then, it follows from (8) and (9) that

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)} + L_1(x)^{2^{2k}} L_2(x)^{2^k} +\beta L_2(x)^{2^k+1}&= N_1(x^{(2^\ell +1)2^{2\ell }}) + M_1(x), \end{aligned}$$

(10)

$$\begin{aligned} L_1(x)L_2(x)&= N_2(x^{(2^\ell +1)2^{2\ell }}) + M_2(x) \end{aligned}$$

(11)

for all $x \in \mathbb {F}_{2^m}$. Write

$$\begin{aligned} N_1(X) = \sum _{i=0}^{m-1} c_i X^{2^i}&\text {and}&N_2(X) = \sum _{i=0}^{m-1} d_i X^{2^{i-2\ell }}. \end{aligned}$$

Note that, for convenience, we shift the summation index of $N_2(X)$.

As L(X, Y) has to be invertible, it is not possible that both $L_1(X)$ and $L_2(X)$ are zero. First, suppose $L_1(X) \ne 0$ and $L_2(X) = 0$. For the case $L_1(X) = 0$ and $L_2(X) \ne 0$, an identical result can be obtained by symmetry. If $L_1(X) \ne 0$ and $L_2(X) = 0$, then it follows from (11) that $N_2(X)=M_2(X) = 0$ as the left-hand side is zero, and (10) becomes

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)} = N_1(x^{(2^\ell +1)2^{2\ell }}) + M_1(x). \end{aligned}$$

(12)

From (12), it follows that the Gold APN functions $x \mapsto x^{2^k+1}$ and $x \mapsto x^{2^\ell +1}$ on $\mathbb {F}_{2^m}$ have to be EA-equivalent. It was shown by Budaghyan et al. [11, Theorem 2.1] that this implies $k = \ell$. The present authors [26, Theorem 4.1], moreover, showed that if $m \ge 5$, the equivalence mappings between equivalent Gold APN functions are linearized monomials. In our case, this means the polynomial $L_1(X)$ is a linearized monomial. In summary, we obtain

$$\begin{aligned} L_1(X)&= a_u X^{2^u}&\text {and}&L_2(X)&= 0 \end{aligned}$$

(13)

for some $u \in \{0, \dots , m-1\}$ and $a_u \in \mathbb {F}_{2^m}^*$. If we consider the case $L_1(X) = 0$ and $L_2(X) \ne 0$, we analogously obtain

$$\begin{aligned} L_1(X)&= 0&\text {and}&L_2(X)&=b_u X^{2^u} \end{aligned}$$

(14)

for some $u \in \{0, \dots , m-1\}$ and $b_u \in \mathbb {F}_{2^m}^*$. In both cases, $M_1(X)=M_2(X)=0$.

Now, let both $L_1(X), L_2(X) \ne 0$. Then, (11) becomes

$$\begin{aligned} \sum _{i=0}^{m-1}a_ib_i x^{2^{i+1}} + \sum _{\begin{array}{c} i,j=0,\\ j \ne i \end{array}}^{m-1}a_ib_j x^{2^i+2^j} = \sum _{i=0}^{m-1}d_ix^{(2^\ell +1)2^i} + M_2(x). \end{aligned}$$

(15)

Note that the first sum on the left-hand side of (15) is linearized. Hence, set $M_2(X) = \sum _{i=0}^{m-1}a_ib_i X^{2^{i+1}}$. We rewrite (15) as

$$\begin{aligned} \sum _{0 \le i < j \le m-1} (a_ib_j + a_jb_i)x^{2^i+2^j} = \sum _{i=0}^{m-1}d_ix^{2^i+ 2^{i+\ell }} \end{aligned}$$

which implies that the equations

$$\begin{aligned} a_i b_{i+\ell } + a_{i+\ell } b_i&= d_i \quad \text {for all } i, \end{aligned}$$

(16)

$$\begin{aligned} a_i b_j + a_j b_i&=0 \quad \ \text {for } j \ne i, i\pm \ell , \end{aligned}$$

(17)

where the subscripts are calculated modulo m, have to hold. We separate the proof into two cases: first, the case that $d_i = 0$ for all $i = 0, \dots , m-1$, and, second, the case that $d_u \ne 0$ for some $u \in \{0,\dots ,m-1\}$.

Case 1. In this case, we show that if $d_i=0$ for all $i = 0, \dots , m-1$, similarly to (12), the problem can be reduced to the equivalence problem of Gold APN functions that has been studied by the present authors [26, Theorem 4.1]. Assume $d_i = 0$ for all $i = 0, \dots , m-1$, which means $N_2(X) = 0$. In this case, (16) and (17) combine to

$$\begin{aligned} a_i b_j + a_j b_i =0 \quad \text {for } j \ne i. \end{aligned}$$

(18)

As $L_1(X)$ and $L_2(X)$ are both nonzero, each polynomial has at least one nonzero coefficient. Assume $a_u$ and $b_{u'}$ are nonzero, where $u,u' \in \{0, \dots , m-1\}$. If $u = u'$, the corresponding term in (11), that is, $a_u b_u X^{2^u+1}$, is linearized and only contributes to $M_2(X)$. If $u \ne u'$, then, by (18),

$$\begin{aligned} a_u b_{u'} + a_{u'} b_u = 0. \end{aligned}$$

Consequently, $a_{u'}$ and $b_u$ have to be nonzero as well, and $a_u, a_{u'}, b_u, b_{u'}$ have to meet the condition $\frac{a_u}{b_u} = \frac{a_{u'}}{b_{u'}}$. Define $\Delta = \frac{a_u}{b_u}$ and note that $\Delta \ne 0$. It follows that $(a_j, b_j)$ satisfies either

$$\begin{aligned} a_j = b_j&= 0&\text {or}&\frac{a_j}{b_j} = \Delta \end{aligned}$$

(19)

for all $j = 0, \dots , m-1$. Consequently, $b_j = \delta a_j$, where $\delta = \frac{1}{\Delta }$, for all $j=0, \dots , m-1$, and $L_2(X)$ is a multiple of $L_1(X)$, namely

$$\begin{aligned} L_2(X) = \delta L_1(X). \end{aligned}$$

(20)

We plug $L_1(X)$ and $L_2(X)$ into (10) and obtain

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)} + \delta ^{2^k} L_1(x)^{2^k(2^k+1)} + \beta \delta ^{2^k+1} L_1(x)^{2^k+1} = N_1(x^{(2^\ell + 1)2^{2\ell }}) + M_1(x). \end{aligned}$$

(21)

Define a polynomial $T(X) \in \mathbb {F}_{2^m}[X]$ as

$$\begin{aligned} T(X) = X^{2^{2k}} + \delta ^{2^k} X^{2^k} + \beta \delta ^{2^k+1} X \end{aligned}$$

and rewrite the left-hand side of (21) as

$$\begin{aligned} T(L_1(x)^{2^k+1}). \end{aligned}$$

We show that T(X) is a permutation polynomial. Since T(X) is linearized, it is sufficient to show that T(X) has no nonzero roots. If T(X) had a nonzero root, it would also be a root of the polynomial

$$\begin{aligned} T'(X) = X^{2^{2k}-1} + \delta ^{2^k}X^{2^k-1} + \beta \delta ^{2^k+1}. \end{aligned}$$

Substitute $X^{2^k-1}$ by Z. Note that this substitution is one-to-one since $\gcd (2^k-1,2^m-1) = 2^{\gcd (k,m)} - 1 = 1$. We obtain

$$\begin{aligned} T'(Z) = Z^{2^k+1} + \delta ^{2^k} Z + \beta \delta ^{2^k+1}. \end{aligned}$$

By Lemma 4.3, the polynomial $T'(Z)$ has no root if and only if $P(X) = X^{2^k+1} + X + \beta$ has no root. This holds by the definition of $\beta$.

Hence, we denote by $T^{-1}(X)$ the inverse of T(X) and rewrite (21) as

$$\begin{aligned} L_1(x)^{2^k+1} = T^{-1}(N_1(x^{(2^\ell +1)2^{2\ell }})) + T^{-1}(M_1(x)). \end{aligned}$$

(22)

Since $T^{-1}(X)$ is also linearized, (22) describes the equivalence problem of two Gold APN functions as in the case that exactly one of $L_1(X)$ and $L_2(X)$ is zero. By [26, Theorem 4.1], it follows that $L_1(X)$ is a monomial. Because of (20), the polynomials $L_1(X)$ and $L_2(X)$ are monomials of the same degree:

$$\begin{aligned} L_1(X)&= a_u X^{2^u}&\text {and}&L_2(X)&= b_u X^{2^u}. \end{aligned}$$

(23)

Moreover, $M_2(X)=a_u b_u X^{2^{u+1}}$ and $M_1(X)=0$.

Case 2. Consider (16) and (17) again and assume $d_u \ne 0$ for some $u \in \{0,\dots ,m-1\}$ which means $N_2(X) \ne 0$. We will show that in this case, similarly to Case 1, the polynomials $L_1(X)$ and $L_2(X)$ need to be monomials. In contrast to Case 1, however, now $L_1(X)$ and $L_2(X)$ will have different degrees. If $d_u \ne 0$, then, by (16), $a_u$ and $b_u$ cannot be zero at the same time. We will separate the proof of Case 2 into two subcases: first, Case 2.1, where both $a_u$ and $b_u$ are nonzero, and second, Case 2.2, where exactly one of $a_u$ and $b_u$ is nonzero. Both these cases will be separated into several subcases again.

Case 2.1. Assume $a_u \ne 0$ and $b_u \ne 0$. It follows from (17) that all pairs $(a_j,b_j)$, where $j \ne u, u \pm \ell$, satisfy (19). We will first show that the only possible nonzero coefficients are $a_j, b_j$ for $j = u, u \pm \ell , u \pm 2\ell$.

By way of contradiction, assume there exists $\ell ' \ne 0, \pm \ell , \pm 2\ell$ such that $a_{u+\ell '}$ and $b_{u+\ell '}$ are nonzero. By (19), this implies $\frac{a_{u+\ell '}}{b_{u+\ell '}} = \Delta$. Since $u+\ell ' \pm \ell \ne u \pm \ell$, it follows from (16) with $i =u + \ell '$ that both $(a_{u+\ell },b_{u+\ell })$ and $(a_{u-\ell },b_{u-\ell })$ also have to satisfy one of the equations in (19). Hence, (19) holds for all $j=0, \dots , m-1$ which means that $L_2(X)$ is a multiple of $L_1(X)$. However, now (11) implies $N_2(X) = 0$. This is a contradiction.

Hence, we assume $a_j=b_j = 0$ for $j \ne u, u \pm \ell , u \pm 2\ell$ for the remainder of Case 2.1. We separate its proof into two subcases, both will lead to contradictions.

Case 2.1.1. Suppose $a_{u \pm 2\ell }=b_{u \pm 2 \ell }=0$. In this case, we obtain only one equation from (16), namely

$$\begin{aligned} a_{u-\ell }b_{u+\ell } + a_{u+\ell }b_{u-\ell } = 0. \end{aligned}$$

Hence, either

• (i) $a_{u-\ell } = a_{u+\ell } = 0$ or $b_{u-\ell } = b_{u+\ell } = 0$, meaning that one of $L_1(X)$ and $L_2(X)$ is a monomial and the other one has at most three nonzero coefficients, or

• (ii) $a_{u-\ell } = b_{u-\ell } = 0$ or $a_{u+\ell } = b_{u+\ell } = 0$, meaning that both $L_1(X)$ and $L_2(X)$ have at most two nonzero coefficients, or

• (iii) $a_{u \pm \ell },b_{u \pm \ell } \ne 0$ and $\frac{a_{u-\ell }}{b_{u-\ell }} = \frac{a_{u+\ell }}{b_{u+\ell }}$, meaning that both $L_1(X)$ and $L_2(X)$ are trinomials.

We will consider each of these three subcases.

Subcase (i). Assume $b_{u-\ell } = b_{u+\ell } = 0$. The case $a_{u-\ell } = a_{u+\ell } = 0$ follows by symmetry. We consider polynomials

$$\begin{aligned} L_1(X)&= a_{u-\ell }X^{2^{u-\ell }} + a_u X^{2^u} + a_{u+\ell }X^{2^{u+\ell }}&\text {and}&L_2(X)&= b_u X^{2^u} \end{aligned}$$

which we plug into the left-hand side of (10). We obtain

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)}&= a_{u-\ell }^{2^{2k}(2^k+1)} x^{2^{u-\ell +2k}(2^k+1)} + a_{u}^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} \nonumber \\&\quad + a_{u+\ell }^{2^{2k}(2^k+1)} x^{2^{u+\ell +2k}(2^k+1)} + a_{u-\ell }^{2^{3k}}a_u^{2^{2k}} x^{2^{u+2k}(2^{k-\ell }+1)} \nonumber \\&\quad + a_{u}^{2^{3k}}a_{u+\ell }^{2^{2k}} x^{2^{u+\ell +2k}(2^{k-\ell }+1)} + a_{u+\ell }^{2^{3k}}a_{u-\ell }^{2^{2k}} x^{2^{u-\ell +2k}(2^{k+2\ell }+1)} \nonumber \\&\quad + a_{u-\ell }^{2^{3k}}a_{u+\ell }^{2^{2k}} x^{2^{u+\ell +2k}(2^{k-2\ell }+1)} + a_{u}^{2^{3k}}a_{u-\ell }^{2^{2k}} x^{2^{u-\ell +2k}(2^{k+\ell }+1)} \nonumber \\&\quad + a_{u+\ell }^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{k+\ell }+1)} \end{aligned}$$

(24)

and

$$\begin{aligned} L_1(x)^{2^{2k}} L_2(x)^{2^k}&= a_{u-\ell }^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^{k-\ell }+1)} + a_{u}^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^k+1)} \nonumber \\&\quad + a_{u+\ell }^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^{k+\ell }+1)} \end{aligned}$$

(25)

and

$$\begin{aligned} \beta L_2(x)^{2^k+1} = \beta b_u^{2^k+1} x^{2^u(2^k+1)}. \end{aligned}$$

(26)

Recall that the right-hand side of (10) is

$$\begin{aligned} \sum _{i=0}^{m-1}c_i x^{2^{i+2\ell }(2^\ell +1)} + M_1(x). \end{aligned}$$

We will show that not all of the first three terms of (24) that all contain the factor $x^{2^k+1}$ can be canceled simultaneously. First, as $0< \ell < \frac{m}{2}$, the terms cannot cancel each other. Second, if $\ell = \frac{m}{2}-k$, the exponent of x in the sixth term can be written as $2^{u-\frac{m}{2}+2k}(2^k+1)$, but by the same reasoning as above, the sixth term cannot cancel any of the first three terms. Third, if m is odd and $k < \frac{m}{4}$, it is possible that $\ell = 2k$. In this case, the term in (26), the first term of (25) and the first term of (24) all contain the factor $x^{2^{u}(2^k+1)}$ and could potentially cancel each other, but the second and third terms of (24) cannot be canceled. Analogously, the third term of (24) could be canceled if m is odd and $\frac{m}{4}<k<\frac{m}{2}$ and $\ell = -2k$, but the first and second terms would remain. Fourth, if $\ell = k$, the first and the second terms of (24) could be canceled by the second term of (25) and the seventh term of (24), respectively. However, the third term would remain. In summary, for arbitrary k and $\ell$, the third term of (24) can never be canceled.

We now compare the left-hand side and the right-hand side of (10): The summands on the left-hand side that contain the factor $x^{2^i(2^k+1)}$ can only be represented on the right-hand side, if $k = \ell$. Hence, assume $k=\ell$. Now, the fourth and the fifth summands of (24) as well as the first summand of (25) become linearized. Consequently,

$$\begin{aligned} M_1(X) = a_{u-k}^{2^{2k}} b_u^{2^k} X^{2^{u+k+1}} + a_{u-k}^{2^{3k}}a_u^{2^{2k}} X^{2^{u+2k+1}} + a_{u}^{2^{3k}}a_{u+k}^{2^{2k}} X^{2^{u+3k+1}}. \end{aligned}$$

Next, consider the eighth and the ninth terms of (24) where the eighth term can be summarized with the third term of (25):

$$\begin{aligned} a_{u+k}^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{2k}+1)},&(a_{u}^{2^{3k}}a_{u-k}^{2^{2k}} + a_{u+k}^{2^{2k}} b_u^{2^k}) x^{2^{u+k}(2^{2k}+1)}. \end{aligned}$$

As $m \ge 5$ and $\gcd (k,m) = 1$, we have $2k \not \equiv \pm k \pmod {m}$. Hence, these terms cannot be represented in the form $c_i x^{2^{i+2k}(2^k+1)}$ on the right-hand side of (10) which means that their coefficients have to be zero. As $a_u \ne 0$, it follows that $a_{u+k} = 0$ which then implies $a_{u-k} = 0$. Hence, $L_1(X)$ and $L_2(X)$ are monomials of the same degree. As this implies $N_2(X)=0$, it contradicts the assumption of Case 2.

Subcase (ii). Assume $a_{u-\ell } = b_{u-\ell } = 0$. The case $a_{u+\ell } = b_{u+\ell } = 0$ follows by symmetry. In our case

$$\begin{aligned} L_1(X)&= a_u X^{2^u} + a_{u+\ell }X^{2^{u+\ell }}&\text {and}&L_2(X)&= b_u X^{2^u} + b_{u+\ell }X^{2^{u+\ell }}. \end{aligned}$$

On the left-hand side of (10), we obtain

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)}&= a_{u}^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} + a_{u+\ell }^{2^{2k}(2^k+1)} x^{2^{u+\ell +2k}(2^k+1)} \\&\quad + a_{u}^{2^{3k}}a_{u+\ell }^{2^{2k}} x^{2^{u+\ell +2k}(2^{k-\ell }+1)} + a_{u+\ell }^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{k+\ell }+1)} \end{aligned}$$

and

$$\begin{aligned} L_1(x)^{2^{2k}} L_2(x)^{2^k}&= a_{u}^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^k+1)} + a_{u+\ell }^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^k+1)}\\&\quad + a_{u}^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^{k-\ell }+1)} + a_{u+\ell }^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^{k+\ell }+1)} \end{aligned}$$

and

$$\begin{aligned} \beta L_2(x)^{2^k+1}&= \beta b_u^{2^k+1} x^{2^u(2^k+1)} + \beta b_{u+\ell }^{2^k+1} x^{2^{u+\ell }(2^k+1)} \\&\quad + \beta b_u^{2^k} b_{u+\ell } x^{2^{u+\ell }(2^{k-\ell }+1)} + \beta b_{u+\ell }^{2^k} b_{u} x^{2^{u}(2^{k+\ell }+1)}. \end{aligned}$$

By similar reasoning as in Subcase (i), not all summands containing the factor $x^{2^k+1}$ can be canceled simultaneously. Consequently, we need $k=\ell$ for these terms to be represented on the right-hand side of (10). If $k=\ell$, the following terms, which cannot be canceled, occur on the left-hand side of (10):

$$\begin{aligned} a_{u+k}^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{2k}+1)},&a_{u+k}^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^{2k}+1)},&\beta b_{u+k}^{2^{2k}} b_u x^{2^u(2^{2k}+1)}. \end{aligned}$$

As they cannot be represented in the form $c_i x^{2^{i+2k}(2^k+1)}$ on the right-hand side of (10), their coefficients need to be zero. Hence $a_{u+k} = b_{u+k} = 0$, which means $L_1(X)$ and $L_2(X)$ are monomials of the same degree. As in Subcase (i), this is a contradiction.

Subcase (iii). Now,

$$\begin{aligned} L_1(X)&= a_{u-\ell }X^{2^{u-\ell }} + a_u X^{2^u} + a_{u+\ell }X^{2^{u+\ell }}\\ \text {and } L_2(X)&= b_{u-\ell }X^{2^{u-\ell }} + b_u X^{2^u} + b_{u+\ell }X^{2^{u+\ell }}, \end{aligned}$$

where all coefficients are nonzero and $\frac{a_{u-\ell }}{b_{u-\ell }} = \frac{a_{u+\ell }}{b_{u+\ell }}$. We plug these polynomials into the left-hand side of (10). By similar reasoning as in Subcases (i) and (ii), not all terms containing the factor $x^{2^k+1}$ can be canceled. Hence, $k=\ell$. Now, the left-hand side contains the following two summands that cannot be canceled:

$$\begin{aligned} a_{u+k}^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{2k}+1)},&\beta b_{u}^{2^{2k}} b_{u-k} x^{2^{u-k}(2^{2k}+1)}. \end{aligned}$$

As none of them can be represented on the right-hand side of (10), their coefficients need to be zero, which means that $a_{u+k} = b_{u-k} = 0$. This contradicts our assumption.

Case 2.1.2. Suppose that not all of $a_{u \pm 2 \ell }, b_{u \pm 2 \ell }$ are zero. Recall that all pairs $(a_j, b_j)$ where $j \ne u, u\pm \ell$ have to satisfy (19). We consider the case that $a_{u+2\ell }$ and $b_{u+2\ell }$ are nonzero. One can obtain an almost identical result by symmetry when assuming that $a_{u-2\ell }$ and $b_{u-2\ell }$ are nonzero.

If $a_{u+2\ell }, b_{u+2\ell } \ne 0$, then, by (19), $\frac{a_{u+2\ell }}{b_{u+2\ell }} = \Delta$. It follows from (17) that also $(a_{u-2\ell },b_{u-2\ell })$ and $(a_{u-\ell }, b_{u-\ell })$ have to satisfy (19). However, (17) does not provide any restriction on the values of $a_{u+\ell }$ and $b_{u+\ell }$. If $(a_{u+\ell }, b_{u+\ell })$ satisfies (19), then all $(a_j,b_j)$ do and we know from the beginning of Case 2.1 that this implies $N_2(X) = 0$. As before, this is a contradiction. If $(a_{u+\ell }, b_{u+\ell })$ does not satisfy (19), then it follows from (17) that $a_j=b_j=0$ for $j =u-\ell , u-2\ell$. Hence,

$$\begin{aligned} L_1(X)&= a_u X^{2^u} + a_{u+\ell }X^{2^{u+\ell }} + a_{u+2\ell }X^{2^{u+2\ell }}\\ \text {and } L_2(X)&= b_u X^{2^u} + b_{u+\ell }X^{2^{u+\ell }} + b_{u+2\ell }X^{2^{u+2\ell }}. \end{aligned}$$

As $\frac{a_u}{b_u} = \frac{a_{u+2\ell }}{b_{u+2\ell }}$, this case is similar to Case 2.1.1, Subcase (iii), when we substitute u by $u+\ell$, with the only difference that now, one of the middle coefficients $a_{u+\ell }, b_{u+\ell }$ can be zero. However, the arguments used in the previous case leading to the conclusion $k=\ell$ still hold. If $k = \ell$, the left-hand side of (10) contains the following terms that cannot be canceled:

$$\begin{aligned} a_{u+2k}^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{3k}+1)},&a_{u+2k}^{2^{2k}}b_{u}^{2^k} x^{2^{u+k}(2^{3k}+1)},&\beta b_{u+2k}^{2^k} b_{u} x^{2^u(2^{3k}+1)}. \end{aligned}$$

They cannot be represented on the right-hand side of (10), hence, their coefficients need to be zero. This contradicts our assumption that $a_u, a_{u+2k}, b_u, b_{u+2k}$ are nonzero.

Case 2.2. Assume, exactly one of $a_u$ and $b_u$ is nonzero. We show the case $a_u \ne 0$ and $b_u = 0$. The case $a_u = 0$ and $b_u \ne 0$ can be proved analogously. So, assume $a_u \ne 0$ and $b_u = 0$. From (16) with $i = u$, we obtain the equation

$$\begin{aligned} a_u b_{u+\ell } = d_u. \end{aligned}$$

As $d_u \ne 0$, it follows that $b_{u+\ell } \ne 0$. From (17) with $i = u$, we obtain

$$\begin{aligned} a_u b_j = 0 \quad \text {for } j \ne u, u\pm \ell . \end{aligned}$$

Consequently, $b_j = 0$ for $j \ne u \pm \ell$. Now, it follows from (17) with $i = u + \ell$ that

$$\begin{aligned} a_j b_{u+\ell } = 0 \quad \text {for } j \ne u-\ell ,u, u + \ell , u + 2\ell . \end{aligned}$$

Consequently, $a_j = 0$ for $j \ne u-\ell ,u, u + \ell , u + 2\ell$. We will separate the proof of Case 2.2 into two subcases: in Case 2.2.1, we consider $b_{u-\ell } \ne 0$, in Case 2.2.2, we suppose $b_{u-\ell } = 0$.

Case 2.2.1. Assume $b_{u-\ell } \ne 0$. From (17) with $i = u-\ell$ and $j = u+2\ell$, we obtain

$$\begin{aligned} a_{u+2\ell } b_{u-\ell } = 0, \end{aligned}$$

which implies $a_{u+2\ell } = 0$, and

$$\begin{aligned} a_{u-\ell }b_{u+\ell } + a_{u+\ell } b_{u-\ell } = 0, \end{aligned}$$

which, recalling that $b_{u+\ell }$ is nonzero, implies either $a_{u-\ell } = a_{u+\ell } = 0$ or $a_{u-\ell }, a_{u+\ell } \ne 0$ and $\frac{a_{u-\ell }}{b_{u-\ell }} = \frac{a_{u+\ell }}{b_{u+\ell }}$. We separate these two subcases:

Subcase (i). Assume $a_{u-\ell } = a_{u+\ell } = 0$. Then,

$$\begin{aligned} L_1(X)&= a_u X^{2^u}&\text {and}&L_2(X)&= b_{u-\ell }X^{2^{u-\ell }} + b_{u+\ell }X^{2^{u+\ell }}. \end{aligned}$$

We plug these polynomials into the left-hand side of (10) and obtain

$$\begin{aligned} L_1(x)^{2^{2k}(2^k+1)} = a_{u}^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} \end{aligned}$$

and

$$\begin{aligned} L_1(x)^{2^{2k}} L_2(x)^{2^k} = a_{u}^{2^{2k}} b_{u-\ell }^{2^k} x^{2^{u-\ell +k}(2^{k+\ell }+1)} + a_{u}^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^{k-\ell }+1)} \end{aligned}$$

and

$$\begin{aligned} \beta L_2(x)^{2^k+1}&= \beta b_{u-\ell }^{2^k+1} x^{2^{u-\ell }(2^k+1)} + \beta b_{u+\ell }^{2^k+1} x^{2^{u+\ell }(2^k+1)} \nonumber \\&\quad + \beta b_{u-\ell }^{2^k} b_{u+\ell } x^{2^{u+\ell }(2^{k-2\ell }+1)} + \beta b_{u+\ell }^{2^k} b_{u-\ell } x^{2^{u-\ell }(2^{k+2\ell }+1)}. \end{aligned}$$

(27)

As in previous cases, if $k \ne \ell$, not all terms containing the factor $x^{2^k+1}$ can be canceled simultaneously. Thus, we need $k = \ell$. However, if $k = \ell$, the left-hand side of (10) contains the term

$$\begin{aligned} a_u^{2^{2k}}b_{u-k}^{2^k} x^{2^u(2^{2k}+1)} \end{aligned}$$

that cannot be represented in the form $c_i x^{2^{i+2k}(2^k+1)}$ on the right-hand side of (10). Hence, its coefficient needs to be zero which contradicts our assumption.

Subcase (ii). Assume $a_{u-\ell }, a_{u+\ell } \ne 0$ and $\frac{a_{u-\ell }}{b_{u-\ell }} = \frac{a_{u+\ell }}{b_{u+\ell }}$. Then,

$$\begin{aligned} L_1(X)&= a_{u-\ell } X^{2^{u-\ell }} + a_u X^{2^u} +a_{u+\ell } X^{2^{u+\ell }}\quad \text {and}\\ L_2(X)&= b_{u-\ell }X^{2^{u-\ell }} + b_{u+\ell }X^{2^{u+\ell }}. \end{aligned}$$

We plug these polynomials into the left-hand side of (10). Then, $L_1(x)^{2^{2k}(2^k+1)}$ is as in (24) and $\beta L_2(x)^{2^k+1}$ is as in (27). Moreover,

$$\begin{aligned} L_1(x)^{2^{2k}} L_2(x)^{2^k}&= a_{u-\ell }^{2^{2k}} b_{u-\ell }^{2^k} x^{2^{u-\ell +k}(2^k+1)} + a_{u+\ell }^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^k+1)} \nonumber \\&\quad + a_{u-\ell }^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^{k-2\ell }+1)} + a_{u}^{2^{2k}} b_{u-\ell }^{2^k} x^{2^{u-\ell +k}(2^{k+\ell }+1)} \nonumber \\&\quad + a_{u}^{2^{2k}} b_{u+\ell }^{2^k} x^{2^{u+\ell +k}(2^{k-\ell }+1)} + a_{u+\ell }^{2^{2k}} b_{u-\ell }^{2^k} x^{2^{u-\ell +k}(2^{k+2\ell }+1)}. \end{aligned}$$

(28)

By the same reasoning as in Subcase (i), it follows that $k=\ell$. However, if $k = \ell$, then the fourth term of (28) cannot be canceled by any other terms on the left-hand side of (10), neither can it be represented on the right-hand side of (10). This implies $b_{u-\ell } = 0$ which contradicts our assumption.

Case 2.2.2. Assume $b_{u-\ell } = 0$. From (17) with $i = u+\ell$ and $j = u-\ell$, it follows that

$$\begin{aligned} a_{u-\ell }b_{u+\ell } = 0 \end{aligned}$$

which, recalling that $b_{u+\ell } \ne 0$, implies $a_{u-\ell } = 0$. Then,

$$\begin{aligned} L_1(X)&= a_u X^{2^u} + a_{u+\ell } X^{2^{u+\ell }} + a_{u+2\ell } X^{2^{u+2\ell }}&\text {and}&L_2(X)&= b_{u+\ell }X^{2^{u+\ell }}. \end{aligned}$$

Plugging these polynomials into (10), the expressions $L_1(x)^{2^{2k}(2^k+1)}$, $L_1(x)^{2^{2k}} L_2(x)^{2^k}$ and $\beta L_2(x)^{2^k+1}$ are as in (24), (25) and (26), respectively, where we substitute u by $u+\ell$. By the same reasoning as in Case 2.1.1, Subcase (i), it follows that $k=\ell$. If $k=\ell$, analogously to Case 2.1.1, Subcase (i), the following terms occur on the left-hand side of (10):

$$\begin{aligned} a_{u+2k}^{2^{3k}}a_{u}^{2^{2k}} x^{2^{u+2k}(2^{3k}+1)},&(a_{u+k}^{2^{3k}}a_{u}^{2^{2k}} + a_{u+2k}^{2^{2k}} b_{u+k}^{2^k}) x^{2^{u+2k}(2^{2k}+1)}. \end{aligned}$$

As neither of them can be represented on the right-hand side of (10), their coefficients need to be zero. As $a_u \ne 0$, it follows that $a_{u+2k} = 0$, and, consequently, $a_{u+k}=0$. Hence, $L_1(X)$ and $L_2(X)$ are monomials of the form

$$\begin{aligned} L_1(X)&= a_u X^{2^u}&\text {and}&L_2(X) = b_{u+k} X^{2^{u+k}}, \end{aligned}$$

(29)

and $M_1(X) = a_u^{2^{2k}}b_{u+k}^{2^k} X^{2^{u+2k+1}}$.

Note that if we consider Case 2.2 with $a_u = 0$ and $b_u \ne 0$, we obtain

$$\begin{aligned} L_1(X)&= a_{u+k} X^{2^{u+k}}&\text {and}&L_2(X) = b_{u} X^{2^{u}} \end{aligned}$$

(30)

and $M_1(X)=a_{u+k}^{2^{2k}} b_u^{2^k} X^{2^{u+2k+1}}$ from Case 2.2.2. This concludes the proof of our Claim.

We summarize the results we have obtained so far. If the Taniguchi APN functions $f_{k,1,\beta }$ and $f_{\ell ,1,\beta '}$ are EL-equivalent, then $k = \ell$ and $L_1(X)$ and $L_2(X)$ meet the following conditions: either, one of the polynomials $L_1(X)$ and $L_2(X)$ is zero and the other one is a monomial, see (13) and (14), or both $L_1(X)$ and $L_2(X)$ are monomials, either of the same degree or of degrees $2^u$ and $2^{u+k}$, see (23), (29) and (30). Vice versa, the same statements hold for $L_3(Y)$ and $L_4(Y)$. It remains to be shown that the EL-equivalence of $f_{k,1,\beta }$ and $f_{k,1,\beta '}$ implies $\beta ' = \beta ^{2^i}$ for some $i \in \{0,\dots ,m-1\}$. Combining the results on $L_1(X),L_2(X),L_3(Y),L_4(Y)$ mentioned above, it is clear that the polynomials $L_A(X,Y)$ and $L_B(X,Y)$ have to be of one of the following forms:

• (a) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_w Y^{2^w}$ and $L_B(X,Y) = b_u X^{2^u} + \overline{b}_w Y^{2^w}$,

• (b) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_w Y^{2^w}$ and $L_B(X,Y) = b_u X^{2^u} + \overline{b}_{w+k} Y^{2^{w+k}}$,

• (c) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_{w+k} Y^{2^{w+k}}$ and $L_B(X,Y) = b_u X^{2^u} + \overline{b}_w Y^{2^w}$,

• (d) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_w Y^{2^w}$ and $L_B(X,Y) = b_{u+k} X^{2^{u+k}} + \overline{b}_w Y^{2^w}$,

• (e) $L_A(X,Y) = a_{u+k} X^{2^{u+k}} + \overline{a}_w Y^{2^w}$ and $L_B(X,Y) = b_u X^{2^u} + \overline{b}_w Y^{2^w}$,

• (f) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_w Y^{2^w}$ and $L_B(X,Y) = b_{u+k} X^{2^{u+k}} + \overline{b}_{w+k} Y^{2^{w+k}}$,

• (g) $L_A(X,Y) = a_u X^{2^u} + \overline{a}_{w+k} Y^{2^{w+k}}$ and $L_B(X,Y) = b_{u+k} X^{2^{u+k}} + \overline{b}_w Y^{2^w}$,

• (h) $L_A(X,Y) = a_{u+k} X^{2^{u+k}} + \overline{a}_{w} Y^{2^{w}}$ and $L_B(X,Y) = b_{u} X^{2^{u}} + \overline{b}_{w+k} Y^{2^{w+k}}$,

• (i) $L_A(X,Y) = a_{u+k} X^{2^{u+k}} + \overline{a}_{w+k} Y^{2^{w+k}}$ and $L_B(X,Y) = b_{u} X^{2^{u}} + \overline{b}_w Y^{2^w}$.

Note that, as $L(X,Y) = (L_A(X,Y), L_B(X,Y))$ has to be a permutation polynomial, it is neither possible that $L_A(X,Y)$ or $L_B(X,Y)$ is zero nor that both $L_A(X,Y)$ and $L_B(X,Y)$ depend only on X or only on Y. We will show that all cases listed above lead to the conclusion that $L_A(X,Y)$ and $L_B(X,Y)$ need to be monomials of the same degree of the shape

$$\begin{aligned} L_A(X,Y)&= a_u X^{2^u}&\text {and}&L_B(X,Y)&= b_u Y^{2^u}. \end{aligned}$$

(31)

We rewrite (8) and (9) considering $k = \ell$:

$$\begin{aligned}&L_A(x,y)^{2^{2k}(2^k+1)} + L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k} +\beta L_B(x,y)^{2^k+1} \nonumber \\&\quad = N_1(x^{2^{2k}(2^k+1)} + x^{2^{2k}} y^{2^k} + \beta ' y^{2^k+1}) + N_3(xy) + M_A(x,y), \end{aligned}$$

(32)

$$\begin{aligned} L_A(x,y)L_B(x,y)&= N_2(x^{2^{2k}(2^k+1)} + x^{2^{2k}} y^{2^k}\nonumber \\ {}&\quad + \beta ' y^{2^k+1}) + N_4(xy) + M_B(x,y). \end{aligned}$$

(33)

We will plug all the possible combinations (a)–(i) into these equations. We begin with (b). By proceeding analogously, the cases (c)–(e) lead to the same result. If we plug the polynomials of (b) into the left-hand side of (33), we obtain

$$\begin{aligned} L_A(x,y)L_B(x,y)&= a_u b_u x^{2^{u+1}} + \overline{a}_w \overline{b}_{w+k} y^{2^w(2^k+1)} \nonumber \\&\quad + a_u \overline{b}_{w+k} x^{2^u}y^{2^{w+k}} + \overline{a}_w b_u x^{2^u} y^{2^w}. \end{aligned}$$

(34)

Note that the first term of (34) is linearized. As there is no term containing the factor $x^{2^k+1}$, we need $N_2(X) = 0$ on the right-hand side of (33). This implies, first, that the coefficient $\overline{a}_w \overline{b}_{w+k}$ of the second summand of (34) has to be zero, and second, that the third and the fourth summands of (34) cannot be represented simultaneously on the right-hand side of (33). The coefficient of the second summand of (34) is zero if $\overline{a}_{w}$ or $\overline{b}_{w+k}$ is zero. We separate the proof into two cases:

Case 1. Assume $\overline{a}_w = 0$. Note that this implies $a_u \ne 0$ and $\overline{b}_{w+k} \ne 0$ as otherwise L(X, Y) would not be a permutation polynomial. If $\overline{a}_w = 0$, then (33) holds only if $u=w+k$. Set $u = w+k$ and plug $L_A(x,y)$ and $L_B(x,y)$ into the left-hand side of (32). We obtain

$$\begin{aligned} L_A(x,y)^{2^{2k}(2^k+1)} = a_u^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} \end{aligned}$$

(35)

and

$$\begin{aligned} L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k} = a_u^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^k+1)} + a_u^{2^{2k}} \overline{b}_u^{2^k} x^{2^{u+2k}} y^{2^{u+k}} \end{aligned}$$

(36)

and

$$\begin{aligned} \beta L_B(x,y)^{2^k+1}&= \beta b_u^{2^k+1} x^{2^u(2^k+1)} + \beta \overline{b}_u^{2^k+1} y^{2^u(2^k+1)} \nonumber \\&\quad + \beta b_u^{2^k} \overline{b}_u x^{2^{u+k}} y^{2^u} + \beta \overline{b}_u^{2^k} b_u x^{2^u} y^{2^{u+k}}. \end{aligned}$$

(37)

The fourth summand of (37) cannot be canceled by any other summand of (35)–(37) and it cannot be represented on the right-hand side of (32). As $\beta , \overline{b}_u \ne 0$, it follows that $b_u = 0$. Consequently, $L_A(X,Y)$ and $L_B(X,Y)$ are monomials of the same degree as in (31).

Case 2. Assume $\overline{b}_{w+k} = 0$. By the same reasoning as above, this implies $b_u \ne 0$ and $\overline{a}_u \ne 0$. Now, (33) holds for $u=w$. Set $u = w$ and plug $L_A(x,y)$ and $L_B(x,y)$ into the left-hand side of (32). The summand $L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k}$ contains the term

$$\begin{aligned} \overline{a}_u^{2^{2k}} b_u^{2^k} x^{2^{u+k}} y^{2^{u+2k}}, \end{aligned}$$

that has a nonzero coefficient and cannot be canceled by the other terms on the left-hand side of (32). However, it cannot be represented on the right-hand side of (32). This is a contradiction.

We next study (f). By symmetry, the same result also holds for (i). Moreover, an analogous approach gives identical results for (g) and (h). If we plug $L_A(X,Y)$ and $L_B(X,Y)$ of (f) into (33), we obtain

$$\begin{aligned} L_A(x,y)L_B(x,y)&= a_u b_{u+k} x^{2^u(2^k+1)} + \overline{a}_w \overline{b}_{w+k} y^{2^w(2^k+1)} \nonumber \\&\quad + a_u \overline{b}_{w+k} x^{2^u}y^{2^{w+k}} + \overline{a}_w b_{u+k} x^{2^{u+k}} y^{2^w}. \end{aligned}$$

(38)

If all coefficients are nonzero, we need $u = w+2k$ to represent the first and the second summands of (38) on the right-hand side of (33). Then, however, the fourth term of (38) cannot be represented on the right-hand side of (33), which is a contradiction.

Now assume one of the coefficients is zero. We show the case $b_{u+k} = 0$. If we assume $a_u = 0$ instead, we end up with the same contradiction as in Case 2 of the study of (b). By symmetry, analogous results can be obtained when assuming $\overline{a}_w = 0$ or $\overline{b}_{w+k} = 0$. If $b_{u+k} = 0$, it follows that $a_{u}$ and $\overline{b}_{w+k}$ are nonzero as otherwise L(X, Y) would not be a permutation polynomial. Moreover, as the first term of (38) vanishes, we need $N_2(X)=0$. Then, also the second term of (38) cannot be represented on the right-hand side of (33) and $\overline{a}_w \overline{b}_{w+k}$ has to be zero. As $\overline{b}_{w+k} \ne 0$, we need $\overline{a}_{w} = 0$ for the second coefficient to be zero. Moreover, we need $u=w+k$ to represent the third summand of (38) on the right-hand side of (33). Consequently, $L_A(X,Y)$ and $L_B(X,Y)$ are monomials as in (31).

Finally, we study (a). If we plug $L_A(X,Y)$ and $L_B(X,Y)$ of (a) into (33), we obtain

$$\begin{aligned} L_A(x,y)L_B(x,y) = a_u b_{u} x^{2^{u+1}} + \overline{a}_{w} \overline{b}_{w} y^{2^{w+1}} + (a_u \overline{b}_{w} + \overline{a}_w b_u) x^{2^u}y^{2^w}. \end{aligned}$$

(39)

We separate two cases: in the first case, the third term of (39) vanishes; in the second case, its coefficient is nonzero.

Case 1. We first show that the third term of (41) can only vanish if all coefficients are nonzero. Suppose $a_u = 0$. Then, $\overline{a}_w b_u$ has to be zero as well. However, this is not possible, as $a_u = 0$ implies that $\overline{a}_w$ and $b_u$ are nonzero. By symmetry, the same result is obtained if we assume that any other coefficient is zero. Consequently, assume all coefficients are nonzero and $\frac{a_u}{b_u} = \frac{\overline{a}_w}{\overline{b}_w}$. Then, (39) does not provide any information, as the left-hand side is a linearized polynomial. We plug $L_A(X,Y)$ and $L_B(X,Y)$ into the left-hand side of (32) and obtain

$$\begin{aligned} L_A(x,y)^{2^{2k}(2^k+1)}&= a_u^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} + \overline{a}_{w}^{2^{2k}(2^k+1)} y^{2^{w+2k}(2^k+1)} \nonumber \\&\quad + a_u^{2^{3k}} \overline{a}_w^{2^{2k}} x^{2^{u+3k}} y^{2^{w+2k}} + \overline{a}_w^{2^{3k}} a_u^{2^{2k}} x^{2^{u+2k}} y^{2^{w+3k}} \end{aligned}$$

(40)

and

$$\begin{aligned} L_A(x,y)^{2^{2k}} L_B(x,y)^{2^k}&= a_u^{2^{2k}} b_u^{2^k} x^{2^{u+k}(2^k+1)} + \overline{a}_w^{2^{2k}} \overline{b}_w^{2^k} y^{2^{w+k}(2^k+1)} \nonumber \\&\quad + a_u^{2^{2k}} \overline{b}_w^{2^k} x^{2^{u+2k}} y^{2^{w+k}} + \overline{a}_w^{2^{2k}} b_u^{2^k} x^{2^{u+k}} y^{2^{w+2k}} \end{aligned}$$

(41)

and

$$\begin{aligned} \beta L_B(x,y)^{2^k+1}&= \beta b_u^{2^k+1} x^{2^u(2^k+1)} + \beta \overline{b}_w^{2^k+1} y^{2^w(2^k+1)} + \nonumber \\&\quad + \beta b_u^{2^k} \overline{b}_w x^{2^{u+k}} y^{2^w} + \beta \overline{b}_w^{2^k} b_u x^{2^u} y^{2^{w+k}}. \end{aligned}$$

(42)

No matter how we choose u and w, the third and the fourth summands of (40) cannot be canceled by the terms of (40)–(42) and they cannot be represented simultaneously on the right-hand side of (32). Hence, at least one of the coefficients needs be zero which is a contradiction.

Case 2. Assume $a_u \overline{b}_{w} + \overline{a}_w b_u \ne 0$. As there are no terms on the left-hand side of (33) containing the factors $x^{2^k+1}$ and $y^{2^k+1}$, it follows that $N_2(X)=0$, and we need $u=w$ to represent the third summand of (39) on the right-hand side of (33). We plug $L_A(X,Y)$ and $L_B(X,Y)$ into (32) and obtain the same expressions as in (40)–(42) with $u=w$. Analogously to Case 1, the third and the fourth term of (40) cannot be represented on the right-hand side of (32) at the same time. Hence, $a_u\overline{a}_w$ has to be zero. Assuming $\overline{a}_w = 0$, we obtain, by similar reasoning as in the previous cases, that $L_A(X,Y)$ and $L_B(X,Y)$ have to be monomials of the same degree as in (31). Assuming $a_u = 0$, we obtain the same contradiction as in the study of (b), Case 2.

In summary, the only possible choice of $L_A(X,Y)$ and $L_B(X,Y)$ that can satisfy (32) and (33) is $L_A(X,Y) = a_u X^{2^u}$ and $L_B(x,y)=\overline{b}_u Y^{2^u}$. Considering  (33) for these monomials, it follows that $N_2(X) = 0$, $N_4(X) = a_u\overline{b}_uX^{X^{2^u}}$, and $M_B(X,Y) = 0$. If we plug $L_A(X,Y)$ and $L_B(X,Y)$ into (32), we obtain

$$\begin{aligned}&a_u^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} + a_u^{2^{2k}} \overline{b}_u^{2^k} x^{2^{u+2k}} y^{2^{u+k}} + \beta \overline{b}_u^{2^k+1} y^{2^u(2^k+1)} \nonumber \\&\quad = N_1(x^{2^{2k}(2^k+1)} + x^{2^{2k}} y^{2^k} + \beta ' y^{(2^k+1)}) + N_3(xy) + M_A(x,y). \end{aligned}$$

(43)

Obviously, $N_3(X) = 0$ and $M_A(X,Y) = 0$ and $N_1(X)$ has to be a monomial of degree u, the same degree as $L_A(X,Y)$ and $L_B(X,Y)$. Write $N_1(X) = c_u X^{2^u}$. Then, (43) becomes

$$\begin{aligned}&a_u^{2^{2k}(2^k+1)} x^{2^{u+2k}(2^k+1)} + a_u^{2^{2k}} \overline{b}_u^{2^k} x^{2^{u+2k}} y^{2^{u+k}} + \beta \overline{b}_u^{2^k+1} y^{2^u(2^k+1)} \\&\quad = c_ux^{2^{u+2k}(2^k+1)} + c_ux^{2^{u+2k}} y^{u+2^k} + c_u\beta '^{2^u} y^{2^u(2^k+1)} \end{aligned}$$

and the coefficients have to meet the following conditions:

$$\begin{aligned} a_u^{2^{2k}(2^k+1)}&= c_u,&a_u^{2^{2k}} \overline{b}_u^{2^k}&= c_u,&\beta \overline{b}_u^{2^k+1}&= c_u \beta '^{2^u}. \end{aligned}$$

(44)

The first two equations of (44) imply $\overline{b}_u = a_u^{2^{2k}}$ and $c_u = \overline{b}_u^{2^k+1}$. Combining the later result with the third equation of (44), it follows that $\beta = \beta '^{2^u}$. $\square$

From the proof of Theorem 4.5, we can deduce the order of the automorphism group of the Taniguchi APN functions. Note that Theorem 4.6 only holds for $m \ge 4$. For $m=2$, the unique Taniguchi APN function $f_{1,1,1}$ on $\mathbb {F}_{2^4}$ is CCZ-equivalent to the Gold APN function $x \mapsto x^3$. Its automorphism group has order 5760. If $m = 3$, the unique Taniguchi APN function $f_{1,1,\beta }$ on $\mathbb {F}_{2^6}$ is CCZ-equivalent to the APN function $x \mapsto x^3 + ux^{24} + x^{10}$, where u is primitive in $\mathbb {F}_{2^6}$, that was first given by Browning et al. [8]. In this case, $|\hbox {Aut}(f_{1,1,\beta })| = 896$.

Theorem 4.6

Let $m \ge 4$, and let $f_{k,\alpha ,\beta }$ be a Taniguchi APN function from Theorem 3.4 on $\mathbb {F}_{2^{2m}}$. Define $\beta ' = \frac{\beta }{\alpha ^{2^{-k}+1}}$. Then,

$$\begin{aligned} |\hbox {Aut}_{EL}(f_{k,\alpha ,\beta })| = {\left\{ \begin{array}{ll} 3m(2^m-1) &{}\text {if } \alpha = 0 \text { and } m = 4, \\ \frac{3}{2}m(2^m-1) &{}\text {if } \alpha = 0 \text { and } m \ge 5,\\ \dfrac{m(2^m-1)}{\min \{u \ge 1 : \beta '^{2^u} = \beta '\}} &{}\text {if } \alpha \ne 0 \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} |\hbox {Aut}(f_{k,\alpha ,\beta })| = {\left\{ \begin{array}{ll} 3m2^{2m}(2^m-1) &{}\text {if } \alpha = 0 \text { and } m =4,\\ 3m2^{2m-1}(2^m-1) &{}\text {if } \alpha = 0 \text { and } m \ge 5,\\ \dfrac{m 2^{2m}(2^m-1)}{\min \{u \ge 1 : \beta '^{2^u} = \beta '\}} &{}\text {if } \alpha \ne 0. \end{array}\right. } \end{aligned}$$

Proof

We determine $|\hbox {Aut}_{EL}(f_{k,\alpha ,\beta })|$; then, $|\hbox {Aut}(f_{k,\alpha ,\beta })|$ follows from Proposition 2.3 and Lemma 2.4. If $\alpha = 0$, according to Proposition 4.1, a Taniguchi APN function $f_{k,0,\beta }$ is linearly equivalent to the Pott–Zhou APN function $g_{k,2k,\beta }$ whose automorphism group was determined by the present authors [26, Theorem 5.2].

If $\alpha \ne 0$, we know from Proposition 4.4 (a) that $f_{k,\alpha ,\beta }$ is linearly equivalent to $f_{k,1,\beta '}$. We study the case $\alpha = 1$. For $m=4$ the results can be confirmed computationally with Magma [6]. Assume $m \ge 5$. Then, the proof of Theorem 4.5 holds. We count the number of equivalence mappings that map $f_{k,1,\beta '}$ on itself. Therefore, we consider the conditions given in (44) which the coefficients of the linearized monomials $L_A(X,Y)$, $L_B(X,Y)$ and $N_1(X)$ have to meet. We have shown that (44) implies

$$\begin{aligned} \overline{b}_u&= a_u^{2^{2k}},&c_u&= \overline{b}_u^{2^k+1},&\text {and}&\beta '^{2^u-1} = 1. \end{aligned}$$

The number of u such that $\beta '^{2^u-1} = 1$ is given by

$$\begin{aligned} \frac{m}{\min \{u \ge 1 : \beta '^{2^u} = \beta '\}}. \end{aligned}$$

Next, we have $2^m-1$ choices for $a_u$. By choosing $a_u$, the coefficients $\overline{b}_u$ and $c_u$ are uniquely determined. $\square$

From Theorem 4.6, we easily deduce the following result about the inequivalence of Taniguchi and Pott–Zhou APN functions. Recall that Pott–Zhou APN functions only exist on $\mathbb {F}_{2^{2m}}$ where m is even and that we have already solved the case $\alpha = 0$ in Proposition 4.1.

Corollary 4.7

Let $m \ge 4$ be even. Let $f_{k,\alpha ,\beta }$, where $\alpha \ne 0$, be a Taniguchi APN function from Theorem 3.1 on $\mathbb {F}_{2^{2m}}$, and let $g_{\ell ,s,\gamma }$ be a Pott–Zhou APN function from Theorem 3.4 on $\mathbb {F}_{2^{2m}}$. Then, $f_{k,\alpha ,\beta }$ and $g_{\ell ,s,\gamma }$ are CCZ-inequivalent.

Proof

The order of the automorphism group of a vectorial Boolean function is invariant under CCZ-equivalence. For a Taniguchi APN function $f_{k, \alpha , \beta }$ on $\mathbb {F}_{2^{2m}}$, we determined the order of the automorphism group $\hbox {Aut}(f_{k, \alpha , \beta })$ in Theorem 4.6. For a Pott–Zhou APN function $g_{\ell ,s,\gamma }$ on $\mathbb {F}_{2^{2m}}$, the present authors [26, Theorem 5.2] showed that

$$\begin{aligned} |\hbox {Aut}(g_{\ell ,s,\gamma })| = {\left\{ \begin{array}{ll} 3m2^{2m}(2^m-1) &{}\text {if } s \in \{0, \frac{m}{2}\},\\ 3m2^{2m-1}(2^m-1) &{}\text {otherwise}.\\ \end{array}\right. } \end{aligned}$$

As clearly $\frac{m}{\min \{u \ge 1 : \beta '^{2^u} = \beta '\}} \le m$, it follows that $\frac{m}{\min \{u \ge 1 : \beta '^{2^u} = \beta '\}}< \frac{3}{2}m < 3m$. Hence, the automorphism groups of $f_{k,\alpha ,\beta }$ and $g_{\ell ,s,\gamma }$ are of different order which implies that the functions are CCZ-inequivalent. $\square$

From Corollary 4.7, we derive the final piece to determine the complete equivalence of Taniguchi APN functions.

Corollary 4.8

Let $m \ge 4$ be even. Two Taniguchi APN functions $f_{k,0,\beta }$, and $f_{\ell ,\alpha ',\beta '}$, where $\alpha ' \ne 0$, from Theorem 3.1 on $\mathbb {F}_{2^{2m}}$ are CCZ-inequivalent.

Proof

According to Proposition 4.1, $f_{k,0,\beta }$ is CCZ-equivalent to a Pott-Zhou APN function $g_{k,2k,\gamma }$ from Theorem 3.4. The result now follows from Corollary 4.7. $\square$

5 On the Total Number of CCZ-Inequivalent Taniguchi APN Functions on $\pmb {\mathbb {F}_{2^{2m}}}$

The results from Sect. 4 allow us to determine the number of CCZ-inequivalent Taniguchi APN functions on $\mathbb {F}_{2^{2m}}$ for any m. This will be done in Theorem 5.5 by counting the number of parameters k, $\alpha$ and $\beta$ that lead to inequivalent functions. Recall from Proposition 4.4 that every Taniguchi APN function $f_{k,\alpha ,\beta }$ where $\alpha \ne 0$ is CCZ-equivalent to a function $f_{k,1,\beta '}$ for some $\beta ' \in \mathbb {F}_{2^m}^*$. Hence, we only need to consider functions with $\alpha = 0$ or $\alpha = 1$. As we know from Proposition 4.1 that $f_{k,0,\beta }$ is equivalent to a Pott–Zhou APN function, whose equivalence problem was solved by the present authors [26], we focus on $\alpha = 1$ first.

Recall from Theorem 4.5 that two Taniguchi APN functions $f_{k,1,\beta }$ and $f_{k,1,\beta '}$ on $\mathbb {F}_{2^{2m}}$ are CCZ-equivalent if and only if $\beta ' = \beta ^{2^i}$ for some $i \in \{0, \dots , m-1\}$. Consequently, to obtain the exact number of $\beta$ providing inequivalent functions for fixed k, we need to determine the number of orbits of $\beta$ such that $X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$ under the action of the Galois group $\hbox {Gal}(\mathbb {F}_{2^m}/ \mathbb {F}_2)$. We will do this in Proposition 5.4 with the help of the following series of technical lemmas.

Lemma 5.1

If $k>1$ is an integer with $\gcd (k,3) = 1$, then 3k does not divide $2^{k}+1$.

Proof

Assume, by way of contradiction, that $3k \mid 2^{k}+1$. By the Chinese Remainder Theorem, $2^{k} \equiv -1 \pmod {3}$ which means that k is odd.

Let $k=p_1^{t_1}\cdots p_s^{t_s}$, where $p_1, \dots , p_s$ are prime numbers such that $3<p_1<p_2<\cdots <p_s$ and $t_i\ge 1$ for $i = 1, \dots , s$. For convenience, we set $p=p_1$ and $t=t_1$ in the remainder of this proof.

By the Chinese Remainder Theorem, it also follows that $2^k\equiv -1 \pmod {p^t}$. Denote by $\varphi (x)$ the Euler’s totient function of x. Since $2^{2^k} \equiv 1 \pmod {p^t}$ and the unit group of the integer ring $\mathbb {Z}_{p^t}$ has order $\varphi (p^t)$, it follows that $\mathrm {ord}_{p^{t}}(2) \mid \gcd (2k, \varphi (p^{t}))$. Note that $\varphi (p^t) = (p-1)p^{t-1}$. As $p-1 < p_i$ for all $i \in \{1,\dots , s\}$, the number $p-1$ is not divisible by any of the $p_i$. Recalling that $k = p^{t} p_2^{t_2}\cdots p_s^{t_s}$, it follows that $\gcd (2k,\varphi (p^t))=2p^{t-1}$. Consequently, $2^{2p^{t-1}}-1\equiv 0 \pmod {p^t}$. Thus, $2^{2p^{t-1}}-1\equiv 4^{p^{t-1}}-1\equiv 0 \pmod {p}$. As $4^{p}=4\pmod {p}$, we obtain $4-1\equiv 0\pmod {p}$ which means $p=3$. This is a contradiction to the assumption $3 < p$. $\square$

Lemma 5.2

Suppose that k and m are positive integers satisfying $\gcd (k,m)=1$. Write $m=rp$ for an integer r and a prime p. For $\beta \in \mathbb {F}_{2^r}$, suppose that the polynomial $P(X)=X^{2^k+1}+X+\beta$ has no root in $\mathbb {F}_{2^r}$.

• (a) If $p\ne 3$, then P(X) has no root in $\mathbb {F}_{2^m}$.

• (b) If $p= 3$, then P(X) has exactly three roots in $\mathbb {F}_{2^m}$.

Proof

Set $\sigma (x)=x^{2^{r}}$ for x in any extension of $\mathbb {F}_{2^r}$.

We show (a) first. Suppose that P(X) has at least one root $x_0 \in \mathbb {F}_{2^m}$. Then, $x_0, \sigma (x_0), \dots , \sigma ^{p-1}(x_0)$ have to be p distinct roots of P(X) in $\mathbb {F}_{2^m}$ because $\sigma (P(x_0))= \sigma (x_0)^{2^k+1}+\sigma (x_0)+\beta =0$ and p is prime. Helleseth and Kholosha [23, Theorem 1] showed that if P(X) has more than one root, then P(X) has exactly three roots in $\mathbb {F}_{2^m}$ which contradicts the assumption that $p\ne 3$.

We next prove (b). Now $m=3r$. If P(X) has at least one root in $\mathbb {F}_{2^m}$, by the proof of (a), it has exactly three roots in $\mathbb {F}_{2^m}$ and we are done. Assume, by way of contradiction, that P(X) has no root in $\mathbb {F}_{2^m}$. First, if $k=1$, then P(X) has degree 3 and is irreducible over $\mathbb {F}_{2^r}$. Therefore, P(X) splits over $\mathbb {F}_{2^m}$ which contradicts our assumption.

From now on, assume $k>1$. Write $P(X) = P_1(X)P_2(X) \cdots P_s(X)$ for irreducible polynomials $P_1(X), \dots , P_s(X) \in \mathbb {F}_{2^m}$. Since $\deg (P(X)) = 2^k+1$ is odd, there exists a polynomial $P_j(X)$, where $j \in \{1,\dots , s\}$, of odd degree. Denote by $J_{\mathrm{odd}}$ the set of all $j \in \{1,\dots ,s\}$ such that $\deg (P_j(X))$ is odd, and let $j^* \in J_{\mathrm{odd}}$ such that $\deg (P_{j^*}(X)) \le \deg (P_j(X))$ for all $j \in J_{\mathrm{odd}}$. Set $\ell = \deg (P_{j^*}(X))$ and note that $\ell > 1$ and $\ell$ is odd. Then, $P_{j^*}(X)$ splits over $\mathbb {F}_{2^{m\ell }}$, which is an extension of $\mathbb {F}_{2^m}$ with $[\mathbb {F}_{2^{m\ell }}:\mathbb {F}_{2^m}]=\ell$. Consequently, P(X) has a root in $\mathbb {F}_{2^{m\ell }}$, and there is no root of P(X) in any proper subfield of $\mathbb {F}_{2^{m\ell }}$ containing $\mathbb {F}_{2^m}$. Define $h = \gcd (m\ell , k)$. As m and k are coprime, this implies $h = \gcd (\ell , k)$ and, in particular, $h \mid \ell$. Then, $\mathbb {F}_{2^h}=\mathbb {F}_{2^{m\ell }}\cap \mathbb {F}_{2^k}$. As $\ell$ is odd, according to Bluher [5, Theorem 5.6], P(X) has exactly $2^{h}+1$ roots in $\mathbb {F}_{2^{m\ell }}$. If $h = 1$, then the roots of P(X) in $\mathbb {F}_{2^{m\ell }}$ are also elements of $\mathbb {F}_{2^m}$ as $m=3r$. This contradicts our assumption. Hence, assume $h > 1$. We may regard $\sigma$ as an element in $\hbox {Gal}(\mathbb {F}_{2^{m\ell }}/\mathbb {F}_{2^r})$. If $3\not \mid \ell$, then it is clear that $x_0$, $\sigma (x_0)$, $\dots , \sigma ^{3\ell }(x_0)$ are pairwise distinct for any root $x_0$ of P(X) in $\mathbb {F}_{2^{m\ell }}$. If $3\mid \ell$, then $x_0$, $\sigma (x_0)$, $\dots , \sigma ^{3\ell }(x_0)$ are still pairwise distinct for any root $x_0$ of P(X) in $\mathbb {F}_{2^{m\ell }}$. The reason is as follows. Suppose that $\sigma ^{j}(x_0)=x_0$ for some $j<3\ell$ with $j\mid 3\ell$. This means $[\mathbb {F}_{2^r}(x_0): \mathbb {F}_{2^r}]=j$. Thus,

$$\begin{aligned}{}[\mathbb {F}_{2^m}(x_0):\mathbb {F}_{2^m}] = {\left\{ \begin{array}{ll} j &{}\text {if } 3\not \mid j,\\ j/3 &{}\text {if } 3\mid j. \end{array}\right. } \end{aligned}$$

For the first case, $3\not \mid j$, as $\mathbb {F}_{2^{m\ell }}=\mathbb {F}_{2^m}(x_0)$ by definition, we get $j=\ell$ which is a contradiction to the assumption that $3\mid \ell$. For the second case, $3\mid j$, we get $\ell = [\mathbb {F}_{2^{m\ell }}:\mathbb {F}_{2^m}] = [\mathbb {F}_{2^m}(x_0):\mathbb {F}_{2^m}] = j/3$ which contradicts the assumption $j<3\ell$.

Therefore, $3\ell$ divides $2^h+1$, in particular, as $h \mid \ell$, we obtain $3h \mid 2^h+1$. By Lemma 5.1, this is only possible if $\gcd (h,3) > 1$ which implies $\gcd (m,k) > 1$. This is a contradiction. $\square$

For any two relatively prime positive integers k and m, define

$$\begin{aligned} \Phi (m) = \{\beta \in \mathbb {F}_{2^m}: X^{2^k+1}+X+\beta \text { has no root in }\mathbb {F}_{2^m}\} \end{aligned}$$

(45)

and

$$\begin{aligned} M(m) =|\Phi (m)| \end{aligned}$$

and

$$\begin{aligned} N(m) = \left| \{\beta \in \Phi (m): \beta \notin \mathbb {F}_{2^{m'}} \text { with } m'< m \text { and } m'\mid m\}\right| . \end{aligned}$$

(46)

According to Lemma 3.3,

$$\begin{aligned} M(m)=\frac{2^m+(-1)^{m+1}}{3}. \end{aligned}$$

(47)

In the following Lemma 5.3, we determine the exact value of N(m).

Lemma 5.3

Suppose that $m=3^{n_0}\prod _{i=1}^t p_i^{n_i}$ where $n_0$ is a non-negative integer, $p_1, \dots , p_t$ are distinct prime numbers, and $n_1, \dots , n_t$ are positive integers. If $t = 0$, that means $m = 3^{n_0}$ and, in particular, includes the case $m=1$, then

$$\begin{aligned} N(m)=\frac{2^{m}+1}{3}. \end{aligned}$$

If $t \ge 1$, then

$$\begin{aligned} N(m)&= \frac{1}{3} \Bigg ( 2^m -\sum _{i=1}^t 2^{\frac{m}{p_i}} + \sum _{\begin{array}{c} i,j=1,\\ j \ne i \end{array}}^t 2^{\frac{m}{p_i p_j}}- \dots \nonumber \\&\quad \dots + (-1)^\ell \sum _{\begin{array}{c} i_1,\dots ,i_\ell = 1\\ \text {pairwise distinct} \end{array}}^t 2^{\frac{m}{p_{i_1} \cdots p_{i_\ell }}}+ \dots + (-1)^t2^{\frac{m}{p_1 p_2 \cdots p_t}}-\varepsilon \Bigg ), \end{aligned}$$

(48)

where

$$\begin{aligned} \varepsilon = {\left\{ \begin{array}{ll} 2 &{} \text {if } t=1 \text { and } m \equiv 2 \pmod {4},\\ 0 &{}\text {otherwise}. \end{array}\right. } \end{aligned}$$

Proof

By definition, to determine N(m), we have to exclude each element in $\Phi (m)\cap \mathbb {F}_{2^{m'}}$ from $\Phi (m)$ for every proper subfield $\mathbb {F}_{2^{m'}}$ of $\mathbb {F}_{2^m}$. We first consider the case $t=0$: If $n_0 = 1$, which means $m=1$, then $X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_2$ if and only if $\beta = 1$. Hence, $N(1) = 1$. If $n_0 \ge 1$, by Lemma 5.2,

$$\begin{aligned} \Phi (m)\cap \mathbb {F}_{2^{m'}}= {\left\{ \begin{array}{ll} \emptyset &{} \text {if } 3m' \mid m,\\ \Phi (m') &{} \text {if } 3m' \not \mid m. \end{array}\right. } \end{aligned}$$

Hence, we get $N(3^{n_0})=M(3^{n_0})$ and, by (47), $M(3^{n_0}) = \frac{2^m+1}{3}$. From now on, assume $t \ge 1$. Then, by the inclusion-exclusion principle,

$$\begin{aligned} N(m)&=M(m)-\sum _{i=1}^t M\left( \frac{m}{p_i}\right) + \sum _{\begin{array}{c} i,j=1,\\ j \ne i \end{array}}^t M\left( \frac{m}{p_ip_j}\right) - \cdots \nonumber \\&\quad \dots +(-1)^\ell \sum _{\begin{array}{c} i_1,\cdots ,i_\ell = 1 \\ \text {pairwise distinct} \end{array}}^t M\left( \frac{m}{p_{i_1}\cdots p_{i_\ell }}\right) + \cdots + (-1)^t M\left( \frac{m}{p_1\cdots p_t}\right) . \end{aligned}$$

(49)

If m is odd, then $m'$ is odd for all $m' \mid m$. If $4 \mid m$, then $m'$ is even for all $m' = \frac{m}{p_{i_1} \cdots p_{i_\ell }}$ that occur in (49). Consequently, in these two cases, by (47), we have $M(m')=\frac{2^{m'}+(-1)^{m+1}}{3}$ for any $m' = \frac{m}{p_{i_1} \cdots p_{i_\ell }}$ occurring in (49). Plugging $M(m')$ into (49), we obtain

$$\begin{aligned} N(m)=&\frac{1}{3}\Bigg ( 2^m - \sum _{i=1}^t 2^{\frac{m}{p_i}} + \sum _{\begin{array}{c} i,j=1,\\ j \ne i \end{array}}^t 2^{\frac{m}{p_i p_j}} - \cdots + (-1)^t 2^{\frac{m}{p_1p_2\cdots p_t}} \Bigg )\nonumber \\&+ \frac{(-1)^{m+1}}{3}\left( 1-\left( {\begin{array}{c}t\\ 1\end{array}}\right) +\left( {\begin{array}{c}t\\ 2\end{array}}\right) -\cdots +(-1)^t \right) . \end{aligned}$$

(50)

Note that the last sum of (50) equals zero which can be seen by using the binomial identity

$$\begin{aligned} (x+y)^n = \sum _{k=0}^{n} \left( {\begin{array}{c}n\\ k\end{array}}\right) x^{n-k} y^k \end{aligned}$$

with $x=1$ and $y=-1$ (or vice versa).

If $m \equiv 2 \pmod {4}$, we set $p_1=2$ and $n_1=1$. By (47),

$$\begin{aligned} M(m') = {\left\{ \begin{array}{ll} \frac{2^{m'}+1}{3} &{}\text {if } m' = \frac{m}{2p_{i_2} \cdots p_{i_\ell }},\\ \frac{2^{m'}-1}{3} &{}\text {if } m' = \frac{m}{p_{i_1} \cdots p_{i_\ell }} \text { and } i_1, \dots , i_\ell \ne 1. \end{array}\right. } \end{aligned}$$

(51)

Plugging (51) into (49), we obtain

$$\begin{aligned} N(m)=&\frac{1}{3}\Bigg ( 2^m - \sum _{i=1}^t 2^{\frac{m}{p_i}} + \sum _{\begin{array}{c} i,j=1,\\ j \ne i \end{array}}^t 2^{\frac{m}{p_i p_j}} - \cdots + (-1)^t 2^{\frac{m}{p_1p_2\cdots p_t}} \Bigg )\nonumber \\&+ \frac{1}{3} \sum _{i=0}^t (-1)^i \left( \left( {\begin{array}{c}t-1\\ i-1\end{array}}\right) - \left( {\begin{array}{c}t-1\\ i\end{array}}\right) \right) . \end{aligned}$$

(52)

We show where the last sum of (52) is coming from and which values it can take. If $t=1$, then $m=3^{n_0} \cdot 2$. Note that m is even and $\frac{m}{2}$ is odd. Hence, in this case, $N(m) = M(m) - M(\frac{m}{2}) = 2^m - 2^\frac{m}{2} -2$, and the last sum of (52) equals $-2$. Now assume $t > 1$. Consider the sum

$$\begin{aligned} \sum _{\begin{array}{c} i_1,\cdots ,i_\ell = 1 \\ \text {pairwise distinct} \end{array}}^t M\left( \frac{m}{p_{i_1}\cdots p_{i_\ell }}\right) \end{aligned}$$

(53)

from (48) for some $\ell \in \{1, \dots , t\}$. This sum consists of $\left( {\begin{array}{c}t\\ \ell \end{array}}\right)$ terms. Assume $p_{i_1}< p_{i_2}< \dots < p_{i_\ell }$. If $i_1 = 1$, which means $p_{i_1} = 2$, then $\frac{m}{2 p_{i_2}\cdots p_{i_\ell }}$ is odd. In this case, we have $\left( {\begin{array}{c}t-1\\ \ell -1\end{array}}\right)$ possibilities to choose $p_{i_2}, \dots , p_{i_\ell }$. On the contrary, if $i_1 \ne 1$, then $\frac{m}{p_{i_1}\cdots p_{i_\ell }}$ is even, and we have $\left( {\begin{array}{c}t-1\\ \ell \end{array}}\right)$ possibilities to choose $p_{i_1}, \dots , p_{i_\ell }$. Combining these results with (51), we have $\left( {\begin{array}{c}t-1\\ \ell -1\end{array}}\right)$ terms of the form $2^{m'} + 1$ and $\left( {\begin{array}{c}t-1\\ \ell \end{array}}\right)$ terms of the form $2^{m'} - 1$ in the sum from (53). Note that, by similar reasoning as in the case m odd or $4 \mid m$, this sum is zero if $t > 1$. $\square$

Consider $\Phi (m)$ as in (45). We have shown in Lemma 4.3 that if $X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$, then neither has $X^{2^k+1} + X + \beta ^{2^i}$ for all $i \in \{0,\dots ,m-1\}$. Consequently, $\Phi (m)$ decomposes into orbits of $\beta \in \mathbb {F}_{2^m}^*$ under the action of the Galois group $\hbox {Gal}(\mathbb {F}_{2^m}/ \mathbb {F}_2)$. In Proposition 5.4, we count this number of orbits.

Proposition 5.4

Let $\Phi (m)$ as in (45), and define

$$\begin{aligned} B(m) = \left\{ \{ \beta ^{2^i} : i \in \{0,\dots ,m-1\} \} : \beta \in \Phi (m)\right\} \end{aligned}$$

as the set of orbits of $\beta \in \mathbb {F}_{2^m}^*$ such that $X^{2^k+1} + X + \beta$ has no root in $\mathbb {F}_{2^m}$ under the action of the Galois group $\hbox {Gal}(\mathbb {F}_{2^m}/ \mathbb {F}_2)$. Moreover, define $b(m) = |B(m)|$. Then,

$$\begin{aligned} b(m) = \sum _{m' \mid m,\ 3 \not \mid \frac{m}{m'}} \frac{N(m')}{m'}, \end{aligned}$$

where $N(m')$ is defined as in (46) and can be calculated as in Lemma 5.3.

Proof

For any subfield $\mathbb {F}_{2^{m'}}$ of $\mathbb {F}_{2^m}$, we count the number of orbits of $\beta \in \Phi (m) \cap \mathbb {F}_{2^{m'} }^*$ under the action of $\hbox {Gal}(\mathbb {F}_{2^{m'}}/\mathbb {F}_2)$ that have full length $m'$. This number is given by $\frac{N(m')}{m'}$. It follows from Lemma 5.2 that we only need to consider the orbits in $\mathbb {F}_{2^{m'}}$ with $3 \not \mid [\mathbb {F}_{2^m}: \mathbb {F}_{2^{m'}}]$. Adding all these numbers gives b(m). $\square$

With the help of Proposition 5.4, we can eventually determine the number of CCZ-inequivalent Taniguchi APN functions on $\mathbb {F}_{2^{2m}}$ in Theorem 5.5. We give a nice lower bound on this number in Corollary 5.6.

Theorem 5.5

Let $m \ge 3$, and denote by n(m) the number of CCZ-inequivalent Taniguchi APN functions $f_{k,\alpha ,\beta }$ from Theorem 3.1 on $\mathbb {F}_{2^{2m}}$. Then,

$$\begin{aligned} n(m) = {\left\{ \begin{array}{ll} \dfrac{\varphi (m)b(m)}{2} &{}\text {if } m\text { is odd},\\ \dfrac{\varphi (m)(b(m)+1)}{2} &{}\text {if } m\text { is even}, \end{array}\right. } \end{aligned}$$

where $\varphi$ denotes Euler’s totient function and b(m) is as in Proposition 5.4.

Proof

Let $m \ge 3$. Thanks to Proposition 4.4, we only need to consider $\alpha \in \{0,1\}$ and $0< k < \frac{m}{2}$. We count the number of CCZ-inequivalent Taniguchi APN functions $f_{k,1,\beta }$ first: According to Theorem 4.5, for $0< k,\ell <\frac{m}{2}$ two functions $f_{k,1,\beta }$ and $f_{\ell ,1,\beta '}$ are CCZ-equivalent if and only if $k = \ell$ and $\beta = \beta '^{2^i}$ for some $i \in \{0,\dots ,m-1\}$. We count the number of pairs $(k,\beta )$ that lead to inequivalent APN functions: As $0< k < \frac{m}{2}$ and $\gcd (k,m)=1$, we have $\frac{\varphi (m)}{2}$ choices for k. The number of admissible $\beta \in \mathbb {F}_{2^m}^*$ equals b(m) from Proposition 5.4. If m is odd, then these are all inequivalent Taniguchi APN functions.

If m is even, according to Lemma 3.2, there also exist Taniguchi APN functions with $\alpha = 0$. In this case, it follows from Corollary 4.8 in combination with Corollary 4.2 that for every valid choice of k, there is additionally exactly one equivalence class of Taniguchi APN functions $f_{k,0,\beta }$ that is inequivalent to all functions with $\alpha \ne 0$. As before, we have $\frac{\varphi (m)}{2}$ choices for k. $\square$

Note that Corollary 5.6 shows that the number of APN functions on $\mathbb {F}_{2^{2m}}$ increases exponentially in m.

Corollary 5.6

Let $m \ge 3$, and define n(m) as the number of CCZ-inequivalent Taniguchi APN functions from Theorem 3.1 on $\mathbb {F}_{2^{2m}}$. Then,

$$\begin{aligned} n(m) \ge \frac{\varphi (m)}{2}\left\lceil \frac{2^m+1}{3m}\right\rceil , \end{aligned}$$

where $\varphi$ denotes Euler’s totient function.

Proof

Define B(m) and b(m) as in Proposition 5.4. The value of b(m) is minimal if all the orbits in B(m) have full length m. By Lemma 3.3, this implies

$$\begin{aligned} b(m) \ge {\left\{ \begin{array}{ll} \left\lceil \frac{2^m-1}{3m}\right\rceil &{}\text {if } m\text { is even},\\ \left\lceil \frac{2^m+1}{3m}\right\rceil &{}\text {if } m\text { is odd}, \end{array}\right. } \end{aligned}$$

and it is easy to see that $\left\lceil \frac{2^m-1}{3m}\right\rceil = \left\lceil \frac{2^m+1}{3m}\right\rceil$ for all $m \ge 3$. $\square$

In Table 2, we list the exact number of CCZ-inequivalent Taniguchi APN functions obtained from Theorem 5.5 for certain values of m. Recall that for $m=2$, there is only one unique Taniguchi APN function. We, moreover, compare these numbers to the lower bound that we have established in Corollary 5.6. It can be seen that the bound is very close to the actual number of Taniguchi APN functions.

Table 2 Number of CCZ-inequivalent Taniguchi APN functions on $\mathbb {F}_{2^{2m}}$ for certain values of m

6 Conclusion and Open Questions

In the present paper, we establish a new lower bound on the total number of CCZ-inequivalent APN functions on the finite field $\mathbb {F}_{2^{2m}}$. We show that the number of APN functions on $\mathbb {F}_{2^{2m}}$ grows exponentially in m. For even m, our result presents a great improvement of the lower bound previously given by the present authors [26]. For odd m, this is the first such lower bound.

Our result now shifts the focus on the following open problems concerning APN functions:

• Establish a lower bound on the total number of CCZ-inequivalent APN functions on the finite field $\mathbb {F}_{2^n}$ with n odd.

• As it is confirmed now that there are very many quadratic APN functions on $\mathbb {F}_{2^{2m}}$, the efforts of finding new constructions of APN functions should focus on the search for non-quadratic ones.

• It was shown by Anbar et al. [1] that Taniguchi APN functions have the classical Walsh spectrum. It would be interesting to find more APN functions with non-classical Walsh spectra.