Some Results on the Known Classes of Quadratic APN Functions

Abstract

In this paper, we determine the Walsh spectra of three classes of quadratic APN functions and we prove that the class of quadratic trinomial APN functions constructed by Göloğlu is affine equivalent to Gold functions.

This work was supported by the Norwegian Research Council.

1 Introduction

For given positive integers n and m, a function F from the finite field ${{\mathrm{\mathbb {F}}}}_{2^n}$ to the finite field ${{\mathrm{\mathbb {F}}}}_{2^m}$ is called a vectorial Boolean function or an (n, m)-function, and in the case when $m=1$ it is simply called a Boolean function. When $m=n$ an (n, n)-function has a unique representation as a univariate polynomial over ${\mathbb F}_{2^n}$ of the form

$$\begin{aligned} F(x)= & {} \sum _{i=0}^{2^n-1}a_ix^i,\ \ \ \ \ a_i\in {\mathbb F}_{2^n}. \end{aligned}$$

Boolean and vectorial Boolean functions have many applications in mathematics and information theory. In particular, they play an important role in cryptography.

In modern society, exchange and storage of information in an efficient, reliable and secure manner is of fundamental importance. Cryptographic primitives are used to protect information against eavesdropping, unauthorized changes and other misuse. In the case of symmetric cryptography ciphers are designed by appropriate composition of nonlinear Boolean functions. For example, the security of block ciphers depends on S-boxes which are (n, m)-functions. For most of cryptographic attacks on block ciphers there are certain properties of functions which measure the resistance of the S-box to these attacks. The differential attack introduced by Biham and Shamir is one of the most efficient cryptanalysis tools for block ciphers [2]. It is based on the study of how differences in an input can affect the resulting difference at the output. An (n, m)-function F is called differentially $\delta$-uniform if the equation $F(x+a)-F(x)=b$ has at most $\delta$ solutions for every nonzero element a of ${{\mathrm{\mathbb {F}}}}_{2^n}$ and every b in ${{\mathrm{\mathbb {F}}}}_{2^m}$. Functions with the smallest possible differential uniformity contribute an optimal resistance to the differential attack [34]. In this sense differentially $2^{n-m}$-uniform functions, called perfect nonlinear (PN), are optimal. However, PN functions exist only for n even and $m\le n/2$ [35]. An important case are differentially 2-uniform functions with $n=m$, called almost perfect nonlinear (APN), which have the smallest possible differential uniformity.

Another powerful attack on block ciphers is linear cryptanalysis by Matsui which is based on finding affine approximations to the action of a cipher [33]. The nonlinearity NL(F) of an (n, m)-function F is the minimum Hamming distance between all the component functions of F (that is, the functions $\mathrm{{tr}}_1^m(v F(x))$ where

$$\mathrm{{tr}}_1^m(x)=x+x^2+\cdots +x^{2^{m-1}}$$

denotes the absolute trace function of ${{\mathrm{\mathbb {F}}}}_{2^m}$ and v is any nonzero element of ${{\mathrm{\mathbb {F}}}}_{2^m}$) and all affine Boolean functions over ${{\mathrm{\mathbb {F}}}}_{2^n}$. The nonlinearity quantifies the level of resistance of the function to the linear attack: the higher is the nonlinearity NL(F) the better is the resistance of F [21]. The functions achieving the upper bound on nonlinearity are called bent functions. All bent functions are also PN and vice versa, that is, these functions have optimal resistance against both linear and differential attacks. As mentioned above, PN (or bent) functions do not exist when $m=n$. In this case, when also n is odd, functions with the best possible nonlinearity are called almost bent (AB). When n is even the upper bound on nonlinearity is still to be determined. All AB functions are APN, but the converse is not true in general. However, for n odd all quadratic APN functions are also AB.

The nonlinearity NL(F) of an (n, m) function F can be expressed by means of the Walsh transform. The Walsh transform of F at $(\alpha ,\beta )\in {\mathbb F}_{2^n}\times {\mathbb F}_{2^m}$ is defined by

$$\begin{aligned} W_F(\alpha ,\beta )= & {} \sum _{x\in {\mathbb F}_{2^n}}(-1)^{\mathrm{{tr}}_1^m(\beta F(x))+\mathrm{{tr}}_1^n(\alpha x)}, \end{aligned}$$

and the Walsh spectrum of F is the set

$$ \{ W_F(\alpha ,\beta ): \alpha \in \mathbb {F}_{2^n}, \beta \in \mathbb {F}_{2^{m}}^*\}.$$

Then

