# Constructing new APN functions through relative trace functions

Lijing Zheng, Haibin Kan, Yanjun Li, Jie Peng, Deng Tang
L. Zheng is with the School of Mathematics and Physics, University of South
China, Hengyang, Hunan, 421001, China, (E-mail: zhenglijing817@163.com).
H. Kan is with the School of Computer Sciences, Fudan University, Shanghai,
200433, China, (E-mail: hbkan@fudan.edu.cn).
Y. Li is with the Mathematics and Science College of Shanghai Normal
University, Shanghai, 200234, China, (yanjlmath90@163.com).
J. Peng is with the Mathematics and Science College of Shanghai Normal
University, Shanghai, 200234, China, (jpeng@shnu.edu.cn).
D. Tang is with the School of Electronic Information and Electrical
Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China,
(dtang@foxmail.com).

Abstract: In 2020, Budaghyan, Helleseth and Kaleyski [IEEE TIT 66(11):
7081-7087, 2020] considered an infinite family of quadrinomials over
$\mathbb{F}_{2^{n}}$ of the form $x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot
2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}}$, where $n=2m$ with $m$ odd. They proved
that such kind of quadrinomials can provide new almost perfect nonlinear (APN)
functions when $\gcd(3,m)=1$, $k=0$, and $(s,a,b,c)=(m-2,\omega,\omega^{2},1)$
or $((m-2)^{-1}~{}{\rm mod}~{}n,\omega,\omega^{2},1)$ in which
$\omega\in\mathbb{F}_{4}\setminus\mathbb{F}_{2}$. By taking $a=\omega$ and
$b=c=\omega^{2}$, we observe that such kind of quadrinomials can be rewritten
as $a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(cx^{2^{s}+1})$, where
$q=2^{m}$ and ${\rm Tr}^{n}_{m}(x)=x+x^{2^{m}}$ for $n=2m$. Inspired by the
quadrinomials and our observation, in this paper we study a class of functions
with the form $f(x)=a{\rm Tr}^{n}_{m}(F(x))+a^{q}{\rm Tr}^{n}_{m}(G(x))$ and
determine the APN-ness of this new kind of functions, where
$a\in\mathbb{F}_{2^{n}}$ such that $a+a^{q}\neq 0$, and both $F$ and $G$ are
quadratic functions over $\mathbb{F}_{2^{n}}$. We first obtain a
characterization of the conditions for $f(x)$ such that $f(x)$ is an APN
function. With the help of this characterization, we obtain an infinite family
of APN functions for $n=2m$ with $m$ being an odd positive integer:
$f(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(b^{3}x^{9})$, where
$a\in\mathbb{F}_{2^{n}}$ such that $a+a^{q}\neq 0$ and $b$ is a non-cube in
$\mathbb{F}_{2^{n}}$. We verify that the aforementioned APN quadrinomials are
CCZ-inequivalent to any other known APN functions over $\mathbb{F}_{2^{10}}$.
We also obtain two infinite families of APN functions: $a{\rm
Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(gx^{5}+ex^{4q+1})$, where
$b,~{}g,~{}e$ satisfy: $i)$ $b$ not a cube, $g=1$, $e=\frac{1}{b^{2q-2}}$; or
$ii)$ $b$ not a cube, and $g=e=b$. We can also find (at least) two new
sporadic instances of APN functions over $\mathbb{F}_{2^{10}}$ up to CCZ-
equivalence.

Keywords: APN functions; relative trace functions; quadratic functions; CCZ-
equivalence

##  1 Introduction

Throughout this paper, we often identify the finite field $\mathbb{F}_{2^{n}}$
with $\mathbb{F}^{n}_{2}$ which is the $n$-dimensional vector space over
$\mathbb{F}_{2}$. Any function
$F:\mathbb{F}_{2^{n}}\rightarrow\mathbb{F}_{2^{m}}$ is called an
$(n,m)$-function or vectorial Boolean functions if the values $n$ and $m$ are
omitted. Vectorial Boolean functions are of critical importance in the field
of symmetric cryptography, and the security of encryption algorithms heavily
depends on the cryptographic properties of the vectorial Boolean functions.
Researchers have proposed various properties to measure the resistance of a
vectorial Boolean function to different kinds of cryptanalysis, including
differential uniformity, nonlinearity, boomerang uniformity, algebraic degree,
and so on. The lower the differential uniformity of a vectorial Boolean
function, the better its security against differential cryptanalysis. In this
paper, we mainly focus on the $(n,n)$-functions. The differential uniformity
of any such functions is at least 2, and the functions achieving this bound
are called almost perfect nonlinear (APN).

It is difficult to find new infinite families of APN functions up to CCZ-
equivalence. Up to now, only 6 infinite families of APN monomials and 14
infinite families of APN polynomials are known, since the early 90’s. On the
other hand, in contrast to these facts, there are a lot of APN functions even
over “small” field: for example, thousands of CCZ-inequivalent APN functions
have been found over $\mathbb{F}_{2^{8}}$ [25]. Constructing new instances of
infinite families is an area of deep heading research. We present Tables I and
II including all currently known infinite families of APN functions. To Table
II, we add the new function found with Theorem 3.3 in Section 3 below. We
refer the readers to a recent nice work of Budaghyan et al. for more details
on the classification of the known families of APN functions [7].

TABLE I: Known infinite families of APN power functions over $\mathbb{F}_{2^{n}}$ Family |  Exponent |  Conditions |  Algebraic degree |  Source
---|---|---|---|---
Gold |  $2^{i}+1$ |  ${\rm gcd}(i,n)=1$ |  2 |  [18]
Kasami |  $2^{2i}-2^{i}+1$ |  ${\rm gcd}(i,n)=1$ |  $i+1$ |  [19]
Welch |  $2^{t}+3$ |  $n=2t+1$ |  $3$ |  [14]
Niho |  |  $2^{t}+2^{t/2}-1$, $t$ even
---
$2^{t}+2^{(3t+1)/2}-1$, $t$ odd
$n=2t+1$ |  | $t/2+1$
---
$t+1$
[15]
Inverse |  $2^{2t}-1$ |  $n=2t+1$ |  $n-1$ |  [1, 22]
Dobbertin |  $2^{4i}+2^{3i}+2^{2i}+2^{i}-1$ |  $n=5i$ |  $i+3$ |  [16]

Throughout this paper, let $\omega\in\mathbb{F}_{4}\backslash\\{0,1\\}.$ Very
recently, Budaghyan, Helleseth, and Kaleyski introduced an infinite family of
quadrinomials over $\mathbb{F}_{2^{n}}$ of the following form:

$g_{s}(x)=x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot
2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}},$

where $n=2m$. They showed that this family can provide new infinite families
of APN functions [12]. More precisely, they showed that $g_{s}(x)$ is a new
APN function if $k=0$, $(s,a,b,c)=(m-2,\omega,\omega^{2},1)$, or
$((m-2)^{-1}~{}{\rm mod}~{}n,\omega,\omega^{2},1)$, if $m$ is odd with ${\rm
gcd}(3,m)=1$. They also pointed out that when $k\geq 1$, $g_{s}(x)$ can also
be APN, however, CCZ-equivalent to some known ones.

Let $n=2m$ and $q=2^{m}$. In this paper, our motivation is to find new
infinite families of APN functions over $\mathbb{F}_{2^{n}}$. We revisit the
above-mentioned two infinite families of APN quadrionomials obtained in [12].
Observing that for any odd positive integer $s$, $\omega^{2^{s}}=\omega^{2}$,
the APN functions for $s=m-2$, or $(m-2)^{-1}{\rm mod}~{}n$ can be rewritten
as $g_{s}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(cx^{2^{s}+1})$,
$a=\omega$, $b=c=\omega^{2}$. Here ${\rm Tr}^{n}_{m}(x):=x+x^{2^{m}}$ for
$n=2m$. Inspired by the quadrinomials and our observation, let
$a\in\mathbb{F}_{2^{n}}$, we study a class of functions with the following
form:

$f(x)=a{\rm Tr}^{n}_{m}(F(x))+a^{q}{\rm Tr}^{n}_{m}(G(x)),~{}a+a^{q}\neq 0,$
(1)

where $F$ and $G$ are quadratic functions with $F(0)=G(0)=0$.

Based on the framework (1), we carefully choose quadratic functions $F$ and
$G$ for finding APN functions. We mainly consider two kinds of functions in
(1) by setting $F$ and $G$ as follows.

$i)$ $F(x)=bx^{3}$, $G(x)=cx^{2^{s}+1}$;

$ii)$ $F(x)=bx^{2^{i}+1}+cx^{2^{i+m}+1}$, $G(x)=gx^{2^{s}+1}+ex^{2^{s+m}+1}$,
where $b,c,g,e\in\mathbb{F}_{2^{n}}$, and $i,s$ are positive integers.

Let $n=2m$ with $m$ odd. Let $a\in\mathbb{F}_{2^{n}}$, and

$f_{s}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(cx^{2^{s}+1}),~{}a+a^{q}\neq 0.$

We can find two more exponents $s=3$, or $m+2$, and the corresponding
conditions on the coefficients such that $f_{s}(x)$ is an APN function over
$\mathbb{F}_{2^{n}}$. Code isomorphism tests (see Sec. 2 below) indicate that
for the exponent $s=3$, the APN function found with Theorem 3.3:

$f_{3}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(b^{3}x^{9}),$

where $b$ is a non-cube, is new up to CCZ-equivalence over
$\mathbb{F}_{2^{10}}$. We can also discover more coefficients for these two
exponents $s=m-2$, and $(m-2)^{-1}{\rm mod}~{}n$ discovered by Budaghyan et
al. such that $f_{s}(x)$ is APN without the assumption that ${\rm
gcd}(3,m)=1$. In this way, some new instances of APN functions over
$\mathbb{F}_{2^{10}}$ and $\mathbb{F}_{2^{14}}$ of the form $f_{s}(x)$ can
also be found.

Let $n=2m$, $q=2^{m}$, $a\in\mathbb{F}_{2^{n}}$, and

$\displaystyle h_{i,s,b,c,g,e}(x)=a{\rm
Tr}^{n}_{m}(bx^{2^{i}+1}+cx^{2^{i+m}+1})+a^{q}{\rm
Tr}^{n}_{m}(gx^{2^{s}+1}+ex^{2^{s+m}+1}),~{}a+a^{q}\neq 0.$

We can find two infinite families of APN functions as follows, by letting
$i=1$, $s=2$, $c=0$.

$\displaystyle h_{1,2,b,0,g,e}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(gx^{5}+ex^{4q+1}),$

where $a\in\mathbb{F}_{2^{n}}$ such that $a+a^{q}\neq 0$, $m$ is odd, and
$b,~{}g,~{}e$ satisfy: $i)$ $b$ not cube, $g=1$, $e=\frac{1}{b^{2q-2}}$; or
$ii)$ $b$ not cube in $\mathbb{F}^{\ast}_{2^{n}}$, and $g=e=b$. By means of
the code isomorphism test, we find that these two classes of APN functions are
CCZ-inequivalent to each other, however, CCZ-equivalent to some functions in
family F12 of Taniguchi over $\mathbb{F}_{2^{10}}$. The critical technique
needed in the proof is to forge links between the cube-ness of some certain
elements and the number of solutions to the equation of the following form:

$\displaystyle Ax^{3}+Bx^{2}+B^{q}x+A^{q}=0.$

The rest of the paper is organized as follows. Some basic definitions are
given in Section 2. We characterize the condition for $f(x)$ with the form (1)
such that $f(x)$ is an APN function over $\mathbb{F}_{2^{n}}$, $n=2m$. In
Section 3, we investigate the APN property of the functions with the form (1)
by letting $F$, $G$ are both Gold functions or both quadratic binomials. We
can find a new infinite family of APN quadrinomials, and generalize the two
infinite families of APN functions found by Budaghyan et al. in [12]. We can
find two infinite families of APN hexanomials, which computationally proved
that they belong to family F12 over $\mathbb{F}_{2^{10}}$. We can also find
(at least) two new APN instances over $\mathbb{F}_{2^{10}}$. A few concluding
remarks are given in Section 4.

