# On the Functions Which are CCZ-equivalent but not EA-equivalent to Quadratic
Functions over $\mathbb{F}_{p^{n}}$

Jaeseong Jeong  Department of Innovation Center for Industrial Mathematics,
NIMS, Seongnam, Republic of Korea Namhun Koo  Institute of Mathematical
Sciences, Ewha Womans University, Seoul, Republic of Korea  Soonhak Kwon
Applied Algebra and Optimization Research Center, Sungkyunkwan University,
Suwon, Republic of Korea

###### Abstract

For a given function $F$ from $\mathbb{F}_{p^{n}}$ to itself, determining
whether there exists a function which is CCZ-equivalent but EA-inequivalent to
$F$ is a very important and interesting problem. For example, Kölsch [33]
showed that there is no function which is CCZ-equivalent but EA-inequivalent
to the inverse function. On the other hand, for the cases of Gold function
$F(x)=x^{2^{i}+1}$ and $F(x)=x^{3}+{\rm Tr}(x^{9})$ over $\mathbb{F}_{2^{n}}$,
Budaghyan, Carlet and Pott (respectively, Budaghyan, Carlet and Leander) [13,
11] found functions which are CCZ-equivalent but EA-inequivalent to $F$. In
this paper, when a given function $F$ has a component function which has a
linear structure, we present functions which are CCZ-equivalent to $F$, and if
suitable conditions are satisfied, the constructed functions are shown to be
EA-inequivalent to $F$. As a consequence, for every quadratic function $F$ on
$\mathbb{F}_{2^{n}}$ ($n\geq 4$) with nonlinearity $>0$ and differential
uniformity $\leq 2^{n-3}$, we explicitly construct functions which are CCZ-
equivalent but EA-inequivalent to $F$. Also for every non-planar quadratic
function on $\mathbb{F}_{p^{n}}$ $(p>2,n\geq 4)$ with $|{\mathcal{W}}_{F}|\leq
p^{n-1}$ and differential uniformity $\leq p^{n-3}$, we explicitly construct
functions which are CCZ-equivalent but EA-inequivalent to $F$. As an
application, for a proper divisor $m$ of $n$, we present many examples of
$(n,m)$-functions $F$ on $\mathbb{F}_{p^{n}}$ such that the CCZ-equivalence
class of $F$ is strictly larger that the EA-equivalence class of $F$.

##  1 Introduction

Vectorial Boolean functions are widely applied in cryptography and coding
theory. Many researchers have been interested in constructing vectorial
Boolean functions with good cryptographic properties. For example, related to
S-Box in AES, _The big APN problem_ , finding an APN permutation on even
dimension, is one of the most prominent problems that many researchers are
interested in. Moreover, functions with low differential uniformity, low
boomerang uniformity, and high nonlinearity have also garnered significant
interest among researchers. Please see [17, 21, 27, 31, 39, 38] for surveys
and general theories on these subjects.

When new cryptographic functions are proposed, researchers consider whether
they are cryptographically equivalent to other known functions or not. One of
such equivalence relations is proposed by Carlet, Charpin and Zinoviev [22],
and it is referred to as CCZ-equivalence named after the proposers. Several
cryptographic properties such as differential spectrum and extended Walsh
spectrum are invariant under CCZ-equivalence. To show that the given two
functions are not CCZ-equivalent, one may compare their differential spectrum
or extended Walsh spectrum. However, proving CCZ-equivalence of two functions
with the same differential spectrum and extended Walsh spectrum is not easy in
general. The EA-equivalence (extended affine equivalence) is another
cryptographic equivalence relation, and it is well known that if two functions
are EA-equivalent then they are CCZ-equivalent. It is also known that EA-
equivalence preserves the algebraic degree, while two CCZ-equivalent functions
may have different algebraic degrees. Two very important topics related with
CCZ and EA equivalences are

  1. 1.

determining whether the two equivalences are the same notion for some class of
functions.

  2. 2.

finding CCZ-equivalent but EA-inequivalent functions if CCZ-equivalence is
strictly more general than EA-equivalence for some class of functions.

For the first topic, it is known that CCZ-equivalence and EA-equivalence are
the same notion

  1. -

for all planar functions over $\mathbb{F}_{p^{n}}$ [14, 35].

  2. -

for all Boolean functions over $\mathbb{F}_{2^{n}}$ [9].

  3. -

for all vectorial bent Boolean functions over $\mathbb{F}_{2^{n}}$ [8].

  4. -

for two quadratic APN functions over $\mathbb{F}_{2^{n}}$ [45].

  5. -

for two non-invertible power functions over $\mathbb{F}_{p^{n}}$ [28].

For a permutation $F$, its compositional inverse $F^{-1}$ is CCZ-equivalent to
$F$. Therefore CCZ-equivalence class of $F$ contains EA-equivalence classes of
both $F$ and $F^{-1}$. For power functions over $\mathbb{F}_{p^{n}}$,
Dempwolff [28] showed that two power functions $x^{s}$ and $x^{t}$ are CCZ-
equivalent to each other if and only if both $s$ and $t$ (or $s$ and
$t^{-1}\pmod{p^{n}-1}$) are in the same cyclotomic coset $\pmod{p^{n}-1}$.
Recently, Kölsch [33] showed that every function over $\mathbb{F}_{2^{n}}$
($n\geq 5$) that is CCZ-equivalent to the inverse function $x^{2^{n}-2}$ is
already EA-equivalent to it.

Our main interest in this paper is the second topic. That is, finding
functions which are CCZ-equivalent but EA-inequivalent to a given function, if
that is possible. Since both of CCZ and EA equivalences are not easy to show,
there are few research results on this topic. Canteaut et al. [19] presented a
new algorithm that efficiently solves the EA-recovery problem for quadratic
functions. Kaleyski[32] studied invariants of EA-equivalence and their
efficient computations. In [13], Budaghyan, Carlet and Pott presented
functions with algebraic degrees $\geq 3$ which are CCZ-equivalent to Gold
functions over binary fields. Also, Budaghyan, Carlet and Leander [11]
presented APN functions with degrees $\geq 3$ which are CCZ-equivalent to
$F(x)=x^{3}+{\rm Tr}(x^{9})$ over $\mathbb{F}_{2^{n}}$. To the authors’
knowledge, these two functions ($x^{2^{i}+1}$ and $x^{3}+{\rm Tr}(x^{9})$) are
the only known examples of quadratic functions which have CCZ-equivalent but
EA-inequivalent functions (which are not compositional inverses) with
algebraic degrees $\geq 3$. Recently, the relations between CCZ and EA
equivalences are studied by Canteaut and Perrin [20] by introducing the
notions of $t$-twisting and thickness spectrum, and also by Budaghyan,
Calderini and Villa [6] by further analyzing the linear structure of given
functions.

In this paper, by extending previous works [13, 11, 20, 6], we show that every
quadratic $(n,n)$\- function over arbitrary finite field $\mathbb{F}_{p^{n}}$
have CCZ-equivalent functions whose algebraic degrees are greater than $2$, if
both the linearity and the differential uniformity of the target quadratic
function are not so bad. Our general approach is to consider functions over
$\mathbb{F}_{p^{n}}$ that have a component function which has a linear
structure. For those functions, we construct a class of CCZ-equivalent
functions, where the algebraic degrees are either $3$ or $4$.

In particular, for every quadratic $(n,n)$-function $F$ on
$\mathbb{F}_{2^{n}}$ ($n\geq 4$) with nonlinearity $>0$ and differential
uniformity $\leq 2^{n-3}$, we explicitly construct functions which are CCZ-
equivalent but EA-inequivalent to $F$. Also, for every non-planar quadratic
$(n,n)$-function $F$ on $\mathbb{F}_{p^{n}}$ ($p$ is odd and $n\geq 4$) with
linearity $\leq p^{n-1}$ and differential uniformity $\leq p^{n-3}$, we
construct functions which are CCZ-equivalent but EA-inequivalent to $F$. As a
straightforward generalization of our methods, we show that, for every
quadratic $(n,m)$-function $F$ on $\mathbb{F}_{p^{n}}$ with $m|n$ and $4\leq
m<n$ satisfying $|{\mathcal{W}}_{F}|\leq p^{n-1}$ and $p^{n-m}<\Delta_{F}\leq
p^{n-3}$ where $p$ is an arbitrary prime, we show that the CCZ-equivalence
class of $F$ is strictly larger than the EA-equivalence class of $F$.

The rest of this paper is organized as follows. In Section 2, we introduce
some preliminaries which are necessary in subsequent sections. In Section 3,
we introduce several properties of linear structure, linear translator and
linear kernel. In Section 4, we mention the properties of Walsh transforms of
strongly plateaued functions over $\mathbb{F}_{p^{n}}$. In Section 5, we
construct CCZ-equivalent functions to the functions with a component function
having a linear structure. In Section 6, considering quadratic functions with
good linearity and differential uniformity, we show that the algebraic degrees
of the resulting functions are greater than two, and hence we have functions
that are CCZ-equivalent but EA-inequivalent to quadratic functions. In Section
7, we give concrete examples. In Section 8, we discuss applications of our
results to $(n,m)$-functions. In Section 9, we give concluding remarks.

##  2 Preliminaries

Let ${\mathbb{F}}_{p^{n}}$ the finite field of $p^{n}$ elements where
$n\in{\mathbb{N}}$ and $p$ is a prime number. Let
${\mathbb{F}}_{p^{n}}^{\times}$ be the multiplicative group consisting of all
invertible elements in ${\mathbb{F}}_{p^{n}}$. To measure the resistance of
the block cipher (especially a $S$-box inside of the block cipher) against the
differential cryptanalysis, for every $a\in{\mathbb{F}}_{p^{n}}^{\times}$ and
$b\in{\mathbb{F}}_{p^{n}}$, we define the difference distribution table
$\Delta_{F}(a,b)$ and the differential uniformity $\Delta_{F}$ for a vectorial
$(n,n)$-function $F:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p^{n}}$ as follows

$\displaystyle\Delta_{F}(a,b)=\\#\\{x\in{\mathbb{F}}_{p^{n}}:F(x+a)-F(x)=b\\},$
$\displaystyle\Delta_{F}=\max\\{\Delta_{F}(a,b):a\in{\mathbb{F}}_{p^{n}}^{\times},b\in{\mathbb{F}}_{p^{n}}\\}.$

We also define the differential of $F$ to the direction of
$a\in{\mathbb{F}}_{p^{n}}^{\times}$ by

$D_{a}F(x)=F(x+a)-F(x)\mbox{ for all }x\in{\mathbb{F}}_{p^{n}}$

so that $\Delta_{F}(a,b)=\\#\\{x\in{\mathbb{F}}_{p^{n}}:D_{a}F(x)=b\\}$. Then
the lower the value of $\Delta_{F}$ is, the better $F$ resists a differential
attack. We say that $F$ is planar or perfect nonlinear (PN) if $\Delta_{F}=1$,
and almost perfect nonlinear (APN) if $\Delta_{F}=2$.

On the other hand, there is one important equivalence notion of vectorial
Boolean functions called Carlet-Charpin-Zinoviev (CCZ) equivalence. This
notion was introduced in [22], and the term CCZ-equivalence was first used in
[13]. This equivalence is broader than other known equivalences such as affine
equivalence and extended affine equivalence (EA-equivalence).

###### Definition 2.1

Two functions $F,F^{\prime}:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p^{n}}$ are
said to be

  1. –

affine equivalent if $F^{\prime}=A_{1}\circ F\circ A_{2}$, where $A_{1}$ and
$A_{2}$ are affine permutations on ${\mathbb{F}}_{p^{n}}$.

  2. –

extended affine equivalent (EA-equivalent) if $F^{\prime}=A_{1}\circ F\circ
A_{2}+A_{3}$, where $A_{1}$ and $A_{2}$ are affine permutations on
${\mathbb{F}}_{p^{n}}$ and $A_{3}:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p^{n}}$
is an affine function.

  3. –

CCZ-equivalent if there exists an affine permutation $\mathscr{L}$ on
$\mathbb{F}_{p^{n}}\times{\mathbb{F}}_{p^{n}}$ such that
$\mathscr{L}({\mathcal{G}}_{F})={\mathcal{G}}_{F^{\prime}}$ where
${\mathcal{G}}_{F}$ is the graph of the function $F$, that is
${\mathcal{G}}_{F}=\\{(x,F(x)):x\in\mathbb{F}_{p^{n}}\\}\subset\mathbb{F}_{p^{n}}\times{\mathbb{F}}_{p^{n}}$.

###### Remark 2.2

We briefly write $F\overset{\textrm{\tiny affine}}{\sim}F^{\prime}$ if $F$ and
$F^{\prime}$ are affine equivalent. In a similar way, we write
$F\overset{\textrm{\tiny EA}}{\sim}F^{\prime}$ (resp. $F\overset{\textrm{\tiny
CCZ}}{\sim}F^{\prime}$) if $F$ and $F^{\prime}$ are EA-equivalent (resp. CCZ-
equivalent). Then, we have the following.

$F\overset{\textrm{\tiny affine}}{\sim}F^{\prime}\Rightarrow
F\overset{\textrm{\tiny EA}}{\sim}F^{\prime}\Rightarrow
F\overset{\textrm{\tiny CCZ}}{\sim}F^{\prime}$

###### Remark 2.3

Since the above mentioned three relations are equivalence relations, we may
naturally think of the equivalence classes for each equivalence relations.
Namely, we denote $\mathscr{C}_{\textrm{affine}}(F)$ the set consisting of all
$F^{\prime}$ such that $F^{\prime}\overset{\textrm{\tiny affine}}{\sim}F$. In
a similar manner, we denote $\mathscr{C}_{\textrm{EA}}(F)$ (resp.
$\mathscr{C}_{\textrm{CCZ}}(F)$) the set consisting of all $F^{\prime}$ such
that $F^{\prime}\overset{\textrm{\tiny EA}}{\sim}F$ (resp.
$F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F$).

It is well-known that the differential uniformity is invariant under CCZ-
equivalence, and consequently under EA-equivalence and affine equivalence.
Another important notion invariant under CCZ-equivalence is the linearity,
which is the maximum absolute value of all Walsh coefficients of a given
function. To explain Walsh coefficient and Walsh transform, we need a notion
of trace function (a very special form of linear function). Let
$n\in{\mathbb{N}}$ and $m$ be a positive divisor of $n$ such that $n=ms$. We
denote ${\rm Tr}^{n}_{m}(x)$ the trace function from ${\mathbb{F}}_{p^{n}}$ to
${\mathbb{F}}_{p^{m}}$, that is

${\rm
Tr}^{n}_{m}(x)=\sum_{j=0}^{s-1}x^{p^{jm}}=x+x^{p^{m}}+x^{p^{2m}}+\cdots+x^{p^{(s-1)m}}.$

When $m=1$, we write ${\rm Tr}(x)$ instead of ${\rm Tr}^{n}_{1}(x)$ if there
is no confusion of related fields. For $d|m$ and $m|n$, it is trivial to check
${\rm Tr}_{d}^{n}(x)={\rm Tr}_{d}^{m}{\rm Tr}_{m}^{n}(x)$ for all
$x\in\mathbb{F}_{p^{n}}$.

Let $\xi=e^{\frac{2\pi i}{p}}\in\mathbb{C}$ be a complex primitive $p^{th}$
root of unity. For $(n,1)$-function
$f:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p}$, its Walsh-Hadamard transform
${\mathcal{W}}_{f}$ is the Fourier transform of the function $\xi^{f(x)}$,
that is,

${\mathcal{W}}_{f}(a)=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{f(x)-{\rm
Tr}(ax)}\mbox{ for every }a\in{\mathbb{F}}_{p^{n}}.$

We define $|{\mathcal{W}}_{f}|$ be the maximum absolute value of all
${\mathcal{W}}_{f}(a)$ for $a\in\mathbb{F}_{p^{n}}$. That is,

$\displaystyle|{\mathcal{W}}_{f}|=\max_{a\in\mathbb{F}_{p^{n}}}|{\mathcal{W}}_{f}(a)|,$
(2.1)

where
$|{\mathcal{W}}_{f}(a)|^{2}={\mathcal{W}}_{f}(a)\overline{{\mathcal{W}}_{f}}(a)$
and $\overline{{\mathcal{W}}_{f}}(a)$ is the complex conjugate of
${\mathcal{W}}_{f}(a)$. Due to Parseval’s identity, one always have
$|{\mathcal{W}}_{f}|^{2}\geq p^{n}$, and a $(n,1)$-function $f$ achieving the
lower bound $|{\mathcal{W}}_{f}|=p^{\frac{n}{2}}$ is called a (generalized or
$p$-ary) bent function. Please refer the book of Mesnager [38] for more about
bent functions.

For $(n,n)$-function $F:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p^{n}}$, we
define its Walsh transform
${\mathcal{W}}_{F}:{\mathbb{F}}_{p^{n}}\times{\mathbb{F}}_{p^{n}}\to{\mathbb{C}}$
by

${\mathcal{W}}_{F}(a,b)={\mathcal{W}}_{{\rm
Tr}(bF)}(a)=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm Tr}(bF(x)-ax)}\mbox{ for
every }a,b\in{\mathbb{F}}_{p^{n}},$

where value ${\mathcal{W}}_{F}(a,b)$ is called the Walsh coefficient of $F$,
and ${\rm Tr}(bF)$ is called a component function of $F$. In a similar way, we
define