$$NL(F)=2^{n-1}-\frac{1}{2}\max _{\alpha \in {\mathbb F}_{2^n},\beta \in {\mathbb F}_{2^m}^*} |W_F(\alpha ,\beta )|.$$

The Walsh spectrum of AB functions consists of three values $0,\pm 2^{\frac{n+1}{2}}$. The Walsh spectrum of a bent function is $\{\pm 2^\frac{n}{2}\}$.

There are several equivalence relations of functions for which differential uniformity and nonlinearity are invariant. Due to these equivalence relations, having only one APN (respectively, AB) function, one can generate a huge class of APN (respectively, AB) functions.

Two functions F and $F^\prime$ from ${\mathbb F}_{2^n}$ to ${\mathbb F}_{2^m}$ are called

• affine equivalent (or linear equivalent) if $F^\prime =A_1\circ F\circ A_2$, where the mappings $A_{1}$ and $A_{2}$ are affine (resp. linear) permutations of ${\mathbb F}_{2^m}$ and ${\mathbb F}_{2^n}$, respectively;

• extended affine equivalent (EA-equivalent) if $F^\prime =A_1\circ F\circ A_2 +A$, where the mappings $A:{\mathbb F}_{2^n}\rightarrow {\mathbb F}_{2^m},\ A_{1}:{\mathbb F}_{2^m}\rightarrow {\mathbb F}_{2^m},\ A_{2}:{\mathbb F}_{2^n}\rightarrow {\mathbb F}_{2^n}$ are affine, and where $A_{1},A_{2}$ are permutations;

• Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) if for some affine permutation $\mathcal {L}$ of ${\mathbb F}_{2^n}\times {\mathbb F}_{2^m}$ the image of the graph of F is the graph of $F'$, that is, $\mathcal {L}(G_F)=G_{F'}$ where $G_F=\{(x,F(x)) \ | \ x\in {\mathbb F}_{2^n}\}$ and $G_{F'}=\{(x,F'(x)) \ | \ x\in {\mathbb F}_{2^n}\}$.

Table 1. Known APN power functions $x^d$ on $\mathbb {F}_{2^n}$.

Table 2. Known classes of quadratic APN polynomials CCZ-inequivalent to power functions on ${{\mathrm{\mathbb {F}}}}_{2^n}$.

Although different, these equivalence relations are connected to each other. It is obvious that linear equivalence is a particular case of affine equivalence, and that affine equivalence is a particular case of EA-equivalence. As shown in [20], EA-equivalence is a particular case of CCZ-equivalence and every permutation is CCZ-equivalent to its inverse. The algebraic degree of a function (if it is not affine) is invariant under EA-equivalence but, in general, it is not preserved by CCZ-equivalence.

There are six known infinite families of power APN functions. They are presented in Table 1. There are also eleven known infinite families of quadratic APN polynomilas CCZ-inequivalent to power functions. They are given in Table 2. Families 3, 4 and 11 in Table 2 are proven to be a part of a general binary construction of APN functions [18].

Classification of APN functions is complete for $n\le 5$ [9]: for these values of n the only APN functions, up to CCZ-equivalence, are power APN functions, and up to EA-equivalence, are power APN functions and those APN functions constructed in [16]. For $n=6$ classification is complete for quadratic APN functions: 13 quadratic APN functions are found in [10] and, as proven in [26], up to CCZ-equivalence, these are the only quadratic APN functions. The only known APN function CCZ-inequivalent to power functions and to quadratic functions was found in [9, 27] for $n=6$. For $n=7$ and $n=8$, as shown in a recent work [37], there are, respectively, more than 470 and more than a thousand CCZ-inequivalent quadratic APN functions. For n odd all power APN functions and the known APN binomials are permutations (see [13, 19]). For n even the only known APN permutation is constructed in [11] for $n=6$. Existence of APN permutations for even $n\ge 8$ is an open problem.

A class of APN functions over ${\mathbb F}_{2^n}$

$$\begin{aligned} x^3+\mathrm{{tr}}_1^n(x^9) \end{aligned}$$

was constructed by Budaghyan, Carlet and Leander in [14]. Later, they generalized this result in [15] to the APN function $F_0(x)$ of the form

$$\begin{aligned} F_0(x)= & {} x^3+a^{-1}\mathrm{{tr}}_1^n(a^3x^9) \end{aligned}$$

(1)

for any positive integer n and any nonzero element a in ${\mathbb F}_{2^n}$, and they also obtained two other classes of APN functions over ${\mathbb F}_{2^n}$

$$\begin{aligned} F_1(x)= & {} x^3+a^{-1}\mathrm{{tr}}_3^n(a^3x^9+a^6x^{18})\end{aligned}$$