##  2 Preliminaries

Let $\mathbb{F}_{2^{n}}$ be the finite field consisting of $2^{n}$ elements,
then the group of units of $\mathbb{F}_{2^{n}}$, denoted by
$\mathbb{F}^{\ast}_{2^{n}}$, is a cyclic group of order $2^{n}-1$. Let
$\alpha\in\mathbb{F}_{2^{n}}.$ It is called a cube in $\mathbb{F}_{2^{n}}$, if
$\alpha=\beta^{3}$ for some $\beta\in\mathbb{F}_{2^{n}}$; otherwise, it is
called a non-cube. Let $m$ and $n$ be two positive integers satisfying
$m~{}|~{}n$, we use ${\rm Tr}^{n}_{m}(\cdot)$ to denote the trace function
form $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{m}}$, i.e., ${\rm
Tr}^{n}_{m}(x)=x+x^{2^{m}}+x^{2^{2m}}+\cdots+x^{2^{(n/m-1)m}}.$

Let $f(x)$ be a function over $\mathbb{F}_{2^{n}}$. Then it can be uniquely
represented as $f(x)=\sum^{2^{n}-1}_{i=0}a_{i}x^{i}$. This is the univariate
representation of $f$. Let $0\leq i\leq 2^{n}-1$. The binary weight of $i$ is
$w_{2}(i)=\sum^{n-1}_{s=0}i_{s}$, where $i=\sum^{n-1}_{s=0}i_{s}2^{s}$,
$i_{s}\in\\{0,1\\}$. The algebraic degree of $f$, denoted by ${\rm deg}(f)$,
is the largest binary weight of an exponent $i$ with $a_{i}\neq 0$ in the
univariate representation of $f$. Functions of algebraic degree one, and two
are called affine, quadratic, respectively.

Given an $(n,n)$-function $F$, we denote by $\Delta_{F}(a,b)$ the number of
solutions to the equation $D_{a}F(x)=b$, where $D_{a}F(x)=F(x)+F(x+a)$ is the
_derivative_ of $F$ in direction $a\in\mathbb{F}_{2^{n}}$. $F$ is called
_differentially $\delta$-uniform_ if the largest value of $\Delta_{F}(a,b)$
equals to $\delta$, for every nonzero $a$ and every $b$. If $F$ is
differentially 2-uniform, we say that $F$ is _almost perfect nonlinear_ (APN).

Two $(n,m)$-functions $F$ and $G$ are called extended affine equivalent (EA-
equivalent) if there exist some affine permutation $L_{1}$ over
$\mathbb{F}_{2^{n}}$ and some affine permutation $L_{2}$ over
$\mathbb{F}_{2^{m}}$, and some affine function $A$ such that $F=L_{2}\circ
G\circ L_{1}+A$. They are called Carlet-Charpin-Zinoviev equivalent (CCZ-
equivalent) if there exists some affine automorphism $L=(L_{1},L_{2})$ of
$\mathbb{F}_{2^{n}}\times\mathbb{F}_{2^{m}}$, where
$L_{1}:\mathbb{F}_{2^{n}}\times\mathbb{F}_{2^{m}}\rightarrow\mathbb{F}_{2^{n}}$
and
$L_{2}:\mathbb{F}_{2^{n}}\times\mathbb{F}_{2^{m}}\rightarrow\mathbb{F}_{2^{m}}$
are affine functions, such that $y=G(x)$ if and only if $L_{2}(x,y)=F\circ
L_{1}(x,y)$. It is well known that EA-equivalence is a special kind of CCZ-
equivalence, and that CCZ-equivalence preserves the differential uniformity
[13]. Proving CCZ-inequivalence of functions can be very difficult in general,
and this is resolved through code isomorphism. Let $\alpha$ be the primitive
element in $\mathbb{F}_{2^{n}}$. Then two $(n,n)$-functions functions $F$ and
$G$ are CCZ-equivalent if and only if $\mathcal{C}_{F}$, $\mathcal{C}_{G}$ are
isomorphic [3], where $\mathcal{C}_{F}$ is the linear code corresponding to
$F$ with the generating matrix as follows.

$\mathcal{C}_{F}=\left(\begin{array}[]{cccc}1&1&\cdots&1\\\
0&\alpha&\cdots&\alpha^{2^{n}-1}\\\
F(0)&F(\alpha)&\cdots&F(\alpha^{2^{n}-1})\\\ \end{array}\right)$

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

$\Delta_{d,f}(x):=f(dx)+f(dx+d)+f(d).$

Then it is well known that $f$ is APN if and only if for every $d\neq 0$,
$\Delta_{d,f}(x)=0$ only has trivial solutions in $x$, i.e., only
$x\in\mathbb{F}_{2}$ can be a solution to $\Delta_{d,f}(x)=0$.

In the following, we determine the APN-ness of the functions with the form
(1).

######  Lemma 2.1.

Let $n=2m$, and $q=2^{m}$. Let $F$, $G$ be quadratic functions over
$\mathbb{F}_{2^{n}}$ satisfying that $F(0)=0$, and $G(0)=0$. Let $f(x)=a{\rm
Tr}^{n}_{m}(F(x))+a^{q}{\rm Tr}^{n}_{m}(G(x)),$ where $a\in\mathbb{F}_{2^{n}}$
such that $a+a^{q}\neq 0$. Then $f(x)$ is APN over $\mathbb{F}_{2^{n}}$, if
and only if the following system

$\displaystyle\begin{cases}\Delta_{d,F}(x)\in\mathbb{F}_{2^{m}}&\\\
\Delta_{d,G}(x)\in\mathbb{F}_{2^{m}}&\end{cases}$ (2)

only has $x=0,1$ as its solutions for any $d\neq 0\in\mathbb{F}_{2^{n}}$.

###### Proof.

Since $f(x)$ is quadratic with $f(0)=0$, it is equivalent to showing that the
following equation only has $x=0,1$ as its solutions for any $d\neq 0$

$\Delta_{d,f}(x)=f(dx)+f(dx+d)+f(d)=0.$ (3)

We have

$\Delta_{d,f}(x)=a{\rm Tr}^{n}_{m}(\Delta_{d,F}(x))+a^{q}{\rm
Tr}^{n}_{m}(\Delta_{d,G}(x))=0.$ (4)

In the following, we shall show that (4) holds if and only if

${\rm Tr}^{n}_{m}(\Delta_{d,F}(x))={\rm Tr}^{n}_{m}(\Delta_{d,G}(x))=0.$

The sufficiency is clear. Let us show the necessity.

Raising (4) to its $q$-th power, we have

$a^{q}{\rm Tr}^{n}_{m}(\Delta_{d,F}(x))+a{\rm Tr}^{n}_{m}(\Delta_{d,G}(x))=0.$
(5)

Adding (4) and (5),

$(a+a^{q}){\rm Tr}^{n}_{m}(\Delta_{d,F}(x))+(a+a^{q}){\rm
Tr}^{n}_{m}(\Delta_{d,G}(x))=0,$

which infers, since $a+a^{q}\neq 0$, that

${\rm Tr}^{n}_{m}(\Delta_{d,F}(x))={\rm Tr}^{n}_{m}(\Delta_{d,G}(x)).$ (6)

Substituting (6) into (4), we can obtain

${\rm Tr}^{n}_{m}(\Delta_{d,F}(x))={\rm Tr}^{n}_{m}(\Delta_{d,G}(x))=0,$

which is exactly the system (2). Therefore, $f(x)$ is APN, if and only if the
system (2) only has trivial solutions $x=0,1$, for any $d\neq 0$. ∎

TABLE II: Known infinite families of quadratic APN polynomials over $\mathbb{F}_{2^{n}}$ ID |  Functions |  Conditions |  Source
---|---|---|---
F1-F2 |  $x^{2^{s}+1}+u^{2^{k}-1}x^{2^{ik}+2^{mk+s}}$ |  $n=pk$, ${\rm gcd}(k,p)={\rm gcd}(s,pk)=1$, $p\in\\{3,4\\}$, $i=sk~{}{\rm mod}~{}p$, $m=p-i$, $n\geq 12$, $u$ primitive in $\mathbb{F}^{\ast}_{2^{n}}$ |  [9]
F3 |  $sx^{q+1}+x^{2^{i}+1}+x^{q(2^{i}+1)}+dx^{2^{i}q+1}+d^{q}x^{2^{i}+q}$ |  $n=2m$, $q=2^{m}$, ${\rm gcd}(i,m)=1$, $d\in\mathbb{F}_{2^{n}}$, $s\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}$, $X^{2^{i}+1}+dX^{2^{i}}+d^{q}X+1$ has no solution $x$ s.t. $x^{q+1}=1$ |  [8, 7]
F4 |  $x^{3}+a^{-1}{\rm Tr}^{n}_{1}(a^{3}x^{9})$ |  $a\neq 0$ |  [10]
F5 |  $x^{3}+a^{-1}{\rm Tr}^{n}_{3}(a^{3}x^{9}+a^{6}x^{18})$ |  $3~{}|~{}n$, $a\neq 0$ |  [11]
F6 |  $x^{3}+a^{-1}{\rm Tr}^{n}_{3}(a^{6}x^{18}+a^{12}x^{36})$ |  $3~{}|~{}n$, $a\neq 0$ |  [11]
F7-F9 |  $ux^{2^{s}+1}+u^{2^{k}}x^{2^{-k}+2^{k+s}}+vx^{2^{-k}+1}+\omega u^{2^{k}+1}x^{2^{s}+2^{k+s}}$ |  $n=3k$, ${\rm gcd}(k,3)={\rm gcd}(s,3k)=1$, $v$, $\omega\in\mathbb{F}_{2^{k}}$, $v\omega\neq 1$, $3~{}|~{}(k+s)$, $u$ primitive in $\mathbb{F}^{\ast}_{2^{n}}$ |  [3, 4]
F10 |  $cx^{q+1}+dx^{2^{i}+1}+d^{q}x^{q(2^{i}+1)}+\sum^{m-1}_{s=1}\gamma_{s}x^{2^{s}(q+1)}$ |  $n=2m$, $q=2^{m}$, ${\rm gcd}(i,m)=1$, $i$, $m$ odd, $\gamma_{s}\in\mathbb{F}_{q}$, $c\notin\mathbb{F}_{q}$, $d$ not a cube |  [3]
F11 |  $(x+x^{q})^{2^{k}+1}+u^{\prime}(ux+u^{q}x^{q})^{(2^{k}+1)2^{i}}+u(x+x^{q})(ux+u^{q}x^{q})$ |  $n=2m$, $m\geq 2$ even, ${\rm gcd}(k,m)=1$, $q=2^{m}$, and $i\geq 2$ even, $u$ primitive in $\mathbb{F}^{\ast}_{2^{n}}$, $u^{\prime}\in\mathbb{F}_{2^{m}}$ not a cube |  [26]
F12 |  $u(u^{q}x+ux^{q})(x+x^{q})+(u^{q}x+ux^{q})^{2^{2i}+2^{3i}}+\alpha(u^{q}x+ux^{q})^{2^{2i}}(x+x^{q})^{2^{i}}+\beta(x+x^{q})^{2^{i}+1}$ |  $n=2m$, $q=2^{m}$, ${\rm gcd}(i,m)=1$, $u$ primitive in $\mathbb{F}^{\ast}_{2^{n}}$, $\alpha$, $\beta\in\mathbb{F}_{2^{m}}$, and $X^{2^{i}+1}+\alpha X+\beta$ has no solution in $\mathbb{F}_{2^{m}}$ |  [23]
F13 |  $L(x)^{2^{i}}x+L(x)x^{2^{i}}$ |  $n=km$, $m\geq 2$, ${\rm gcd}(n,i)=1$, $L(x)=\sum^{k-1}_{j=0}a_{j}x^{2^{jm}}$ satisfies the conditions in Theorem 6.3 of [6] |  [6]
F14 |  $x^{3}+\omega x^{2^{s}+1}+\omega^{2}x^{3q}+x^{(2^{s}+1)q}$ |  $n=2m$, $q=2^{m}$, $m$ odd, $3\nmid m$, $\omega$ primitive in $\mathbb{F}^{\ast}_{2^{2}}$, $s=m-2$, $(m-2)^{-1}~{}{\rm mod}~{}n$ |  [12]
F15 |  $a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(b^{3}x^{9})$ |  $n=2m$, $m$ odd, $q=2^{m}$, $a\notin\mathbb{F}_{q}$, $b$ not a cube |  new