$\displaystyle|{\mathcal{W}}_{F}|\overset{\textrm{def}}{=}\max_{a\in\mathbb{F}_{p^{n}},b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{F}(a,b)|=\max_{a\in\mathbb{F}_{p^{n}},b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{{\rm
Tr}(bF)}(a)|=\max_{b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{{\rm
Tr}(bF)}|.$ (2.2)

The value $|{\mathcal{W}}_{F}|$ is called the linearity of $F$ and is written
as $\textup{{L}}(F)=|{\mathcal{W}}_{F}|$. For a binary case (i.e., $p=2$), we
also define $\textup{{NL}}(F)$ (the nonlinearity of $F$) as
$\textup{{NL}}(F)=2^{n-1}-\frac{1}{2}|{\mathcal{W}}_{F}|=2^{n-1}-\frac{1}{2}\textup{{L}}(F)$.
For arbitrary characteristic $p$, it is well-known that $|{\mathcal{W}}_{F}|$
is invariant under CCZ-equivalence.

There is one more notion (which we will discuss very often) so called
algebraic degree which is invariant under EA-equivalence but not under CCZ-
equivalence. Any $(n,n)$-function $F$ on $\mathbb{F}_{p^{n}}$ is uniquely
represented by a univariate polynomial $F(x)\in\mathbb{F}_{p^{n}}[x]$ of
degree $<p^{n}$. That is,

$F(x)=\sum_{i=0}^{p^{n}-1}a_{i}x^{i},\quad a_{i}\in\mathbb{F}_{p^{n}}.$

For any integer $0\leq k<p^{n}$ with its $p$-ary expansion
$k=\sum_{j=0}^{n-1}k_{j}p^{j}$, we define $p$-weight of $k$, $w_{p}(k)$, as
$w_{p}(k)=\sum_{j=0}^{n-1}k_{j}$. An algebraic degree of $F$, $d^{\circ}(F)$,
is the maximum value among all $w_{p}(i)$ with $a_{i}\neq 0$;

$d^{\circ}(F)=\max_{\begin{subarray}{c}{0\leq i<p^{n}}\\\ {a_{i}\neq
0}\end{subarray}}w_{p}(i)\quad\text{ where
}F(x)=\sum_{i=0}^{p^{n}-1}a_{i}x^{i}.$

An $(n,n)$-function $F$ with its algebraic degree two is called a quadratic
function, and a quadratic function with no affine term,

$F(x)=\sum_{i\leq j}a_{i,j}x^{p^{i}+p^{j}},\quad
a_{i,j}\in\mathbb{F}_{p^{n}},$

is called a DO-polynomial (Dembowski-Ostrom polynomial). It is understood that
the summation indices $i\leq j$ becomes strict (i.e., $i<j$) if $p=2$.

##  3 Linear Structure, Linear Translator and Linear Kernel

Let $q=p^{n}$ be a power of a prime $p$ and let
$f:\mathbb{F}_{q^{n}}\rightarrow\mathbb{F}_{q}$ be a $(n,1)$-function on
$\mathbb{F}_{q^{n}}$.

###### Definition 3.1

Let $\gamma\in\mathbb{F}_{q^{n}}$ and $b\in\mathbb{F}_{q}$. We say $\gamma$ is
a $b$-linear structure of $f$ if

$\displaystyle f(x+\gamma)-f(x)=b\quad\text{ for all }x\in\mathbb{F}_{q^{n}},$

and $\gamma$ is called a linear structure of $f$ if $\gamma$ is a $b$-linear
structure of $f$ for some $b\in\mathbb{F}_{q}$. We also say $f$ has a
(nontrivial) linear structure if there exists
$\gamma\in\mathbb{F}_{q^{n}}^{\times}$ such that $\gamma$ is a linear
structure of $f$.

###### Definition 3.2

Let $\gamma\in\mathbb{F}_{q^{n}}$ and $b\in\mathbb{F}_{q}$. We say $\gamma$ is
a $b$-linear translator of $f$ if

$\displaystyle f(x+u\gamma)-f(x)=ub\quad\text{ for all
}x\in\mathbb{F}_{q^{n}}\text{ and }\text{ for all }u\in\mathbb{F}_{q},$

and $\gamma$ is called a linear translator of $f$ if $\gamma$ is a $b$-linear
translator of $f$ for some $b\in\mathbb{F}_{q}$. We also say $f$ has a
(nontrivial) linear translator if there exists
$\gamma\in\mathbb{F}_{q^{n}}^{\times}$ such that $\gamma$ is a linear
translator of $f$.

If $\gamma$ is a $b$-linear translator, then $\gamma$ is also a $b$-linear
structure. However, it turns out that, over a prime field $\mathbb{F}_{p}$,
‘linear translator’ and ‘linear structure’ are the same notion as is shown
below.

###### Lemma 3.3

Let $b\in\mathbb{F}_{p}$ and $\gamma\in\mathbb{F}_{p^{n}}^{\times}$. Let
$f:\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p}$ be a $(n,1)$-function. Then
$\gamma$ is a $b$-linear structure of $f$ if and only if $\gamma$ is a
$b$-linear translator of $f$.

Proof. $(\Leftarrow)$ is clear by taking $u=1$. $(\Rightarrow)$ For any
$u\in\mathbb{F}_{p^{n}}$,

$\displaystyle
f(x+u\gamma)-f(x)=\sum_{k=1}^{u}f(x+k\gamma)-f(x+(k-1)\gamma)=\sum_{k=1}^{u}f(x_{k}+\gamma)-f(x_{k})=\sum_{k=1}^{u}b=ub,$

where $x_{k}=x+(k-1)\gamma$.

###### Remark 3.4

It is well-known (e.g. see [34]) that the set

${\mathcal{LK}}_{f}\overset{\text{\rm
def}}{=}\\{\gamma\in\mathbb{F}_{p^{n}}:\gamma\text{ is a linear structure of
}f\\}$

is a vector subspace of $\mathbb{F}_{p^{n}}$ over $\mathbb{F}_{p}$, which is
briefly sketched below for the case of component functions. The subspace
${\mathcal{LK}}_{f}$ is called the linear kernel of $f$.

Let $F(x)\in{\mathbb{F}}_{p^{n}}[x]$ be an $(n,n)$-function and let

$\displaystyle L_{\gamma}(x)$
$\displaystyle\overset{\text{def}}{=}L_{\gamma,F}(x)=F(x+\gamma)-F(x)-(F(\gamma)-F(0))=D_{\gamma}F(x)-D_{\gamma}F(0)$

be the differential $D_{\gamma}F(x)$ with its constant term killed. Let
$\beta\in\mathbb{F}_{p^{n}}^{\times}$ and let

$\begin{split}\mathcal{LK}&\overset{\text{def}}{=}\mathcal{LK}_{{\rm Tr}(\beta
F)}\\\ &=\\{\gamma\in{\mathbb{F}}_{p^{n}}:{\rm Tr}(\beta
D_{\gamma}F(x))=\,\text{constant}\,={\rm Tr}(\beta D_{\gamma}F(0))\textrm{ for
all }x\in\mathbb{F}_{p^{n}}\\}\\\ &=\\{\gamma\in{\mathbb{F}}_{p^{n}}:{\rm
Tr}(\beta L_{\gamma}(x))=0\textrm{ for all }x\in\mathbb{F}_{p^{n}}\\}\\\
&=\\{\gamma\in\mathbb{F}_{p^{n}}:{\rm
Im}L_{\gamma}\subset\langle\beta\rangle^{\perp}\\}=\\{\gamma\in\mathbb{F}_{p^{n}}:\beta\in({\rm
Im}L_{\gamma})^{\perp}\\}\end{split}$ (3.1)

be the linear kernel of the component function ${\rm Tr}(\beta F)$, where
$W^{\perp}\overset{\textrm{def}}{=}\\{x\in\mathbb{F}_{p^{n}}:{\rm
Tr}(xw)=0\text{ for all }w\in W\\}$ for a subset $W$ of $\mathbb{F}_{p^{n}}$.

###### Remark 3.5

From the definition of the linear kernel, one has

$\gamma$ is a linear structure of ${\rm Tr}(\beta F)$ $\Leftrightarrow$
$\gamma\in{\mathcal{LK}}_{{\rm Tr}(\beta F)}$ $\Leftrightarrow$ ${\rm
Tr}(\beta L_{\gamma}(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$

From

$\displaystyle L_{\gamma+\gamma^{\prime}}(x)$
$\displaystyle=F(x+\gamma+\gamma^{\prime})-F(x)-(F(\gamma+\gamma^{\prime})-F(0))$
$\displaystyle=F(x+\gamma+\gamma^{\prime})-F(x+\gamma)-(F(\gamma^{\prime})-F(0))+F(x+\gamma)-F(x)-(F(\gamma)-F(0))$
$\displaystyle\qquad+F(\gamma^{\prime})-F(0)+F(\gamma)-F(0)-(F(\gamma+\gamma^{\prime})-F(0))$
$\displaystyle=L_{\gamma^{\prime}}(x+\gamma)+L_{\gamma}(x)+F(\gamma^{\prime})+F(\gamma)-F(\gamma+\gamma^{\prime})-F(0)$
$\displaystyle=L_{\gamma^{\prime}}(x+\gamma)+L_{\gamma}(x)-L_{\gamma}(\gamma^{\prime}),$
(3.2)

one has

${\rm Tr}(\beta L_{\gamma+\gamma^{\prime}}(x))={\rm Tr}(\beta
L_{\gamma^{\prime}}(x+\gamma))+{\rm Tr}(\beta L_{\gamma}(x))-{\rm Tr}(\beta
L_{\gamma}(\gamma^{\prime})),$

which implies that ${\mathcal{LK}}={\mathcal{LK}}_{{\rm Tr}(\beta F)}$ is
indeed a vector (sub)space of $\mathbb{F}_{p^{n}}$. (Please refer Remark 3.5.)
Note that $L_{\gamma}(\gamma^{\prime})=L_{\gamma^{\prime}}(\gamma)$ for all
$\gamma,\gamma^{\prime}\in\mathbb{F}_{p^{n}}$. Also note that $L_{\gamma}(x)$
is linear if $F$ is quadratic. Therefore Equation (3.2) for quadratic $F$ is
simplified as

$\displaystyle
L_{\gamma+\gamma^{\prime}}(x)=L_{\gamma}(x)+L_{\gamma^{\prime}}(x).$ (3.3)

###### Remark 3.6

  1. 1.

For a binary case, it is proven in [23] that, up to the cyclotomic equivalence
of the exponent, Gold function $x^{2^{i}+1}$ is the only (nonlinear) power
function $x^{d}$ whose component function ${\rm Tr}(\beta x^{d})$ has a linear
structure for some $\beta$.

  2. 2.

It is almost trivial that PN function $F$ on $\mathbb{F}_{p^{n}}$ ($p\neq 2$)
does not have any (nonzero) component function which has a linear structure,
since $\Delta_{F}=1$ implies that $D_{\gamma}F$ is surjective for all
$\gamma\in\mathbb{F}_{p^{n}}$. Therefore $D_{\gamma}{\rm Tr}(\beta F(x))={\rm
Tr}(\beta D_{\gamma}F(x))$ cannot be a constant function for $\beta\neq 0$.

###### Definition 3.7

Let $f:\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p}$ be an $(n,1)$-function. We
say $f$ is ($p$-ary) partially-bent if $D_{\gamma}f$ is either a constant or a
balanced function for every $\gamma\in\mathbb{F}_{p^{n}}$. A vectorial
$(n,n)$-function $F$ on $\mathbb{F}_{p^{n}}$ is called strongly plateaued if
${\rm Tr}(bF)$ is partially-bent for every $b\in\mathbb{F}_{p^{n}}$.

###### Remark 3.8

The above definition of ‘strongly plateaued’ comes from Definition $67$ in
[21], where binary case was dealt. For $p$-ary $(n,n)$-function, the above
definition also make sense since Proposition 4.1 implies that every nonzero
component function has one single nonzero absolute Walsh value.

###### Remark 3.9

  1. 1.

Note that $p$-ary $(n,1)$-function $f$ is called balanced if
$f^{-1}(i)\overset{\text{def}}{=}\\{x\in\mathbb{F}_{p^{n}}:f(x)=i\\}$ is a
subset of size $p^{n-1}$ for every $0\leq i<p$.

  2. 2.

If $(n,n)$-function $F$ on $\mathbb{F}_{p^{n}}$ is quadratic, then since
$L_{\gamma}$ is linear, ${\rm Tr}(bL_{\gamma}(x))$ is either zero function or
balanced function. That is, every quadratic $(n,n)$-function is strongly
plateaued.

###### Proposition 3.10

Properties of strongly plateaued $(n,n)$-functions varies depending on the
characteristic $p$ as follows:

  1. 1.

When $p=2$, every strongly plateaued $(n,n)$-function $F$ on
$\mathbb{F}_{2^{n}}$ has a (nonzero) component function which has a
(nontrivial) linear structure.

  2. 2.

When $p\neq 2$, a strongly plateaued $(n,n)$-function $F$ on
$\mathbb{F}_{p^{n}}$ has a (nonzero) component function which has a
(nontrivial) linear structure if and only if $F$ is not PN(Perfect Nonlinear).

Proof.

1. If $F$ has no component function ${\rm Tr}(\beta F)$ which has a linear structure except for $\beta=0$, then $D_{\gamma}({\rm Tr}(\beta F))$ is balanced for all $\beta,\gamma\in\mathbb{F}_{2^{n}}^{\times}$, which implies that ${\rm Tr}(\beta F)$ is bent for all $\beta\in\mathbb{F}_{2^{n}}^{\times}$. This is impossible because there is no bent $(n,n)$-function for $p=2$ (See [40]).

2. If $\gamma$ is a linear structure of ${\rm Tr}(\beta F)$ for some $\beta,\gamma\in\mathbb{F}_{p^{n}}^{\times}$, then one has ${\rm Tr}(\beta L_{\gamma}(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$, i.e., $\beta\in({\rm Im}L_{\gamma})^{\perp}$. Therefore $D_{\gamma}F$ is not surjective. The other direction is also clear.

As a special case of strongly plateaued functions, we have a more detailed
description on the linear structures of component functions of quadratic
function $F$ below.

###### Proposition 3.11

Let $F$ be a quadratic $(n,n)$-function on $\mathbb{F}_{p^{n}}$ such that
$\Delta_{F}>1$. Then there exist $\gamma,\beta\in\mathbb{F}_{p^{n}}^{\times}$
such that $\gamma$ is a linear structure of ${\rm Tr}(\beta F(x))$ (i.e.,
${\rm Tr}(\beta L_{\gamma}(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$). More
precisely,

  1. 1

If $p=2$, then for every $\gamma\in\mathbb{F}_{p^{n}}^{\times}$, there exists
$\beta\in\mathbb{F}_{p^{n}}^{\times}$ such that ${\rm Tr}(\beta
L_{\gamma}(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$.

  2. 2

If $p>2$ and $\Delta_{F}>1$ (i.e., $F$ is not PN), then there exist
$\gamma,\beta\in\mathbb{F}_{p^{n}}^{\times}$ such that ${\rm Tr}(\beta
L_{\gamma}(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$.

Proof.
1. Since $L_{\gamma}(x)=F(x+\gamma)+F(x)+F(\gamma)+F(0)$ is linear such that $L_{\gamma}(0)=0=L_{\gamma}(\gamma)$, one has $|{\rm Ker}L_{\gamma}|\geq 2$. Therefore ${\rm Im}L_{\gamma}$ is a subspace of $\mathbb{F}_{p^{n}}$ of dimension $\leq n-1$, that is, $L_{\gamma}$ is not surjective. Consequently there exists nonzero $\beta\in({\rm Im}L_{\gamma})^{\perp}=\\{b\in\mathbb{F}_{p^{n}}:{\rm Tr}(bL_{\gamma}(x))=0\text{ for all }x\in\mathbb{F}_{p^{n}}\\}$.

2. Since $F$ is not a PN function, one has $\Delta_{F}=p^{s}$ for some $1\leq s\leq n$. Therefore there exists $\gamma\in\mathbb{F}_{p^{n}}^{\times}$ such that $|{\rm Ker}L_{\gamma}|=\Delta_{F}=p^{s}$. For this choice of $\gamma$, one has a subspace ${\rm Im}L_{\gamma}$ of dimension $n-s\leq n-1$. In the same way, there exists nonzero $\beta\in({\rm Im}L_{\gamma})^{\perp}$.

##  4 Walsh Transform of ($p$-ary) Strongly Plateaued Functions over Arbitrary
Characteristic

The subsequent survey also applies to quadratic functions as a special case.
Moreover, we will give concrete examples of $F^{\prime}$ satisfying
$F\overset{\textrm{\tiny CCZ}}{\sim}F^{\prime}$ but $F\overset{\textrm{\tiny
EA}}{\not\sim}F^{\prime}$ only for quadratic $F$ in Section 7. For a binary
case, Walsh transform of strongly plateaued functions is well-documented (See
for example [18]). In fact, The case $p\neq 2$ is not so much different from
the case $p=2$. However, for the clarity of the exposition for general $p$, we
briefly survey Walsh transform of strongly plateaued functions on
$\mathbb{F}_{p^{n}}$ with arbitrary characteristic $p$.

Let $F:{\mathbb{F}}_{p^{n}}\to{\mathbb{F}}_{p^{n}}$ be a strongly plateaued
function (or a quadratic function). Let $b\in\mathbb{F}_{p^{n}}^{\times}$ and
let $\mathcal{LK}=\mathcal{LK}_{{\rm
Tr}(bF)}=\\{\gamma\in{\mathbb{F}}_{p^{n}}:{\rm Tr}(bL_{\gamma}(x))=0\textrm{
for all }x\in\mathbb{F}_{p^{n}}\\}$ be the linear kernel of ${\rm Tr}(bF)$
with $L_{\gamma}(x)=F(x+\gamma)-F(x)-(F(\gamma)-F(0))$ (See Equation (3.1)).
Noting that $\bar{\xi}=\xi^{-1}$,

$\displaystyle|{\mathcal{W}}_{F}(a,b)|^{2}$
$\displaystyle=\sum_{y\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm
Tr}(bF(y)-ay)}\cdot\sum_{x\in{\mathbb{F}}_{p^{n}}}(\xi^{-1})^{{\rm
Tr}(bF(x)-ax)}$ $\displaystyle=\sum_{x,y\in{\mathbb{F}}_{p^{n}}}\xi^{-{\rm
Tr}(a(y-x))}\xi^{{\rm Tr}(b[F(y)-F(x)])}$
$\displaystyle=\sum_{x,\gamma\in{\mathbb{F}}_{p^{n}}}\xi^{-{\rm
Tr}(a\gamma)}\xi^{{\rm Tr}(b[F(x+\gamma)-F(x)])}$
$\displaystyle=\sum_{\gamma\in{\mathbb{F}}_{p^{n}}}\xi^{-{\rm
Tr}(a\gamma)}\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm
Tr}(b[F(x+\gamma)-F(x)])}$
$\displaystyle=\sum_{\gamma\in{\mathbb{F}}_{p^{n}}}\xi^{-{\rm
Tr}(a\gamma)}\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm
Tr}(bL_{\gamma}(x))+\epsilon_{\gamma}}\qquad(\epsilon_{\gamma}={\rm
Tr}(b[F(\gamma)-F(0)]))$ $\displaystyle=\sum_{\gamma\in\mathcal{LK}}\xi^{-{\rm
Tr}(a\gamma)}\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{\epsilon_{\gamma}}+\sum_{\gamma\notin\mathcal{LK}}\xi^{-{\rm
Tr}(a\gamma)}\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm
Tr}(bL_{\gamma}(x))+\epsilon_{\gamma}}.$

For $\gamma\notin\mathcal{LK}$, since ${\rm Tr}(bL_{\gamma}(x))$ is a balanced
function if $F$ is strongly plateaued (or since ${\rm Tr}(bL_{\gamma}(x))$ is
nonzero linear function if $f$ is quadratic), ${\rm Tr}(bL_{\gamma}(x))$ takes
every $u\in\mathbb{F}_{p}$ equally many times. Therefore since
$\sum_{u=0}^{p-1}\xi^{u}=0$, one gets

$\displaystyle|{\mathcal{W}}_{F}(a,b)|^{2}=p^{n}\sum_{\gamma\in\mathcal{LK}}\xi^{-{\rm
Tr}(a\gamma)+\epsilon_{\gamma}}.$

Now let $\\{\gamma_{1},\gamma_{2},\cdots,\gamma_{k}\\}$ be a basis for
$\mathcal{LK}$ over $\mathbb{F}_{p}$ and let
$\epsilon_{i}\overset{\textrm{def}}{=}\epsilon_{\gamma_{i}}={\rm
Tr}(b[F(\gamma_{i})-F(0)])$ for $1\leq i\leq k$. Then using the vector space
property of $\mathcal{LK}$, for any
$\gamma=\sum_{i=1}^{k}e_{i}\gamma_{i}\in\mathcal{LK}$ with
$e_{i}\in\mathbb{F}_{p}$, one can express $\epsilon_{\gamma}$ as

$\epsilon_{\gamma}=\epsilon_{\sum_{i=1}^{k}e_{i}\gamma_{i}}=\sum_{i=1}^{k}e_{i}\epsilon_{\gamma_{i}}=\sum_{i=1}^{k}e_{i}\epsilon_{i}\,\,\in\mathbb{F}_{p}.$

Extend $\\{\gamma_{1},\gamma_{2},\cdots,\gamma_{k}\\}$ to a basis
$\\{\gamma_{1},\gamma_{2},\cdots,\gamma_{k},\gamma_{k+1},\cdots,\gamma_{n}\\}$
for $\mathbb{F}_{p^{n}}$ and let $\\{\alpha_{1},\cdots,\alpha_{n}\\}$ be a
unique dual basis of $\\{\gamma_{1},\cdots,\gamma_{n}\\}$, i.e., ${\rm
Tr}(\alpha_{i}\gamma_{j})=1$ if $i=j$ and ${\rm Tr}(\alpha_{i}\gamma_{j})=0$
if $i\neq j$.

Let $a=\sum_{i=1}^{n}a_{i}\alpha_{i}\in\mathbb{F}_{p^{n}}$
($a_{i}\in\mathbb{F}_{p}$). Then

$\displaystyle|{\mathcal{W}}_{F}(a,b)|^{2}$
$\displaystyle=p^{n}\sum_{\gamma\in\mathcal{LK}}\xi^{-{\rm
Tr}\left((\sum_{i=1}^{n}a_{i}\alpha_{i})(\sum_{j=1}^{k}e_{j}\gamma_{j})\right)+\epsilon_{\gamma}}$
$\displaystyle=p^{n}\sum_{\gamma\in\mathcal{LK}}\xi^{-(\sum_{i=1}^{k}a_{i}e_{i})+\epsilon_{\gamma}}=p^{n}\sum_{\gamma\in\mathcal{LK}}\xi^{\sum_{i=1}^{k}(\epsilon_{i}-a_{i})e_{i}}.$

As $\gamma=\sum_{i=1}^{k}e_{i}\gamma_{i}$ runs through all elements of
$\mathcal{LK}$, the vectors $\langle e_{1},\cdots,e_{k}\rangle$ runs through
all vectors of $\mathbb{F}_{p}^{k}$. Therefore, if
$\langle\epsilon_{1}-a_{1},\cdots,\epsilon_{k}-a_{k}\rangle$ is a nonzero
vector, $\sum_{i=1}^{k}(\epsilon_{i}-a_{i})e_{i}\in\mathbb{F}_{p}$ is balanced
for all inputs $\langle e_{1},\cdots,e_{k}\rangle$. With these observations,
one has the following well-known result of Walsh transform of strongly
plateaued (or quadratic) functions over arbitrary characteristic $p$.

###### Proposition 4.1

(Walsh transform of strongly plateaued functions) Let
$F(x)\in\mathbb{F}_{p^{n}}[x]$ be an $(n,n)$-function such that $F$ is
strongly plateaued (or quadratic). Let $a,b\in\mathbb{F}_{p^{n}}$. let
${\mathcal{LK}}={\mathcal{LK}}_{{\rm Tr}(bF)}$ be the linear kernel of ${\rm
Tr}(bF)$ of dimension $0\leq k\leq n$ such that ${\mathcal{LK}}$ has a basis
$\\{\gamma_{1},\cdots,\gamma_{k}\\}$, and
$\\{\gamma_{1},\cdots,\gamma_{k},\gamma_{k+1},\cdots\gamma_{n}\\}$ is a basis
for $\mathbb{F}_{p^{n}}$. Let $\\{\alpha_{1},\cdots,\alpha_{n}\\}$ be a unique
dual basis of $\\{\gamma_{1},\cdots,\gamma_{n}\\}$. Let
$a=\sum_{i=1}^{n}a_{i}\alpha_{i}$ and $\epsilon_{i}={\rm
Tr}(b[F(\gamma_{i})-F(0)])$ $(1\leq i\leq k)$. Then one has

$|{\mathcal{W}}_{F}(a,b)|^{2}=p^{n}\sum_{\gamma(=\sum_{j=1}^{k}e_{j}\gamma_{j})\in\mathcal{LK}}\xi^{\sum_{i=1}^{k}(\epsilon_{i}-a_{i})e_{i}}=\begin{cases}p^{n+k}&\text{
if }\epsilon_{i}=a_{i}\text{ for all }1\leq i\leq k\\\ 0&\text{ if
not}.\end{cases}$

Consequently one has,

$\displaystyle|{\mathcal{W}}_{{\rm Tr}(bF)}|$
$\displaystyle=p^{\frac{n+k}{2}}\quad\text{ where }k=\dim{\mathcal{LK}}_{{\rm
Tr}(bF)},$ $\displaystyle|{\mathcal{W}}_{F}|$
$\displaystyle=p^{\frac{n+k_{m}}{2}}\quad\text{ where
}k_{m}=\max_{b\in\mathbb{F}_{p^{n}}^{\times}}\dim{\mathcal{LK}}_{{\rm
Tr}(bF)}.$

##  5 CCZ-Equivalence of Some Functions Having Linear Structure

###### Lemma 5.1

Let $\alpha,\beta\in\mathbb{F}_{p^{n}}$ and
$\gamma\in\mathbb{F}_{p^{n}}^{\times}$. Let
${\mathscr{L}}:\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}$
be defined by

$\displaystyle\mathscr{L}:\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}$
$\displaystyle\rightarrow\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}$
$\displaystyle(x,y)$ $\displaystyle\mapsto(x+\gamma{\rm Tr}(\alpha x+\beta
y),y).$

Then, ${\mathscr{L}}$ is a linear permutation on
$\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}$ if and only if ${\rm
Tr}(\alpha\gamma)\neq-1$.