(2)

$$\begin{aligned} F_2(x)= & {} x^3+a^{-1}\mathrm{{tr}}_3^n(a^6x^{18}+a^{12}x^{36}) \end{aligned}$$

(3)

for any positive integer n divisible by 3 and any nonzero element a in ${\mathbb F}_{2^n}$ and where $\mathrm{{tr}}_3^n(x)=\sum _{i=0}^{n/3-1}x^{2^{3i}}$ is the trace function from ${\mathbb F}_{2^n}$ to its subfield ${{\mathrm{\mathbb {F}}}}_{2^3}$. When n is even each of the functions $F_0$, $F_1$ and $F_2$ defines two CCZ-inequivalent functions one for $a=1$ and one for any $a\ne 1$, that is, all together they give six different functions. When n is odd each of the functions $F_0$, $F_1$ and $F_2$ defines only one function, up to CCZ-inequivalence, that is, all together they give three different functions [15]. In Table 2 the functions $F_0$, $F_1$ and $F_2$ correspond to families 5, 6 and 7, respectively. In the present paper we determine the Walsh spectra of the functions $F_0$, $F_1$ and $F_2$. The Walsh spectra of the remaining functions in Tables 1 and 2 have been determined in [6,7,8, 17, 28, 30, 36]. Note that the Walsh spectrum of the function $F_0$ with $a=1$ was previously found in [5] and we generalize this result to any $a\ne 0$. The results on the Walsh spectra show that all the known families of quadratic APN functions have Gold like Walsh spectra. Note that there exists a quadratic APN function for $n=6$ with Walsh spectrum different from Gold [10].

In 2015 a family of quadratic APN trinomials on ${{\mathrm{\mathbb {F}}}}_{2^n}$

$$\begin{aligned} G(x)= & {} x^{2^k+1}+\big (\mathrm{{tr}}_m^n(x)\big )^{2^k+1}, \end{aligned}$$

(4)

with $\gcd (k, n) =1$ and $n =2m =4t$, was constructed in [29]. It was claimed there to be CCZ-inequivalent to power functions. However, in the present paper we prove that this family is in fact affine equivalent to Gold power functions.

2 Walsh Spectra of $F_1$ and $F_2$

In this section, we determine the Walsh spectra of the APN functions $F_1$ and $F_2$. According to the definition, for any $b,c\in {\mathbb F}_{2^n}$, one gets

$$\begin{aligned} g_i(x)= \mathrm{{tr}}_1^n(bF_i(x)+cx)= & {} \mathrm{{tr}}_1^n(bx^3+ba^{-1}\mathrm{{tr}}_3^n(a^3x^9+a^6x^{18})^i+cx) \\= & {} \mathrm{{tr}}_1^n(bx^3+cx)+\mathrm{{tr}}_1^n(ba^{-1}\mathrm{{tr}}_3^n(a^3x^9+a^6x^{18})^i) \\= & {} \mathrm{{tr}}_1^n(bx^3+cx)+\mathrm{{tr}}_1^3\mathrm{{tr}}_3^n(ba^{-1}\mathrm{{tr}}_3^n(a^3x^9+a^6x^{18})^i) \\= & {} \mathrm{{tr}}_1^n(bx^3+cx)+\mathrm{{tr}}_1^3\mathrm{{tr}}_3^n(\mathrm{{tr}}_3^n(ba^{-1})(a^3x^9+a^6x^{18})^i) \\= & {} \mathrm{{tr}}_1^n(bx^3+cx+\mathrm{{tr}}_3^n(ba^{-1})(a^3x^9+a^6x^{18})^i) \end{aligned}$$

for $i\in \{1,2\}$. For simplicity, denote $\mathrm{{tr}}_3^n(ba^{-1})=\delta ^2$. By a direct calculation, one obtains that

(5)

which implies that

$$\begin{aligned} |W_{F_i}(b,c)|^2= & {} \sum _{x\in {\mathbb F}_{2^n}}\sum _{u\in {\mathbb F}_{2^n}}(-1)^{g_i(x)+g_i(x+u)} \\ {}= & {} \sum _{u\in {\mathbb F}_{2^n}}(-1)^{g_i(u)}\sum _{x\in {\mathbb F}_{2^n}}(-1)^{\mathrm{{tr}}_1^n(xL^i_{a,b,\delta }(u))}, \end{aligned}$$

where $L^i_{a,b,\delta }(u)$ is defined as