##  3 Three infinite families of APN functions

We want to find new APN functions of the form (1). In the following two
subsections, the functions $F$ and $G$ were chosen very carefully to satisfy
the conditions characterized in Lemma 2.1. This will yield a new infinite
family of APN quadrinomails, two infinite families of APN hexanomials, and (at
least) two sporadic APN functions CCZ-inequivalent to any other known APN
functions over $\mathbb{F}_{2^{10}}$.

###  3-A F, G are both of Gold type

We need the following two lemmas, which will be used in the proof of Theorem
3.3.

######  Lemma 3.1.

Let $n=2m$ for $m$ odd, $q=2^{m}$. Suppose that for some
$c\in\mathbb{F}_{2^{n}}$ we have

$c^{3}(c+c^{2}+c^{4})^{q}\in\mathbb{F}_{2^{m}}.$

Then $c$ is a cube in $\mathbb{F}_{2^{n}}$.

###### Proof.

Since ${\rm gcd}(3,2^{m}-1)=1$, any element of $\mathbb{F}_{2^{m}}$ is a cube.
In the following, we assume that $c\notin\mathbb{F}_{2^{m}}$. Noting that
$c^{3}(c+c^{2}+c^{4})^{q}=c^{(q+1)+2}+c^{2(q+1)+1}+c^{3(q+1)+q}$, we have
$c^{q+1}(c+c^{q})^{2}+c^{2(q+1)}(c+c^{q})+c^{3(q+1)}(c+c^{q})=0$ by the
assumption that $c^{3}(c+c^{2}+c^{4})^{q}\in\mathbb{F}_{2^{m}}$. Since
$c+c^{q}\neq 0$, we have $c^{q+1}(c+c^{q})+c^{2(q+1)}+c^{3(q+1)}=0$, and hence
$c+c^{q}=c^{q+1}+c^{2(q+1)}$. Note that any nonzero element $c$ of
$\mathbb{F}_{2^{n}}$ has a unique polar decomposition of the form $c=vk$,
where $k^{q+1}=1$, and $v^{q-1}=1$. Substituting $c=vk$ into
$c+c^{q}=c^{q+1}+c^{2(q+1)}$, we have $k+k^{-1}=v+v^{3}$. By assumption that
$c\notin\mathbb{F}_{2^{m}}$, we have $k\neq 1$. Then according to [21, Theorem
7], we have that $k$ is a cube in
$U:=\\{x\in\mathbb{F}_{2^{n}}~{}|~{}x^{q+1}=1\\}$. Therefore, $c=vk$ is a cube
in $\mathbb{F}_{2^{n}}$. ∎

Let $s$ be a positive integer with ${\rm gcd}(s,n)=1$. Let
$x\in\mathbb{F}_{2^{n}}$. It is clear that $x+x^{2^{s}}\neq 0$, if and only if
$x\neq 0,1$. We have the following lemma.

######  Lemma 3.2.

Let $n=2m$ for $m$ odd with ${\rm gcd}(3,m)=1$. Let s be a positive integer
such that $3s\equiv 1~{}{\rm mod}~{}n$. Suppose that for some
$x\in\mathbb{F}_{2^{n}}\backslash\\{0,1\\}$, we have

$\frac{x+x^{2}}{(x+x^{2^{s}})^{2^{2s}-2^{s}+1}}\in\mathbb{F}_{2^{m}}.$

Then $x+x^{2^{s}}$ is a cube.

###### Proof.

Let $d=x+x^{2^{s}}$. Then $d\neq 0$, since $x\neq 0,1$, and ${\rm
gcd}(s,n)=1$. We can express $x+x^{2}=d+d^{2^{s}}+d^{2^{2s}}$. Then

$\frac{x+x^{2}}{(x+x^{2^{s}})^{2^{2s}-2^{s}+1}}=\frac{d+d^{2^{s}}+d^{2^{2s}}}{d^{2^{2s}-2^{s}+1}}=d^{-2^{s}(2^{s}-1)}+d^{-(2^{s}-1)^{2}}+d^{2^{s}-1}=A^{-2^{s}}+A^{-2^{s}+1}+A,$

where $A=d^{2^{s}-1}$. Then the condition of this lemma is equivalent to that
$A^{-2^{s}}+A^{-2^{s}+1}+A+1\in\mathbb{F}_{2^{m}},$ which is exaclty

$\frac{(A+1)^{2^{s}+1}}{A^{2^{s}}}\in\mathbb{F}_{2^{m}}.$

If $A=1$, i.e., $d^{2^{s}-1}=1$, then $d=1$, and hence $x+x^{2^{s}}=1$ is a
cube. In fact, since ${\rm gcd}(2^{s}-1,2^{n}-1)=1$, $g(x)=x^{2^{s}-1}$ is a
permutation of $\mathbb{F}_{2^{n}}$. Then by $g(d)=g(1)=1$, we have $d=1$. If
$A\neq 1$, then there exists some $\alpha\in\mathbb{F}^{\ast}_{2^{m}}$ such
that $A^{2^{s}}=(A+1)^{2^{s}+1}\alpha$. Since $s$ is odd, $3~{}|~{}2^{s}+1$,
we have $A^{2^{s}+1}\alpha$ is a cube, and hence $A^{2^{s}}$ is a cube, that
is, $A$ is a cube. However, note that ${\rm gcd}(3,2^{s}-1)=1$, we have that
$d$ is a cube, when $A=d^{2^{s}-1}$ is. ∎

In the following theorem, we investigate the APN property of the functions
with the form (1) by letting $F(x)=bx^{3}$, and $G(x)=cx^{2^{s}+1}$. This
allows us to find a new infinite family of APN quadrinomials $f(x)=a{\rm
Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(b^{3}x^{9})$, where $b$ is a non-
cube in $\mathbb{F}_{2^{n}}$.

######  Theorem 3.3.

Let $n=2m$ with $m\geq 1$ odd, and $q=2^{m}$. Let $a\in\mathbb{F}_{2^{n}}$,
and $f_{s}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(cx^{2^{s}+1})$
with $a\notin\mathbb{F}_{q}$, $bc\neq 0$, $s$ odd. Then $f_{s}(x)$ is APN over
$\mathbb{F}_{2^{n}}$, if $s,b,c$ satisfy the following

i) $s=m-2$, $b$ not a cube, $\frac{c^{4}}{b}\in\mathbb{F}_{2^{m}}$; or

ii) $s=(m-2)^{-1}~{}{\rm mod}~{}n$, $b$ not a cube,
$\frac{c^{2^{s}-1}}{b^{2^{2s}}}\in\mathbb{F}_{2^{m}}$; or

iii) $s=3$, $b$ not a cube, $\frac{c}{b^{3}}\in\mathbb{F}_{2^{m}}$; or

iv) ${\rm gcd}(3,m)=1$, $3s\equiv 1{\rm~{}mod~{}}n$, $b$ not a cube,
$\frac{c}{b^{2^{2s}-2^{s}+1}}\in\mathbb{F}_{2^{m}}$; or

v) $s=m$, $b$ not a cube, $c\notin\mathbb{F}_{2^{m}};$ or

vi) $s=m+2$, $b$ not a cube, $bc\in\mathbb{F}_{2^{m}}$; or

vii) $s=n-1$, $\frac{c^{2}}{b}\notin\mathbb{F}_{2^{m}}$.

###### Proof.

Let $F(x)=bx^{3}$, $G(x)=cx^{2^{s}+1}$. Then

$\Delta_{d,F}(x)=d^{3}b(x^{2}+x),~{}{\rm
and}~{}\Delta_{d,G}(x)=d^{2^{s}+1}c(x^{2^{s}}+x).$

According to Lemma 2.1, proving $f_{s}(x)$ is an APN function over
$\mathbb{F}_{2^{n}}$ is equivalent to showing that the system:
$\Delta_{d,F}(x)\in\mathbb{F}_{2^{m}}$, and
$\Delta_{d,G}(x)\in\mathbb{F}_{2^{m}}$ can only has trivial solutions $x=0,1$
for any $d\neq 0$. Assume, to the contrary, that $f_{s}(x)$ is not an APN
function, when $s,b,c$ satisfy the conditions of one item in this theorem.
Then the following system

$\displaystyle\begin{cases}d^{3}b(x^{2}+x)=\alpha,&\\\
d^{2^{s}+1}c(x^{2^{s}}+x)=\beta.&\end{cases}$ (7)

has a non-trivial solution $x\notin\mathbb{F}_{2}$ for some $d\neq 0$, where
$\alpha,~{}\beta\in\mathbb{F}_{2^{m}}$ with $\alpha\neq 0$.

Since $m$ is odd, ${\rm gcd}(3,2^{m}-1)=1$, we have that $\alpha=e^{3}$ for
some $e\in\mathbb{F}^{\ast}_{2^{n}}.$ Dividing both sides of the first
equation in (7) by $e^{3}$, we obtain that $(d/e)^{3}b(x^{2}+x)=1$. Dividing
both sides of the second equation in (7) by $e^{2^{s}+1}$, we have
$(d/e)^{2^{s}+1}c(x^{2^{s}}+x)=\beta e^{-(2^{s}+1)}$. Since $s$ is odd, we
have $3~{}|~{}2^{s}+1$, and $e^{2^{s}+1}\in\mathbb{F}_{2^{m}}.$ Therefore, the
system (7) has a non-trivial solution $x\notin\\{0,1\\}$ if and only if the
system

$\displaystyle\begin{cases}d^{3}b(x^{2}+x)=1,&\\\
d^{2^{s}+1}c(x^{2^{s}}+x)=\beta.&\end{cases}$ (8)

has a solution for some $d\in\mathbb{F}^{\ast}_{2^{n}}$ and
$\beta\in\mathbb{F}_{2^{m}}.$

$i)$ $s=m-2$, $b$ is a non-cube in $\mathbb{F}_{2^{n}}$ and
$\frac{c^{4}}{b}\in\mathbb{F}^{\ast}_{2^{m}}$.

Raising the second equation in (8) to its fourth power, we have
$d^{q+4}c^{4}(x^{q}+x^{4})=\beta^{4}$. From the first equation, we have
$d^{3}=\frac{1}{b(x^{2}+x)}$. Substituting this relation into the previous
equation, we have
$d^{q+1}\frac{c^{4}}{b}\frac{x^{q}+x^{4}}{x^{2}+x}\in\mathbb{F}_{2^{m}}$.
Since $d^{q+1}\in\mathbb{F}^{\ast}_{2^{m}}$, and
$\frac{c^{4}}{b}\in\mathbb{F}^{\ast}_{2^{m}}$ by assumption, we have
$\frac{x^{q}+x^{4}}{x+x^{2}}\in\mathbb{F}_{2^{m}}$. By [12, Lemma 1], we have
$x+x^{2}$ is a cube in $\mathbb{F}_{2^{n}}$, and hence $b$ is a cube by
$d^{3}b(x^{2}+x)=1$, a contradiction to the assumption that $b$ is a non-cube.

$ii)$ $s=(m-2)^{-1}~{}{\rm mod}~{}n$, $b$ is a non-cube in
$\mathbb{F}^{\ast}_{2^{n}}$ and
$\frac{c^{2^{s}-1}}{b^{2^{2s}}}\in\mathbb{F}^{\ast}_{2^{m}}$.