Proof. Since the linearity of ${\mathscr{L}}$ is clear, it is enough to show

${\mathscr{L}}\text{ is one to one }\Longleftrightarrow{\rm
Tr}(\alpha\gamma)\neq-1$

Now,

$\displaystyle{\mathscr{L}}(x,y)={\mathscr{L}}(x^{\prime},y^{\prime})$
$\displaystyle\Leftrightarrow(x+\gamma{\rm Tr}(\alpha x+\beta
y),y)=(x^{\prime}+\gamma{\rm Tr}(\alpha x^{\prime}+\beta
y^{\prime}),y^{\prime})$ $\displaystyle\Leftrightarrow y^{\prime}=y\text{ and
}x+\gamma{\rm Tr}(\alpha x)=x^{\prime}+\gamma{\rm Tr}(\alpha x^{\prime})$
$\displaystyle\Leftrightarrow y^{\prime}=y\text{ and }x-x^{\prime}=-\gamma{\rm
Tr}(\alpha(x-x^{\prime}))=-\gamma u\quad(u={\rm
Tr}(\alpha(x-x^{\prime}))\in\mathbb{F}_{p})$ $\displaystyle\Leftrightarrow
y^{\prime}=y\text{ and }-\gamma u=\gamma u{\rm Tr}(\alpha\gamma)$
$\displaystyle\Leftrightarrow y^{\prime}=y\text{ and }u({\rm
Tr}(\alpha\gamma)+1)=0\quad(\because\gamma\neq 0)$
$\displaystyle\Leftrightarrow y^{\prime}=y\text{ and
}x^{\prime}=x\quad\text{or}\quad y^{\prime}=y\text{ and }{\rm
Tr}(\alpha\gamma)=-1\quad(x-x^{\prime}=-\gamma u)$

###### Proposition 5.2

Let $p$ be a prime. Suppose that $F_{0}(x)\in\mathbb{F}_{p^{n}}[x]$ is an
$(n,n)$-function such that $\gamma$ is a linear structure of ${\rm Tr}(\beta
F_{0})$ for some $\beta,\gamma\in\mathbb{F}_{p^{n}}^{\times}$. Then, choosing
$\alpha,c\in\mathbb{F}_{p^{n}}$ satisfying

$\displaystyle{\rm Tr}(\alpha\gamma)=-2,\qquad{\rm Tr}(c\beta\gamma)=-{\rm
Tr}(\beta D_{\gamma}F_{0}(0)),$

and letting $F(x)=F_{0}(x)+cx$, the function

$\displaystyle H(x)=x+\gamma{\rm Tr}\left(\alpha x+\beta F(x)\right)$

is an involution, i.e. $H\circ H(x)=x$ for all $x\in\mathbb{F}_{p^{n}}$.

Proof. Since

$\displaystyle L_{\gamma,F}(x)$
$\displaystyle=F(x+\gamma)-F(x)-(F(\gamma)-F(0))$
$\displaystyle=F_{0}(x+\gamma)-F_{0}(x)+c\gamma-(F_{0}(\gamma)+c\gamma-
F_{0}(0))=L_{\gamma,F_{0}}(x),$

$L_{\gamma}(x)=L_{\gamma,F}(x)=L_{\gamma,F_{0}}(x)$ is independent of choices
of $F(x)=F_{0}(x)+cx$ for any $c\in\mathbb{F}_{p^{n}}$. On the other hand,
$D_{\gamma}F(x)=D_{\gamma}F_{0}(x)+c\gamma$ so that

$\displaystyle{\rm Tr}(\beta D_{\gamma}F(x))={\rm
Tr}\left(\beta(D_{\gamma}F_{0}(x)+c\gamma)\right)={\rm Tr}(\beta
D_{\gamma}F_{0}(x))+{\rm Tr}(c\beta\gamma).$

Since $\gamma$ is a linear structure of ${\rm Tr}(\beta F_{0}(x))$ (i.e.,
${\rm Tr}(\beta D_{\gamma}F_{0}(x))={\rm Tr}(\beta D_{\gamma}F_{0}(0))$ for
all $x\in\mathbb{F}_{p^{n}}$), choosing any $c\in\mathbb{F}_{p^{n}}$
satisfying

$\displaystyle{\rm Tr}(c\beta\gamma)=-{\rm Tr}(\beta D_{\gamma}F_{0}(0))=-{\rm
Tr}(\beta[F_{0}(\gamma)-F_{0}(0)]),$

one finds that $\gamma$ is a $0$-linear structure of ${\rm Tr}(\beta F(x))$
with $F(x)=F_{0}(x)+cx$. That is,

$\displaystyle{\rm Tr}(\beta D_{\gamma}F(x))=0\text{ for all
}x\in\mathbb{F}_{p^{n}}.$ (5.1)

Define $\varepsilon$ as an $(n,1)$-function

$\displaystyle\varepsilon=\varepsilon(x)={\rm Tr}\left(\alpha x+\beta
F(x)\right)$

so that $H(x)=x+\gamma\varepsilon$. Then

$\displaystyle F\circ
H(x)=F(x+\gamma\varepsilon)=F(x)+F(x+\gamma\varepsilon)-F(x)=F(x)+D_{\gamma\varepsilon}F(x),$
(5.2)

where $D_{\gamma\varepsilon}F(x)$ is defined as

$\displaystyle
D_{\gamma\varepsilon}F(x)=F(x+\gamma\varepsilon)-F(x)=F\left(x+\gamma{\rm
Tr}(\alpha x+\beta F(x))\right)-F(x).$

Then

$\displaystyle H\circ H(x)$ $\displaystyle=H(x)+\gamma{\rm Tr}\left(\alpha
H(x)+\beta F(H(x))\right)$ $\displaystyle=x+\gamma\varepsilon+\gamma{\rm
Tr}\left(\alpha(x+\gamma\varepsilon)+\beta[F(x)+D_{\gamma\varepsilon}F(x)]\right)$
(5.3) $\displaystyle=x+\gamma\varepsilon+\gamma\varepsilon+\gamma{\rm
Tr}\left(\alpha\gamma\varepsilon+\beta D_{\gamma\varepsilon}F(x)\right)$
$\displaystyle=x+\gamma\varepsilon(2+{\rm Tr}(\alpha\gamma))+\gamma{\rm
Tr}\left(\beta D_{\gamma\varepsilon}F(x)\right)$ $\displaystyle=x+\gamma{\rm
Tr}\left(\beta D_{\gamma\varepsilon}F(x)\right).\qquad(\because{\rm
Tr}(\alpha\gamma)=-2)$ (5.4)

Also, from Equation (5.1), one has ${\rm Tr}(\beta D_{\gamma}F(x))=0$ for all
$x\in\mathbb{F}_{p^{n}}$. Moreover, from Lemma 3.3 by taking $f(x)={\rm
Tr}(\beta F(x))$, one has

$\displaystyle{\rm Tr}\left(\beta F(x+\gamma u)-\beta F(x)\right)={\rm
Tr}(\beta D_{\gamma u}F(x))=0$

for all $x\in\mathbb{F}_{p^{n}}$ and for all $u\in\mathbb{F}_{p}$. Therefore,
from Equation (5.4), one has $H\circ H(x)=x$ for all $x\in\mathbb{F}_{p^{n}}$.

###### Theorem 5.3

Under the same conditions as in Proposition 5.2, $F_{0}$ and $F\circ H$ are
CCZ-equivalent. More precisely, we have the following equivalence

$F_{0}\overset{\textrm{\tiny EA}}{\sim}F\overset{\textrm{\tiny
CCZ}}{\sim}F\circ H.$

Proof. $F_{0}\overset{\textrm{\tiny EA}}{\sim}F$ is clear because
$F(x)=F_{0}(x)+cx$. From Lemma 5.1, one gets

$\displaystyle\mathscr{L}(x,F(x))$ $\displaystyle=(x+\gamma{\rm Tr}(\alpha
x+\beta F(x)),F(x))=(H(x),F(x))$ $\displaystyle=(H(x),F\circ H\circ
H(x))\quad\because H\text{ is an involution. }$ $\displaystyle=(y,F\circ
H(y))\qquad(y=H(x))$

Since $\mathscr{L}$ is a permutation on
$\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{n}}$ if ${\rm
Tr}(\alpha\gamma)\neq-1$, and since $H$ is a permutation on
$\mathbb{F}_{p^{n}}$, the mapping $\mathscr{L}$ gives a graph isomorphism
between the two sets $\\{(x,F(x)):x\in\mathbb{F}_{p^{n}}\\}$ and $\\{(x,F\circ
H(x)):x\in\mathbb{F}_{p^{n}}\\}$.

###### Remark 5.4

The resulting function $F\circ H$ is essentially, as you can see the
expression in Proposition 5.6, a generalized form arising from switching
technique. This idea is originally due to Dillon and developed in many
articles such as [30, 36].

###### Remark 5.5

It should be mentioned that, for a binary field, similar observations and
results are found in [20, 6]. In [20], Canteaut and Perrin used the notion of
function twisting and linear structure to derive a similar result as above. It
is also mentioned in page $242$ that “…it is very unlikely that the resulting
function has degree $2$.”. Also in [6], Budaghyan, Calderini and Villa
obtained a similar construction using a linear structure. In page $15$, they
also remarked that “…such a transformation could lead to a function of degree
$3$.”. However, none of the papers [20, 6] give a new explicit example of
cubic function which is CCZ-equivalent to given quadratic function. At this
moment, to the authors’ knowledge, the following two functions

– $x^{2^{i}+1}$ in [13],

– $x^{3}+a^{-1}{\rm Tr}(a^{3}x^{9})$ in [11],

are the only explicit examples of quadratic functions which have (non-obvious)
CCZ-equivalent functions of algebraic degree $\geq 3$.

As a result of Theorem 5.3, it is natural to ask whether $F$ and $F\circ H$ is
EA-equivalent or not. A straightforward approach is to examine the algebraic
degree of $F\circ H$. We expect that $d^{\circ}(F)<d^{\circ}(F\circ H)$ under
mild restrictions on the differential uniformity and the (non)linearity of
$F$, but it seems to be a complicated problem for general situations. However,
for a quadratic case (i.e., $d^{\circ}(F)=2$), we have a satisfactory result
saying that

$d^{\circ}(F\circ H)=\begin{cases}3&\text{ if }p=2\\\ 3\text{ or }4&\text{ if
}p>2.\end{cases}$

To validate the above result, we first need to find a polynomial expression of
$F\circ H$ when $d^{\circ}(F)=2$. Let

$F(x)=F_{\text{\tiny DO}}(x)+F_{\ell}(x)+F(0),$

where $F_{\ell}$ is the linear part of $F$ and

$F_{\text{\tiny DO}}(x)=\sum_{i\leq j}a_{i,j}x^{p^{i}+p^{j}}\qquad(\text{When
}p=2,\text{ the ordering is strict, i.e., }i<j)$

is the DO-part of $F(x)$.

###### Proposition 5.6

Let $F(x)$ be any quadratic $(n,n)$-function and let $H(x)=x+\gamma{\rm
Tr}(\alpha x+\beta F(x))$ with $\alpha,\beta,\gamma\in\mathbb{F}_{p^{n}}$.
Then, letting $\varepsilon={\rm Tr}(\alpha x+\beta F(x))$, one has

$\displaystyle F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon),$

where $F_{\text{\tiny DO}}$ is the DO-part of $F$. More precisely,

  1. 1.

If $p=2$, then

$\displaystyle F\circ H(x)$ $\displaystyle=F(x)+\varepsilon D_{\gamma}F(x).$
(5.5)

  2. 2.

If $p>2$, then

$\displaystyle F\circ H(x)$ $\displaystyle=F(x)+\varepsilon
D_{\gamma}F(x)+F_{\text{\tiny DO}}(\gamma)(\varepsilon^{2}-\varepsilon).$
(5.6)

Proof. Using $H(x)=x+\gamma\varepsilon$,

$\displaystyle F\circ H(x)$
$\displaystyle=F(x+\gamma\varepsilon)=F_{\text{\tiny
DO}}(x+\gamma\varepsilon)+F_{\ell}(x+\gamma\varepsilon)+F(0).$ (5.7)

Since

$\displaystyle F_{\text{\tiny DO}}(x+\gamma\varepsilon)$
$\displaystyle=\sum_{i\leq
j}a_{i,j}(x+\gamma\varepsilon)^{p^{i}+p^{j}}=\sum_{i\leq
j}a_{i,j}(x^{p^{i}}+\gamma^{p^{i}}\varepsilon)(x^{p^{j}}+\gamma^{p^{j}}\varepsilon)$
$\displaystyle=\sum_{i\leq
j}a_{i,j}\left(x^{p^{i}+p^{j}}+(\gamma^{p^{j}}x^{p^{i}}+\gamma^{p^{i}}x^{p^{j}}+\gamma^{p^{i}+p^{j}})\varepsilon+\gamma^{p^{i}+p^{j}}(\varepsilon^{2}-\varepsilon)\right)$
$\displaystyle=F_{\text{\tiny DO}}(x)+\varepsilon D_{\gamma}F_{\text{\tiny
DO}}(x)+F_{\text{\tiny DO}}(\gamma)(\varepsilon^{2}-\varepsilon),$ (5.8)

Combining Equation (5.7) and (5.8), one has

$\displaystyle F\circ H(x)$ $\displaystyle=F_{\text{\tiny
DO}}(x+\gamma\varepsilon)+F_{\ell}(x+\gamma\varepsilon)+F(0)$
$\displaystyle=F_{\text{\tiny DO}}(x)+\varepsilon D_{\gamma}F_{\text{\tiny
DO}}(x)+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)+F_{\ell}(x)+F_{\ell}(\gamma)\varepsilon+F(0)$
$\displaystyle=\\{F_{\text{\tiny
DO}}(x)+F_{\ell}(x)+F(0)\\}+\varepsilon\\{D_{\gamma}F_{\text{\tiny
DO}}(x)+F_{\ell}(\gamma)\\}+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)$ $\displaystyle=F(x)+\varepsilon
D_{\gamma}F(x)+F_{\text{\tiny DO}}(\gamma)(\varepsilon^{2}-\varepsilon).$

From the above Proposition, to show $d^{\circ}(F\circ H)>2$, it is enough to
show that the algebraic degrees of $\varepsilon D_{\gamma}F(x)$ and
$\varepsilon^{2}$ are greater than two. In the following section, we will show
that

$\displaystyle d^{\circ}(\varepsilon D_{\gamma}F(x))$
$\displaystyle=3\quad\text{ for any }p,\quad\text{ and }$ $\displaystyle\quad
d^{\circ}(\varepsilon^{2})$ $\displaystyle=4\quad\text{ for odd }p,$

are satisfied under certain mild restrictions on $F$.

##  6 Algebraic Degrees of Products of Quadratic Functions

For quadratic $F(x)\in\mathbb{F}_{p^{n}}[x]$, recall that
$L_{\gamma}(x)=F(x+\gamma)-F(x)-(F(\gamma)-F(0))$ is bilinear with respect to
$\gamma,x\in\mathbb{F}_{p^{n}}.$ That is,
$L_{\gamma_{1}+\gamma_{2}}(x)=L_{\gamma_{1}}(x)+L_{\gamma_{2}}(x)$ and
$L_{\gamma}(x+y)=L_{\gamma}(x)+L_{\gamma}(y)$. Moreover $L_{\gamma}(x)$ is
symmetric in the sense that $L_{\gamma}(\beta)=L_{\beta}(\gamma)$.

###### Lemma 6.1

Let $F(x)\in\mathbb{F}_{p^{n}}[x]$ be a quadratic $(n,n)$-function and let

$F_{3}(x)={\rm Tr}(\beta F(x))D_{\gamma}F(x)$

with $\beta,\gamma\in\mathbb{F}_{p^{n}}$. Then for any
$\gamma_{1},\gamma_{2},\gamma_{3}\in{\mathbb{F}}_{p^{n}}$, we have

$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3}))L_{\gamma}(\gamma_{1})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{2}))L_{\gamma}(\gamma_{3}).$

Proof. From $F_{3}(x)={\rm Tr}(\beta F(x))D_{\gamma}F(x)={\rm Tr}(\beta
F(x))\left(L_{\gamma}(x)+(F(\gamma)-F(0))\right)$, one gets
$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)=D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}\left({\rm
Tr}(\beta F(x))L_{\gamma}(x)\right)$ because $d^{\circ}({\rm Tr}(\beta
F(x))\leq 2$. Now

$\displaystyle D_{\gamma_{1}}\left({\rm Tr}(\beta F(x))L_{\gamma}(x)\right)$
$\displaystyle={\rm Tr}(\beta F(x+\gamma_{1}))L_{\gamma}(x+\gamma_{1})-{\rm
Tr}(\beta F(x))L_{\gamma}(x)$ $\displaystyle={\rm Tr}\left(\beta
F(x+\gamma_{1})-\beta F(x)\right)L_{\gamma}(x)+{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})$ $\displaystyle={\rm Tr}\left(\beta
L_{\gamma_{1}}(x)+\beta(F(\gamma_{1})-F(0))\right)L_{\gamma}(x)+{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})$ $\displaystyle={\rm Tr}\left(\beta
L_{\gamma_{1}}(x)\right)L_{\gamma}(x)+{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})+{\rm
Tr}(\beta(F(\gamma_{1})-F(0)))L_{\gamma}(x).$

Since $d^{\circ}(L_{\gamma}(x))\leq 1$, one has

$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}\left({\rm Tr}(\beta
F(x))L_{\gamma}(x)\right)=D_{\gamma_{3}}D_{\gamma_{2}}\left[{\rm
Tr}\left(\beta L_{\gamma_{1}}(x)\right)L_{\gamma}(x)+{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})\right],$

where

$\displaystyle D_{\gamma_{2}}$ $\displaystyle\left[{\rm Tr}\left(\beta
L_{\gamma_{1}}(x)\right)L_{\gamma}(x)+{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})\right]$ $\displaystyle=\,$
$\displaystyle{\rm Tr}\left(\beta
L_{\gamma_{1}}(x+\gamma_{2})\right)L_{\gamma}(x+\gamma_{2})+{\rm Tr}(\beta
F(x+\gamma_{1}+\gamma_{2}))L_{\gamma}(\gamma_{1})$ $\displaystyle-{\rm
Tr}\left(\beta L_{\gamma_{1}}(x)\right)L_{\gamma}(x)-{\rm Tr}(\beta
F(x+\gamma_{1}))L_{\gamma}(\gamma_{1})$ $\displaystyle=\,$ $\displaystyle{\rm
Tr}\left(\beta L_{\gamma_{1}}(x)\right)L_{\gamma}(\gamma_{2})+{\rm
Tr}\left(\beta L_{\gamma_{1}}(\gamma_{2})\right)L_{\gamma}(x)+{\rm
Tr}\left(\beta L_{\gamma_{1}}(\gamma_{2})\right)L_{\gamma}(\gamma_{2})$
$\displaystyle+{\rm Tr}\left(\beta
L_{\gamma_{2}}(x+\gamma_{1})+\beta(F(\gamma_{2})-F(0))\right)L_{\gamma}(\gamma_{1}).$

Since $D_{\gamma_{3}}$ kills all the constant terms, we get

$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}\left({\rm Tr}(\beta
F(x))L_{\gamma}(x)\right)={\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{2}))L_{\gamma}(\gamma_{3})+{\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3}))L_{\gamma}(\gamma_{1}).$

###### Proposition 6.2

Suppose that $F$ is a quadratic $(n,n)$-function with $n\geq 4$ and suppose
that

$|{\mathcal{W}}_{F}|\overset{\text{\rm
def}}{=}\max_{b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{{\rm
Tr}(bF)}|<p^{n}\quad\textrm{and}\quad\Delta_{F}\leq p^{n-3}.$

Let $\varepsilon={\rm Tr}(\alpha x+\beta F(x))$ with
$\alpha\in\mathbb{F}_{p^{n}}$ and $\beta\in\mathbb{F}_{p^{n}}^{\times}$. Then,
one has $d^{\circ}(\varepsilon D_{\gamma}F)=3$ for any
$\gamma\in\mathbb{F}_{p^{n}}^{\times}$.

Proof. Since $d^{\circ}(F)=2$ and $d^{\circ}({\rm Tr}(\alpha
x)D_{\gamma}F(x))\leq 2$, to prove the proposition, it is enough to show that
$d^{\circ}(F_{3})=3$ where $F_{3}(x)={\rm Tr}(\beta F(x))D_{\gamma}F(x)$. On
the contrary, suppose that $d^{\circ}(F_{3})\leq 2$. Then for any
$\gamma_{1},\gamma_{2},\gamma_{3}\in\mathbb{F}_{p^{n}}$, one has
$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)=0$ for all
$x\in\mathbb{F}_{p^{n}}$. On the other hand, by Lemma 6.1, one has