$$\begin{aligned} L^i_{a,b,\delta }(u)=(\delta ^{2/i}+\delta ^{1/i})a^3u^8+bu^2+(bu)^{2^{-1}}+((\delta ^{2/i}+\delta ^{1/i})a^3u)^{2^{-3}}. \end{aligned}$$

(6)

Note that $g_i(u)+g_i(u+v)+g_i(v)=\mathrm{{tr}}_1^n(vL^i_{a,b,\delta }(u))$ due to (5) and (6). This means that for any u satisfying $L^i_{a,b,\delta }(u)=0$ and any $v\in {\mathbb F}_{2^n}$ we have

$$\begin{aligned} g_i(u+v)=g_i(u)+g_i(v) \end{aligned}$$

which implies that

$$\begin{aligned} |W_{F_i}(b,c)|^2 =0,\; \ \ \ \ \ \mathrm{or}\; \ \ \ \ \ 2^n\cdot |\{x\in {\mathbb F}_{2^n}: L^i_{a,b,\delta }(u)=0\}|. \end{aligned}$$

(7)

In what follows, we discuss the number of solutions $u\in {\mathbb F}_{2^n}$ to $L^i_{a,b,\delta }(u)=0$ by adopting Dobbertin’s method [25], which also was used by Bracken et al. in [5] to determine the Walsh spectrum of $F_0(x)$ for the case of $a=1$.

For simplicity, define $\theta _i=(\delta ^{2/i}+\delta ^{1/i})a^3$ for $i=1,2$. Then $L^i_{a,b,\delta }(u)=0$ can be written as $\theta _iu^8+bu^2+(bu)^{2^{-1}}+(\theta _iu)^{2^{-3}}=0$ and it can be readily verified that

$$\begin{aligned} uL^i_{a,b,\delta }(u)= & {} \phi _i(u)+ \phi _i(u)^{2^{-1}}, \end{aligned}$$

where $\phi _i(u)$ is given as

$$\begin{aligned} \phi _i(u)=bu^3+\theta _iu^9+\theta _i^{\frac{1}{2}}u^{\frac{9}{2}}+\theta _i^{\frac{1}{4}}u^{\frac{9}{4}}. \end{aligned}$$

(8)

Then, if $L^i_{a,b,\delta }(u)=0$, we must have $\phi _i(u)\in {\mathbb F}_{2}$.

Proposition 1

Let $a,b\in {\mathbb F}_{2^n}$ with $ab\ne 0$ and $\delta ^2=\mathrm{{tr}}_3^n(ba^{-1})$. If $\delta ^{2/i}+\delta ^{1/i}\not =0$, then $L^i_{a,b,\delta }(u)=0$ if and only if $\phi _i(u)=0$ for $i=1,2$.

Proof

If $\phi _i(u)=0$, we have $L^i_{a,b,\delta }(u)=0$; and if $L^i_{a,b,\delta }(u)=0$, we have $\phi _i(u)\in {\mathbb F}_{2}$. Thus, to complete the proof, we need to show that $L^i_{a,b,\delta }(u)=0$ implies that $\phi _i(u)=0$ for $i=1,2$. Suppose that $\phi _i(u)=1$, one then gets $b=\theta _iu^6+\theta _i^{1/2}u^{3/2}+\theta _i^{1/4}u^{-3/4}+u^{-3}$ which together with $\theta _i=(\delta ^{2/i}+\delta ^{1/i})a^3$ leads to

$$\begin{aligned} \frac{b}{a}=(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})a^2u^6+(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})^{\frac{1}{2}}a^{\frac{1}{2}}u^{\frac{3}{2}}+(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})^{\frac{1}{4}}a^{-\frac{1}{4}}u^{-\frac{3}{4}}+a^{-1}u^{-3}. \end{aligned}$$

(9)

For convenience, define $\mathrm{{tr}}_3^n(a^2u^6)=t$ and $\mathrm{{tr}}_3^n(a^{-1}u^{-3})=r$. Notice that $\delta ^{\frac{1}{2}}=\delta ^4$ and $\delta ^{\frac{1}{4}}=\delta ^2$ since $\delta \in {\mathbb F}_{2^3}$. Then by $\mathrm{{tr}}_3^n(ba^{-1})=\delta ^2$ and (9) one has that

$$\begin{aligned} \delta ^2=\mathrm{{tr}}_3^n(\frac{b}{a})=(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})t+(\delta ^{\frac{1}{i}}+\delta ^{\frac{1}{2i}})t^{\frac{1}{4}}+(\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})r^{\frac{1}{4}}+r. \end{aligned}$$

(10)

Rewrite (10) with respect to the variable r we have