It can be seen from the proof of Theorem 2 in [12] that the critical
conditions ensuring the APN-ness of this $f_{s}(x)$ are exactly that $b$ is a
non-cube in $\mathbb{F}_{2^{n}}$ and
$\frac{c^{2^{s}-1}}{b^{2^{2s}}}\in\mathbb{F}^{\ast}_{2^{m}}$. We invite the
readers to check it, and we omit the arguments here.

$iii)$ $s=3$, $b$ is a non-cube in $\mathbb{F}_{2^{n}}$ and
$\frac{c}{b^{3}}\in\mathbb{F}^{\ast}_{2^{m}}.$

It can be seen that in this case (8) becomes

$\displaystyle\begin{cases}d^{3}b(x^{2}+x)=1,&\\\
d^{9}c(x^{8}+x)=\beta.&\end{cases}$

Substituting $d^{3}=\frac{1}{b(x+x^{2})}$ into the second equation of the
above system, we have

$\displaystyle\frac{c}{b^{3}}\cdot\frac{x+x^{8}}{(x+x^{2})^{3}}=\beta,$

which infers that $\frac{x+x^{8}}{(x+x^{2})^{3}}\in\mathbb{F}_{2^{m}}$, since
$\frac{c}{b^{3}}\in\mathbb{F}^{\ast}_{2^{m}}$ by assumption. It implies that
$(x+x^{2})^{3}(x+x^{8})^{q}\in\mathbb{F}_{2^{m}}$. Denoting $e=x+x^{2}$, we
have $x+x^{8}=e+e^{2}+e^{4}$, and hence
$e^{3}(e+e^{2}+e^{4})^{q}\in\mathbb{F}_{2^{m}}$. Now, according to Lemma 3.1,
$e=x+x^{2}$ is a cube. Then $b$ is a cube by $d^{3}b(x+x^{2})=1$, which
contradicts to the assumption that $b$ is a non-cube.

$iv)$ ${\rm gcd}(3,m)=1$, $3s\equiv 1{\rm~{}mod~{}}n$, $b$ is a non-cube in
$\mathbb{F}_{2^{n}}$ and
$\frac{c^{2^{2s}-2^{s}+1}}{b}\in\mathbb{F}^{\ast}_{2^{m}}$.

Since ${\rm gcd}(2^{s}-1,2^{n}-1)=2^{{\rm gcd}(s,n)}-1=1$, we have that
$x+x^{2^{s}}\neq 0$, when $x\neq 0,1$. Then (8) becomes

$\displaystyle\begin{cases}d^{2^{3s}+1}b(x+x^{2})=1,&\\\
d^{2^{s}+1}c(x+x^{2^{s}})=\beta,&\end{cases}$

where $\beta\in\mathbb{F}_{2^{m}}$ with $\beta\neq 0$, since $x+x^{2^{s}}\neq
0$. By the second equation, we have
$d^{2^{s}+1}=\frac{\beta}{c(x+x^{2^{s}})}$. Substituting this relation into
the first equation, noting that $2^{3s}+1=(2^{s}+1)(2^{2s}-2^{s}+1)$, we have

$\displaystyle\frac{b}{c^{2^{2s}-2^{s}+1}}\cdot\frac{x+x^{2}}{(x+x^{2^{s}})^{2^{2s}-2^{s}+1}}\in\mathbb{F}_{2^{m}},$

which infers, since $\frac{b}{c^{2^{2s}-2^{s}+1}}\in\mathbb{F}^{\ast}_{2^{m}}$
by assumption, that

$\displaystyle\frac{x+x^{2}}{(x+x^{2^{s}})^{2^{2s}-2^{s}+1}}\in\mathbb{F}^{\ast}_{2^{m}}.$
(9)

Now, by the assumption that $b$ is a non-cube in $\mathbb{F}_{2^{n}}$ and
$\frac{c^{2^{2s}-2^{s}+1}}{b}\in\mathbb{F}^{\ast}_{2^{m}}$, we have that $c$
is a non-cube. On the other hand, by (9) and Lemma 3.2, we have that
$x+x^{2^{s}}$ is a cube, which infers that $c$ is a cube from the second
equation $d^{2^{s}+1}c(x+x^{2^{s}})=\beta$ of the above system, a
contradiction.

$v)$ $s=m$, $b$ is a non-cube in $\mathbb{F}_{2^{n}}$, and
$c\notin\mathbb{F}_{2^{m}}.$

It can be seen that (8) becomes

$\displaystyle\begin{cases}d^{3}b(x+x^{2})=1,&\\\
d^{2^{m}+1}c(x+x^{2^{m}})=\beta,&\end{cases}$

where $\beta\in\mathbb{F}_{2^{m}}$. Since $c\notin\mathbb{F}_{2^{m}}$, and
$d^{2^{m}+1}\in\mathbb{F}^{\ast}_{2^{m}},$ $x+x^{2^{m}}\in\mathbb{F}_{2^{m}}$
for any $d\neq 0$, $x\in\mathbb{F}_{2^{n}}$, by the second equation, we have
$\beta$ must equal to zero, which infers that $x\in\mathbb{F}_{2^{m}}$. Then
by the fact that any element of $\mathbb{F}_{2^{m}}$ is a cube, we have
$d^{3}(x+x^{2})$ is a cube in $\mathbb{F}^{\ast}_{2^{n}}$, which implies that
$b$ is a cube in $\mathbb{F}^{\ast}_{2^{n}}$, a contradiction to the
assumption that $b$ is a non-cube.

$vi)$ $s=m+2$, $b$ is a non-cube in $\mathbb{F}_{2^{n}}$ and
$bc\in\mathbb{F}^{\ast}_{2^{m}}$. It can be seen (8) becomes

$\displaystyle\begin{cases}d^{3}b(x+x^{2})=1,&\\\
d^{4(q+1)-3}c(x+x^{4q})=\beta,&\end{cases}$

where $\beta\in\mathbb{F}_{2^{m}}$ with $\beta\neq 0$ since $x+x^{4q}\neq 0$
when $x\neq 0,1$. Since $d^{3}b(x+x^{2})=1$, we have
$d^{3}=\frac{1}{b(x+x^{2})}$. Substituting this relation into the second
equation, we have

$\displaystyle d^{4(q+1)}bc(x+x^{2})(x+x^{4q})=\beta.$

Then by the assumption that $bc\in\mathbb{F}^{\ast}_{2^{m}}$, we have
$(x+x^{2})(x+x^{4q})\in\mathbb{F}_{2^{m}}$. According to [12, Lemma 1], we
have $x+x^{2}\neq 0$ is a cube, which infers that $b$ is a cube by
$d^{3}b(x+x^{2})=1$, a contradiction to the assumption that $b$ is a non-cube.

$vii)$ $s=n-1$, $\frac{c^{2}}{b}\notin\mathbb{F}_{2^{m}}$.

Since ${\rm gcd}(2^{s}-1,2^{n}-1)=2^{{\rm gcd}(s,n)}-1=1$, we have that
$x+x^{2^{s}}\neq 0$, if $x\neq 0,1$. It can be seen that (8) becomes

$\displaystyle\begin{cases}d^{3}b(x+x^{2})=1,&\\\
d^{2^{s}+1}c(x+x^{2^{s}})=\beta,&\end{cases}$

where $\beta\in\mathbb{F}_{2^{m}}$ with $\beta\neq 0$. Squaring the second
equation, we have $d^{3}c^{2}(x+x^{2})=\beta^{2}$. Comparing with the first
equation, we have $\frac{c^{2}}{b}=\beta^{2}\in\mathbb{F}_{2^{m}}$, which
contradicts with the assumption that
$\frac{c^{2}}{b}\notin\mathbb{F}_{2^{m}}.$ ∎

######  Remark 3.4.

Code isomorphism tests described in Section 2 suggest that all the polynomials
from the same item of Theorem 3.3 are all CCZ-equivalent; the APN function
$x^{3}+\omega x^{2^{s}+1}+\omega^{2}x^{3q}+x^{(2^{s}+1)q}$ discovered in [12]
is CCZ-equivalent to all the functions in i), ii), respectively, for $s=m-2$,
and $s=(m-2)^{-1}~{}{\rm mod}~{}n$, if ${\rm gcd}(3,m)=1$; the polynomials
$f_{s}(x)$ for $s=m+2$ in vi) are equivalent to the ones for $s=m-2$ in i);
the polynomials $f_{s}(x)$ for $s=m$ in v) are equivalent to some functions in
family F10 from Table II, see also the arguments in Remark 3.7 below; the
polynomial $f_{s}(x)$ for $s=n-1$ in vii) is CCZ-equivalent to $x^{3}$.

The remaining value of $s=3$ in iii) yields APN quadrinomials $f_{3}(x)$,
which are CCZ-inequivalent to any currently known APN function over
$\mathbb{F}_{2^{10}}$. By the arguments above that all the polynomials in the
same item are all CCZ-equivalent, we only take a representative of iii). We
let $f_{3}(x)=\omega{\rm Tr}^{n}_{m}(bx^{3})+\omega^{2}{\rm
Tr}^{n}_{m}(b^{3}x^{9})$, where $b$ is a non-cube,
$\omega\in\mathbb{F}_{2^{2}}\backslash\mathbb{F}_{2}$. We use this $f_{3}(x)$
to compare against representatives from all the known infinite families
including $f_{s}(x)$, $s=m-2$, $(m-2)^{-1}~{}{\rm mod}~{}n$ in i), ii) which
are essentially due to Budaghyan, Helleseth, and Kaleyski ([12]). Note that,
Budaghyan et al. had presented a table listing all the representatives, except
family F12, of all the known CCZ-inequivalent APN functions over
$\mathbb{F}_{2^{10}}$, see Table III of [12]. To complete the work of code
isomorphism test, we have to find all the representatives of F12 over
$\mathbb{F}_{2^{10}}$. Thanks to the nice work [20], we can obtain these
representatives. In fact, let $\gamma$ be a primitive element in
$\mathbb{F}^{\ast}_{2^{5}}$, according to [20, Theorem 4.5], there are exactly
6 of CCZ-inequivalent Taniguchi APN functions from F12: $i=1$, take
$\alpha=1$, $\beta=1,~{}\gamma^{7},~{}\gamma^{11}$; $i=2$, take $\alpha=1$,
$\beta=1,~{}\gamma^{3},~{}\gamma^{15}$. The notations $i,~{}\alpha,~{}\beta$
used here are the same as the ones used in family F12 of Table II.

######  Remark 3.5.

Let $n=2m$ with $m$ odd, and ${\rm gcd}(m,3)=1$. Let $q=2^{m}$. Let $z$ be a
primitive element in $\mathbb{F}^{\ast}_{2^{n}}$, and
$\omega=z^{\frac{2^{n}-1}{3}}$. Then $\omega$ is a primitive element in
$\mathbb{F}_{2^{2}}$. Let $s=m-2$ or $(m-2)^{-1}{\rm~{}mod}~{}n$. Then
$g_{s}(x)=x^{3}+\omega x^{2^{s}+1}+\omega^{2}x^{3q}+x^{(2^{s}+1)q}$ is an APN
function ([12]). It can be seen that $g_{s}(x)$ can be covered by our theorem.
In fact, noting that $\omega^{2^{s}}=\omega^{2}$ for any odd $s$,
$g_{s}(x)=\omega{\rm Tr}^{n}_{m}(\omega^{2}x^{3})+\omega^{2}{\rm
Tr}^{n}_{m}(\omega^{2}x^{2^{s}+1})=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(cx^{2^{s}+1})$, where $a=\omega,b=c=\omega^{2}$. It is clear that
$a+a^{q}=1\neq 0$, and $b=\omega$ is a non-cube since ${\rm gcd}(m,3)=1$, and
$\frac{c^{4}}{b}=1=\frac{c^{2^{t}-1}}{b^{2^{2t}}}$, where
$t=(m-2)^{-1}{\rm~{}mod}~{}n$. Then by $i)$, $ii)$ of the above theorem, we
have that $g_{s}(x)$ is APN over $\mathbb{F}_{2^{n}}$, for $s=m-2$, and
$(m-2)^{-1}{\rm~{}mod}~{}n$, respectively.

######  Remark 3.6.