$\displaystyle D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)={\rm
Tr}(\beta L_{\gamma_{2}}(\gamma_{3}))L_{\gamma}(\gamma_{1})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{2}))L_{\gamma}(\gamma_{3}),$ (6.1)

which is a constant independent of $x$ (but depending on
$\gamma_{1},\gamma_{2},\gamma_{3}$). We will show that the derivative is
nonzero for some suitable choices of $\gamma_{1},\gamma_{2}$ and $\gamma_{3}$.
From the assumption, one gets

$\displaystyle p^{s}\overset{\textrm{def}}{=}|{\rm
Ker}L_{\gamma}|\leq\Delta_{F}\leq p^{n-3}.$ (6.2)

Also, one has the following isomorphism between vector spaces over
$\mathbb{F}_{p}$,

$\mathbb{F}_{p^{n}}/{\rm Ker}L_{\gamma}\cong{\rm Im}L_{\gamma},$

which implies that $|{\rm Im}L_{\gamma}|=p^{n-s}\geq p^{3}$ by the Equation
(6.2). Therefore ${\rm Im}L_{\gamma}$ is a vector subspace of dimension
$n-s\geq 3$ over $\mathbb{F}_{p}$ and there exist at least three independent
(nonzero) vectors in ${\rm Im}L_{\gamma}$. Moreover, we have a disjoint
(additive) coset decomposition of $\mathbb{F}_{p^{n}}$ as

$\displaystyle\mathbb{F}_{p^{n}}=\cup_{i=0}^{p^{n-s}-1}=K_{0}\cup
K_{1}\cup\cdots\cup K_{p^{n-s}-1}\qquad(K_{i}=\theta_{i}+{\rm Ker}L_{\gamma})$

with $\theta_{0}=0$ and $K_{0}={\rm Ker}L_{\gamma}$, and different cosets maps
to different elements under $L_{\gamma}$, i.e.,
$L_{\gamma}(\theta_{i}+x)=L_{\gamma}(\theta_{i})$ for all $x\in{\rm
Ker}L_{\gamma}$. Recall that the linear kernel of ${\rm Tr}(\beta F)$

$\displaystyle\mathcal{LK}$ $\displaystyle=\mathcal{LK}_{{\rm Tr}(\beta F)}$
$\displaystyle=\\{\gamma\in{\mathbb{F}}_{p^{n}}:{\rm Tr}(\beta
F(x+\gamma)-bF(x))={\rm Tr}(\beta F(\gamma)-bF(0))\textrm{ for all
}x\in\mathbb{F}_{p^{n}}\\}$
$\displaystyle=\\{\gamma\in{\mathbb{F}}_{p^{n}}:{\rm Tr}(\beta
L_{\gamma}(x))=0\textrm{ for all
}x\in\mathbb{F}_{p^{n}}\\}=\\{\gamma\in\mathbb{F}_{p^{n}}:{\rm
Im}L_{\gamma}\subset\langle\beta\rangle^{\perp}\\}$ (6.3)

is a subspace of dimension (say) $k_{\beta}$ such that $|{\mathcal{W}}_{{\rm
Tr}(\beta F)}|=p^{\frac{n+k_{\beta}}{2}}$. Our assumption of

$|{\mathcal{W}}_{F}|=\max_{b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{{\rm
Tr}(bF)}|<p^{n}$

says that the dimension $k_{b}$ of linear kernel $\mathcal{LK}_{{\rm Tr}(bF)}$
strictly smaller than $n$, i.e., $k_{b}<n$ for all
$b\in\mathbb{F}_{p^{n}}^{\times}$. (When $p=2$, an equivalent assumption is
$\textup{{NL}}(F)\neq 0$ (or $\textup{{L}}(F)<2^{n}$).) Therefore we get

$\dim\mathcal{LK}=\dim\mathcal{LK}_{{\rm Tr}{(\beta F)}}=k_{\beta}\leq n-1,$

which implies

$|\mathcal{LK}|\leq
p^{n-1}\quad\textrm{i.e.,}\,\,|\mathbb{F}_{p^{n}}\setminus\mathcal{LK}|\geq
p^{n}-p^{n-1}.$

We claim that the number of $1\leq i\leq p^{n-s}-1$ such that
$K_{i}\subset{\mathcal{LK}}$ (i.e., the number of nonzero cosets $K_{i}$
contained in ${\mathcal{LK}}$) is at most $p^{n-s-1}$. If not, there are
$p^{n-s-1}+1$ different $K_{i}$ such that $K_{i}\subset{\mathcal{LK}}$. Since
all cosets are disjoint, one gets
$p^{n-1}+p^{s}=(p^{n-s-1}+1)p^{s}\leq|{\mathcal{LK}}|\leq p^{n-1}$ which is a
contradiction. Therefore, the number of $K_{i}(1\leq i\leq p^{n-s}-1)$ such
that $K_{i}\not\subset{\mathcal{LK}}$ is at least
$p^{n-s}-1-p^{n-s-1}=(p-1)p^{n-s-1}-1$. Pick any nonzero coset
$K_{i}\not\subset{\mathcal{LK}}$ and choose any $\gamma_{1}\in
K_{i}\setminus{\mathcal{LK}}$. Since there are $p-1$ cosets
$tK_{i}=t\theta_{i}+{\rm Ker}L_{\gamma}$ $(1\leq t\leq p-1)$ such that
$tK_{i}$ and $K_{i}$ are dependent over $\mathbb{F}_{p}$ and since
$p-1<(p-1)p^{2}-1\leq(p-1)p^{n-s-1}-1$, there exists $K_{j}(\neq tK_{i})$ such
that $K_{j}\not\subset{\mathcal{LK}}$. Now, choose any $\gamma_{2}\in
K_{j}\setminus{\mathcal{LK}}$. Then one has
$\gamma_{1},\gamma_{2}\not\in{\mathcal{LK}}$ and, via the isomorphism
$\mathbb{F}_{p^{n}}/{\rm Ker}L_{\gamma}\cong{\rm Im}L_{\gamma}$, one gets two
linearly independent vectors $L_{\gamma}(\gamma_{1}),L_{\gamma}(\gamma_{2})$
over $\mathbb{F}_{p}$. Since
$\gamma_{1},\gamma_{2}\not\in{\mathcal{LK}}={\mathcal{LK}}_{{\rm Tr}(\beta
F)}$, in view of the definition of ${\mathcal{LK}}$ in (6.3), there exist
$x_{1},x_{2}\in\mathbb{F}_{p^{n}}^{\times}$ such that

$\displaystyle{\rm Tr}(\beta
L_{\gamma_{1}}(x_{1}))=1\quad\textrm{and}\quad{\rm Tr}(\beta
L_{\gamma_{2}}(x_{2}))=1.$ (6.4)

So far, $\gamma_{1}$ and $\gamma_{2}$ are determined and we will choose
$\gamma_{3}$ to make $D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)$
nonvanishing. From Equation (6.1), we see that
$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)$ is a
$\mathbb{F}_{p}$-linear combination of three vectors
$L_{\gamma}(\gamma_{j})\,\,(1\leq j\leq 3)$, where $L_{\gamma}(\gamma_{1})$
and $L_{\gamma}(\gamma_{2})$ are linearly independent over $\mathbb{F}_{p}$.
If ${\rm Tr}(\beta L_{\gamma_{1}}(\gamma_{2}))=0$, then from Equation (6.4),
choose $\gamma_{3}$ satisfying ${\rm Tr}(\beta L_{\gamma_{2}}(\gamma_{3}))=1$.
Then one has

$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)=L_{\gamma}(\gamma_{1})+{\rm
Tr}(\beta L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})$

which is nonzero. If ${\rm Tr}(\beta L_{\gamma_{1}}(\gamma_{2}))\neq 0$, since
$\dim{\rm Im}L_{\gamma}=n-s\geq 3$, one can choose
$\gamma_{3}\in\mathbb{F}_{p^{n}}$ such that $L_{\gamma}(\gamma_{3})$ is not
spanned by $\\{L_{\gamma}(\gamma_{1}),L_{\gamma}(\gamma_{2})\\}$. Then

$D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}F_{3}(x)={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3}))L_{\gamma}(\gamma_{1})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{2}))L_{\gamma}(\gamma_{3})$

is a nonzero vector of $\mathbb{F}_{p^{n}}$.

###### Remark 6.3

Please be aware that if any of the two conditions $|{\mathcal{W}}_{F}|<p^{n}$
and $\Delta_{F}\leq p^{n-3}$ is not satisfied, then there are some functions
$F$ such that $d^{\circ}(\varepsilon D_{\gamma}F)<3$. Let us give such
examples for a binary case. Let $F(x)=x{\rm Tr}(x)$ be a quadratic
$(n,n)$-function on $\mathbb{F}_{2^{n}}$. It is clear that
$\textup{{NL}}(F)=0$ since ${\rm Tr}(F(x))={\rm Tr}(x)$. Let $\gamma=1=\beta$
and $\alpha=0$. Then, since $d^{\circ}({\rm Tr}(F))=1$, one gets
$d^{\circ}\left({\rm Tr}(F(x))D_{1}F(x)\right)<3$. Also, for the same
$F(x)=x{\rm Tr}(x)$, by choosing $\gamma\in\mathbb{F}_{2^{n}}^{\times}$ and
$\beta\in\mathbb{F}_{2^{n}}\setminus{\mathbb{F}}_{2}$ satisfying ${\rm
Tr}(\gamma)=0$ and ${\rm Tr}(\beta\gamma)=0$, one gets ${\rm Tr}(\beta
D_{\gamma}F(x))=0$ for all $x\in\mathbb{F}_{2^{n}}$ where ${\rm Tr}(\beta
F(x))={\rm Tr}(x){\rm Tr}(\beta x)$ and $D_{\gamma}F(x)=\gamma{\rm Tr}(x)$.
Therefore one has $d^{\circ}\left({\rm Tr}(\beta F)D_{\gamma}F\right)=2$ even
if $d^{\circ}({\rm Tr}(\beta F))=2$ and $d^{\circ}(D_{\gamma}F)=1$. For
another example, let $F(x)=x^{5}=x^{2^{2}+1}\in{\mathbb{F}}_{2^{4}}[x]$ be a
Gold function on ${\mathbb{F}}_{2^{4}}$. Note that $\Delta_{F}=4>2=2^{n-3}$.
Then one has ${\rm Tr}(F(x))=x^{5}+x^{10}+x^{5}+x^{10}=0$ for all $x$, which
implies that $d^{\circ}\left({\rm Tr}(F(x))D_{\gamma}F(x)\right)=0$ for any
$\gamma$. For another extreme case, let
$F(x)=x^{2^{i}+1}+x^{2^{j}+1}+x^{2^{i}+2^{j}}$ (with $i\neq j$) be a quadratic
$(n,n)$-function on $\mathbb{F}_{2^{n}}$. It is clear that $\Delta_{F}=2^{n}$
since $D_{1}F(x)=x^{2^{i}}+x+1+x^{2^{j}}+x+1+x^{2^{i}}+x^{2^{j}}+1=1$.
Therefore one has $d^{\circ}\left({\rm Tr}(\beta F)D_{1}F\right)<3$ for any
$\beta$.

###### Lemma 6.4

Let $p$ be an odd prime and let $F(x)\in\mathbb{F}_{p^{n}}[x]$ be a quadratic
$(n,n)$-function. Let $F_{4}(x)={\rm Tr}(\beta F(x))^{2}$. Then in a similar
manner as in the proof of Lemma 6.1, for any
$\gamma,\gamma_{1},\gamma_{2},\gamma_{3}\in\mathbb{F}_{p^{n}}$, one has

$\displaystyle\textstyle\frac{1}{2}D_{\gamma_{3}}D_{\gamma_{2}}$
$\displaystyle D_{\gamma_{1}}D_{\gamma}F_{4}(x)$ $\displaystyle={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3})){\rm Tr}(\beta L_{\gamma}(\gamma_{1}))+{\rm
Tr}(\beta L_{\gamma_{1}}(\gamma_{3})){\rm Tr}(\beta
L_{\gamma}(\gamma_{2}))+{\rm Tr}(\beta L_{\gamma_{1}}(\gamma_{2})){\rm
Tr}(\beta L_{\gamma}(\gamma_{3})).$

Proof. One has

$\displaystyle D_{\gamma}F_{4}(x)$ $\displaystyle={\rm Tr}(\beta
F(x+\gamma))^{2}-{\rm Tr}(\beta F(x))^{2}$ $\displaystyle=\\{{\rm Tr}(\beta
F(x+\gamma))-{\rm Tr}(\beta F(x))+2{\rm Tr}(\beta F(x))\\}\\{{\rm Tr}(\beta
F(x+\gamma))-{\rm Tr}(\beta F(x))\\}$ $\displaystyle=\\{{\rm Tr}(\beta
D_{\gamma}F(x))+2{\rm Tr}(\beta F(x))\\}{\rm Tr}(\beta D_{\gamma}F(x)).$

Since $d^{\circ}\\{{\rm Tr}(\beta D_{\gamma}F)^{2}\\}\leq 2$ and since $p\neq
2$, one has

$\displaystyle\textstyle\frac{1}{2}D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}D_{\gamma}F_{4}(x)=D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}\\{{\rm
Tr}(\beta F(x)){\rm Tr}(\beta D_{\gamma}F(x))\\}.$ (6.5)

From Lemma 6.1,

$\displaystyle D_{\gamma_{3}}$ $\displaystyle
D_{\gamma_{2}}D_{\gamma_{1}}\\{{\rm Tr}(\beta F(x))D_{\gamma}F(x)\\}$
$\displaystyle={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3}))L_{\gamma}(\gamma_{1})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{3}))L_{\gamma}(\gamma_{2})+{\rm Tr}(\beta
L_{\gamma_{1}}(\gamma_{2}))L_{\gamma}(\gamma_{3}).$

Multiply $\beta$ to both sides of the above equation and take the trace, then
since the trace map commutes with differentials,

$\displaystyle D_{\gamma_{3}}$ $\displaystyle
D_{\gamma_{2}}D_{\gamma_{1}}\\{{\rm Tr}(\beta F(x)){\rm Tr}(\beta
D_{\gamma}F(x))\\}$ (6.6) $\displaystyle={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3})){\rm Tr}(\beta L_{\gamma}(\gamma_{1}))+{\rm
Tr}(\beta L_{\gamma_{1}}(\gamma_{3})){\rm Tr}(\beta
L_{\gamma}(\gamma_{2}))+{\rm Tr}(\beta L_{\gamma_{1}}(\gamma_{2})){\rm
Tr}(\beta L_{\gamma}(\gamma_{3})).$

Combining Equations (6.5) and (6.6), we get the desired result.

###### Proposition 6.5

Let $p$ be an odd prime and let $F$ be a quadratic $(n,n)$-function with
$n\geq 4$. Suppose that

$|{\mathcal{W}}_{F}|\overset{\text{\rm
def}}{=}\max_{b\in\mathbb{F}_{p^{n}}^{\times}}|{\mathcal{W}}_{{\rm
Tr}(bF)}|\leq p^{n-1}.$

Let $\varepsilon={\rm Tr}(\alpha x+\beta F(x))$ with
$\alpha\in\mathbb{F}_{p^{n}}$ and $\beta\in\mathbb{F}_{p^{n}}^{\times}$. Then,
one has $d^{\circ}(\varepsilon^{2})=4$.

Proof. In a similar manner as in Proposition 6.2, it is enough to show
$d^{\circ}(F_{4})=4$ where $F_{4}(x)={\rm Tr}(\beta F(x))^{2}$. Let
$\tau=\frac{1}{2}D_{\gamma_{3}}D_{\gamma_{2}}D_{\gamma_{1}}D_{\gamma}F_{4}(x)$.
If $d^{\circ}(F_{4})\leq 3$, then one has $\tau=0$ for all
$\gamma,\gamma_{1},\gamma_{2}$ and $\gamma_{3}$ in $\mathbb{F}_{p^{n}}$.
However, we will show that $\tau\neq 0$ for some suitably chosen
$\gamma,\gamma_{1},\gamma_{2},\gamma_{3}$. Letting $\gamma_{1}=\gamma$ and
$\gamma_{3}=\gamma_{2}$,

$\displaystyle\tau$ $\displaystyle={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{3})){\rm Tr}(\beta L_{\gamma}(\gamma_{1}))+{\rm
Tr}(\beta L_{\gamma_{1}}(\gamma_{3})){\rm Tr}(\beta
L_{\gamma}(\gamma_{2}))+{\rm Tr}(\beta L_{\gamma_{1}}(\gamma_{2})){\rm
Tr}(\beta L_{\gamma}(\gamma_{3}))$ $\displaystyle={\rm Tr}(\beta
L_{\gamma_{2}}(\gamma_{2})){\rm Tr}(\beta L_{\gamma}(\gamma))+2{\rm Tr}(\beta
L_{\gamma}(\gamma_{2}))^{2}.$ (6.7)

Letting $\dim{\mathcal{LK}}_{{\rm Tr}(\beta F)}=k_{\beta}$
($\dim{\mathcal{LK}}_{{\rm Tr}(\beta F)}$ is the dimension of the linear
kernel of ${\rm Tr}(\beta F)$, one has
$p^{n+{k_{\beta}}}\leq|{\mathcal{W}}_{F}|^{2}\leq p^{2n-2}$, where the first
$\leq$ comes from Proposition 4.1 and the second $\leq$ comes from the
assumption. Therefore $k_{\beta}\leq n-2$, or equivalently,
$|{\mathcal{LK}}_{{\rm Tr}(\beta F)}|=p^{k_{\beta}}\leq p^{n-2}$. Now,
choosing any $\gamma\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm
Tr}(\beta F)}$, ${\rm Tr}(\beta L_{\gamma}(x))$ is a balanced (linear)
function on $\mathbb{F}_{p^{n}}$, i.e., ${\rm Tr}(\beta L_{\gamma}(x))$ takes
$j\in\mathbb{F}_{p}$ exactly $p^{n-1}$ times for every $0\leq j<p$. Also, for
all $\gamma^{\prime}\in{\mathcal{LK}}_{{\rm Tr}(\beta F)}$, one has ${\rm
Tr}(\beta L_{\gamma}(\gamma^{\prime}))={\rm Tr}(\beta
L_{\gamma^{\prime}}(\gamma))=0$. Since all elements $\gamma^{\prime}$ of
${\mathcal{LK}}_{{\rm Tr}(\beta F)}$ satisfies ${\rm Tr}(\beta
L_{\gamma}(\gamma^{\prime}))=0$ with $|{\mathcal{LK}}_{{\rm Tr}(\beta F)}|\leq
p^{n-2}$, and since ${\rm Tr}(\beta L_{\gamma}(x))$ is a balanced function
$(\because\gamma\notin{\mathcal{LK}}_{{\rm Tr}(\beta F)})$, ${\rm Tr}(\beta
L_{\gamma}(x))=0$ is satisfied for at least $p^{n-2}$ values of
$x\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$, and ${\rm
Tr}(\beta L_{\gamma}(x))=j$ is satisfied for exactly $p^{n-1}$ values of
$x\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$ for every
$1\leq j\leq p-1$. Now, from Equation (6.7), we consider two cases: If ${\rm
Tr}(\beta L_{\gamma}(\gamma))=0$ for some
$\gamma\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$, then
choose $\gamma_{2}\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta
F)}$ satisfying ${\rm Tr}(\beta L_{\gamma}(\gamma_{2}))=1$ (there are exactly
$p^{n-1}$ such $\gamma_{2}$ in
$\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$). Then one has
$\tau=2{\rm Tr}(\beta L_{\gamma}(\gamma_{2}))^{2}=2\neq 0$. If ${\rm Tr}(\beta
L_{\gamma}(\gamma))\neq 0$ for all
$\gamma\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$, then
choose $\gamma_{2}\in\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta
F)}$ satisfying ${\rm Tr}(\beta L_{\gamma}(\gamma_{2}))=0$ (there are at least
$p^{n-2}$ such $\gamma_{2}$ in
$\mathbb{F}_{p^{n}}\setminus{\mathcal{LK}}_{{\rm Tr}(\beta F)}$). Then one has
$\tau={\rm Tr}(\beta L_{\gamma_{2}}(\gamma_{2})){\rm Tr}(\beta
L_{\gamma}(\gamma))\neq 0$.

It also turns out that our constructed function $F\circ H$ is EA-inequivalent
to any power function. To prove that, we recall Proposition $4$ in [13].

###### Proposition 6.6

Let $F$ be an $(n,n)$-function on $\mathbb{F}_{p^{n}}$. If there exists
$c\in\mathbb{F}_{p^{n}}^{\times}$ such that $d^{\circ}({\rm
Tr}(cF))\not\in\\{0,1,d^{\circ}(F)\\}$, then $F$ is EA-inequivalent to any
power function.

Proof. The case for $p=2$ is proven in [13]. The case for arbitrary
characteristic is exactly the same as in [13].

###### Theorem 6.7

(Main Theorem) Let $F_{0}(x)$ be a quadratic $(n,n)$-function on
$\mathbb{F}_{p^{n}}$ with $n\geq 4$. Then, one concludes the followings.

  1. 1.

When $p=2$: Suppose that $|{\mathcal{W}}_{F_{0}}|<2^{n}$ (i.e.,
$\textup{{NL}}(F_{0})\neq 0$) and $\Delta_{F_{0}}\leq 2^{n-3}$. Then for any
$\gamma\in\mathbb{F}_{2^{n}}^{\times}$, one can choose
$\beta\in\mathbb{F}_{2^{n}}^{\times}$ such that ${\rm Tr}(\beta
D_{\gamma}F(x))=0$ for all $x\in\mathbb{F}_{2^{n}}$, where $F(x)=F_{0}(x)+cx$
and $c\in\mathbb{F}_{2^{n}}$ is determined by the condition ${\rm
Tr}(c\beta\gamma)={\rm Tr}(\beta(F_{0}(\gamma)+F_{0}(0)))$. Choosing
$\alpha\in\mathbb{F}_{2^{n}}$ satisfying ${\rm Tr}(\alpha\gamma)=0$, the
function

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)\quad(\,\,\text{with
}\varepsilon={\rm Tr}(\alpha x+\beta F(x))\,\,)$