$$\begin{aligned} (\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})r^2+r+(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})t+(\delta ^{\frac{1}{i}}+\delta ^{\frac{1}{2i}})t^2+\delta ^2=0. \end{aligned}$$

Note that $\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}}\ne 0$ due to $\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}}\not =0$. Then the above equation has solution $r\in {\mathbb F}_{2^3}$ if and only if

$$\begin{aligned} \mathrm{{tr}}_1^3((\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})((\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})t+(\delta ^{\frac{1}{i}}+\delta ^{\frac{1}{2i}})t^2+\delta ^2))=0. \end{aligned}$$

(11)

It can be readily verified that for $i=1,2$ we have

$$(\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})^2(\delta ^{\frac{2}{i}}+\delta ^{\frac{1}{i}})^2=(\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})(\delta ^{\frac{1}{i}}+\delta ^{\frac{1}{2i}}),$$

which implies that (11) holds if and only if

$$\mathrm{{tr}}_1^3((\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})\delta ^2)=0.$$

Observe that $(\delta ^{\frac{1}{2i}}+\delta ^{\frac{1}{4i}})\delta ^2=(\delta ^4+\delta ^2)\delta ^2=\delta ^6+\delta ^4$ if $i=1$, and it equals $(\delta ^2+\delta )\delta ^2=\delta ^4+\delta ^3$ if $i=2$. Thus, no matter which case we arrive at $\mathrm{{tr}}_1^3(\delta ^3+\delta )=0$. By $\mathrm{{tr}}_1^3(\delta ^3)=\mathrm{{tr}}_1^3(\delta )$ and $\delta ^7=1$ we have $\delta ^3+\delta ^6+\delta ^5=\delta +\delta ^2+\delta ^4$ which leads to $\delta =0,1$, a contradiction with $\delta ^{2/i}+\delta ^{1/i}\not =0$. Therefore, if $\delta ^{2/i}+\delta ^{1/i}\not =0$, then there is no solution $r\in {\mathbb F}_{2^3}$ to (10) and $L^i_{a,b,\delta }(u)=0$ if and only if $\phi _i(u)=0$. This completes the proof.

Proposition 2

Let $a,b\in {\mathbb F}_{2^n}$ with $ab\ne 0$ and $\delta ^2=\mathrm{{tr}}_3^n(ba^{-1})$. Then $L^i_{a,b,\delta }(u)=0$ defined by (6) has at most four roots in ${\mathbb F}_{2^n}$ for any $i\in \{1,2\}$.

Proof

If $\theta _i=0$, i.e., $\delta ^{2/i}+\delta ^{1/i}=0$, then (6) is reduced to $bu^2+(bu)^{2^{-1}}=0$ which has at most four roots in ${\mathbb F}_{2^n}$ for any nonzero b. Next we consider the case $\theta _i\ne 0$. By Proposition 1, for this case we have $L^i_{a,b,\delta }(u)=0$ if and only if $\phi _i(u)=0$. Thus, to complete the proof, it suffices to show that $\phi _i(u)=0$ has at most four roots in ${\mathbb F}_{2^n}$ for any $i\in \{1,2\}$. If $\phi _i(u)=0$ has no nonzero solution for some $\theta _i$ and b, then the desired result follows. Now let v be any fixed nonzero solution of $\phi _i(u)=0$, then for any u satisfying $\phi _i(u)=0$ we have

$$\begin{aligned} u(u+v)\phi _i(v)+v(u+v)\phi _i(u)+uv\phi _i(u+v)=0. \end{aligned}$$

A direct calculation based on (8) gives

$$\begin{aligned} \theta _i^{\frac{1}{2}}(u^2v^{\frac{9}{2}}+v^2u^{\frac{9}{2}}+u^5v^{\frac{3}{2}}+v^5u^{\frac{3}{2}})=\theta _i^{\frac{1}{4}}(u^2v^{\frac{9}{4}}+v^2u^{\frac{9}{4}}+u^3v^{\frac{5}{4}}+v^3u^{\frac{5}{4}}), \end{aligned}$$

which can be written as

$$\begin{aligned} \theta _i^{\frac{1}{4}}(u^4v+uv^4)(u^{\frac{1}{2}}v+uv^{\frac{1}{2}})=(u^2v+uv^2)(u^{\frac{1}{4}}v+uv^{\frac{1}{4}}) \end{aligned}$$

(12)

since $\theta _i \ne 0$. Then, let $u=vz$, one obtains that

$$\begin{aligned} \theta _i^{\frac{1}{4}}v^{\frac{9}{4}}(z^4+z)(z^{\frac{1}{2}}+z)=(z^2+z)(z^{\frac{1}{4}}+z). \end{aligned}$$