Let $n=2m$ with $m$ odd. Let us investigate the APN property of $f_{m-2}(x)$
further. A pair ($b,c$) is said to satisfy property $\mathbf{P}_{m-2}$, if $b$
is a cube in $\mathbb{F}^{\ast}_{2^{n}}$, and $c\in\mathbb{F}^{\ast}_{2^{n}}$
such that the following assertion holds:

For any $x\in\mathbb{F}_{2^{n}}$ with $x\neq 0,1$, $x+x^{2}$ is a non-cube in
$\mathbb{F}_{2^{n}}$, if
$\frac{c^{4}}{b}\cdot\frac{x^{q}+x^{4}}{x+x^{2}}\in\mathbb{F}_{2^{m}}$.

Then $f_{m-2}(x)$ is APN over $\mathbb{F}_{2^{n}}$ for these $b$, $c$. In
fact, this assertion can be seen from the proof of $i)$ in the above theorem.
With the help of computer, we find that when $m=5$, $7$, there exist a lot of
pairs ($b,c$) satisfying $\mathbf{P}_{m-2}$. More precisely, let $m=5$ or $7$,
$z$ be a primitive element in $\mathbb{F}^{\ast}_{2^{2m}}$,
$j=\frac{(2^{m}+1)}{3}$, and $U=\\{(z^{j})^{i}~{}|~{}{\rm gcd}(3,i)=1,~{}1\leq
i\leq 2^{n}-1\\}$. Then any pair ($b,c$) with $b\neq 0$ a cube, and
$\frac{c^{4}}{b}\in U$ satisfies $\mathbf{P}_{m-2}$. However, when $m=9$,
$11$, there does not exist such ($b,c$). We therefore propose the following:

Open Problem 1. Does there exist infinite odd integer $m\geq 1$ such that
$\mathbf{P}_{m-2}$ holds?

######  Remark 3.7.

Let $n=2m$ with $m$ odd, and $q=2^{m}$. Let us revisit the function
$f_{m}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm Tr}^{n}_{m}(cx^{2^{m}+1})$
investigated in $v)$. Replacing $bx^{3}$ by $bx^{2^{i}+1}$, we let $f(x)=a{\rm
Tr}^{n}_{m}(bx^{2^{i}+1})+a^{q}{\rm Tr}^{n}_{m}(cx^{2^{m}+1})$, where $i$ is
an odd positive integer with ${\rm gcd}(i,m)=1$. With similar arguments, by
$3~{}|~{}2^{i}+1$ and ${\rm gcd}(i,m)=1$, we can obtain that $f(x)$ is APN, if
$b$ is a non-cube in $\mathbb{F}_{2^{n}}$, and $c\notin\mathbb{F}_{2^{m}}$.
Note that $\frac{1}{a}f(x)=dx^{2^{m}+1}+{\rm Tr}^{n}_{m}(bx^{2^{i}+1})$, where
$d=a^{q-1}(c+c^{q})$ can be chosen as any element in
$\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}$, since
$a,~{}c\notin\mathbb{F}_{q}$, we have that $f(x)$ in fact are exactly the
functions in family F10 up to EA-equivalence. This observation suggests that
it is worthy to finding APN functions with the following form:

$\displaystyle f_{i,s}(x)=a{\rm Tr}^{n}_{m}(bx^{2^{i}+1})+a^{q}{\rm
Tr}^{n}_{m}(cx^{2^{s}+1}),~{}\text{where~{}}a\in\mathbb{F}_{2^{n}}~{}such~{}that~{}a+a^{q}\neq
0,~{}n=2m~{}\text{is a positive integer}.$ (10)

######  Remark 3.8.

It is noted that there does not exist elements satisfying the conditions in
$iv)$. However, we decide to preserve this item, because we feel that the
technique used in the proof may provide some insights for the constructions of
APN functions.

###  3-B F, G are both quadratic binomials

Let us consider more general case. Let $n=2m$ with $m$ a positive integer. Let

$\displaystyle h_{i,s,b,c,g,e}(x)=a{\rm
Tr}^{n}_{m}(bx^{2^{i}+1}+cx^{2^{i+m}+1})+a^{q}{\rm
Tr}^{n}_{m}(gx^{2^{s}+1}+ex^{2^{s+m}+1}),$ (11)

where $a\in\mathbb{F}_{2^{n}}$ such that $a+a^{q}\neq 0$,
$b,c,g,e\in\mathbb{F}_{2^{n}}$.

In this subsection, we want to find APN functions of the form (11). We remark
first that the APN polynomials considered in family F3 can be covered by
$h_{i,s,b,c,g,e}(x)$. In fact, let $i=m$, $b\notin\mathbb{F}_{2^{m}}$, $c=0$,
$g=1$, then (11) becomes
$a^{q-1}(b+b^{q})x^{q+1}+x^{2^{s}+1}+x^{(2^{s}+1)q}+ex^{2^{s}q+1}+e^{q}x^{2^{s}+q}$,
which are exactly the functions in F3, since $a^{q-1}(b+b^{q})$ can be choosen
as any elements in $\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}$.

We can find two infinite families of APN functions with the above form (11),
and computationally prove that they are CCZ-inequivalent to any APN power
functions over $\mathbb{F}_{2^{10}}$, and we can find a new sporadic instance
of APN functions over $\mathbb{F}_{2^{10}}$.

######  Theorem 3.9.

[24] Let $n=2m$, and $a\in\mathbb{F}^{\ast}_{2^{n}}$. Let $t_{1}$ be one
solution in $\mathbb{F}_{2^{n}}$ of $t^{2}+at+1=0$ (if ${\rm
Tr}^{n}_{1}\Big{(}\frac{1}{a^{2}}\Big{)}=0$). Let $f(x)=x^{3}+x+a$, then

$\bullet$ $f$ has no zeros in $\mathbb{F}_{2^{n}}$ if and only if ${\rm
Tr}^{n}_{1}\Big{(}\frac{1}{a^{2}}\Big{)}=0$, and $t_{1}$ is not a cube in
$\mathbb{F}_{2^{n}}$.

$\bullet$ $f$ has three zeros in $\mathbb{F}_{2^{n}}$ if and only if ${\rm
Tr}^{n}_{1}\Big{(}\frac{1}{a^{2}}\Big{)}=0$, and $t_{1}$ is a cube in
$\mathbb{F}_{2^{n}}$.

We need the following theorem, which will be used for generating APN functions
(see Corollary 1). Let $n=2m$ with $m$ being an odd positive integer, and
$q=2^{m}$. Let $x\in\mathbb{F}_{2^{n}}$ with $x\neq 0,1$. Then fix the
following notations for this given element $x$.

$\displaystyle r:=x^{q+1};~{}h:=x+x^{q};~{}c:=x+x^{2};$ $\displaystyle
D:=A(A^{q+1}+B^{q+1});~{}H:=A^{2}(A^{q}B^{3}+AB^{3q}+B^{2+2q}),$

where $A,B$ are some elements determined by $x$. By a routine work, we have
that

$\displaystyle h+h^{2}=c+c^{q}.$

The following result can not only give rise to APN functions of the form (11)
but can also yield Budaghyan-Carlet APN hexanomials (family F3), and hence it
has its own importance and we state it as a theorem. The proof can be seen in
the appendix.

######  Theorem 3.10.

Let $n=2m$ with $m$ being an odd positive integer. Let $x$ be any given
element in $\mathbb{F}_{2^{n}}\backslash\\{0,1\\}$. Use the notations given as
above. Let

$\displaystyle f(y)=Ay^{3}+By^{2}+B^{q}y+A^{q}=0.$ (12)

Then equation (12) has no solutions in $\mathbb{F}_{2^{n}}$, if A, B, c
satisfy

1) $A=c^{2-2q}(h+c+c^{2})$, $B=c+c^{2}$, and $c=x+x^{2}$ is a non-cube in
$\mathbb{F}_{2^{n}}$; or

2) $A=\frac{h+c+c^{2}}{c^{q}}$, $B=1+c$, and $c=x+x^{2}$ is a non-cube in
$\mathbb{F}_{2^{n}}$.

######  Remark 3.11.

Let $n=2m$, and $q=2^{m}$. Recall first that the condition needed in family F3
is that

$\displaystyle y^{2^{i}+1}+dy^{2^{i}}+d^{q}y+1=0$ (13)

has no solutions in $U=\\{x\in\mathbb{F}_{2^{n}}~{}|~{}x^{q+1}=1\\}$. Here $i$
is a positive integer with ${\rm gcd}(i,m)=1$. When $i=1$, this condition is
exactly that $y^{3}+dy^{2}+d^{q}y+1=0$ has no solutions in $U$.

With the same notations as in Theorem 3.10. Let $A$ be the elements given in
1) or 2). Let
$\Gamma=\\{A\in\mathbb{F}^{\ast}_{2^{m}}~{}|~{}x\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}},~{}c=x+x^{2}~{}\text{not
cube}\\}$. Numerical experiments suggest that $\Gamma$ is always nonempty for
any odd $m$. This can yield Budaghyan-Carlet APN functions in family F3. In
fact, let $A\in\Gamma$, then (12) becomes

$\displaystyle y^{3}+dy^{2}+d^{q}y+1=0,~{}d=\frac{B}{A}.$

According to Theorem 3.10, the above equation has no solutions in
$\mathbb{F}_{2^{n}}$. Therefore, this theorem can be used to yield APN
functions in family F3. It is noted that the existence of the coefficients $d$
such that the equation (13) has no solutions in $U$ (or $\mathbb{F}_{2^{n}}$)
for a given positive integer $i$ had also been studied in [2, 5].We expect
that $\Gamma$ does indeed empty for any odd positive integer $m$, and hence
propose the following:

Open problem 2. Let $n=2m$ with $m$ odd. Show that $\Gamma$ is always
nonempty.

It is also interesting and important to consider the following question.

Open problem 3. Let $n=2m$ with $m$ a positive integer, $q=2^{m}$. Let $i$ be
a positive with ${\rm gcd}(m,i)=1$. Find more exponents $i$, and elements
$A,B$ such that the following equation has no solutions in
$\mathbb{F}_{2^{n}}$.

$\displaystyle Ay^{2^{i}+1}+By^{2^{i}}+B^{q}y+A^{q}=0.$

In the following, we investigate the APN property of the functions with the
form (11) by letting $i=1,c=0$. We does indeed find two infinite families of
APN functions. But, astonishingly enough, the function obtained happened to be
CCZ-equivalent to some functions in family F12 with a completely different
from that of Taniguchi.

######  Corollary 1.

Let $n=2m$ be a positive integer with $m$ odd, and $q=2^{m}$. Let
$h_{s}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(gx^{2^{s}+1}+ex^{2^{s+m}+1})$ with $a\notin\mathbb{F}_{q}$,
$bge\neq 0$. Then $h_{s}(x)$ is APN over $\mathbb{F}_{2^{n}}$, if $s,b,g,e$
satisfy

$\displaystyle 1)$
$\displaystyle~{}~{}~{}s=2,~{}b{\rm~{}is~{}not~{}a~{}cube},~{}g=1,~{}e=\frac{1}{b^{2q-2}};{~{}~{}\rm
or}$ $\displaystyle 2)$
$\displaystyle~{}~{}~{}s=2,~{}b{\rm~{}is~{}not~{}a~{}cube},~{}g=e=b.$

###### Proof.

1) $s=2$, $b$ is not a cube, $g=1$, $e=\frac{1}{b^{2q-2}}$.

Let $F(x)=bx^{3}$, $G(x)=x^{2^{s}+1}+ex^{2^{s+m}+1}$. Then we have

$\displaystyle\Delta_{d,F}=d^{3}b(x+x^{2}),~{}\Delta_{d,G}=d^{2^{s}+1}(x+x^{2^{s}})+d^{2^{s+m}+1}e(x+x^{2^{s+m}}).$

According to Lemma 2.1, we have that $h_{s}(x)$ is APN if the following system