has an algebraic degree $3$ and satisfies $F\circ H\overset{\textrm{\tiny
CCZ}}{\sim}F_{0}$ and $F\circ H\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$.
Moreover $F\circ H$ is EA-inequivalent to any power function.

  2. 2.

When $p>2$: Suppose that $|{\mathcal{W}}_{F_{0}}|\leq p^{n-1}$ and
$1<\Delta_{F_{0}}\leq p^{n-3}$. Then there exist
$\gamma,\beta\in\mathbb{F}_{p^{n}}^{\times}$ such that ${\rm Tr}(\beta
D_{\gamma}F(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$, where $F(x)=F_{0}(x)+cx$
and $c\in\mathbb{F}_{p^{n}}$ is determined by the condition ${\rm
Tr}(c\beta\gamma)=-{\rm Tr}(\beta(F_{0}(\gamma)-F_{0}(0)))$. Choosing
$\alpha\in\mathbb{F}_{p^{n}}$ satisfying ${\rm Tr}(\alpha\gamma)=-2$, the
function

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)\quad(\,\,\text{with
}\varepsilon={\rm Tr}(\alpha x+\beta F(x))\,\,)$

satisfies $F\circ H\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ and $F\circ
H\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$, where $d^{\circ}(F\circ H)=3$ if
$F_{\text{\tiny DO}}(\gamma)=0$, and $d^{\circ}(F\circ H)=4$ if
$F_{\text{\tiny DO}}(\gamma)\neq 0$. Furthermore, when $F_{\text{\tiny
DO}}(\gamma)=0$, then $F\circ H$ is EA-inequivalent to any power function.
Also, when $F_{\text{\tiny DO}}(\gamma)\neq 0$, by assuming that $F_{0}$ is a
DO-polynomial (one can always assume this up to EA-equivalence), $F\circ H$ is
EA-inequivalent to any power function if ${\rm Tr}(c\beta\gamma)=0$.

Proof. Existence of such $\gamma,\beta\in\mathbb{F}_{p^{n}}^{\times}$ is
guaranteed by Proposition 3.11. Existence of $\alpha,c\in\mathbb{F}_{p^{n}}$
is guaranteed by Proposition 5.2. CCZ-equivalence of constructed $F\circ H$ is
provided by Theorem 5.3. Explicit expressions of $F\circ H$ for each
characteristic are provided by Proposition 5.6. EA-inequivalence (or
$d^{\circ}(F\circ H)>2$) is guaranteed by Propositions 6.2 and 6.5. Therefore
one only needs to prove the last part of each assertion.

(1.) Since $\textup{{NL}}(F)\neq 0$ and $\beta\neq 0$, one has $d^{\circ}({\rm
Tr}(\beta F))=2$. Also from

${\rm Tr}(\beta[F\circ H(x)])={\rm Tr}(\beta F(x))+\varepsilon{\rm Tr}(\beta
D_{\gamma}F(x))={\rm Tr}(\beta F(x)),$

one gets $d^{\circ}({\rm Tr}(\beta[F\circ H]))=d^{\circ}({\rm Tr}(\beta
F))=2$. Therefore using Proposition 6.6, one concludes that $F\circ
H\overset{\textrm{\tiny EA}}{\not\sim}x^{s}$ for any $s\in{\mathbb{Z}}$.

(2.) The proof of the case $F_{\text{\tiny DO}}(\gamma)=0$ is exactly same to
the assertion 1. If $F_{\text{\tiny DO}}(\gamma)\neq 0$, then since $F_{0}$ is
a DO-polynomial, one has $F_{0}(x)=F_{\text{\tiny DO}}(x)$. Therefore using

$0={\rm Tr}(c\beta\gamma)=-{\rm Tr}(\beta(F_{0}(\gamma)-F_{0}(0)))=-{\rm
Tr}(\beta F_{0}(\gamma))=-{\rm Tr}(\beta F_{\text{\tiny DO}}(\gamma)),$

one gets

$\displaystyle{\rm Tr}(\beta[F\circ H(x)])={\rm Tr}(\beta
F(x))+\varepsilon{\rm Tr}(\beta
D_{\gamma}F(x))+(\varepsilon^{2}-\varepsilon){\rm Tr}(\beta F_{\text{\tiny
DO}}(\gamma))={\rm Tr}(\beta F(x)).$

And the rest is similar to the assertion 1.

###### Corollary 6.8

Let $n$ be even and let $F(x)$ be a quadratic APN function from
$\mathbb{F}_{2^{n}}$ to itself. Then one has
$\mathscr{C}_{\textrm{EA}}(F)\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F)$, i.e.,
there exists
$F^{\prime}\in\mathscr{C}_{\textrm{CCZ}}(F)\setminus\mathscr{C}_{\textrm{EA}}(F)$.

Proof. Since there is no quadratic APN permutation for even $n$ (See [42].),
$F^{\prime}=F\circ H$ is non-obvious function which is CCZ-equivalent but EA-
inequivalent to $F$.

##  7 Concrete Examples

###  7.1 Gold Functions for $p=2$

For a binary case, Budaghyan et al. [13] constructed examples of
$(n,n)$-function $F^{\prime}$ such that

$G\overset{\textrm{\tiny EA}}{\not\sim}F^{\prime}\quad\text{ but }\quad
G\overset{\textrm{\tiny CCZ}}{\sim}F^{\prime}$

where $G(x)=x^{2^{i}+1}$ (with $\gcd(i,n)=1$ and $n\geq 4$) is the Gold
function. Such $G$ is an AB(almost bent) function for odd $n$, and is an APN
function for even $n$. We summarize, in Table 2, $F^{\prime}(x)$ and the
corresponding linear permutation ${\mathscr{L}}$ on
$\mathbb{F}_{2^{n}}\times\mathbb{F}_{2^{n}}$ (for CCZ-equivalence) used in
[13].

Table 1: $F^{\prime}(x)$ and ${\mathscr{L}}$ used in [13] $n$ | $F^{\prime}(x)$ | ${\mathscr{L}}(x,y)$ | $d^{\circ}(F^{\prime})$
---|---|---|---
odd | $x^{2^{i}+1}+(x^{2^{i}}+x){\rm Tr}(x^{2^{i}+1}+x)$ | $(x+{\rm Tr}(x+y),y+{\rm Tr}(x+y))$ | $3$
even | $x^{2^{i}+1}+(x^{2^{i}}+x+1){\rm Tr}(x^{2^{i}+1})$ | $(x+{\rm Tr}(y),y)$ | $3$
Table 2: Our Rediscovery $n$ | $F\circ H$ | $\alpha$ | $\beta$ | $\gamma$ | $c$
---|---|---|---|---|---
odd | $x^{2^{i}+1}+x+(x^{2^{i}}+x){\rm Tr}(x^{2^{i}+1}+x)$ | $0$ | $1$ | $1$ | $1$
even | $x^{2^{i}+1}+(x^{2^{i}}+x+1){\rm Tr}(x^{2^{i}+1})$ | $0$ | $1$ | $1$ | $0$
even | $x^{2^{i}+1}+x+(x^{2^{i}}+x){\rm Tr}(x^{2^{i}+1}+x)$ | $0$ | $1$ | $1$ | $1$

Using our methods in Section 5 and 6, we can reproduce the above result in a
unified way. Recall that, for a given function $F_{0}(x)=G(x)=x^{2^{i}+1}$, we
constructed

$F(x)=F_{0}(x)+cx,\quad{\mathscr{L}}(x,y)=(x+\gamma{\rm Tr}(\alpha x+\beta
y),y),\quad H(x)=x+\gamma{\rm Tr}(\alpha x+\beta F(x))$

satisfying

$\displaystyle{\rm Tr}(\alpha\gamma)$ $\displaystyle=-2=0,$ $\displaystyle{\rm
Tr}(c\beta\gamma)$ $\displaystyle={\rm Tr}(\beta D_{\gamma}F_{0}(0))={\rm
Tr}(\beta D_{\gamma}F_{0}(x))\quad\text{ for all }x\in\mathbb{F}_{2^{n}},$

where the second condition guarantees that $\gamma$ is a $0$-linear structure
of ${\rm Tr}(\beta F(x))$ (See Proposition 5.2). Under these conditions, we
proved that $F_{0}\overset{\textrm{\tiny CCZ}}{\sim}F\circ H$. For simplicity,
one may first choose $\alpha=0$. Also, choosing $\gamma=1=\beta$, one has
${\rm Tr}(\beta D_{\gamma}F_{0}(x))={\rm Tr}((x+1)^{2^{i}+1}+x^{2^{i}+1})={\rm
Tr}(x^{2^{i}}+x+1)={\rm Tr}(1)=n$ for all $x\in\mathbb{F}_{2^{n}}$. Therefore
it is enough to choose $c$ satisfying ${\rm Tr}(c)={\rm
Tr}(c\beta\gamma)=n={\rm Tr}(1)$. When $n$ is odd, then one may choose $c=1$
so that ${\rm Tr}(c)=1$. In this case, one has

$F(x)=x^{2^{i}+1}+x,\quad H(x)=x+\gamma{\rm Tr}(\alpha x+\beta F(x))=x+{\rm
Tr}(x^{2^{i}+1}+x)=x+\varepsilon$

and

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)=x^{2^{i}+1}+x+{\rm
Tr}(x^{2^{i}+1}+x)(x^{2^{i}}+x),$

which is EA-equivalent to $F^{\prime}(x)$ in [13]. On the other hand, when $n$
is even, one may choose either $c=0$ or $c=1$ since ${\rm Tr}(c)=0={\rm
Tr}(1)$ is satisfied in either case. Therefore, if $c=0$, one gets

$F(x)=x^{2^{i}+1},\quad H(x)=x+\gamma{\rm Tr}(\alpha x+\beta F(x))=x+{\rm
Tr}(x^{2^{i}+1})=x+\varepsilon$

and

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)=x^{2^{i}+1}+{\rm
Tr}(x^{2^{i}+1})(x^{2^{i}}+x+1),$

which is same to $F^{\prime}(x)$ in [13]. Also if $c=1$, then one has

$F(x)=x^{2^{i}+1}+x,\quad H(x)=x+\gamma{\rm Tr}(\alpha x+\beta F(x))=x+{\rm
Tr}(x^{2^{i}+1}+x)=x+\varepsilon$

and

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)=x^{2^{i}+1}+x+{\rm
Tr}(x^{2^{i}+1}+x)(x^{2^{i}}+x),$

which is CCZ-equivalent to $x^{2^{i}+1}$. In other words, one concludes that

###### Remark 7.1

Independent of the parity of $n$, one has

$\displaystyle x^{2^{i}+1}\overset{\textrm{\tiny
EA}}{\not\sim}x^{2^{i}+1}+(x^{2^{i}}+x){\rm
Tr}(x^{2^{i}+1}+x)\overset{\textrm{\tiny CCZ}}{\sim}x^{2^{i}+1}.$

###  7.2 Other APN functions on $\mathbb{F}_{2^{n}}$

One may also apply our main theorem to all quadratic APN functions found so
far. For example, in page $407$ of the book of Carlet [21], there is a table
which lists CCZ-inequivalent quadratic functions. We rewrite the list in our
Table 3 with our choice of $\alpha,\beta,\gamma$ and $c$.

Table 3: Known classes of quadratic APN functions CCZ inequivalent to power
functions on $\mathbb{F}_{2^{n}}$, and $\ell(x)$ satisfying $\ell(\beta)=0$

$F_{0}(x)$ |  Conditions on $F_{0}$ | $\ell(x)$ | $\begin{array}[]{l}\text{APN}\\\ \text{proven}\end{array}$
---|---|---|---
$\begin{array}[]{l}x^{2^{s}+1}+g^{2^{k}-1}x^{2^{ik}+2^{tk+s}}\end{array}$ | $\begin{array}[]{l}n=pk,\operatorname{gcd}(k,p)=\operatorname{gcd}(s,pk)=1,\\\ p\in\\{3,4\\},i=sk\bmod p,t=p-i,\\\ n\geq 12,g\text{ primitive in }\mathbb{F}_{2^{n}}^{\times}\end{array}$ | $\begin{array}[]{l}x^{2^{n-s}}+x+\\\ (\omega x)^{2^{tk}}+(\omega x)^{2^{ik-s}}\end{array}$ | [10]
$\begin{array}[]{l}ax^{2^{i}(q+1)}+x^{2^{i}+1}+\\\ x^{q\left(2^{i}+1\right)}+x^{q+1}+\\\ vx^{2^{i}q+1}+v^{q}x^{2^{i}+q}\end{array}$ | $\begin{array}[]{l}q=2^{m},n=2m,\operatorname{gcd}(i,m)=1,\\\ v\in\mathbb{F}_{2^{n}},a\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{q},\\\ X^{2^{i}+1}+vX^{2^{i}}+v^{q}X+1\\\ \text{has no zero in }\mathbb{F}_{2^{n}}\text{ s.t. }x^{q+1}=1\end{array}$ | $\begin{array}[]{l}\left[(a+v^{2^{m}}+1)x\right]^{2^{2m-i}}+\\\ \left[(a+v+1)x\right]^{2^{m-i}}+\\\ vx^{2^{m}}+vx\end{array}$ | [7]
$\begin{array}[]{l}x^{3}+a^{-1}{\rm Tr}\left(a^{3}x^{9}\right)\end{array}$ | $\begin{array}[]{l}a\neq 0\end{array}$ | $\begin{array}[]{l}x^{2^{n-1}}+x+\tilde{a}{\rm Tr}(\frac{x}{a})\\\ \end{array}$ | [11]
$\begin{array}[]{l}x^{3}+a^{-1}{\rm Tr}_{3}^{n}\left(a^{3}x^{9}+a^{6}x^{18}\right)\end{array}$ | $\begin{array}[]{l}3\mid n,a\neq 0\end{array}$ | $\begin{array}[]{l}x^{2^{n-1}}+x+\tilde{a}{\rm Tr}^{n}_{3}\left(\frac{x}{a}+\left(\frac{x}{a}\right)^{4}\right)\\\ \end{array}$ | [12]
$\begin{array}[]{l}x^{3}+a^{-1}{\rm Tr}_{3}^{n}\left(a^{6}x^{18}+a^{12}x^{36}\right)\end{array}$ | $\begin{array}[]{l}3\mid n,a\neq 0\end{array}$ | $\begin{array}[]{l}x^{2^{n-1}}+x+\tilde{a}{\rm Tr}^{n}_{3}\left(\left(\frac{x}{a}\right)^{2}+\left(\frac{x}{a}\right)^{4}\right)\\\ \end{array}$ | [12]
$\begin{array}[]{l}gx^{2^{s}+1}+g^{2^{k}}x^{2^{2k}+2^{k+s}}+\\\ vx^{2^{2k}+1}+wg^{2^{k}+1}x^{2^{s}+2^{k+s}}\end{array}$ | $\begin{array}[]{l}n=3k,\operatorname{gcd}(k,3)=\operatorname{gcd}(s,3k)=1,\\\ v,w\in\mathbb{F}_{2^{k}},vw\neq 1,\\\ 3\mid(k+s),g\text{ primitive in }\mathbb{F}_{2^{n}}^{\times}\end{array}$ | $\begin{array}[]{l}\left[(g+wg^{2^{k}+1})x\right]^{2^{3k-s}}+\\\ \left[(g^{2^{k}}+wg^{2^{k}+1})x\right]^{2^{2k-s}}+\\\ \left[(g^{2^{k}}+v)x\right]^{2^{k}}+(g+v)x\end{array}$ | [4]
$\begin{array}[]{l}\left(x+x^{2^{m}}\right)^{2^{k}+1}+\\\ v\left(gx+g^{2^{m}}x^{2^{m}}\right)^{(2^{k}+1)2^{i}}+\\\ g\left(x+x^{2^{m}}\right)\left(gx+g^{2^{m}}x^{2^{m}}\right)\end{array}$ | $\begin{array}[]{l}n=2m,m\geq 2\text{ even, }\\\ \operatorname{gcd}(k,m)=1\text{ and }i\geq 2\text{ even }\\\ g\text{ primitive in }\mathbb{F}_{2^{n}}^{\times},v\in\mathbb{F}_{2^{m}}\text{ not cube}\end{array}$ | $\begin{array}[]{l}g\tilde{g}^{2^{m-k}}\left[(vx)^{2^{m}}+vx\right]^{2^{m-k-i}}+\\\ g\tilde{g}^{2^{k}}\left[(vx)^{2^{m}}+vx\right]^{2^{m-i}}+\\\ \tilde{g}\left[(gx)^{2^{m}}+gx\right]\end{array}$ | [46]
$\begin{array}[]{l}a^{2}x^{2^{2m+1}+1}+v^{2}x^{2^{m+1}+1}+\\\ ax^{2^{2m}+2}+vx^{2^{m}+2}+\\\ \left(w^{2}+w\right)x^{3}\end{array}$ | $\begin{array}[]{l}n=3m,m\text{ odd; }U\text{ subgroup of}\\\ \mathbb{F}_{2^{n}}^{\times}\text{ of order }2^{2m}+2^{m}+1,\\\ L(x)=ax^{2^{2m}}+vx^{2^{m}}+wx\in\mathbb{F}_{2^{n}}[x],\\\ \text{ s.t. }\forall u_{1},u_{2}\in U,L(u_{1})\notin\\{0,u_{1}\\}\text{ and }\\\ u_{1}^{2}L(u_{2})+u_{2}L(u_{1})^{2}\neq 0\\\ \Rightarrow\frac{u_{2}^{2}L(u_{1})+u_{1}L(u_{2})^{2}}{u_{1}^{2}L(u_{2})+u_{2}L(u_{1})^{2}}\notin\mathbb{F}_{2^{m}}\\\ \end{array}$ | $\begin{array}[]{l}\left[\left(a+v+w^{2}+w\right)x\right]^{2^{3m-1}}+\\\ \left(vx\right)^{2^{2m}}+\left(v^{2}x\right)^{2^{2m-1}}+\\\ \left(ax\right)^{2^{m}}+\left(a^{2}x\right)^{2^{m-1}}+\\\ \left(a^{2}+v^{2}+w^{2}+w\right)x\end{array}$ | [5]
$\begin{array}[]{l}v\left(v^{q}x+vx^{q}\right)\left(x^{q}+x\right)+\\\ \left(v^{q}x+vx^{q}\right)^{2^{2i}+2^{3i}}+\\\ a\left(v^{q}x+vx^{q}\right)^{2^{2i}}\left(x^{q}+x\right)^{2^{i}}+\\\ w\left(x^{q}+x\right)^{2^{i}+1}\end{array}$ | $\begin{array}[]{l}q=2^{m},n=2m,\operatorname{gcd}(i,m)=1\\\ X^{2^{i}+1}+aX+w\\\ \text{ has no zero in }\mathbb{F}_{2^{m}}\end{array}$ | $\begin{array}[]{l}\tilde{v}^{2^{i}}\left[(ax)^{2^{m}}+ax\right]^{2^{m-i}}+\\\ v^{2^{m}}\tilde{v}^{2^{i}}\left[x^{2^{m}}+x\right]^{2^{m-2i}}+\\\ v^{2^{m}}\tilde{v}^{2^{m-i}}\left[x^{2^{m}}+x\right]^{2^{m-3i}}+\\\ \tilde{v}\left[(vx)^{2^{m}}+vx\right]\end{array}$ | [43]
$\begin{array}[]{l}x^{3}+\omega\left(x^{2^{i}+1}\right)^{2^{k}}+\\\ \omega^{2}x^{3\cdot 2^{m}}+\left(x^{2^{i+m}+2^{m}}\right)^{2^{k}}\end{array}$ | $\begin{array}[]{l}n=2m;m\text{ odd };3\nmid m\\\ i=m-2\text{ or }i\equiv(m-2)^{-1}\pmod{n}\\\ \omega\in\mathbb{F}_{4}\setminus\mathbb{F}_{2}\end{array}$ | $\begin{array}[]{l}x^{2^{2m-1}}+\omega^{2^{k}}x^{2^{2m-k}}+\\\ \omega^{2^{k+1}}x^{2^{2m-k-i}}+\omega x^{2^{m}}+\\\ \omega^{2}x^{2^{m-1}}+x^{2^{m-k}}+\\\ x^{2^{m-k-i}}+x\end{array}$ | [16]

$-$ $\beta\in\mathbb{F}_{2^{n}}$ is a unique nonzero root of $\ell(x)$.
$-$ $\tilde{a}=a^{3\cdot 2^{n-3}}+a^{3}$, $\tilde{g}=g^{2^{m}}+g$, and
$\tilde{v}=v^{q}+v$ in the third column.

Explanation of Table 3:

For all APN function $F_{0}(x)$ in the Table 3, we choose

$\displaystyle\alpha=0,\gamma=1\text{ and }c=F_{0}(1),$ (7.1)

and $\beta\in\mathbb{F}_{2^{n}}$ is a unique nonzero root of linearized
$\ell(x)$. Then the resulting function

$\displaystyle F\circ H(x)$ $\displaystyle=F(x)+{\rm Tr}(\beta F(x))D_{1}F(x)$
$\displaystyle=F_{0}(x)+cx+{\rm Tr}(\beta F(x))(F_{0}(x+1)+F_{0}(x)+c)$