(13)

Note that v is a fixed nonzero element which means that z is uniquely determined by u. Thus, one can conclude that the number of solutions $z\in {\mathbb F}_{2^n}$ to (13) is no less than that of $u\in {\mathbb F}_{2^n}$ to $\phi _i(u)=0$. Let $w=z^2+z$ and rewrite (13) as

$$\begin{aligned} w\varOmega _i(w):=\theta _i^{\frac{1}{4}}v^{\frac{9}{4}}(w^2+w)w^{\frac{1}{2}}+w(w^{\frac{1}{2}}+w^{\frac{1}{4}})=0. \end{aligned}$$

(14)

Observe that (12) holds for any u satisfying $\phi _i(u)=0$ and the solution set of $\phi _i(u)=0$ is an ${\mathbb F}_{2}$-linear space due to Proposition 1. Then, one can conclude that the solution sets of both (13) and (14) are ${\mathbb F}_{2}$-linear spaces. Assume that $w_1, w_2$ and $w_1+w_2$ are solutions of (14), then we have

$$\begin{aligned} 0=\varOmega _i(w_1)+\varOmega _i(w_2)+\varOmega _i(w_1+w_2)=\theta _i^{\frac{1}{4}}v^{\frac{9}{4}}(w_1^{\frac{1}{2}}w_2+w_2^{\frac{1}{2}}w_1) \end{aligned}$$

since (14) holds if and only if $\varOmega _i(w)=0$, which leads to $w_1w_2^2+w_2^2w_1=w_1w_2(w_1+w_2)=0$, i.e., $w_1=0$, $w_2=0$ or $w_1=w_2$. This means that (14) has at most two distinct solutions in ${\mathbb F}_{2^n}$ and then (13) has at most four solutions in z since $w=z^2+z$. This completes the proof.

Theorem 1

The Walsh spectra of both functions $F_1$ and $F_2$ defined by (2) and (3) respectively are $\{0,\pm 2^{(n+1)/2}\}$ if n is odd and $\{0,\pm 2^{n/2},\pm 2^{(n+2)/2}\}$ otherwise.

Proof

The Walsh transform of $F_i$, $i=1,2$, takes values from $\{0,\pm 2^{(n+1)/2}\}$ if n is odd and takes values from $\{0,\pm 2^{n/2},\pm 2^{(n+2)/2}\}$ if n is even. This follows from (7) and Proposition 2.

The Walsh transform takes all three values for n odd and all 5 values for n even since quadratic functions are plateaud and there exists no bent function from ${{\mathrm{\mathbb {F}}}}_{2^n}$ to itself, while in case of n even quadratic APN functions have some bent components.

3 Walsh Spectrum of $F_0$

Bracken et al. in [5] had determined the Walsh spectrum of the APN function $F_0$ for the case of $a=1$. In this section, we determine its Walsh spectrum for any nonzero element $a\in {\mathbb F}_{2^n}$ by using the same techniques. By the definition, for any $b,c\in {\mathbb F}_{2^n}$, one gets

$$\begin{aligned} \mathrm{{tr}}_1^n(bF_0(x)+cx)= & {} \mathrm{{tr}}_1^n(bx^3+ba^{-1}\mathrm{{tr}}_1^n(a^3x^9)+cx) \\= & {} \mathrm{{tr}}_1^n(bx^3+cx+\mathrm{{tr}}_1^n(ba^{-1})a^3x^9). \end{aligned}$$

For simplicity, let $\mathrm{{tr}}_1^n(ba^{-1})=\delta$ and $g_0(x)=\mathrm{{tr}}_1^n(bF_0(x)+cx)$. Then, by a direct calculation, one obtains that

(15)

which implies that

$$\begin{aligned} |W_{F_0}(b,c)|^2= & {} \sum _{x\in {\mathbb F}_{2^n}}\sum _{u\in {\mathbb F}_{2^n}}(-1)^{g_0(x)+g_0(x+u)} \\ {}= & {} \sum _{u\in {\mathbb F}_{2^n}}(-1)^{g_0(u)}\sum _{x\in {\mathbb F}_{2^n}}(-1)^{\mathrm{{tr}}_0^n(xL^0_{a,b,\delta }(u))}, \end{aligned}$$

where $L^0_{a,b,\delta }(u)$ is defined as

$$\begin{aligned} L^0_{a,b,\delta }(u)=(bu)^{2^{-1}}+bu^2+(\delta a^3u)^{2^{-3}}+\delta a^3u^8. \end{aligned}$$

(16)