$\displaystyle\begin{cases}d^{3}b(x+x^{2})=\alpha&\\\
d^{2^{s}+1}(x+x^{2^{s}})+d^{2^{s+m}+1}e(x+x^{2^{s+m}})=\beta&\end{cases}$

only has $x=0,1$ as its solutions for any $d\neq 0$, where $\alpha$,
$\beta\in\mathbb{F}_{2^{m}}.$ Assume, to the contrary, that there exists some
$d\neq 0$, $x\neq 0,1$ such that the above system holds. Now let $s=2$, $b$ is
a non-cube, $e=\frac{1}{b^{2q-2}}$. Then $\alpha\neq 0$,
$b=\frac{\alpha}{d^{3}(x+x^{2})}$, $e=b^{-(2q-2)}=d^{6q-6}(x+x^{2})^{2q-2}$
(note that $\alpha^{2q-2}=1$). Substituting it into the second equation of the
above system, we have

$\displaystyle d^{5}(x+x^{4})+d^{10q-5}(x+x^{2})^{2q-2}(x+x^{4q})=\beta,$

which is equivalent to

$\displaystyle
d^{5}(x+x^{4})+d^{10q-5}(x+x^{2})^{2q-2}(x+x^{4q})+\Big{(}d^{5}(x+x^{4})+d^{10q-5}(x+x^{2})^{2q-2}(x+x^{4q})\Big{)}^{q}=0.$
(14)

Let $u=d^{5}$. Then the above equation becomes

$\displaystyle
u(x+x^{4})+u^{2q-1}(x+x^{2})^{2q-2}(x+x^{4q})+\Big{(}u(x+x^{4})+u^{2q-1}(x+x^{2})^{2q-2}(x+x^{4q})\Big{)}^{q}=0.$
(15)

Note that any nonzero element $u$ of $\mathbb{F}_{2^{n}}$ has a unique polar
decomposition of the form $u=vk$, where $v^{q+1}=1$, and $k^{q-1}=1$.
Substituting $u=vk$ into (15), then (15) can be reduced as

$\displaystyle
v(x+x^{4})+v^{2q-1}(x+x^{2})^{2q-2}(x+x^{4q})+\Big{(}v(x+x^{4})+v^{2q-1}(x+x^{2})^{2q-2}(x+x^{4q})\Big{)}^{q}=0.$

Multiplying both sides by $v^{3}$ of the above equation, by the fact that
$v^{q}=v^{-1}$, we have

$\displaystyle Ay^{3}+By^{2}+B^{q}y+A^{q}=0,$

where $y=v^{2}\in\mathbb{F}_{2^{n}}$, and $A$, $B$ are given in 1) of Theorem
3.10. Now, according to 1) of Theorem 3.10, we obtian that the element
$x+x^{2}$ is a cube, and hence $b$ is a cube from the first equation
$d^{3}b(x+x^{2})=\alpha$ of the system, since
$\alpha\in\mathbb{F}^{\ast}_{2^{m}}$ is a cube. This derives a contradiction
to the assumption that $b$ is a non-cube.

2) $s=2$, $b$ is not a cube, $g=e=b$.

Let $F(x)=bx^{3}$ and $G(x)=bx^{5}+bx^{4q+1}$. We have

$\displaystyle\Delta_{d,F}(x)=d^{3}b(x+x^{2})\hskip 5.69046pt{\rm and}\hskip
5.69046pt\Delta_{d,G}(x)=d^{5}b(x+x^{4})+d^{4q+1}b(x+x^{4q}).$

By Lemma 2.1, $h_{s}(x)$ is APN if and only if the following system

$\displaystyle\begin{cases}d^{3}b(x+x^{2})=\alpha\\\
d^{5}b(x+x^{4})+d^{4q+1}b(x+x^{4q})=\beta\end{cases}$

only has trivial solutions $x\in\mathbb{F}_{2}$ for any
$d\in\mathbb{F}_{2^{n}}^{*}$ and $\alpha,\beta\in\mathbb{F}_{2^{m}}$. Assume
now that there exist some $d\in\mathbb{F}_{2^{n}}^{*}$,
$\alpha\in\mathbb{F}_{2^{m}}$, $\beta\in\mathbb{F}_{2^{m}}$ such that the
system has non-trivial solutions
$x\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2}$. Then $\alpha\neq 0$. By the
first equation, we have $b=\frac{\alpha}{d^{3}(x+x^{2})}$. Substituting this
relation into the second equation, we have

$\displaystyle\frac{d^{2}(x+x^{4})}{x+x^{2}}+\frac{d^{4q-2}(x+x^{4q})}{x+x^{2}}=\frac{\beta}{\alpha},$

which implies that

$\displaystyle\frac{d^{2}(x+x^{4})}{x+x^{2}}+\frac{d^{4q-2}(x+x^{4q})}{x+x^{2}}+\bigg{(}\frac{d^{2}(x+x^{4})}{x+x^{2}}+\frac{d^{4q-2}(x+x^{4q})}{x+x^{2}}\bigg{)}^{q}=0,$

since $\alpha,~{}\beta\in\mathbb{F}_{2^{m}}$. Let $\mu=d^{2}$. We have

$\displaystyle\frac{\mu(x+x^{4})}{x+x^{2}}+\frac{\mu^{2q-1}(x+x^{4q})}{x+x^{2}}+\bigg{(}\frac{\mu(x+x^{4})}{x+x^{2}}+\frac{\mu^{2q-1}(x+x^{4q})}{x+x^{2}}\bigg{)}^{q}=0.$
(16)

To complete the proof, it suffices to show that $x+x^{2}$ is a cube of
$\mathbb{F}_{2^{n}}$, which will derive that $b$ is a cube from the first
equation of the above system and this will yield a contradiction to the
assumption that $b$ is a non-cube. Let $\mu=\nu k$, where $\nu^{q+1}=1$ and
$k\in\mathbb{F}_{2^{m}}^{*}$, and substitute $\mu=\nu k$ into (16), we have

$\displaystyle\frac{\nu(x+x^{4})}{x+x^{2}}+\frac{\nu^{2q-1}(x+x^{4q})}{x+x^{2}}+\bigg{(}\frac{\nu(x+x^{4})}{x+x^{2}}+\frac{\nu^{2q-1}(x+x^{4q})}{x+x^{2}}\bigg{)}^{q}=0.$

Multiplying both sides of the above equation by $\nu^{3}$, we have

$\displaystyle Ay^{3}+By^{2}+B^{q}y+A^{q}=0,$

where $y=\nu^{2}$, $A=\Big{(}\frac{x+x^{4q}}{x+x^{2}}\Big{)}^{q}$ and
$B=\frac{x+x^{4}}{x+x^{2}}=1+x+x^{2}$. According to 2) of Theorem 3.10,
$x+x^{2}$ is a cube in $\mathbb{F}_{2^{n}}$, otherwise, the above equation has
no solutions in $\mathbb{F}_{2^{n}}$. ∎

Example 1. Besides the two infinite classes of APN functions presented in
Corollary 1, we can also find a new instance of APN functions over
$\mathbb{F}_{2^{10}}$ CCZ-inequivalent to any other known APN functions. Let
$z$ be a primitive element in $\mathbb{F}^{\ast}_{2^{10}}$. Then

$\displaystyle h_{s}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(gx^{5}+ex^{4q+1})$

is an APN function over $\mathbb{F}_{2^{10}}$, where $b=1$, $g=z$,
$e=z^{369}$.

TABLE III: All Known CCZ-inequivalent APN functions over $\mathbb{F}_{2^{10}}$, $q=2^{5}$ Function |  Conditions |  Family
---|---|---
$x^{2^{i}+1}$ |  $i=1,3$ |  Gold
$x^{57}$ |  $-$ |  Kasami
$x^{339}$ |  $-$ |  Dobbertin
$x^{6}+x^{33}+\alpha^{31}x^{192}$ |  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$ |  F3
$x^{33}+x^{72}+\alpha^{31}x^{258}$ |  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$ |  F3
$x^{3}+{\rm Tr}^{10}_{1}(x^{9})$ |  $-$ |  F4
$x^{3}+\alpha^{-1}{\rm Tr}^{10}_{1}(\alpha^{3}x^{9})$ |  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$ |  F4
| $u(u^{q}x+ux^{q})(x+x^{q})+$
---
$(u^{q}x+ux^{q})^{2^{2i}+2^{3i}}+$
$\alpha(u^{q}x+ux^{q})^{2^{2i}}(x+x^{q})^{2^{i}}+$
$\beta(x+x^{q})^{2^{i}+1}$
|  $u$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$,
---
$z$ primitive in $\mathbb{F}^{\ast}_{2^{5}}$,
$i=1$, $\alpha=1$, $\beta=1,z^{7},z^{11}$;
$i=2$, $\alpha=1$, $\beta=1,z^{3},z^{15}$
F12
$B(x)=x^{3}+\alpha^{341}x^{36}$ |  $-$ |  sporadic, see [17]
|  $x^{3}+\omega x^{2^{s}+1}+$$\omega^{2}x^{3q}+x^{(2^{s}+1)q}$
---
|  $s=3,7,$ $\omega$ primitive in $\mathbb{F}^{\ast}_{2^{2}}$
---
F14
| $\alpha{\rm Tr}^{n}_{m}(\alpha x^{3})+\alpha^{q}{\rm
Tr}^{n}_{m}(\alpha^{3}x^{9})$
---
|  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$
---
F15
| $\alpha{\rm Tr}^{n}_{m}(x^{3})+\alpha^{q}{\rm Tr}^{n}_{m}(\alpha^{11}x^{9})$
---
|  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$
---
| sporadic, see
---
Remark 3.6
| $\alpha{\rm Tr}^{n}_{m}(x^{3})+\alpha^{q}{\rm Tr}^{n}_{m}(\alpha
x^{5}+\alpha^{369}x^{4q+1})$
---
|  $\alpha$ primitive in $\mathbb{F}^{\ast}_{2^{10}}$
---
| sporadic, see
---
Example 1

##  4 Conclusions

Let $n=2m$, and $q=2^{m}$. We studied a class of quadratic functions with the
form $f(x)=a{\rm Tr}^{n}_{m}(F(x))+a^{q}{\rm Tr}^{n}_{m}(G(x))$, where $F$,
$G$ are quadratic functions. We found a new infinite family of APN
quadrinomials over $\mathbb{F}_{2^{n}}$, $a\in\mathbb{F}_{2^{n}}$, $n=2m$ with
$m$ odd as follows.

$\displaystyle f_{1}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(b^{3}x^{9}),~{}b\text{~{}not~{}a~{}cube},~{}a\notin\mathbb{F}_{q}.$

We generalized the two infinite families of APN functions obtained in [12] to
a broader condition on $m$, that is, the assumption that ${\rm gcd}(3,m)=1$
needed in [12] can be removed, up to CCZ-equivalence. We also found two
infinite families of APN functions over $\mathbb{F}_{2^{2m}}$ for odd $m$,
which turned out to be in family F12, that is, the the Taniguchi APN functions
when $m=5$, as follows.

$\displaystyle f_{2}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(x^{5}+\frac{1}{b^{2q-2}}x^{4q+1}),~{}b\text{~{}not~{}a~{}cube},~{}a\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}},$

and

$\displaystyle f_{3}(x)=a{\rm Tr}^{n}_{m}(bx^{3})+a^{q}{\rm
Tr}^{n}_{m}(bx^{5}+bx^{4q+1}),~{}b\text{~{}not~{}a~{}cube},~{}a\in\mathbb{F}_{2^{n}}\backslash\mathbb{F}_{2^{m}}.$

Code isomorphism tests showed that $f_{2}$ and $f_{3}$ are CCZ-inequivalent to
each other over $\mathbb{F}_{2^{10}}$. We found two new instances of APN
functions over $\mathbb{F}_{2^{10}}$. We also proposed three open problems,
and we cordially invite the readers to attack these open problems.