is cubic and is CCZ-equivalent to $F_{0}(x)$. Here, $\ell(x)$ is determined as
follows: Since $\beta$ must satisfy ${\rm Tr}(\beta L_{1}(x))=0$ for all $x$
with $L_{1}(x)=F_{0}(x+1)+F_{0}(x)+F_{0}(1)+F_{0}(0)$, we write
$L_{1}(x)=\sum_{i=0}^{n-1}a_{i}x^{2^{i}}$. Then

$\displaystyle 0={\rm Tr}(\beta L_{1}(x))={\rm Tr}\left(\sum_{i=0}^{n-1}\beta
a_{i}x^{2^{i}}\right)={\rm Tr}\left(\left(\sum_{i=0}^{n-1}(\beta
a_{i})^{2^{n-i}}\right)x\right).$

Therefore, $\beta$ is a root of

$\displaystyle\ell(x)=\sum_{i=0}^{n-1}a_{n-i}^{2^{i}}x^{2^{i}}.$ (7.2)

The choices of $\alpha,\beta,\gamma$ and $c$ are not unique and there are many
alternative choices are possible. For example, other than Gold functions,
Budaghyan et al. [11] found CCZ-equivalent $F^{\prime}$ of algebraic degree
$3$ and $4$ for the quadratic $F_{0}(x)=x^{3}+a^{-1}{\rm Tr}(a^{3}x^{9})$ with
different parameters. Among the $10$ APN functions in Table 3,
$F_{0}(x)=x^{3}+a^{-1}{\rm Tr}(a^{3}x^{9})$ is the only (published) one where
the existence of (non-obvious) $F^{\prime}$ is known such that
$F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ and
$F^{\prime}\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$. Moreover, (quadratic)
APN permutation is very rare in the sense that there is no quadratic APN
permutation on even dimension [42], and for odd $n$, the only permutation in
Table 3 is the function in the first row with odd $n=3k$ and
$\gcd(k,3)=1=\gcd(s,3k)$. It is conjectured in [10] that the algebraic degree
of the inverse function is $\frac{3k+1}{2}$. Therefore, based on that
conjecture, it is very probable that our cubic $F\circ H$ is also EA-
inequivalent to the inverse function.

It should be mentioned that, though not listed in Table 3, there is a sporadic
case of (recently discovered) quadratic APN permutation on dimension $9$. That
is, Beierle and Leander [2] found the following two quadratic APN permutations
on ${\mathbb{F}}_{2^{9}}$:

$\displaystyle F_{0}(x)$
$\displaystyle=x^{3}+u^{2}x^{2^{3}+2}+ux^{2^{4}+2^{3}}+u^{4}x^{2^{6}+2^{4}}+u^{6}x^{2^{7}+2^{3}},$
(7.3) $\displaystyle F_{1}(x)$
$\displaystyle=x^{3}+ux^{2^{3}+2}+u^{2}x^{2^{4}+1}+u^{4}x^{2^{6}+2^{4}}+u^{5}x^{2^{7}+2^{6}},$
(7.4)

where $u\in{\mathbb{F}}_{2^{3}}$ with $u^{3}+u+1=0$. (See also [3].) It is
straightforward to check that the inverses of $F_{0}$ and $F_{1}$ both have
algebraic degree $5$. Therefore our $F\circ H$ are non-obvious functions which
are CCZ-equivalent but not EA-equivalent to the functions in Equations (7.3)
and (7.4). Let us explain how the ‘Explanation of Table 3’ can also be applied
to this sporadic case.

###### Example 7.2

Let

$F_{0}(x)=x^{3}+u^{2}x^{2^{3}+2}+ux^{2^{4}+2^{3}}+u^{4}x^{2^{6}+2^{4}}+u^{6}x^{2^{7}+2^{3}}\in{\mathbb{F}}_{2^{9}}[x]$

be a APN permutation in Equation (7.3). Let $\alpha=0,\gamma=1$ and
$c=F_{0}(1)=u^{2}$ similarly as in Table 3 (See Equation (7.1).). Then, one
gets

$\displaystyle L_{1}(x)$ $\displaystyle=F_{0}(x+1)+F_{0}(x)+F_{0}(1)+F_{0}(0)$
$\displaystyle=x^{2}+x+u^{2}(x^{2^{3}}+x^{2})+u(x^{2^{4}}+x^{2^{3}})+u^{4}(x^{2^{6}}+x^{2^{4}})+u^{6}(x^{2^{7}}+x^{2^{3}})$
$\displaystyle=x+u^{6}x^{2}+u^{3}x^{2^{3}}+u^{2}x^{2^{4}}+u^{4}x^{2^{6}}+u^{6}x^{2^{7}}.$

The corresponding $\ell(x)$ (see Equation (7.2)) is easily calculated as

$\ell(x)=u^{3}x^{2^{8}}+u^{3}x^{2^{6}}+ux^{2^{5}}+u^{4}x^{2^{3}}+u^{3}x^{2^{2}}+x,$

and $\beta=u^{5}=u^{2}+u+1$ is a unique nonzero root of $\ell(x)$. Therefore
one has

$\displaystyle F(x)=F_{0}(x)+u^{2}x,\,\,H(x)=x+\gamma{\rm Tr}(\alpha x+\beta
F(x))=x+{\rm Tr}(u^{5}F_{0}(x)+x),$

and

$\displaystyle F\circ H(x)$ $\displaystyle=F(x)+{\rm Tr}(\beta F(x))D_{1}F(x)$
$\displaystyle=F_{0}(x)+u^{2}x+\left(F_{0}(x+1)+F_{0}(x)+u^{2}\right){\rm
Tr}\left(u^{5}F_{0}(x)+x\right),$

where

$\displaystyle F\circ H\overset{\textrm{\tiny
CCZ}}{\sim}F_{0}\quad\text{and}\,\,F\circ H\overset{\textrm{\tiny
EA}}{\not\sim}F_{0}.$

The case for $F_{1}$ in Equation (7.4) can be dealt in the same manner.

We present another example from the Table 3, where one may use different
approach for determining $\alpha,\beta,\gamma$ and $c$.

###### Example 7.3

Let

$\displaystyle F_{0}(x)=x^{3}+a^{-1}{\rm
Tr}_{3}^{n}(a^{3}x^{9}+a^{6}x^{18})\quad\text{ with }\,3|n\text{ and
}a\in\mathbb{F}_{2^{n}}^{\times}.$

It is well-known [12] that $F_{0}$ is APN for all nonzero $a$. Though a
systematic approach is possible as is shown in Table 3, we provide an
alternative description on finding CCZ-equivalent $F\circ H$ for this case.
For this $F_{0}(x)$, letting $q=2^{3}$, one has

$\displaystyle L_{\gamma}(x)=x^{2}\gamma+x\gamma^{2}+a^{-1}J\quad\text{ with
}\,J={\rm
Tr}_{3}^{n}(a^{3}(x^{q}\gamma+x\gamma^{q})+a^{6}(x^{2q}\gamma^{2}+x^{2}\gamma^{2q}))\in{\mathbb{F}}_{2^{3}}.$
(7.5)

When ${\rm Tr}_{3}^{n}(a)=0$:

Let $\beta=a^{3},\gamma=a^{-1}$ and $c=a^{-2}$. Then, for all
$x\in\mathbb{F}_{2^{n}}$, one gets

$\displaystyle{\rm Tr}(\beta L_{\gamma}(x))$ $\displaystyle={\rm
Tr}(x^{2}\beta\gamma+x\beta\gamma^{2})+{\rm Tr}_{1}^{3}{\rm
Tr}_{3}^{n}(a^{2}J)$ $\displaystyle={\rm
Tr}(x^{2}\beta\gamma+x\beta\gamma^{2})+{\rm Tr}_{1}^{3}(J[{\rm
Tr}_{3}^{n}(a)]^{2})={\rm
Tr}(x^{2}\beta\gamma+x^{2}\beta^{2}\gamma^{4})\quad(\because{\rm
Tr}_{3}^{n}(a)=0)$ $\displaystyle={\rm
Tr}(\beta\gamma(1+\beta\gamma^{3})x^{2})=0.\quad\quad(\because\beta\gamma^{3}=1)$

Also, from

$\displaystyle{\rm Tr}(\beta(F_{0}(\gamma)+F_{0}(0)))$ $\displaystyle={\rm
Tr}(a^{3}\\{a^{-3}+a^{-1}{\rm
Tr}_{3}^{n}(a^{3}\gamma^{9}+a^{6}\gamma^{18})\\})$ $\displaystyle={\rm
Tr}(1)+{\rm Tr}_{1}^{3}{\rm Tr}_{3}^{n}\\{a^{2}{\rm
Tr}_{3}^{n}(a^{3}\gamma^{9}+a^{6}\gamma^{18})\\}={\rm
Tr}(1),\quad(\because{\rm Tr}_{3}^{n}(a)=0)$

one has

${\rm Tr}(c\beta\gamma)={\rm Tr}(1)={\rm Tr}(\beta(F_{0}(\gamma)+F_{0}(0))).$

When ${\rm Tr}_{3}^{n}(a)\neq 0$: In this case, let $\omega={\rm
Tr}_{3}^{n}(a)\in{\mathbb{F}}_{2^{3}}^{\times}$.

Let $\beta=\omega^{5}a^{3},\gamma=\omega^{3}a^{-1}$ and $c=\omega^{6}a^{-2}$.
Then, from Equation (7.5), one gets

$\displaystyle{\rm Tr}(\beta L_{\gamma}(x))$ $\displaystyle={\rm
Tr}(x^{2}\beta\gamma+x\beta\gamma^{2})+{\rm Tr}_{1}^{3}{\rm
Tr}_{3}^{n}(\omega^{5}a^{2}J)$ $\displaystyle={\rm
Tr}(x^{2}\beta\gamma+x\beta\gamma^{2})+{\rm Tr}_{1}^{3}(J\omega^{5}[{\rm
Tr}_{3}^{n}(a)]^{2})$ $\displaystyle={\rm
Tr}(x^{2}\beta\gamma+x^{2}\beta^{2}\gamma^{4})+{\rm
Tr}_{1}^{3}(J)\quad(\because{\rm Tr}_{3}^{n}(a)=\omega\text{ and
}\omega^{7}=1).$

Therefore, from Equation (7.5), writing $J={\rm Tr}_{3}^{n}(y+y^{2})$ with
$y=a^{3}(x^{q}\gamma+x\gamma^{q})$, one finally has

${\rm Tr}(\beta L_{\gamma}(x))={\rm
Tr}(\beta\gamma(1+\beta\gamma^{3})x^{2})+{\rm Tr}_{1}^{3}{\rm
Tr}_{3}^{n}(y+y^{2})=0.\quad(\because\beta\gamma^{3}=1\text{ and }{\rm
Tr}_{1}^{n}(y+y^{2})=0)$

Also, from

$\displaystyle{\rm Tr}(\beta(F_{0}(\gamma)+F_{0}(0)))$ $\displaystyle={\rm
Tr}(\omega^{5}a^{3}\\{\omega^{9}a^{-3}+a^{-1}{\rm
Tr}_{3}^{n}(a^{3}\gamma^{9}+a^{6}\gamma^{18})\\})$ $\displaystyle={\rm
Tr}(1)+{\rm Tr}_{1}^{3}{\rm Tr}_{3}^{n}\\{\omega^{5}a^{2}{\rm
Tr}_{3}^{n}(a^{3}\gamma^{9}+a^{6}\gamma^{18})\\}$ $\displaystyle={\rm
Tr}(1)+{\rm Tr}_{1}^{3}{\rm Tr}_{3}^{n}(a^{3}\gamma^{9}+a^{6}\gamma^{18})={\rm
Tr}(1),\quad(\because{\rm Tr}_{3}^{n}(a)=\omega\text{ and }\omega^{7}=1)$

one has

${\rm Tr}(c\beta\gamma)={\rm Tr}(1)={\rm Tr}(\beta(F_{0}(\gamma)+F_{0}(0))).$

As a consequence, assuming $a\neq 0$ and $3|n$, one gets

$\displaystyle x^{3}+a^{-1}{\rm
Tr}_{3}^{n}(a^{3}x^{9}+a^{6}x^{18})=F_{0}(x)\overset{\textrm{\tiny
CCZ}}{\sim}F\circ H(x)=F(x)+{\rm Tr}(\alpha x+\beta F(x))D_{\gamma}F(x),$

and $F_{0}\overset{\textrm{\tiny EA}}{\not\sim}F\circ H$, where
$F(x)=F_{0}(x)+cx$ and $\alpha,\beta,\gamma$ and $c$ are chosen as in Table 4.

Table 4: $\alpha,\beta,\gamma$ and $c$ satisfying $F\circ H\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ but $F\circ H\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$ | $\alpha$ | $\beta$ | $\gamma$ | $c$
---|---|---|---|---
When ${\rm Tr}_{3}^{n}(a)=0$ | $0$ | $a^{3}$ | $a^{-1}$ | $a^{-2}$
When ${\rm Tr}_{3}^{n}(a)=\omega\neq 0$ | $0$ | $\omega^{5}a^{3}$ | $\omega^{3}a^{-1}$ | $\omega^{6}a^{-2}$

###### Remark 7.4

The above choice of $\alpha,\beta,\gamma$ and $c$ is just one example of
parameter choices. For APN case as above, for any $\gamma\neq 0$, there exists
a unique $\beta\neq 0$ satisfying ${\rm Tr}(\beta L_{\gamma}(x))=0$ for all
$x$. Also, for each given choice of $(\gamma,\beta)$ pair, there are $2^{n-1}$
possible choices of $\alpha$ and $c$, respectively. For example, one may
choose any $\alpha\in\mathbb{F}_{2^{n}}$ satisfying ${\rm
Tr}(\alpha\gamma)=0$, and $\alpha=0$ or $\alpha=(\omega^{-1}+\omega^{-2})a$ is
just one of such choices.

###  7.3 Gold Functions for $p>2$

For Gold function $G(x)=x^{p^{i}+1}\in\mathbb{F}_{p^{n}}[x]$ with $p$ odd, the
following is well-known. (See for example [47, 1].)

  1. 1.

$G(x)$ is planar (i.e., PN) if and only if $\frac{n}{\gcd(i,n)}$ is odd.

  2. 2.

If $\frac{n}{\gcd(i,n)}$ is even, then $|{\rm Ker}L_{\gamma}|=p^{\gcd(i,n)}$
for every $\gamma\in\mathbb{F}_{p^{n}}^{\times}$, where
$L_{\gamma}(x)=G(x+\gamma)-G(x)-(G(\gamma)-G(0))=\gamma
x^{p^{i}}+\gamma^{p^{i}}x$. Consequently, one has $\Delta_{G}=p^{\gcd(i,n)}$.

###### Remark 7.5

It is proven in [14, 35] that for the case of planar function $F(x)$, one has
$\mathscr{C}_{\textrm{EA}}(F)=\mathscr{C}_{\textrm{CCZ}}(F)$, i.e., every
$F^{\prime}$ satisfying $F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F$ also
satisfies $F^{\prime}\overset{\textrm{\tiny EA}}{\sim}F$.

From the previous remark, we are only interested in the case of
$G(x)=x^{p^{i}+1}\in\mathbb{F}_{p^{n}}[x]$ with even $n$ such that
$\frac{n}{\gcd(i,n)}$ is also even.

###### Corollary 7.6

Let $n\geq 4$ and $G(x)=x^{p^{i}+1}\in\mathbb{F}_{p^{n}}[x]$ where
$\frac{n}{d}$ is even with $d=\gcd(i,n)$. Suppose that $i\neq\frac{n}{2}$.
Then the function in Theorem 6.7

$\displaystyle F\circ H(x)$ $\displaystyle=F(x)+\varepsilon
D_{\gamma}F(x)+F_{\text{\tiny DO}}(\gamma)(\varepsilon^{2}-\varepsilon)$
$\displaystyle=F(x)+\varepsilon
D_{\gamma}F(x)+\gamma^{p^{i}+1}(\varepsilon^{2}-\varepsilon)$
$\displaystyle(\text{with }$ $\displaystyle
F(x)=x^{p^{i}+1}+cx,\,\,\,\varepsilon={\rm Tr}(\alpha x+\beta
F(x)),\,\,\,H(x)=x+\gamma\varepsilon)$

is of algebraic degree $4$ and $F\circ H\overset{\textrm{\tiny
CCZ}}{\sim}F\overset{\textrm{\tiny EA}}{\sim}F_{0}=G$.

Proof. When $\frac{n}{d}$ is even with $d=\gcd(i,n)$, it is shown in [24, 25]
(See also [44].) that
$|{\mathcal{W}}_{G}(a,b)|\in\\{0,p^{\frac{n}{2}},p^{\frac{n}{2}+d}\\}$ for all
$a,b\in\mathbb{F}_{p^{n}}$, which implies that
$|{\mathcal{W}}_{G}|=p^{\frac{n}{2}+d}$. On the other hand, from Proposition
6.5, our function $F\circ H$ satisfying $F\circ H\overset{\textrm{\tiny
CCZ}}{\sim}F\overset{\textrm{\tiny EA}}{\sim}F_{0}=G$ has an algebraic degree
$4$ if $|{\mathcal{W}}_{G}|\leq p^{n-1}$. Therefore one has $F\circ
H\not\overset{\textrm{\tiny EA}}{\sim}G$ if $\frac{n}{2}+d\leq n-1$ (i.e., if
$d\leq\frac{n}{2}-1$). Since any proper divisor $d$ of $n$ must satisfy
$d\leq\frac{n}{2}$, it is guaranteed that one always have $d^{\circ}(F\circ
H)=4$ (i.e., $F\circ H\overset{\textrm{\tiny EA}}{\not\sim}G$) if
$i\neq\frac{n}{2}$ and $\frac{n}{d}=\text{even}$.

For explicit choices of $\alpha,\beta,\gamma$ and $c$, let us first choose
$\gamma=1$. Then, from Proposition 5.2, $\alpha$ is determined by the
condition ${\rm Tr}(\alpha\gamma)={\rm Tr}(\alpha)=-2$. Also, since
$L_{\gamma}(x)=x^{p^{i}}\gamma+\gamma^{p^{i}}x=x^{p^{i}}+x$, one gets

${\rm Tr}(\beta L_{\gamma}(x))={\rm Tr}(\beta(x^{p^{i}}+x))={\rm
Tr}((\beta^{p^{n-i}}+\beta)x)=0\quad\text{ for all }x\in\mathbb{F}_{p^{n}}$

if and only if $\beta^{p^{n-i}}=-\beta$, i.e., $\beta^{p^{n-i}-1}=-1$. Letting
$n=dn^{\prime}$ and $i=di^{\prime}$ with $d=\gcd(n,i)$, one has
$n^{\prime}=\text{even}$ and $i^{\prime}=\text{odd}$
$(\because\frac{n}{d}=\text{even})$. Since

$\beta^{p^{n-i}-1}=\left(\beta^{p^{d}-1}\right)^{\frac{(p^{d})^{n^{\prime}-i^{\prime}}-1}{p^{d}-1}}=\left(\beta^{p^{d}-1}\right)^{(p^{d})^{n^{\prime}-i^{\prime}-1}+(p^{d})^{n^{\prime}-i^{\prime}-2}+\cdots+(p^{d})+1},$

and since

$(p^{d})^{n^{\prime}-i^{\prime}-1}+(p^{d})^{n^{\prime}-i^{\prime}-2}+\cdots+(p^{d})+1\equiv
n^{\prime}-i^{\prime}\equiv 1\pmod{2},$

choosing $\beta$ satisfying $\beta^{p^{d}-1}=-1$ (i.e.,
$\beta^{p^{d}}+\beta=0$), one has

$\beta^{p^{n-i}-1}=\left(\beta^{p^{d}-1}\right)^{\frac{(p^{d})^{n^{\prime}-i^{\prime}}-1}{p^{d}-1}}=(-1)^{n^{\prime}-i^{\prime}}=-1.$

For this choice of $\beta$, one also gets

$\displaystyle{\rm Tr}(\beta)={\rm Tr}_{1}^{d}{\rm Tr}_{d}^{n}(\beta)$
$\displaystyle={\rm
Tr}_{1}^{d}\left(\beta+\beta^{p^{d}}+\beta^{p^{2d}}+\beta^{p^{3d}}+\cdots+\beta^{p^{(n^{\prime}-2)d}}+\beta^{p^{(n^{\prime}-1)d}}\right)$
$\displaystyle={\rm
Tr}_{1}^{d}\left(\beta+\beta^{p^{d}}+(\beta+\beta^{p^{d}})^{p^{2d}}+\cdots+(\beta+\beta^{p^{d}})^{p^{(n^{\prime}-2)d}}\right)={\rm
Tr}_{1}^{d}(0)=0.$

Therefore, the condition on $c$ in Proposition 5.2,