Note that $g_0(u)+g_0(u+v)+g_0(v)=\mathrm{{tr}}_1^n(vL^0_{a,b,\delta }(u))$ due to (15) and (16). This means that for any u satisfying $L^0_{a,b,\delta }(u)=0$ and any $v\in {\mathbb F}_{2^n}$ we have

$$\begin{aligned} g_0(u+v)=g_0(u)+g_0(v) \end{aligned}$$

which implies that

$$\begin{aligned} |W_{F_0}(b,c)|^2 =0,\;\mathrm{or}\; 2^n|\{x\in {\mathbb F}_{2^n}: L^0_{a,b,\delta }(u)=0\}|. \end{aligned}$$

(17)

Next we aim to determine the number of solutions to $L^0_{a,b,\delta }(u)=0$ in order to determine the possible values of the Walsh spectrum of $F_0(x)$. First, if $\delta =\mathrm{{tr}}_1^n(ba^{-1})=0$, then $L^0_{a,b,\delta }(u)=0$ is reduced to $L^0_{a,b,0}(u)=(bu)^{2^{-1}}+bu^2=0$ which has at most 4 roots in ${\mathbb F}_{2^n}$. Now we assume that $\delta =\mathrm{{tr}}_1^n(ba^{-1})=1$, then $L^0_{a,b,\delta }(u)=0$ is reduced to $L^0_{a,b,1}(u)=(bu)^{2^{-1}}+bu^2+(a^3u)^{2^{-3}}+ a^3u^8=0$, and it is straightforward to verify that

$$\begin{aligned} uL^0_{a,b,1}(u)=\phi _0(u)+\phi _0(u)^{2^{-1}}, \end{aligned}$$

(18)

where $\phi _0(u)$ is defined by

$$\phi _0(u)=bu^3+a^3u^9+a^{\frac{3}{2}}u^{\frac{9}{2}}+a^{\frac{3}{4}}u^{\frac{9}{4}}.$$

Proposition 3

Let $a,b\in {\mathbb F}_{2^n}$ with $\delta =\mathrm{{tr}}_1^n(ba^{-1})=1$. Then $L^0_{a,b,1}(u)=0$ if and only if $\phi _0(u)=0$.

Proof

According to (18), we have $L^0_{a,b,1}(u)=0$ if $\phi _0(u)=0$; and $\phi _0(u)\in {\mathbb F}_{2}$ if $L^0_{a,b,1}(u)=0$. Thus, to complete the proof, we need to show that $L^0_{a,b,1}(u)=0$ implies that $\phi _0(u)=0$. Suppose that $\phi _0(u)=1$, one then gets $b=a^3u^6+a^{3/2}u^{3/2}+a^{3/4}u^{-3/4}+u^{-3}$ which leads to

$$\begin{aligned} ba^{-1}=a^2u^6+a^{\frac{1}{2}}u^{\frac{3}{2}}+a^{-\frac{1}{4}}u^{-\frac{3}{4}}+a^{-1}u^{-3}. \end{aligned}$$

This contradicts with the condition that $\mathrm{{tr}}_1^n(ba^{-1})=1$. This completes the proof.

Proposition 4

Let $a,b\in {\mathbb F}_{2^n}$ with $ab\ne 0$ and $\delta =\mathrm{{tr}}_1^n(ba^{-1})$. Then $L^0_{a,b,\delta }(u)=0$ defined by (16) has at most four roots in ${\mathbb F}_{2^n}$.

Proof

This can be proved completely the same as Proposition 2.

Theorem 2

The Walsh spectrum of the function $F_0$ defined by (1) is $\{0,\pm 2^{(n+1)/2}\}$ if n is odd and $\{0,\pm 2^{n/2},\pm 2^{(n+2)/2}\}$ otherwise.

Proof

The Walsh transform of $F_0$ takes values from $\{0,\pm 2^{(n+1)/2}\}$ if n is odd and takes values from $\{0,\pm 2^{n/2},\pm 2^{(n+2)/2}\}$ if n is even. This follows from (17) and Proposition 4. The Walsh transform takes all three values for n odd and all 5 values for n even by the same reasons as in Theorem 1.

4 Equivalence of Göloğlu’s APN Trinomial to Gold Functions

In this section we prove that the function G defined by (4) is affine equivalent to the Gold function $x^{2^{m-k}+1}$. Note first that

$$ G(x) = x^{2^m(2^k+1)}+x^{2^k+2^m}+x^{2^{m+k}+1}, $$

and it is affine equivalent to the function

$$G'(x) =\big (G(x)\big )^{2^m}= x^{2^k+1}+x^{2^k+2^m}+x^{2^{m+k}+1}.$$