## References

  * [1] T. Beth., C. Ding., On almost perfect nonlinear permutations, Workshop on the Theory and Application of Cryptographic Techniques, Springer, pp. 65-76, 1993.
  * [2] A. W. Bluher., On existence of Budaghyan-Carlet APN hexanomials, Finite fields and their applications, vol. 24, pp. 118-123, 2013.
  * [3] C. Bracken., E. Byrne., N. Markin., G. McGuire., New families of quadratic almost perfect nonlinear trinomials and multinomias, Finite fields and their applications, vol. 14, no. 3, pp. 703-714, 2008.
  * [4] C. Bracken., E. Byrne., N. Markin., G. McGuire., A few more quadratic APN functions, Cryptography and Communications, vol. 3, no. 1, pp. 43-53, 2011.
  * [5] C. Bracken., C. H. Tan., Y. Tan., On a class of quadratic polynomials with no zeros and its application to APN functions, Finite fields and their applications, vol. 24, pp. 26-36, 2014.
  * [6] L. Budaghyan., M. Calderini., C. Carlet., R. Coutter., I. Villa., Constructing APN functions through isotopic shift, IEEE Transactions on Information Theory, vol. 66, no. 8, pp. 5299-5309, 2020.
  * [7] L. Budaghyan., M. Calderini., I. Villa., On equivalence between known families of quadratic APN functions, Finite fields and their applications, vol. 66, 101704, 2020.
  * [8] L. Budaghyan., C. Carlet., Classes of quadratic APN trinomials and hexanomials and related structures, IEEE Transactions on Information Theory, vol. 54, no. 5, pp. 2354-2357, 2008.
  * [9] L. Budaghyan., C. Carlet., G. Leander., Two classes of quadratic APN binomials inequivalent to power functions, IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 4218-4229, 2008.
  * [10] L. Budaghyan., C. Carlet., G. Leander., Constructing new APN functions from known ones, Finite fields and their applications, vol. 15, no. 2, pp. 150-159, 2009.
  * [11] L. Budaghyan., C. Carlet., G. Leander., On a construction of quadratic APN functions, in Proceedings of IEEE Information Theory Workshop, ITW’09, pp. 374-378, 2009.
  * [12] L. Budaghyan., T. Helleseth., N. Kaleyski., A new family of APN quadrinomials, IEEE Transactions on Information Theory, vol. 66, no. 11, pp. 7081-7087, 2020.
  * [13] C. Carlet., P. Charpin., V. Zinoviev., _Codes, bent functions and permutations suitable for DES-like cryptosystems_ , Designs, Codes and Cryptography, vol. 15, no. 2, pp. 125-156, 1998.
  * [14] H. Dobbertion., Almost perfect nonlinear power functions on GF($2^{n}$): the Welch case, IEEE Transactions on Information Theory, vol. 45, no. 4, pp. 1271-1275, 1999.
  * [15] H. Dobbertion., Almost perfect nonlinear power functions on GF($2^{n}$): the Niho case, Information and Computation, vol. 151, no. 1, pp. 57-72, 1999.
  * [16] H. Dobbertin., Almost perfect nonlinear power functions on GF($2^{n}$): A new case for $n$ divisible by 5, International Conference on Finite Fields and Applications, pp. 113-121, 2001.
  * [17] Y, Edel., G. Kyureghyan., A. Pott., A new APN functions which is not equivalent to a power mapping, IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 744-747, 2006.
  * [18] R. Gold., Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Transactions on Information Theory, vol. 14, no. 1, pp. 154-156, 1968.
  * [19] T. Kasami., The weight enumerators for several classes of subcodes of the 2nd order binary Reed-Muller codes, Information and Control, vol. 18, no. 4, pp. 369-394, 1971.
  * [20] C. Kaspers., Y. Zhou., The number of almost perfect nonlinear functions grows exponentially, Journal of Cryptography, In Press.
  * [21] H. K. Kim., S. Mesnager., Solving $x^{2^{k}+1}+x+a=0$ in $\mathbb{F}_{2^{n}}$ with ${\rm gcd}(n,k)=1$, Finite fields and their applications, vol. 63, 101630, 2020.
  * [22] K. Nyberg., Differetially uniform mappings for cryptography, Lecture Notes in Computer Science, vol. 765, pp. 55-64, 1994.
  * [23] H. Taniguchi., On some quadratic APN functions, Designs, codes and cryptography, vol. 87, pp. 1973-1983, 2019.
  * [24] K. S. Williams., Note on Cubics over GF($2^{n}$) and GF($3^{n}$)∗, Journal of Number Theory, vol. 7, pp. 361-365, 1975.
  * [25] Y, Yu., M. Wang., Y. Li., A matrix approach for constructing quadratic APN functions, Designs, codes and cryptography, vol. 73, no. 2, pp. 587-600, 2014.
  * [26] Y. Zhou., A. Pott., A new family of semifields with 2 parameters, Advances in Mathematics, vol. 234, pp. 43-60, 2013.

##  5 Appendix

###  5-A Proof of 1) in Theorem 3.10

###### Proof.

It can be checked that $A^{q+1}+B^{q+1}=(x+x^{q})^{5}=h^{5}$ in this case. In
the following, we assume that $c$ is a non-cube in $\mathbb{F}_{2^{n}}$. Note
that $A\neq 0$. In fact, if $A=0$, then $h+c+c^{2}=x^{4}+x^{q}=0$, which
implies that $x\in\mathbb{F}_{2^{n}}\cap\mathbb{F}_{2^{m-2}}=\mathbb{F}_{2}$,
since $m$ is odd, and ${\rm gcd}(n,m-2)=1$, a contradiction to the assumption
that $x\neq 0,1$. Let $y:=y+\frac{B}{A}$. Then equation $(\ref{key-1})$
becomes

$\displaystyle
y^{3}+\frac{AB^{q}+B^{2}}{A^{2}}y+\frac{A^{q+1}+B^{q+1}}{A^{2}}=0.$

Let $y=Ez$, where $E$ satisfies that $E^{2}=\frac{AB^{q}+B^{2}}{A^{2}}$. Note
that $E\neq 0$. In fact, this would imply that $AB^{q}=B^{2}$, and hence
$A^{q}B=B^{2q}$, $A^{q+1}B^{q+1}=B^{2(q+1)}$. However, by the fact that $B\neq
0$ (if $B=0$, then $c=0,1$, a contradiction to the assumption that $c$ is a
non-cube), we have $A^{q+1}+B^{q+1}=0$, which implies that $(x+x^{q})^{5}=0$,
i.e., $x\in\mathbb{F}_{q}$, and then $c=x+x^{2}\in\mathbb{F}_{2^{m}}$ is a
cube in $\mathbb{F}_{2^{n}}$, since every element in $\mathbb{F}_{2^{m}}$ is a
cube by the fact that ${\rm gcd}(3,2^{m}-1)=1$ (since $m$ is odd), a
contradiction.

Then the above equation becomes

$\displaystyle z^{3}+z+a=0,$ (17)

where $a\neq 0$ satisfies that

$\displaystyle a=\frac{A^{q+1}+B^{q+1}}{A^{2}E^{3}}.$

It can be checked that

$\displaystyle\frac{1}{a^{2}}=\frac{(AB^{q}+B^{2})^{3}}{A^{2}(A^{q+1}+B^{q+1})^{2}}.$
(18)

It is clear that equation (12) has no solutions in $\mathbb{F}_{2^{n}}$ if and
only if (17) has no solutions. To complete the proof, according to Theorem
3.9, we have to show that ${\rm Tr}^{n}_{1}\Big{(}\frac{1}{a^{2}}\Big{)}=0$,
and $t_{1}$ is a non-cube in $\mathbb{F}_{2^{n}}$, where $t_{1}$ is one
solution in $\mathbb{F}_{2^{n}}$ of $t^{2}+at+1=0$.

Claim 1. ${\rm Tr}^{n}_{1}\Big{(}\frac{1}{a^{2}}\Big{)}=0$.

In fact, we have

$\displaystyle\frac{1}{a^{2}}=\frac{(AB^{q}+B^{2})^{3}}{A^{2}(A^{q+1}+B^{q+1})^{2}}=\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}+\Bigg{(}\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}\Bigg{)}^{2},$
(19)

where $M$ is one solution of the following equation

$\displaystyle M^{2}+DM+H=0.$ (20)

Recall the notations that $D=A(A^{q+1}+B^{q+1})$,
$H=A^{2}(A^{q}B^{3}+AB^{3q}+B^{2+2q})$, $A=c^{2-2q}(h+c+c^{2})$, $B=c+c^{2}$,
$c=x+x^{2}$. We need only to show that the above equation in $M$ has solutions
in $\mathbb{F}_{2^{n}}$, i.e., ${\rm
Tr}^{n}_{1}\Big{(}{\frac{H}{D^{2}}}\Big{)}=0$. This can be seen from the
following fact.

$\displaystyle\frac{H}{D^{2}}=\frac{A^{q}B^{3}+AB^{3q}+B^{2+2q}}{(A^{q+1}+B^{q+1})^{2}}$

is an element in $\mathbb{F}_{2^{m}}$, since $A^{q}B^{3}+AB^{3q}={\rm
Tr}^{n}_{m}(A^{q}B^{3})$, $A^{q+1}$, $B^{q+1}\in\mathbb{F}_{2^{m}}$.

Next, we need to find one solution $t_{1}$ in $\mathbb{F}_{2^{n}}$ of
$t^{2}+at+1=0$, and show that $t_{1}$ is a non-cube. It is clear that $t_{1}$
can be represented as $av$, where $v=\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}$,
since $\frac{1}{a^{2}}=v+v^{2}$ according to (19). Note that $t_{1}=av$
satisfies that

$\displaystyle t^{2}_{1}=a^{2}v^{2}=\frac{(B^{3}+M)^{2}}{(AB^{q}+B^{2})^{3}}.$

Therefore, to show $t_{1}$ is a non-cube in $\mathbb{F}_{2^{n}}$, we have to
show that $B^{3}+M$ is a non-cube.

Claim 2. $B^{3}+M$ is a non-cube in $\mathbb{F}_{2^{n}}$.

Our strategy is to find the explicit expression of $M$, and then show that
$B^{3}+M$ is a non-cube. To this end, we have to revisit equation (20), and
explore more information on the element $\frac{H}{D^{2}}$ (it is in
$\mathbb{F}_{2^{m}}$). Very fortunately, we find that ${\rm
Tr}^{m}_{1}\Big{(}\frac{H}{D^{2}}\Big{)}=0.$ In fact, recall the notations
that $h=x+x^{q}$, and $r=x^{q+1}$, we find (with computer assistance) that (a
surprise)

$\displaystyle\frac{H}{D^{2}}=u+u^{2},$ (21)

where

$\displaystyle u=\frac{h^{2}(r+r^{2})+r+r^{4}+hr^{2}}{h^{5}}.$

Then $M$ can be chosen as $Du$ (this is because it suffices to find one
solution of $M^{2}+DM+H=0$). We find that

$\displaystyle M=Du=A(A^{q+1}+B^{q+1})u$ $\displaystyle=$ $\displaystyle
c^{2-2q}(h+c+c^{2})h^{5}\cdot\frac{h^{2}(r+r^{2})+r+r^{4}+hr^{2}}{h^{5}}$
$\displaystyle=$
$\displaystyle\frac{c^{2}(h+c+c^{2})({h^{2}(r+r^{2})+r+r^{4}+hr^{2})}}{c^{2q}}.$

Then, recall the notation that $B=c+c^{2}$, we can obtain the expression of
$B^{3}+M$ as follows.

$\displaystyle\begin{aligned}
B^{3}+M&=&\frac{h(c^{2q+4}+c^{q+5}+c^{q+4})+c^{2q+4}+c^{q+5}}{c^{2q}}\\\
&=&\frac{c^{2}\Big{(}h(c^{2q+4}+c^{q+5}+c^{q+4})+c^{2q+4}+c^{q+5}\Big{)}}{c^{2+2q}}.\end{aligned}$
(22)

The above expression can be deduced from

$\displaystyle h+h^{2}=c+c^{q},~{}c^{q+1}=r+r^{2}+hr.$