${\rm Tr}(c\beta\gamma)=-{\rm Tr}(\beta D_{\gamma}G(0))=-{\rm
Tr}(\beta(G(\gamma)-G(0))=-{\rm Tr}(\beta\gamma^{p^{i}+1})=-{\rm Tr}(\beta)=0$

is satisfied by choosing $c=0$. Consequently, for our choice of parameters
($c=0,\gamma=1$, ${\rm Tr}(\alpha)=-2,\beta^{p^{d}}+\beta=0$), the function
$F\circ H=G\circ H$ ($\because c=0$) is written as

$\displaystyle G\circ H(x)$ $\displaystyle=G(x)+\varepsilon
D_{\gamma}G(x)+\gamma^{p^{i}+1}(\varepsilon^{2}-\varepsilon)$
$\displaystyle=x^{p^{i}+1}+\varepsilon(x^{p^{i}}+x+1)+\varepsilon^{2}-\varepsilon,\qquad(\text{with
}\varepsilon={\rm Tr}(\alpha x+\beta x^{p^{i}+1}))$

where the algebraic degree of $G\circ H$ is $4$.

###### Remark 7.7

The elements $\alpha$ and $\beta$ satisfying ${\rm Tr}(\alpha)=-2$ and
$\beta^{p^{d}}+\beta=0$ can be chosen as follows.

  1. 1.

If $\gcd(n,p)=1$, then ${\rm Tr}(1)=n\neq 0$. Thus letting
$\alpha=-\frac{2}{n}\in\mathbb{F}_{p}$, one gets ${\rm Tr}(\alpha)=-2$. If
$p|n$ or or if no restriction of $p$ and $n$ is given, let $\tau$ be any
primitive root of $\mathbb{F}_{p^{n}}^{\times}$ and let $h(x)$ be the monic
irreducible polynomial of $\tau$. Then letting
$\frac{h(x)}{x-\tau}=\sum_{i=0}^{n-1}a_{i}x^{i}$, one has ${\rm
Tr}\left(\frac{a_{0}}{h^{\prime}(\tau)}\right)=1$ where $h^{\prime}(x)$ is the
usual (formal) derivative of $h$. (See Theorem 1.5 and 4.23 in [37].)
Therefore letting $\alpha=-2\frac{a_{0}}{h^{\prime}(\tau)}$, one gets ${\rm
Tr}(\alpha)=-2$.

  2. 2.

Choose any $\zeta\in{\mathbb{F}}_{p^{2d}}\setminus{\mathbb{F}}_{p^{d}}$. Since
$2d|n$, one gets $\zeta\in\mathbb{F}_{p^{n}}^{\times}$. Letting
$\beta=\zeta-\zeta^{p^{d}}$, one has
$\beta^{p^{d}}+\beta=\zeta^{p^{d}}-\zeta+\zeta-\zeta^{p^{d}}=0$.

###### Corollary 7.8

Under the same assumption as in Corollary 7.6 and letting $c=0,\gamma=1$ and
choosing $\alpha$ and $\beta$ as in Remark 7.7, the function

$G\circ
H(x)=x^{p^{i}+1}+\varepsilon(x^{p^{i}}+x+1)+\varepsilon^{2}-\varepsilon\qquad(\text{with
}\varepsilon={\rm Tr}(\alpha x+\beta x^{p^{i}+1}))$

is CCZ-equivalent to $G(x)=x^{p^{i}+1}$ but not EA-equivalent to each other.
That is,

$G\circ H\overset{\textrm{\tiny EA}}{\not\sim}G\qquad\text{and }\quad G\circ
H\overset{\textrm{\tiny CCZ}}{\sim}G.$

Moreover, $G\circ H$ is EA-inequivalent to any power function.

Proof. Since $G_{\text{\tiny DO}}(\gamma)=\gamma^{p^{i}+1}=1\neq 0$ and since
${\rm Tr}(c\beta\gamma)=0$, using Theorem 6.7, one has $G\circ
H\overset{\textrm{\tiny EA}}{\not\sim}x^{s}$ for any $s\in{\mathbb{Z}}$.

##  8 Applications to Quadratic $(n,m)$-Functions

In this section, we state that our main Theorem 6.7 in previous section has a
natural generalization to $(n,m)$-functions
$:\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p^{m}}$, where $m$ is a positive
divisor of $n$. One can define the Walsh transform and the differential
uniformity of $(n,m)$-function $F(x)$ in a similar manner. For a given
quadratic $(n,m)$-function $F$, if $\Delta_{F}>p^{n-m}$, one can show that
there exists $\gamma\in\mathbb{F}_{p^{n}}^{\times}$ and
$\beta\in\mathbb{F}_{p^{m}}^{\times}$ such that $\gamma$ is a linear structure
of ${\rm Tr}_{1}^{m}(\beta F)$. That is, using the following modifications;

$\Delta_{F}>1\longrightarrow\Delta_{F}>p^{n-m}\quad\text{and}\quad{\rm
Tr}(\beta F(x))\longrightarrow{\rm Tr}_{1}^{m}(\beta F(x)),$

it is straightforward to show that Proposition 3.11 also holds for the case of
$(n,m)$-function $F$. Lemma 5.1 is valid for the following $\mathscr{L}$:

$\displaystyle\mathscr{L}:\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{m}}$
$\displaystyle\rightarrow\mathbb{F}_{p^{n}}\times\mathbb{F}_{p^{m}}$
$\displaystyle(x,y)$ $\displaystyle\mapsto(x+\gamma({\rm Tr}(\alpha x)+{\rm
Tr}_{1}^{m}(\beta y)),y),$

where $\alpha,\gamma\in\mathbb{F}_{p^{n}}$ and $\beta\in\mathbb{F}_{p^{m}}$.
Also, for a given $(n,m)$-function $F_{0}$, Proposition 5.2 is still valid
using the following modifications;

$\displaystyle F(x)=F_{0}(x)+cx\quad$ $\displaystyle\longrightarrow\quad
F(x)=F_{0}(x)+{\rm Tr}_{m}^{n}(cx),$ $\displaystyle{\rm
Tr}(c\beta\gamma)=-{\rm Tr}(\beta D_{\gamma}F_{0}(0))\quad$
$\displaystyle\longrightarrow\quad{\rm Tr}(c\beta\gamma)=-{\rm
Tr}_{1}^{m}(\beta D_{\gamma}F_{0}(0)),$ $\displaystyle H(x)=x+\gamma{\rm
Tr}\left(\alpha x+\beta F(x)\right)\quad$ $\displaystyle\longrightarrow\quad
H(x)=x+\gamma\left({\rm Tr}(\alpha x)+{\rm Tr}_{1}^{m}(\beta F(x))\right).$

With these modifications, the validity of Theorem 5.3 and Proposition 5.6 is
unchanged. Lemma 6.1 is valid with the modifications ${\rm Tr}(\beta
F(x))\rightarrow{\rm Tr}_{1}^{m}(\beta F(x))$ and ${\rm Tr}(\beta
L_{\gamma_{i}}(\gamma_{j}))\rightarrow{\rm Tr}_{1}^{m}(\beta
L_{\gamma_{i}}(\gamma_{j}))$. Proposition 6.2 is still true with no
modification except for the previously mentioned ${\mathcal{W}}_{{\rm
Tr}_{1}^{m}(bF)}$ and $\varepsilon={\rm Tr}(\alpha x)+{\rm Tr}_{1}^{m}(\beta
F(x))$. In the exactly same manner as in Lemma 6.1 and Proposition 6.2, one
finds that Lemma 6.4 and Proposition 6.5 are also valid. Summing up all these
together, one has the following generalization of Theorem 6.7 as follows.

###### Theorem 8.1

(Generalization of Theorem 6.7) Let $F_{0}(x)$ be a quadratic $(n,m)$-function
on $\mathbb{F}_{p^{n}}$ with $n\geq 4$ and $m$ is a positive divisor of $n$.
Then, one concludes the followings.

  1. 1.

When $p=2$: Suppose that $|{\mathcal{W}}_{F_{0}}|<2^{n}$ (i.e.,
$\textup{{NL}}(F_{0})\neq 0$) and $2^{n-m}<\Delta_{F_{0}}\leq 2^{n-3}$. Then
for any $\gamma\in\mathbb{F}_{2^{n}}^{\times}$, one can choose
$\beta\in\mathbb{F}_{2^{m}}^{\times}$ such that ${\rm Tr}_{1}^{m}(\beta
D_{\gamma}F(x))=0$ for all $x\in\mathbb{F}_{2^{n}}$, where $F(x)=F_{0}(x)+{\rm
Tr}_{m}^{n}(cx)$ and $c\in\mathbb{F}_{2^{n}}$ is determined by the condition
${\rm Tr}(c\beta\gamma)={\rm Tr}_{1}^{m}(\beta(F_{0}(\gamma)+F_{0}(0)))$.
Choosing $\alpha\in\mathbb{F}_{2^{n}}$ satisfying ${\rm Tr}(\alpha\gamma)=0$,
the function

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)\quad(\,\,\text{with
}\varepsilon={\rm Tr}(\alpha x)+{\rm Tr}_{1}^{m}(\beta F(x))\,\,)$

has an algebraic degree $3$ and satisfies $F\circ H\overset{\textrm{\tiny
CCZ}}{\sim}F_{0}$ and $F\circ H\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$.

  2. 2.

When $p>2$: Suppose that $|{\mathcal{W}}_{F_{0}}|\leq p^{n-1}$ and
$p^{n-m}<\Delta_{F_{0}}\leq p^{n-3}$. Then there exist
$\gamma\in\mathbb{F}_{p^{n}}^{\times}$ and
$\beta\in\mathbb{F}_{p^{m}}^{\times}$ such that ${\rm Tr}_{1}^{m}(\beta
D_{\gamma}F(x))=0$ for all $x\in\mathbb{F}_{p^{n}}$, where $F(x)=F_{0}(x)+{\rm
Tr}_{m}^{n}(cx)$ and $c\in\mathbb{F}_{p^{n}}$ is determined by the condition
${\rm Tr}(c\beta\gamma)=-{\rm Tr}_{1}^{m}(\beta(F_{0}(\gamma)-F_{0}(0)))$.
Choosing $\alpha\in\mathbb{F}_{p^{n}}$ satisfying ${\rm Tr}(\alpha\gamma)=-2$,
the function

$F\circ H(x)=F(x)+\varepsilon D_{\gamma}F(x)+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)\quad(\,\,\text{with
}\varepsilon={\rm Tr}(\alpha x)+{\rm Tr}_{1}^{m}(\beta F(x))\,\,)$

satisfies $F\circ H\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ and $F\circ
H\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$, where $d^{\circ}(F\circ H)=3$ if
$F_{\text{\tiny DO}}(\gamma)=0$, and $d^{\circ}(F\circ H)=4$ if
$F_{\text{\tiny DO}}(\gamma)\neq 0$.

The above theorem implies that, for most of quadratic $(n,m)$-functions $F$,
there exists a function $F^{\prime}$ such that
$F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F$ but
$F^{\prime}\overset{\textrm{\tiny EA}}{\not\sim}F$. In other words, the notion
of CCZ-equivalence is strictly more general than the notion of EA-equivalence
in the following sense.

###### Corollary 8.2

Let $p$ be an arbitrary prime. Let $n\geq 4$ and $m$ is a divisor of $n$ such
that $4\leq m<n$. Let $F$ be a quadratic $(n,m)$-function on
$\mathbb{F}_{p^{n}}$. Suppose that

$|{\mathcal{W}}_{F}|\leq p^{n-1}\text{ and }p^{n-m}<\Delta_{F}\leq p^{n-3}.$

Then the CCZ-equivalence class of $F$ is strictly larger than the EA-
equivalence class of $F$. That is, one has
$\mathscr{C}_{\textrm{EA}}(F)\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F)$.

###### Remark 8.3

It should be mentioned that two examples of $(n,m)$-functions $F$ with $m|n$
satisfying
$\mathscr{C}_{\textrm{EA}}(F)\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F)$ are
already known. One is the binary case $F(x)={\rm Tr}_{m}^{n}(x^{3})$ in [9],
and the other is a $p$-ary ($p>2$) case $F(x)={\rm Tr}_{m}^{n}(x^{2}-x^{p+1})$
in [15]. Moreover, for a given $(n,m)$-function $F$ satisfying
$\mathscr{C}_{\textrm{EA}}(F)\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F)$ and for
any $k\geq 1$, it is shown in [9] that one can construct $(n,m+k)$-function
$F^{\prime}$ satisfying
$\mathscr{C}_{\textrm{EA}}(F^{\prime})\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F^{\prime})$.
See also [41] for a generalization of these methods over finite abelian
groups.

Please note that, when $m=n$, Theorem 8.1 is exactly same to Theorem 6.7. When
$m$ is a proper divisor of $m$ (i.e., $m<n$), then one needs a stronger
assumption of the lower bound of $\Delta_{F}$ in Theorem 8.1, that is,
$p^{n-m}<\Delta_{F}$. Moreover, the case $\Delta_{F}=p^{n-m}$ happens if and
only if $F$ is a bent (or perfect non-linear) $(n,m)$-function. Recall that,
in Section 2, we defined that $(n,1)$-function $f$ on $\mathbb{F}_{p^{n}}$ is
bent if $|{\mathcal{W}}_{f}|=p^{\frac{n}{2}}$. In a similar manner, we define
that $(n,m)$-function $F$ on $\mathbb{F}_{p^{n}}$ is bent if every component
function ${\rm Tr}_{1}^{m}(bF)\,\,(b\in\mathbb{F}_{p^{m}}^{\times})$ is bent.
Then the following equivalent conditions are well-known (See for example
[40].):

  1. –

$F:\mathbb{F}_{p^{n}}\rightarrow\mathbb{F}_{p^{m}}$ is bent.

  2. –

$D_{\gamma}{\rm Tr}_{1}^{m}(\beta F)$ is balanced for every
$\beta\in\mathbb{F}_{p^{m}}^{\times}$ and
$\gamma\in\mathbb{F}_{p^{n}}^{\times}$.

  3. –

$D_{\gamma}F$ is balanced for every $\gamma\in\mathbb{F}_{p^{n}}^{\times}$.

  4. –

$\Delta_{F}=p^{n-m}$.

Therefore, _explicit examples_ of $(n,m)$-function $F$ satisfying the
assumptions of Theorem 8.1 can be constructed by finding non-bent
$(n,m)$-function $F$ satisfying $\Delta_{F}\leq p^{n-3}$. Since every
$(n,m)$-function is of the form ${\rm Tr}_{m}^{n}(G)$ for some
$(n,n)$-function $G$, we may construct explicit examples of $(n,m)$-functions
satisfying Theorem 8.1 using our previous results in Section 6 as follows.

###### Theorem 8.4

Let $F_{0}(x)$ be a quadratic $(n,n)$-function on $\mathbb{F}_{p^{n}}$
satisfying the conditions of Theorem 6.7 with corresponding
$\alpha,\beta,\gamma,c$ in $\mathbb{F}_{p^{n}}$ and $F(x)=F_{0}(x)+cx$.
Letting $\Delta_{F}=p^{s}$, assume further that $0<s\leq m-3$ (i.e.,
$p^{n-m}<p^{n-m+s}\leq p^{n-3}$) where $m|n$ with $m\geq 4$. Then the
$(n,m)$-function

$F_{0}^{\prime}(x)={\rm Tr}_{m}^{n}(\beta F(x))$

satisfies the conditions of Theorem 8.1 with
$\alpha^{\prime}=\alpha,\beta^{\prime}=1,\gamma^{\prime}=\gamma$ and
$c^{\prime}=0$. Therefore, using

$\varepsilon^{\prime}={\rm Tr}(\alpha^{\prime}x)+{\rm
Tr}_{1}^{m}(\beta^{\prime}F^{\prime}(x))={\rm Tr}(\alpha x)+{\rm
Tr}_{1}^{m}({\rm Tr}_{m}^{n}(\beta F(x)))={\rm Tr}(\alpha x+\beta
F(x))=\varepsilon,$

one has the followings.

  1. 1.

When $p=2$:

$\displaystyle F^{\prime}\circ H^{\prime}$
$\displaystyle=F^{\prime}+\varepsilon^{\prime}D_{\gamma^{\prime}}F^{\prime}=F^{\prime}+\varepsilon
D_{\gamma}F^{\prime}$ $\displaystyle={\rm Tr}_{m}^{n}(\beta F)+\varepsilon{\rm
Tr}_{m}^{n}(\beta D_{\gamma}F)$

is CCZ-equivalent to $F^{\prime}={\rm Tr}_{m}^{n}(\beta F)$ but not EA-
equivalent to each other.

  2. 2.

When $p>2$:

$\displaystyle F^{\prime}\circ H^{\prime}$
$\displaystyle=F^{\prime}+\varepsilon^{\prime}D_{\gamma^{\prime}}F^{\prime}+{F}_{\text{\tiny
DO}}^{\prime}(\gamma^{\prime})({\varepsilon^{\prime}}^{2}-\varepsilon^{\prime})$
$\displaystyle={\rm Tr}_{m}^{n}(\beta F)+\varepsilon{\rm Tr}_{m}^{n}(\beta
D_{\gamma}F)+{{\rm Tr}_{m}^{n}(\beta F_{\text{\tiny
DO}})}(\gamma)({\varepsilon}^{2}-\varepsilon)$

is CCZ-equivalent to $F^{\prime}={\rm Tr}_{m}^{n}(\beta F)$ but not EA-
equivalent to each other.

Proof. Since $c^{\prime}=0$, one has $F^{\prime}(x)=F_{0}^{\prime}(x)={\rm
Tr}_{m}^{n}(\beta F(x))$ and

${\rm Tr}_{1}^{m}(\beta^{\prime}D_{\gamma^{\prime}}F^{\prime}(x))={\rm
Tr}_{1}^{m}(D_{\gamma}{\rm Tr}_{m}^{n}(\beta F(x)))={\rm Tr}_{1}^{m}({\rm
Tr}_{m}^{n}(\beta D_{\gamma}F(x)))={\rm Tr}(\beta D_{\gamma}F(x))=0,$

which says that $\gamma^{\prime}=\gamma$ is a $0$-linear structure of ${\rm
Tr}_{1}^{m}(F^{\prime})$. Also, for $a\in\mathbb{F}_{p^{n}}$ and
$b\in\mathbb{F}_{p^{m}}$, one has

$\displaystyle{\mathcal{W}}_{F^{\prime}}(a,b)$
$\displaystyle=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm
Tr}_{1}^{m}(bF^{\prime}(x))-{\rm
Tr}(ax)}=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm Tr}_{1}^{m}(b{\rm
Tr}_{m}^{n}(\beta F(x)))-{\rm Tr}(ax)}$
$\displaystyle=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm Tr}_{1}^{m}({\rm
Tr}_{m}^{n}(b\beta F(x)))-{\rm
Tr}(ax)}=\sum_{x\in{\mathbb{F}}_{p^{n}}}\xi^{{\rm Tr}(b\beta F(x))-{\rm
Tr}(ax)}={\mathcal{W}}_{F}(a,b\beta).$

Therefore one gets $|{\mathcal{W}}_{F^{\prime}}|=|{\mathcal{W}}_{F}|<2^{n}$
for a binary case and $|{\mathcal{W}}_{F^{\prime}}|=|{\mathcal{W}}_{F}|\leq
p^{n-1}$ for odd characteristic case. Note that $F^{\prime}={\rm
Tr}_{m}^{n}(\beta F)$ is not a bent function because ${\rm
Tr}_{1}^{m}(F^{\prime})={\rm Tr}(\beta F)$ is not a bent function (since
$\gamma$ is a $0$-linear structure of ${\rm Tr}(\beta F)$). Thus one has the
lower bound $p^{n-m}<\Delta_{F^{\prime}}$. For the upper bound, one gets
$\Delta_{F^{\prime}}=\underset{\delta\in\mathbb{F}_{p^{n}}^{\times}}{\max}|{\rm
Ker}({\rm Tr}_{m}^{n}\circ\beta L_{\delta})|\leq p^{n-m+s}\leq p^{n-3}$ where
$L_{\delta}(x)=F(x+\delta)-F(x)-(F(\delta)-F(0))$.

An obvious implication of the above theorem for the case of APN function over
$\mathbb{F}_{2^{n}}$ is the folowing.

###### Corollary 8.5

For every quadratic APN function $F_{0}(x)$ on $\mathbb{F}_{2^{n}}$ $(n\geq
4)$ with $F(x)=F_{0}(x)+cx$ satisfying ${\rm Tr}(\beta D_{\gamma}F(x))=0$ for
all $x$, one has $\Delta_{F^{\prime}}=2^{n-m+1}$ with $F^{\prime}={\rm
Tr}_{m}^{n}(\beta F)$. Thus the condition $2^{n-m}<\Delta_{F^{\prime}}\leq
2^{n-3}$ is satisfied for every positive divisor $m$ of $n$ with $m\geq 4$,
and the following function

$F^{\prime}+\varepsilon D_{\gamma}F^{\prime}={\rm Tr}_{m}^{n}(\beta
F)+\varepsilon{\rm Tr}_{m}^{n}(\beta D_{\gamma}F)\qquad(\varepsilon={\rm
Tr}(\alpha x+\beta F(x)))$

is of algebraic degree $3$ and is CCZ-equivalent to ${\rm Tr}_{m}^{n}(\beta
F)$ but not EA-equivalent to each other.

###### Remark 8.6

When $m=n$, one has $F^{\prime}=\beta F$ and $F^{\prime}+\varepsilon
D_{\gamma}F^{\prime}=\beta(F+\varepsilon D_{\gamma}F)$ so that one gets the
same result of the case of $(n,n)$-functions in Theorem 6.7. Also when
$m=\frac{n}{2}$ with even $n$, one gets $(2m,m)$-function $F^{\prime}$ such
that $F^{\prime}$ has a CCZ-equivalent but not EA-equivalent function
$F^{\prime}+\varepsilon D_{\gamma}F^{\prime}$. That is, examples of $(2m,m)$
function $F^{\prime}$ satisfying
$\mathscr{C}_{\textrm{EA}}(F^{\prime})\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F^{\prime})$.

We present more explicit examples related to the equivalent classes of
$(n,m)$-functions arising from Gold functions over $\mathbb{F}_{2^{n}}$.

###### Corollary 8.7

$($Binary $(n,m)$-functions arising from Gold function$)$ Let $n\geq 4$ and
$m$ be a divisor of $n$ with $m\geq 4$. Let $i\geq 1$ be an integer such that
$\gcd(i,n)=1$ (i.e., $x^{2^{i}+1}$ is APN). Then,