Linear functions

$$\begin{aligned} L_1(x)= & {} \gamma ^{2^k}x^{2^{m+k}}+\gamma x^{2^{k}},\\ L_2(x)= & {} \gamma x^{2^{m}}+\gamma ^{2^{k}} x, \end{aligned}$$

where $\gamma$ is a primitive element of ${{\mathrm{\mathbb {F}}}}_{2^2}$, are permutations. Indeed, it is easy to see that the equations $L_1(x)=0$ and $L_2(x)=0$ have only 0 as a solution. Note that $L_1(x)=0$ implies $L_1(x)^{2^m}=0$ which give

$$\begin{aligned} \gamma ^{2^k} x^{2^{m+k}}= & {} \gamma x^{2^k},\\ \gamma ^{2^{m+k}} x^{2^k}= & {} \gamma ^{2^m} x^{2^{m+k}}. \end{aligned}$$

Hence, assuming $x\ne 0$ and multiplying both sides of the equalities above gives $\gamma ^{2^k+2^{m+k}} = \gamma ^{2^m+1}$ or $\gamma = \gamma ^2$ (see explanation below) contradicting that $\gamma$ is primitive in ${{\mathrm{\mathbb {F}}}}_{2^2}$. The proof for $L_2$ being a permutation is similar.

Further we have

$$\begin{aligned} \big (L_1(x)\big )^{2^{m-k}+1}= & {} \gamma ^{2^m+2^k}x^{2^{m+k}+1}{+} \gamma ^{2^{m-k}+1}x^{2^{m}+2^k} {+}\gamma ^{2^{m-k}+2^k}x^{2^{m+k}+2^m} +\gamma ^{2^m+1}x^{2^{k}+1}\\= & {} x^{2^{m+k}+1}+ x^{2^{m}+2^k} +\gamma x^{2^{m+k}+2^m} +\gamma ^{2}x^{2^{k}+1} \end{aligned}$$

and

$$\begin{aligned} L_2\circ G'(x)= & {} \gamma \big (x^{2^k+1}+x^{2^k+2^m}+x^{2^{m+k}+1}\big )^{2^{m}}{+}\gamma ^{2^{k}} \big (x^{2^k+1}+x^{2^k+2^m}+x^{2^{m+k}+1}\big )\\= & {} \big (\gamma +\gamma ^{2^k}\big ) \big (x^{2^{m+k}+1}+x^{2^{m}+2^k}\big )+\gamma x^{2^{m+k}+2^m}+\gamma ^{2^{k}}x^{2^k+1}\\= & {} x^{2^{m+k}+1}+x^{2^{m}+2^k}+\gamma x^{2^{m+k}+2^m}+\gamma ^{2}x^{2^k+1} \end{aligned}$$

since $\gcd (k, n) =1$, $n =2m =4t$, and then

$$\begin{aligned} \gamma +\gamma ^{2^k}= & {} \gamma +\gamma ^{2}=1,\\ \gamma ^{2^{m}+2^k}= & {} \gamma ^{2^{m-k}+1}=\gamma ^3=1,\\ \gamma ^{2^{m-k}+2^k}= & {} \gamma ^{2^k+2^{m+k}}=\gamma ^4=\gamma ,\\ \gamma ^{2^{m}+1}&=\gamma ^2.&\end{aligned}$$

Hence $\big (L_1(x)\big )^{2^{m-k}+1}=L_2\circ G'(x)=L_2'\circ G(x)$ where $L_2'(x)=L_2(x^{2^m})$ is, obviously, a linear permutation. Therefore $x^{2^{m-k}+1}$ and G are affine equivalent.

Table 3. CCZ-inequivalent APN functions over $\mathbb {F}_{2^n}$ from the known APN classes ($6\le n\le 11$ and a primitive in $\mathbb {F}_{2^n}$).

Proposition 5

Let k, n, m, t be positive integers such that $\gcd (k, n) =1$, $n =2m =4t$. Then the function G defined by (4) and the function $x^{2^{m-k}+1}$ over ${{\mathrm{\mathbb {F}}}}_{2^n}$ are affine equivalent.

Remark 1

For $k=1$ the APN function G and its equivalence to Gold functions were known from [14].

We note that it is possible to check CCZ-equivalence of functions with a computer for n up to 12. However, since most of the known families of APN functions are defined for many different parameters and coefficients it becomes extremely difficult to check CCZ-equivalence of a given function to all of them. For this reason we tested all possible parameters and coefficients to produce Table 3 of all CCZ-inequivalent functions arising from the known infinite families of APN functions for $n\le 11$.