Note that $h,~{}c^{2+2q}\in\mathbb{F}^{\ast}_{2^{m}}$ is a cube, it suffices
to show that

$\displaystyle
hc^{2}\Big{(}h(c^{2q+4}+c^{q+5}+c^{q+4})+c^{2q+4}+c^{q+5}\Big{)}$

is a non-cube. By the fact that $h+h^{2}=c+c^{q}$, we have

$\displaystyle
hc^{2}\Big{(}h(c^{2q+4}+c^{q+5}+c^{q+4})+c^{2q+4}+c^{q+5}\Big{)}=c^{5}c^{q+1}((c+c^{q})^{2}+h^{2}).$

Since $c^{q+1}$, $c+c^{q}$, $h\in\mathbb{F}^{\ast}_{2^{m}}$ are all cubes in
$\mathbb{F}_{2^{n}}$, we have that the above element is a non-cube, when $c$
is a non-cube. ∎

###  5-B Proof of 2) in Theorem 3.10

###### Proof.

The proof is similar to that of 1) in Theorem 3.10. Recall the following
notations: $r=x^{q+1};h=x+x^{q};c=x+x^{2};$$A=\frac{h+c+c^{2}}{c^{q}};B=1+c,$
from which we can obtain that $h+h^{2}=c+c^{q}$ and
$A^{q+1}+B^{q+1}=\frac{(x+x^{q})^{5}}{(x+x^{2})^{q+1}}=\frac{h^{5}}{c^{q+1}}$.
Note that $A\neq 0$, otherwise, we have $x+x^{4q}=0$ that means that
$x\in\mathbb{F}_{2^{n}}\cap\mathbb{F}_{4q}=\mathbb{F}_{2}$, since
$\gcd(m+2,n)=1$. Then setting $y:=y+\frac{B}{A}$, this can transform (12) into

$\displaystyle
y^{3}+\frac{AB^{q}+B^{2}}{A^{2}}y+\frac{A^{q+1}+B^{q+1}}{A^{2}}=0.$ (23)

Observe that $B\neq 0$ (otherwise $c=1$ is a cube) and $AB^{q}+B^{2}\neq 0$,
otherwise, we have $A^{q+1}+B^{q+1}=0$, that is, $h=0$, which implies that
$c\in\mathbb{F}_{q}$ contracting to the assumption that $c$ is a non-cube,
since $\gcd(3,2^{m}-1)=1$ for any odd $m$. Thus we can transform the equation
(23) into

$\displaystyle z^{3}+z+a=0$ (24)

by setting $y=Ez$, where $a,E\in\mathbb{F}_{2^{n}}^{*}$ such that

$\displaystyle E^{2}=\frac{AB^{q}+B^{2}}{A^{2}}\hskip 5.69046pt{\rm and}\hskip
5.69046pta^{2}=\frac{A^{2}(A^{q+1}+B^{q+1})^{2}}{(AB^{q}+B^{2})^{3}}.$

We need now to prove that equation (24) has no solutions in
$\mathbb{F}_{2^{n}}$. According to Theorem 3.9, we have to show that ${\rm
Tr}_{1}^{n}\Big{(}\frac{1}{a^{2}}\Big{)}=0$ and the solutions in
$\mathbb{F}_{2^{n}}$ of equation $t^{2}+at+1=0$ are not cubes of
$\mathbb{F}_{2^{n}}$.

Firstly, we prove that ${\rm Tr}_{1}^{n}\Big{(}\frac{1}{a^{2}}\Big{)}=0$. Note
that $\frac{1}{a^{2}}$ can be written as

$\displaystyle\frac{1}{a^{2}}=\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}+\bigg{(}\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}\bigg{)}^{2},$
(25)

where $M$ is a solution of

$\displaystyle M^{2}+DM+H=0,$ (26)

where $D=A(A^{q+1}+B^{q+1})$ and $H=A^{2}(AB^{3q}+A^{q}B^{3}+B^{2(q+1)})$.
Then we transform the problem into showing that equation (26) has solutions in
$\mathbb{F}_{2^{n}}$, which is equivalent to ${\rm
Tr}_{1}^{n}\Big{(}\frac{H}{D^{2}}\Big{)}=0$. Indeed, it can be seen that

$\displaystyle\frac{H}{D^{2}}=\frac{AB^{3q}+A^{q}B^{3}+B^{2(q+1)}}{(A^{q+1}+B^{q+1})^{2}}=\frac{{\rm
Tr}_{m}^{n}(AB^{3q})+B^{2(q+1)}}{(A^{q+1}+B^{q+1})^{2}},$

which is clearly in $\mathbb{F}_{q}$. Thus, ${\rm
Tr}_{1}^{n}\Big{(}\frac{H}{D^{2}}\Big{)}=0$.

Then, we show that the solutions of $t^{2}+at+1=0$ are not cubes in
$\mathbb{F}_{2^{n}}$. Assume that $t_{1}$ is a solution of $t^{2}+at+1=0$.
Then by (25), it can be represented by $t_{1}=a\nu$, where
$\nu=\frac{B^{3}+M}{A(A^{q+1}+B^{q+1})}$, and thus

$\displaystyle
t_{1}^{2}=a^{2}\nu^{2}=\frac{(B^{3}+M)^{2}}{(AB^{q}+B^{2})^{3}}.$

Therefore, to show $t_{1}$ is not a cube, it suffices to show $(B^{3}+M)^{2}$
and thus $B^{3}+M$ is not a cube of $\mathbb{F}_{2^{n}}$. In the following, we
show this fact by giving the explicit expression of $M$ by revisiting (26)
again.

By the above discussion, we have obtained that
$\frac{H}{D^{2}}\in\mathbb{F}_{q}$. We further want to show that ${\rm
Tr}_{1}^{m}\Big{(}\frac{H}{D^{2}}\Big{)}=0$, which is equivalent to showing

$\displaystyle\frac{H}{D^{2}}=\mu+\mu^{2}$ (27)

for some $\mu\in\mathbb{F}_{2^{m}}$. Recall that $A=\frac{h+c+c^{2}}{c^{q}}$,
$B=1+c$ and $A^{q+1}+B^{q+1}=\frac{h^{5}}{c^{q+1}}$, we have

$\displaystyle A^{q}B^{3}+AB^{3q}=$
$\displaystyle\frac{(h+c^{q}+c^{2q})B^{3}}{c}+\frac{(h+c+c^{2})B^{3q}}{c^{q}}$
$\displaystyle=$
$\displaystyle\frac{c^{q}(h+c^{q}+c^{2q})B^{3}+c(h+c+c^{2})B^{3q}}{c^{q+1}}$
$\displaystyle=$
$\displaystyle\frac{h(c^{q}B^{3}+cB^{3q})+c^{q}B^{3}(c^{q}+c^{2q})+cB^{3q}(c+c^{2})}{c^{q+1}}.$

While

$\displaystyle h(c^{q}B^{3}+cB^{3q})=$ $\displaystyle
h\big{(}c^{q}(1+c+c^{2}+c^{3})+c(1+c^{q}+c^{2q}+c^{3q})\big{)}$
$\displaystyle=$ $\displaystyle
h(c+c^{q}+c^{q+1}(c+c^{q})+c^{q+1}(c+c^{q})^{2})$

and

$\displaystyle c^{q}B^{3}(c^{q}+c^{2q})+cB^{3q}(c+c^{2})=$ $\displaystyle
c^{q}(1+c+c^{2}+c^{3})(c^{q}+c^{2q})+(c^{q}(1+c+c^{2}+c^{3})(c^{q}+c^{2q}))^{q}$
$\displaystyle=$ $\displaystyle
c^{2q}+c^{3q}+c^{2q+1}+c^{3q+1}+c^{2q+2}+c^{3q+2}+c^{2q+3}+c^{3q+3}+$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}(c^{2q}+c^{3q}+c^{2q+1}+c^{3q+1}+c^{2q+2}+c^{3q+2}+c^{2q+3}+c^{3q+3})^{q}$
$\displaystyle=$
$\displaystyle(c+c^{q})^{2}+c^{3}+c^{3q}+c^{q+1}(c+c^{q})+c^{q+1}(c+c^{q})^{2}.$

We have

$\displaystyle
c+c^{q}=x+x^{q}+(x+x^{q})^{2},c^{q+1}=x^{q+1}+x^{2(q+1)}+x^{q+1}(x+x^{q}),$

from which we can obtain that

$\displaystyle h(c^{q}B^{3}+cB^{3q})=$
$\displaystyle(x+x^{q})^{2}+(x+x^{q})^{3}+x^{q+1}(x+x^{q})^{2}+x^{q+1}(x+x^{q})^{3}+x^{q+1}(x+x^{q})^{5}$
$\displaystyle+x^{q+1}(x+x^{q})^{6}+x^{(2q+1)}(x+x^{q})^{2}+x^{(2q+1)}(x+x^{q})^{5}$

and

$\displaystyle c^{q}B^{3}(c^{q}+c^{2q})+cB^{3q}(c+c^{2})=$
$\displaystyle(x+x^{q})^{2}+(x+x^{q})^{3}+(x+x^{q})^{5}+(x+x^{q})^{6}+x^{q+1}(x+x^{q})^{2}$
$\displaystyle+x^{q+1}(x+x^{q})^{3}+x^{q+1}(x+x^{q})^{4}+x^{q+1}(x+x^{q})^{5}$
$\displaystyle+x^{2(q+1)}(x+x^{q})^{2}+x^{2(q+1)}(x+x^{q})^{4}.$

Thus we have

$\displaystyle c^{q+1}(A^{q}B^{3}+AB^{3q})=$
$\displaystyle(x+x^{q})^{5}+(x+x^{q})^{6}+x^{q+1}(x+x^{q})^{4}+x^{q+1}(x+x^{q})^{6}$
$\displaystyle+x^{2(q+1)}(x+x^{q})^{4}+x^{2(q+1)}(x+x^{q})^{5}$

and

$\displaystyle c^{2(q+1)}(A^{q}B^{3}+AB^{3q})=$ $\displaystyle
x^{q+1}(x+x^{q})^{5}+x^{q+1}(x+x^{q})^{7}+x^{2(q+1)}(x+x^{q})^{4}+x^{2(q+1)}(x+x^{q})^{7}$
$\displaystyle+x^{4(q+1)}(x+x^{q})^{4}+x^{4(q+1)}(x+x^{q})^{5}.$

We further have

$\displaystyle c^{2(q+1)}B^{2(q+1)}=$ $\displaystyle c^{2(q+1)}(1+c)^{2(q+2)}$
$\displaystyle=$ $\displaystyle c^{2(q+1)}+c^{2(q+1)}(c+c^{q})^{2}+c^{4(q+1)}$
$\displaystyle=$ $\displaystyle
x^{2(q+1)}+x^{2(q+1)}(x+x^{q})^{6}+x^{4(q+1)}(x+x^{q})^{2}+x^{8(q+1)}.$

Recall that $h=x+x^{q}$, $r=x^{q+1}$. Thus, we have

$\displaystyle c^{2(q+1)}(A^{q}B^{3}+AB^{3q}+B^{2(q+1)})=$ $\displaystyle
rh^{5}+rh^{7}+r^{2}+r^{2}h^{4}+r^{2}h^{6}+r^{2}h^{7}+r^{4}h^{2}+r^{4}h^{4}+r^{4}h^{5}+r^{8},$

and

$\displaystyle\frac{H}{D^{2}}=\frac{r}{h^{5}}+\frac{r}{h^{3}}+\frac{r^{2}}{h^{10}}+\frac{r^{2}}{h^{6}}+\frac{r^{2}}{h^{4}}+\frac{r^{2}}{h^{3}}+\frac{r^{4}}{h^{8}}+\frac{r^{4}}{h^{6}}+\frac{r^{4}}{h^{5}}+\frac{r^{8}}{h^{10}}=\mu+\mu^{2}$

where $\mu=\frac{r+r^{4}+r^{2}h+(r+r^{2})h^{2}}{h^{5}}$. The rest of this
proof is similar to that of Theorem 3.10, so we omit it here.∎