${\rm Tr}_{m}^{n}(x^{2^{i}+1})+{\rm Tr}_{m}^{n}(x^{2^{i}}+x){\rm
Tr}(x^{2^{i}+1}+x)$

is of algebraic degree three, and is CCZ-equivalent to ${\rm
Tr}_{m}^{n}(x^{2^{i}+1})$ but not EA-equivalent to each other.

Proof. This is an immediate consequence of Theorem 8.4 or Corollary 8.5 saying
that

${\rm Tr}_{m}^{n}(F(x))\overset{\textrm{\tiny EA}}{\not\sim}{\rm
Tr}_{m}^{n}(F(x))+{\rm Tr}_{m}^{n}(D_{1}F(x)){\rm
Tr}(x^{2^{i}+1}+x)\overset{\textrm{\tiny CCZ}}{\sim}{\rm Tr}_{m}^{n}(F(x))$

with $F(x)=x^{2^{i}+1}+x$ and $\gamma=1,\beta=1,\alpha=0,c=1$ so that
$\varepsilon={\rm Tr}(x^{2^{i}+1}+x)$, which is analogous to Remark 7.1 of
Section 7.1.

###### Remark 8.8

From Corollary 8.7, consider the case that $n$ is even and $m=\frac{n}{2}$
($m\geq 4$ and $\gcd(i,2m)=1$). Then one gets

$\displaystyle{\rm
Tr}_{m}^{2m}(x^{2^{i}+1})=x^{2^{i}+1}+x^{(2^{i}+1)2^{m}}\text{ {\rm and}
}\,{\rm Tr}_{m}^{2m}(x^{2^{i}}+x)=x+x^{2^{i}}+x^{2^{m}}+x^{2^{i+m}}$

so that the following cubic $(2m,m)$-function

$x^{2^{i}+1}+x^{(2^{i}+1)2^{m}}+\left(x+x^{2^{i}}+x^{2^{m}}+x^{2^{i+m}}\right){\rm
Tr}\left(x^{2^{i}+1}+x\right)$

is CCZ-equivalent to $x^{2^{i}+1}+x^{(2^{i}+1)2^{m}}$ but not EA-equivalent to
each other. We think that this is an interesting example in the sense that the
greatest $1\leq m\leq n$ such that there exists a binary bent $(n,m)$-function
is the case $m=\frac{n}{2}$ with $n=$even (See [40].). Moreover, it is shown
in [8] that CCZ-equivalence coincides with EA-equivalence for the case of bent
functions. Summing up these together, we have the following remark.

###### Remark 8.9

Let $n\geq 8$ be even and let $F$ be an $(n,m)$-function on
${\mathbb{F}}_{2}^{n}$. Then, $m=\frac{n}{2}$ is the greatest possible integer
$m$ such that there exist two $(n,m)$-functions $F$ and $F^{\prime}$ such that
$\mathscr{C}_{\textrm{EA}}(F)=\mathscr{C}_{\textrm{CCZ}}(F)$ and
$\mathscr{C}_{\textrm{EA}}(F^{\prime})\subsetneqq\mathscr{C}_{\textrm{CCZ}}(F^{\prime})$.
Examples of such $F$ are bent functions, and examples of $F^{\prime}$ are non-
bent functions satisfying $|{\mathcal{W}}_{F^{\prime}}|<2^{n}$ and
$\Delta_{F^{\prime}}\leq 2^{n-3}$.

For non-binary cases, examples of $(n,m)$-functions on $\mathbb{F}_{p^{n}}$
satisfying Theorem 8.1 and 8.4 can also be given in the same manner. We will
give such examples arising from Gold function $G(x)=x^{p^{i}}+1$ on
$\mathbb{F}_{p^{n}}$ with even $n$ and $\gcd(i,n)=1$. In this case, from
Section 7.3, recall that $|{\mathcal{W}}_{G}|=p^{\frac{n}{2}+1}$ and
$\Delta_{G}=p$. Therefore, with the same parameters $c=0,\gamma=1$ and
$\alpha,\beta\in\mathbb{F}_{p^{n}}$ as in Remark 7.7 and Corollary 7.8, one
has

###### Corollary 8.10

$($Non-binary $(n,m)$-functions arising from Gold function$)$ Let $p$ be an
odd prime. Let $n\geq 4$ be even and $m\geq 4$ be a divisor of $n$. Let
$\alpha\in\mathbb{F}_{p^{n}}$ and $\beta\in{\mathbb{F}}_{p^{2}}^{\times}$ such
that ${\rm Tr}(\alpha)=-2$ and $\beta^{p}+\beta=0$. Let $\varepsilon={\rm
Tr}(\alpha x+\beta x^{p^{i}+1})$ and $\gcd(i,n)=1$. Then the following
$(n,m)$-function on $\mathbb{F}_{p^{n}}$,

$\displaystyle{\rm Tr}_{m}^{n}(\beta x^{p^{i}+1})+\varepsilon{\rm
Tr}_{m}^{n}\left(\beta(x^{p^{i}}+x+1)\right)+{\rm
Tr}_{m}^{n}(\beta)(\varepsilon^{2}-\varepsilon),$ (8.1)

is of algebraic degree $3$ or $4$, and is CCZ-equivalent to ${\rm
Tr}_{m}^{n}(\beta x^{p^{i}+1})$ but not EA-equivalent to each other.

Proof. Letting $F^{\prime}(x)={\rm Tr}_{m}^{n}(\beta x^{p^{i}+1})$, Theorem
8.4 implies that

$F^{\prime}(x)\overset{\textrm{\tiny CCZ}}{\sim}F^{\prime}(x)+\varepsilon
D_{\gamma}F^{\prime}(x)+F^{\prime}_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)\overset{\textrm{\tiny
EA}}{\not\sim}F^{\prime}(x),$

where

$\displaystyle D_{\gamma}F^{\prime}(x)$ $\displaystyle=D_{1}{\rm
Tr}_{m}^{n}(\beta x^{p^{i}+1})={\rm Tr}_{m}^{n}(\beta D_{1}x^{p^{i}+1})$
$\displaystyle={\rm Tr}_{m}^{n}(\beta((x+1)^{p^{i}+1}-x^{p^{i}+1}))={\rm
Tr}_{m}^{n}(\beta(x^{p^{i}}+x+1)),\text{ and}$ $\displaystyle
F^{\prime}_{\text{\tiny DO}}(\gamma)$
$\displaystyle=F^{\prime}(\gamma)=F^{\prime}(1)={\rm Tr}_{m}^{n}(\beta).$

It is also straightforward to see $\Delta_{F^{\prime}}=p^{n-m+1}$.

###### Remark 8.11

The $(n,m)$-function in Corollary 8.10 is of algebraic degree three if ${\rm
Tr}_{m}^{n}(\beta)=0$, and four if ${\rm Tr}_{m}^{n}(\beta)\neq 0$. Since $n$
is even and $\beta\in{\mathbb{F}}_{p^{2}}$, one has ${\rm
Tr}_{m}^{n}(\beta)=0$ if $m$ is odd, and ${\rm
Tr}_{m}^{n}(\beta)=\frac{n}{m}\beta$ if $m$ is even. Therefore, the function
in (8.1) is cubic if $m$ is odd or $\frac{n}{m}\equiv 0\pmod{p}$, and is
quartic otherwise.

###### Corollary 8.12

Let $p=3$. Let $n\geq 4$ be even and $m\geq 4$ be a divisor of $n$. Let
$\alpha\in{\mathbb{F}}_{3^{n}}$ and $\beta\in{\mathbb{F}}_{3^{2}}^{\times}$
such that ${\rm Tr}(\alpha)=1$ and $\beta^{2}=-1$. Let $\varepsilon={\rm
Tr}(\alpha x+\beta x^{3^{i}+1})$ and $\gcd(i,n)=1$. Then the following
$(n,m)$-function on ${\mathbb{F}}_{3^{n}}$,

${\rm Tr}_{m}^{n}(\beta x^{3^{i}+1})+\varepsilon{\rm
Tr}_{m}^{n}\left(\beta(x^{3^{i}}+x+1)\right)+{\rm
Tr}_{m}^{n}(\beta)(\varepsilon^{2}-\varepsilon),$

is of algebraic degree $3$ if $m\equiv 1\pmod{2}$ or $\frac{n}{m}\equiv
0\pmod{3}$, and is of degree $4$ otherwise, and is CCZ-equivalent to ${\rm
Tr}_{m}^{n}(\beta x^{3^{i}+1})$ but not EA-equivalent to each other.

##  9 Conclusions and Future Works

For almost all quadratic $(n,n)$-functions $F_{0}$ over $\mathbb{F}_{p^{n}}$
with $n\geq 4$, we constructed $F^{\prime}$ satisfying
$F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ but
$F^{\prime}\overset{\textrm{\tiny EA}}{\not\sim}F_{0}$. For a binary case,
assuming $\textup{{NL}}(F_{0})\neq 0$ and $\Delta_{F_{0}}\leq 2^{n-3}$, the
function

$F^{\prime}=F+\varepsilon D_{\gamma}F\quad(\text{with }F(x)=F_{0}(x)+cx\text{
and }\varepsilon={\rm Tr}(\alpha x+\beta F(x)))$

satisfies $F_{0}\overset{\textrm{\tiny
EA}}{\not\sim}F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ for many
suitably chosen $\alpha,\beta,\gamma$ and $c$ in $\mathbb{F}_{2^{n}}$, where
the number of possible choices of $\\{\alpha,\beta,\gamma,c\\}$ is at least
$2^{2n-2}(2^{n}-1)$ and exactly $2^{2n-2}(2^{n}-1)$ if $F_{0}$ is APN. For a
field $\mathbb{F}_{p^{n}}$ with $p>2$, assuming $|{\mathcal{W}}_{F_{0}}|\leq
p^{n-1}$ and $1<\Delta_{F_{0}}\leq p^{n-3}$, the function

$F^{\prime}=F+\varepsilon D_{\gamma}F+F_{\text{\tiny
DO}}(\gamma)(\varepsilon^{2}-\varepsilon)\quad(\text{with
}F(x)=F_{0}(x)+cx\text{ and }\varepsilon={\rm Tr}(\alpha x+\beta F(x)))$

satisfies $F_{0}\overset{\textrm{\tiny
EA}}{\not\sim}F^{\prime}\overset{\textrm{\tiny CCZ}}{\sim}F_{0}$ for many
suitably chosen $\alpha,\beta,\gamma$ and $c$ in $\mathbb{F}_{2^{n}}$, where
the number of possible choices of $\\{\alpha,\beta,\gamma,c\\}$ is at least
$p^{2n-2}(p-1)$.

For arbitrary characteristic $p$, one can choose $\alpha,\beta,\gamma$ and $c$
(in the order of $\gamma\mapsto\\{\beta,\alpha\\}\mapsto c$) satisfying

$\displaystyle{\rm Tr}(\beta D_{\gamma}F_{0}(x))$ $\displaystyle={\rm
Tr}(\beta D_{\gamma}F_{0}(0))\text{ for all }x\in\mathbb{F}_{p^{n}},\,\,{\rm
Tr}(\alpha\gamma)=-2,$ $\displaystyle\text{\emph{and} }\,\,{\rm
Tr}(c\beta\gamma)$ $\displaystyle=-{\rm Tr}(\beta D_{\gamma}F_{0}(0)).$

For a fixed $F_{0}$, such construction generates many $F^{\prime}$ because
$F^{\prime}$ is depending on the choices of $\alpha,\beta,\gamma$ and $c$.
Though all of such $F^{\prime}$ are CCZ-equivalent to each other, EA-
equivalence or (EA-inequivalence) among them are unclear at this moment.
Moreover such $F^{\prime}$ are no longer plateaued, and the corresponding the
Walsh spectrum needs to be investigated further. Also, it may be possible to
apply our technique to general $(n,m)$-functions, where $m$ is not necessarily
a divisor of $n$. Our technique (especially in Proposition 5.2) heavily relies
on the equivalence between the linear structure and the linear translator over
the prime field ${\mathbb{F}}_{p}$, where the linear map ${\rm Tr}_{1}^{n}$
has its image in ${\mathbb{F}}_{p}$. That is the reason why we could not
extended the ideas in [13, 11], where they also used the trace maps over the
intermediate fields such as ${\rm Tr}_{3}^{n}$ or ${\rm Tr}_{d}^{n}$ with
$d|n$. Therefore, extending Proposition 5.2 to the trace map over the
intermediate fields is also desirable.

## References

  * [1] D. Bartoli and M. Timpanella, _On a generalization of planar functions_ , J. Algebraic Combinatorics, Vol. 52, 187-213, 2020.
  * [2] C. Beierle and G. Leander, _New instances of quadratic APN functions_ , IEEE Trans. Inform. Theory, Vol. 68(3), pp. 670-678, 2022.
  * [3] C. Beierle, C. Carlet, G. Leander and L. Perrin _A further study of quadratic APN permutations in dimension nine_ , preprint, available at https://arxiv.org/abs/2104.08008.
  * [4] C. Bracken, E. Byrne, N. Markin, and G. McGuire, _New families of quadratic almost perfect nonlinear trinomials and multinomials_ , Finite Fields and Their Applications, Vol. 14, pp. 703–714, 2008.
  * [5] L. Budaghyan, M. Calderini, C. Carlet, R. S. Coulter and I. Villa, “Constructing APN Functions Through Isotopic Shifts,” IEEE Transactions on Information Theory, Vol. 66, no. 8, pp. 5299-5309, Aug. 2020, doi: 10.1109/TIT.2020.2974471.
  * [6] L. Budaghyan, M. Calderini, and I. Villa, _On relations between CCZ- and EA-equivalences_ , Cryptogr. Comm,, Vol. 12, Issue 1, pp.85-100, 2020. DOI : 10.1007/s12095-019-00367-5
  * [7] L. Budaghyan and C. Carlet, _Classes of quadratic APN trinomials and hexanomials and related structures_ , IEEE Transactions on Information Theory, Vol. 54 (5), pp. 2354–2357, 2008.
  * [8] L. Budaghyan and C. Carlet, _On CCZ-equivalence and its use in secondary constructions of bent functions_ , Preproceedings of International Workshop on Coding and Cryptography WCC 2009, pp. 19–36, 2009.
  * [9] L. Budaghyan, and C. Carlet, _CCZ-equivalence of single and multi output Boolean functions_ , Proceedings of Fq9 (International Conference on Finite Fields and Their Applications), Contemp. Math., Vol. 518, pp. 43–54, Amer. Math. Soc., 2010.
  * [10] L. Budaghyan, C. Carlet, and G. Leander, _Two classes of quadratic APN binomials inequivalent to power functions_ , IEEE Transactions on Information Theory, Vol. 54 (9), pp. 4218–4229, 2008.
  * [11] L. Budaghyan, C. Carlet, and G. Leander, _Constructing new APN functions from known ones_ , Finite Fields and Their Applications, Vol. 15, pp. 150–159, 2009.
  * [12] L. Budaghyan, C. Carlet, and G. Leander, _On a construction of quadratic APN functions,_ Proceedings of the IEEE Information Theory Workshop ITW 2009, pp. 374–378, 2009.
  * [13] L. Budaghyan, C. Carlet, and A. Pott, _New classes of almost bent and almost perfect nonlinear functions_ , IEEE Trans. Inform. Theory, Vol. 52, issue 3, pp. 1141-1152, 2006.
  * [14] L. Budaghyan and T. Helleseth, _New perfect nonlinear multinomials over $\mathbb{F}_{p^{2k}}$ for any odd prime $p$_, SETA 2008, LNCS 5203, pp. 403-414, 2008.
  * [15] L. Budaghyan and T. Helleseth, _On isotopisms of commutative presemifields and CCZ-equivalence of functions_ , Internat. J. Found. Comput. Sci., Vol. 22, pp. 1243-1258, 2011.
  * [16] L. Budaghyan, T. Helleseth and N. Kaleyski, _A new family of APN quadrinomials_ , IACR Cryptology ePrint Archive (http://eprint.iacr.org/) 2019/994
  * [17] A. Canteaut, Lecture Notes on Cryptographic Boolean Functions, Inria, 2016, available at https://www.rocq.inria.fr/secret/Anne.Canteaut/poly.pdf.
  * [18] A. Canteaut and P. Charpin, _Decomposing bent functions_ , IEEE Trans. Inform. Theory, Vol. 49, issue 8, pp. 2004-2019, 2003.
  * [19] A. Canteaut, A. Couvreur and L. Perrin, _Recovering or testing extended-affine equivalence_ , IEEE Trans. Inform. Theory, Vol. 68, issue 9, pp. 6187-6206, 2022.
  * [20] A. Canteaut and L. Perrin, _On CCZ-equivalence, extended-affine equivalence, and function twisting_ , Finite Fields Appl., Vol. 56, pp. 209-246, 2019.
  * [21] C. Carlet, Boolean Functions for Cryptography and Coding Theory, Cambridge University Press, Cambridge, 2020.
  * [22] C. Carlet, P. Charpin and V. Zinoviev, Codes, _Bent functions and permutations suitable for DES-like cryptosystems_ , Des. Codes Cryptogr., Vol. 15, pp. 125-156, 1998.
  * [23] P. Charpin and G. M. Kyureghyan, _On a class of permutation polynomials over $\mathbb{F}_{2^{n}}$_, Proceedings of SETA 2008, LNCS Vol. 5203, pp. 368-376, 2008.
  * [24] R. S. Coulter, _Explicit evaluations of some Weil sums_ , Acta Arith., Vol. 83, pp. 241-251, 1998.
  * [25] R. S. Coulter, _Further evaluations of Weil sums_ , Acta Arith., Vol. 86, pp. 217-226, 1998.
  * [26] R. S. Coulter, _On the evaluation of a class of Weil sums in characteristic 2_ , New Zealand J. Math., Vol. 28, pp. 171-184, 1999.
  * [27] T. W. Cusick and P. Stǎnicǎ, Cryptographic Boolean Functions and Applications, 2nd ed., Academic Press, Elsevier, 2017.
  * [28] U. Dempwolff, _CCZ equivalence of power functions_ , Des. Codes Cryptogr., Vol. 86, No. 3, pp.665-692, 2018. DOI : 10.1007/s10623-017-0350-8
  * [29] Y. Edel, G. Kyureghyan, and A. Pott, _A new APN function which is not equivalent to a power mapping_ , IEEE Trans. Inform. Theory, Vol. 52,744–747, 2006.
  * [30] Y. Edel and A. Pott, _A new almost perfect nonlinear function which is not quadratic_ , Adv. Math. Commun., Vol. 3, 59-81, 2009
  * [31] X.-D. Hou, _$p$ -ary and $q$-ary versions of certain results about bent functions and resilient functions_, Finite Fields and Their Applications, Vol. 10, pp. 566-582, 2004.
  * [32] N. Kaleyski, _Deciding EA-equivalence via invariants_ , Cryptogr. Comm., Vol. 14, Issue 2, pp. 271-290, 2022. DOI : 10.1007/s12095-021-00513-y
  * [33] L. Kölsch, _On CCZ-equivalence of the inverse function_ , IEEE Trans. Inform. Theory, Vol. 67, issue 7, pp. 4856-4862, 2021.
  * [34] G. M. Kyureghyan, _Constructing permutations of finite fields via linear translators_ , J. Combinatorial Theory Ser A, Vol. 118, pp. 1052-1061, 2011.
  * [35] G. M. Kyureghyan and A. Pott, _Some theorems on planar mapping_ , WAIFI 2008, LNCS 5130, pp. 117-122, 2008.
  * [36] C. Li, C. Riera, and P. Stǎnicǎ, _Low $c$-differentially uniform functions via an extension of Dillon’s switching method_, a preprint, available at https://arxiv.org/abs/2204.08760.
  * [37] A. J. Menezes (Editor), Applications of Finite Fields, Kluwer Academic Publisher, 1993.
  * [38] S. Mesnager, Bent Functions: Fundamantals ans Results, Springer, 2016.
  * [39] S. Mesnager, B. Mandal, and M. Msahli, _Survey on recent trends towards generalized differential and boomerang uniformities_ , Cryptogr. Comm., Vol. 14, pp. 691-735, 2022.
  * [40] K. Nyberg, _Perfect non-linear S-boxes_ , Proceedings of EUROCRYPT 1991, LNCS Vol. 547, pp. 378-386, 1992.
  * [41] A. Pott and Y. Zhou, _CCZ and EA equivalence between mappings over finite Abelian groups_ , Designs, Codes and Cryptography, Vol. 66, pp. 99-109, 2013.
  * [42] J. Seberry, X. M. Zhang and Y. Zheng, _Pitfalls in designing substitution boxes_ , Proceedings of CRYPTO 1994, LNCS Vol. 839, pp. 383-396, 1994.
  * [43] H. Taniguchi, _On some quadratic APN functions_ , Designs, Codes and Cryptography, Vol. 87 (9), pp. 1973–1983, 2019.
  * [44] X. Xie, N. Li, X. Zeng, X. Tang, and Y. Yao, _Several classes of bent functions over finite fields_ , Designs, Codes and Cryptography, Vol. 91, pp. 309-332, 2023.
  * [45] S. Yoshiara, _Equivalence of quadratic APN functions_ , J. Algebr. Comb., Vol. 35, pp. 461–475, 2012.
  * [46] Y. Zhou and A. Pott, _A new family of semifields with 2 parameters_ , Advances in Mathematics, Vol. 234, pp. 43–60, 2013.
  * [47] M. E. Zieve, _Planar functions and perfect nonlinear monomials over finite fields_ , Designs, Codes and Cryptography, Vol. 75, pp. 71-80, 2015.