A matrix approach for constructing quadratic APN functions

Abstract

A one to one correspondence is given between quadratic homogeneous APN functions and a special kind of matrices which we call as QAM’s. By modifying the elements of a known QAM, new quadratic APN functions can be constructed. Based on the nice mathematical structures of the QAM’s, an efficient algorithm for constructing quadratic APN functions is proposed. On $\mathbb {F}_{2^7}$, we have found 471 new CCZ-inequivalent quadratic APN functions, which is 20 times more than the number of the previously known ones. Before this paper, It is only found 23 classes of CCZ-inequivalent APN functions on $\mathbb {F}_{2^8}$. With the method of this paper, we have found 2,252 new CCZ-inequivalent quadratic APN functions, and this number is still increasing.

1 Introduction

Low differentially uniform permutations are very useful in cryptography, they can provide good resistance against differential attack. For example, the advanced encryption standard (AES) [12] uses a differentially 4-uniform permutation as its substitution box (S-box). The differentially 4-uniform permutation is the best choice for now due to the lack of differentially 2-uniform permutations on $\mathbb {F}_{2^{8}}$. For clarity, we first introduce the following definitions.

Definition 1

A mapping $F: \mathbb {F}_{2^{n}}\rightarrow \mathbb {F}_{2^{n}}$ is called differentially $\delta (F)$- uniform if

$$\begin{aligned} \delta (F)=\max _{a \in \mathbb {F}_{2^{n}}^{\star },b \in \mathbb {F}_{2^{n}}}\#\varDelta _{F} (a,b), \end{aligned}$$

where $\varDelta _{F} (a,b)=\{x \in \mathbb {F}_{2^{n}}: F(x+a)+F(x)=b\}$, and $\#\varDelta _{F} (a,b)$ is the cardinality of $\varDelta _{F} (a,b)$. If $\delta (F)=2$, F is called almost perfect nonlinear (APN) [1].

Definition 2

[11] Let F and $F^\prime$ be two functions from $\mathbb {F}_{2^n}$ to $\mathbb {F}_{2^n}$.

• (i) F and $F^\prime$ are Extended affine equivalent (EA-equivalent) if

  $$\begin{aligned} F'(x)=A_{1}(F(A_{2}(x)))+A_{3}(x), \end{aligned}$$

  where $A_{1}$ and $A_{2}$ are affine permutations on $\mathbb {F}_{2^n}$, and $A_{3}$ is an affine function on $\mathbb {F}_{2^n}$.

• (ii) F and $F^\prime$ are Carlet–Charpin–Zinoviev equivalent (CCZ-equivalent) if there exists an affine permutation which maps $G_{F}$ onto $G_{F'}$, where $G_{F}=\{(x,F(x)): x \in \mathbb {F}_{2^n}\}$ is the graph of $F$, and $G_{F'}$ is the graph of $F'$.

Note that $\delta (F)$ is always even, and APN functions provide optimal resistance against differential attack. The terminology APN was introduced by Nyberg and Knudsen [23] in 1992. Carlet, Charpin and Zinoviev proved that if a function is APN, then its CCZ-equivalent functions are all APN. CCZ-equivalence is a generalization of EA-equivalence. A function $F(x)=\sum _{j=0}^{2^n-1}c_jx^j\in \mathbb {F}_{2^{n}}[x]$ is called quadratic if the maximum Hamming weight of the binary expansion of j with $c_j\ne 0$ equals 2. According to Yoshiara’s results [24], two quadratic APN functions are CCZ-equivalent if and only if they are EA-equivalent.

An APN function is new if it is not CCZ equivalent to any known ones. For a long time, finding new APN functions is an important research topic in cryptography. In recent years, most of the new APN functions found are quadratic [2–9, 13–20]. For a systematic knowledge of APN functions, the readers can turn to [10].

Our work was motivated by a recent breakthrough on APN functions. In 2009, Dillon et al. [4, 5, 13] found an APN permutation in dimension six, which is the first APN permutation in even dimension. Their idea can be summarized as follows: firstly, finding an APN function, and then checking whether this APN function is CCZ-equivalent to a permutation or not. Thus, if we want to find new APN permutations in even dimensions, we must find new APN functions first.

Our aim is to find as many new APN functions as possible, especially on $\mathbb {F}_{2^{8}}$. Then we will check wether these new APN functions are CCZ-equivalent to some permutations. If some of these functions are CCZ-equivalent to permutations, then this will prove the existence of APN permutations on $\mathbb {F}_{2^8}$.

The contributions of this paper are as follows. In Sect.  2, a one to one correspondence is given between quadratic homogeneous APN functions and QAMs (see definition 5 in Sect. 2). In Sect. 3, some relations are proposed between quadratic homogeneous functions and their corresponding matrices, in particular, some properties of QAMs are given. These QAMs have nice mathematical structures and constructing QAMs is easier than constructing quadratic APN functions directly. In Sect. 4, based on some properties of the QAMs, we have designed an efficient algorithm to search for the new APN functions. Before this paper, the scholars [13, 16] have found 19 and 23 classes of CCZ-inequivalent APN functions on $\mathbb {F}_{2^{7}}$ and $\mathbb {F}_{2^8}$ respectively. With the algorithm of this paper, we have found more than 471 new CCZ-inequivalent APN functions on $\mathbb {F}_{2^7}$, and more than 2252 new CCZ-inequivalent quadratic APN functions on $\mathbb {F}_{2^{8}}$. The number of CCZ-inequivalent quadratic APN functions on $\mathbb {F}_{2^{8}}$ is still arising. We have checked all these new APN functions on $\mathbb {F}_{2^8}$, none of them is CCZ-equivalent to a permutation.

2 Notation and basic ideas

2.1 Notation

Let $n$ be a positive integer, $\mathbb {F}_{2^n}$ be a finite field with $2^n$ elements, and $\mathbb {F}_{2^n}[x]$ be the polynomial ring in variable $x$ over $\mathbb {F}_{2^n}$.

Definition 3

Quadratic functions on $\mathbb {F}_{2^n}$ without linear and constant terms are called quadratic homogeneous functions.

Definition 4

[21] Two bases $\{\alpha _{1},\ldots ,\alpha _{n}\}$ and $\{\theta _{1},\theta _{2},\ldots ,\theta _{n}\}$ of $\mathbb {F}_{2^{n}}$ over $\mathbb {F}_{2}$ are said to be dual if for $1 \le u,j \le n$ we have

$$\begin{aligned} {\text{ Tr }}(\alpha _{u}\theta _{j})=\left\{ \begin{array}{ll} 0 &{} {\text{ for }}\quad u \ne j;\\ 1 &{} {\text{ for }}\quad u = j.\end{array}\right. \end{aligned}$$

We will use the following convention and notation throughout the paper.

• (i) For positive integers $r,s$, $\mathbb {F}_{2^n}^{r\times s}$ denotes the space of $r\times s$ matrices over $\mathbb {F}_{2^n}$. For a matrix $A$, let $A[i]$ be the $i$th row of $A$, $A[i,j]$ be the $(i,j)$ entry of $A$, and $B=\mathrm{Submatrix}(A,1,1,r,c)$ the $r\times c$ submatrix of $A$ consisting of the first $r$ rows and the first $c$ columns.

• (ii) Suppose $\{\alpha _{1},\alpha _{2}, \ldots ,\alpha _{n}\}$ is a basis of $\mathbb {F}_{2^{n}}$ over $\mathbb {F}_{2}$, and $\{\theta _{1},\theta _{2},\ldots , \theta _{n}\}$ is its dual basis. Let $M_{\alpha }\in \mathbb {F}_{2^n}^{n\times n}$ and $M_{\theta }\in \mathbb {F}_{2^n}^{n\times n}$ with $M_{\alpha }[i,u]=\alpha _{u}^{2^{i-1}}$ and $M_\theta [i,u]=\theta _{u}^{2^{i-1}}$ for $1 \le u,i\le n$. Then $M_{\alpha }^{T}M_{\theta } =(\mathrm{Tr}(\alpha _{u}\theta _{j}))_{n\times n}$ for $1\le u,j \le n$, so $M_{\alpha }^{T}M_{\theta }=I_{n}$, where $I_{n}$ is the $n\times n$ identity matrix. Thus $M_{\theta }^{-1}=M_{\alpha }^{T}$, where $M_{\alpha }^{T}$ is the transpose of $M_{\alpha }$.

• (iii) Suppose $\eta _{1},\eta _{2},\ldots ,\eta _{m}\in \mathbb {F}_{2^n}$ ($m, n \ge 1$), and $B=(\eta _{1},\eta _{2},\ldots ,\eta _{m})\in \mathbb {F}_{2^{n}}^{m}$. Let $\mathrm{Span}(B)$=$\mathrm{Span}( \eta _{1},\eta _{2},\ldots ,\eta _{m})$ be the subspace spanned by $\{\eta _{1},\eta _{2},\ldots ,\eta _{m}\}$ over $\mathbb {F}_2$. The rank of $B$ over $\mathbb {F}_2$, denoted as $\mathrm{{Rank}_{\mathbb {F}_{2}}}(B)$, is defined as the dimension of $\mathrm{Span}(B)$ over $\mathbb {F}_2$. Suppose $\eta _{i}=\sum _{j=1}^{n}\lambda _{i,j}\alpha _{j}$ for $1 \le i \le m$, where $\lambda _{i,j} \in \mathbb {F}_{2}$ for all $i,j$. Define an $m\times n$ matrix $\varLambda =(\lambda _{i,j})_{m\times n}$. Then $\mathrm{{Rank}_{\mathbb {F}_{2}}}(B)$ equals to the rank of $\varLambda$.

Now we introduce a class of matrices which will play an important role in the present paper.

Definition 5

Let $H=(h_{u,v })_{n\times n}$ be an $n\times n$ matrix over $\mathbb {F}_{2^{n}}$. $H$ is called a quadratic APN matrix (QAM) if

• (i) $H$ is symmetric and the elements in its main diagonal are zero;

• (ii) Every nonzero linear combination of the $n$ rows (or “columns” because of $H$ being symmetric) of $H$ has rank $n-1$.

2.2 One to one correspondence between quadratic homogeneous APN functions and QAMs

In order to prove Theorem 1 below, we need to give a matrix representation of quadratic homogeneous functions.

Let $F(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}} \in \mathbb {F}_{2^{n}}[x]$ be a quadratic homogeneous function. We define an $n\times n$ matrix $E=(e_{i,t})_{n\times n}$ by setting

$$\begin{aligned} e_{i,t} = \left\{ \begin{array}{ll} c_{i,t} &{} {\text{ if }}\quad i > t;\\ 0 &{} {\text{ if }}\quad i \le t.\\ \end{array} \right. \end{aligned}$$

(1)

Let $X=(x^{2^{0}},x^{2^{1}},\ldots ,x^{2^{n-1}})^{T}$. Then we have

$$\begin{aligned} F(x)=X^{T}EX. \end{aligned}$$

(2)

Let $x=x_{1}\alpha _{1}+x_{2}\alpha _{2}+\cdots +x_{n}\alpha _{n}$, where $x_{i} \in \mathbb {F}_{2}$, $1\le i\le n$. Then (2) can be written as

$$\begin{aligned} F(x)=\overline{x}^{T}M^{T}EM\overline{x}, \end{aligned}$$

(3)

where $\overline{x}=(x_{1},x_{2},\ldots ,x_{n})^{T}$, and $M=M_{\alpha }$.

Now for $F(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}} \in \mathbb {F}_{2^{n}}[x]$, let $C_F$ be an $n\times n$ matrix with $C_F[t,i]=C_F[i,t]=c_{i,t}$ for $1\le t < i \le n$, and $C_F[i,i]=0$ for $1\le i \le n$. Thus by definition of $E$, we have $C_F=E+E^T$.

Given a basis $\alpha =\{\alpha _1,\ldots ,\alpha _n\}$ for $\mathbb {F}_{2^{n}}$ over $\mathbb {F}_2$, and let $M=M_{\alpha }$. For any quadratic homogeneous function $F(x)$, let $H=M^{T}C_F M$. Then $H$ is a symmetric matrix over $\mathbb {F}_{2^{n}}$ with main diagonal elements zero.

Conversely, for a symmetric matrix $H$ over $\mathbb {F}_{2^n}$ with main diagonal elements all zero, we can define a unique quadratic homogeneous function $F(x)$ such that $H=M^T C_F M$. $F(x)$ is called the quadratic function defined by $H$ relative to the ordered basis $\alpha$.

Based on (3), we can build a one to one correspondence between quadratic homogeneous APN functions and QAMs.

Theorem 1

Let $F(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}} \in \mathbb {F}_{2^{n}}[x]$, $C_F$ and $M$ be defined as above, and $H=M^{T}C_F M$. Then, $\delta (F)=2^{k}$ if and only if the smallest rank of any nonzero linear combination of the $n$ rows of $H$ is $n-k$. In particular, $F$ is APN on $\mathbb {F}_{2^{n}}$ if and only if $H$ is a QAM.

Proof

Let $E$ and $\overline{x}$ be the same as in (1) and (3), and $a=a_{1}\alpha _{1}+a_{2}\alpha _{2}+\cdots +a_{n}\alpha _{n}$, where $\overline{a}=(a_{1},\cdots ,a_{n})^T\in \mathbb {F}_{2}^{n}\backslash \{0\}$. Let

$$\begin{aligned} D_{a}(x)=F(x+a)+F(x)+F(a). \end{aligned}$$

Then $D_{a}(x)$ is a linear function. So $\delta (F)=2^{k}$ if and only if

$$\begin{aligned} \max \{\mathrm{dim}_{\mathbb {F}_{2}}(\mathrm{Ker}(D_{a}))\,\,|\,\, a \in \mathbb {F}_{2^{n}}^{\star }\}=k. \end{aligned}$$

Based on (3), we have

$$\begin{aligned} D_{a}(x)&= (\overline{x}+\overline{a})^{T}M^{T}EM(\overline{x}+\overline{a}) +\overline{x}^{T}M^{T}EM\overline{x}+\overline{a}^{T}M^{T}EM\overline{a}\\&= \overline{x}^{T}M^{T}EM(\overline{x}+\overline{a}+\overline{x}) +\overline{a}^{T}M^{T}EM(\overline{x}+\overline{a}+\overline{a})\\&= \overline{x}^{T}M^{T}EM\overline{a}+\overline{a}^{T}M^{T}EM\overline{x} \\&= \overline{x}^{T}M^{T}EM\overline{a}+(\overline{a}^{T}M^{T}EM\overline{x})^{T} \\&= \overline{x}^{T}M^{T}(E+E^{T})M\overline{a} \\&= \overline{x}^{T}M^{T}C_{F}M\overline{a} \\&= \overline{x}^{T}H\overline{a}. \end{aligned}$$

By linear algebra, $D_{a}(x)=0$ has $2^{k}$ solutions if and only if $\mathrm{{Rank}_{\mathbb {F}_{2}}}((H\overline{a})^{T})=n-k$. $H\overline{a}$ is a nonzero linear combination of the $n$ columns of $H$ since $\overline{a}\in \mathbb {F}_{2}^{n}\backslash \{0\}$. Thus $\delta (F)=2^{k}$ if and only if

$$\begin{aligned} D_{a}(x)=\overline{x}^{T}H\overline{a}=0 \end{aligned}$$

has $2^{k}$ solutions for any $\overline{a}\in \mathbb {F}_{2}^{n}\backslash \{0\}$.

Note that $H$ is symmetric, thus the above results implies the conclusion. $\square$

The matrix $H$ associated with $F(x)$ in Theorem 1 is called the matrix of $F(x)$ relative to the ordered basis $\{\alpha _1,\ldots ,\alpha _n\}$.

Note that $M$ is an invertible matrix over $\mathbb {F}_{2^{n}}$, so the correspondence between quadratic homogeneous APN functions and QAMs is one to one. It seems that another similar approach have been considered by Knuth and Edel, the readers can turn to Slides from the talk [14] for details.

Theorem 1 is very useful when we want to study the differential properties of the quadratic functions, and it can be generalized to $\mathbb {F}_{p^{n}}$, where $p$ is any prime and $n$ is a positive integer. In this paper, we use only this theorem to study the quadratic APN functions on $\mathbb {F}_{2^n}$.

3 Theoretical results

In this section, we give some theoretical results concerning relationship between quadratic homogeneous functions and their corresponding matrices. Since our aim is to construct new APN functions up to EA-equivalence, thus we need to understand EA-equivalence of two functions in terms of their corresponding matrices.

Let $F(x)$ be a given quadratic homogeneous function. First we study what happens to corresponding matrices when the ordered basis is changed. Let $\alpha =\{\alpha _1,\ldots ,\alpha _n\}$ and $\beta =\{\beta _1,\ldots ,\beta _n\}$ be two ordered bases for $\mathbb {F}_{2^{n}}$ over $\mathbb {F}_2$. Assume $H_{\alpha }$ and $H_{\beta }$ are corresponding matrices for $F(x)$ relative to the $\alpha ,\beta$ respectively. How are the matrices $H_{\alpha }$ and $H_{\beta }$ related?

As we know, there is a unique invertible $n\times n$ matrix $P$ such that

$$\begin{aligned} (\beta _1,\ldots ,\beta _n)=(\alpha _1,\ldots ,\alpha _n)P. \end{aligned}$$

Hence we have $M_{\beta }=M_{\alpha }P$. So we have $H_{\beta }=M_{\beta }^T C_FM_{\beta }=P^TH_{\alpha }P$.

Conversely, assume that $H',H$ are two $n\times n$ symmetric matrices with main diagonal elements all zeros such that $H'=P^T H P$ for an invertible matrix $P$ over $\mathbb {F}_2$.

Let $F(x)$ be the quadratic function defined by $H$ relative to the ordered basis $\alpha$. Let $\gamma =\{\gamma _1,\ldots ,\gamma _n\}$ be defined by $(\gamma _1,\ldots ,\gamma _n)=(\alpha _1,\ldots ,\alpha _n)P$. Then $\gamma$ is a basis for $\mathbb {F}_{2^{n}}$, and $F(x)$ is also the quadratic function defined by $H'$ relative to ordered basis $\gamma$.

Now let $F'(x)$ be the quadratic function defined by $H'$ relative to $\alpha$, then how are the functions $F(x)$ and $F'(x)$ related ? In order to answer this problem, we first note the following lemma.

Lemma 1

Suppose $H=(h_{u,v})_{n\times n}$ is a symmetric matrix over $\mathbb {F}_{2^n}$ with $h_{u,u}=0$ for all $1 \le u \le n$. Define a set $S=\{K=(k_{u,v})_{n\times n} \mid k_{u,v} + k_{v,u}=h_{u,v} \text{ for } \text{ all } 1\le v \le u \le n \}.$ Then

• (1) $W \in S$ if and only if $W+W^{T}=H$.

• (2) If $W_{1}+W_{1}^{T}=H$ and $W_{2}+W_{2}^{T}=H$, then there exists a symmetric matrix $A$ such that $W_{2}=W_{1}+A$.

Proof

(1) is obvious, omitting it, we prove only (2) in the following. Let $W_{1}+W_{1}^{T}=H$ and $W_{2}+W_{2}^{T}=H$, then for any symmetric matrix $A$, we have

$$\begin{aligned} (W_{1}+A)+(W_{1}+A)^{T}=W_{1}+W_{1}^{T}+A+A^{T}=W_{1}+W_{1}^{T}=H, \end{aligned}$$

which implies that $W_{1}+A \in S$ for any symmetric matrix $A$.

Define a set $S'=\{W_{1}+A \mid A \text{ is } \text{ symmetric }\}$. Easy to see that $\#S'=2^{n^{2}(n+1)/2}=\#S$, and for any $W \in S'$, we have $W+W^{T}=H$. Thus we have $S=S'$. So $W_{2}\in S'$, Hence there exists a symmetric matrix $A$ with $W_{2}=W_{1}+A$. $\square$

Theorem 2

Let $H\in \mathbb {F}_{2^{n}}^{n\times n}$ be a symmetric matrix with main diagonal elements all zero, and $P\in \mathbb {F}_{2}^{n\times n}$ be an invertible matrix. Suppose $H'=P^{T}HP$, then the quadratic functions defined by $H$ and $H'$ relative to an ordered basis $\alpha$ are EA-equivalent. In particular, $H$ is a QAM if and only if $H'$ is a QAM.

Proof

Let the functions defined by $H$ and $H'$ relative to $\alpha$ be $F(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}}$, and $F'(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}'x^{2^{i-1}+2^{t-1}}$ respectively.

Let $E=(e_{i,t})$, and $E'=(e'_{i,t})$ be two $n \times n$ matrices such that

$$\begin{aligned} e_{i,t} = \left\{ \begin{array}{ll} c_{i,t} &{} \mathrm{if}\quad i > t; \\ 0 &{} \mathrm{if}\quad i \le t,\\ \end{array} \text{ and } e'_{i,t}=\left\{ \begin{array}{ll} c'_{i,t} &{} \mathrm{if}\quad i > t; \\ 0 &{} \mathrm{if}\quad i \le t.\\ \end{array} \right. \right. \end{aligned}$$

By (3), we have

$$\begin{aligned} F(x)=\overline{x}^{T}M^{T}EM\overline{x}, \text{ and } F'(x)=\overline{x}^{T}M^{T}E'M\overline{x}, \end{aligned}$$

where $\overline{x}=(x_{1},x_{2},\ldots ,x_{n})^{T} \in \mathbb {F}_{2}^{n}$.

Let $W=M^{T}EM$, and $W'=M^{T}E'M$. Then $W+W^{T}=H$, and $W'+ W'^{T}=H'$, which implies that $P^{T}WP+P^{T}W^{T}P=P^{T}HP=H'=W'+ W'^{T}$. According to Lemma 1, there exists a symmetric matrix $A=(a_{u,v})_{n\times n}$ such that $W'=P^{T}WP+A$. Thus we have $\overline{x}^{T}W'\overline{x}=\overline{x}^{T}(P^{T}WP+A)\overline{x}$. Hence

$$\begin{aligned} F'(x)&= \overline{x}^{T}M^{T}E'M\overline{x}= \overline{x}^{T}P^{T}M^{T}EMP\overline{x}+\overline{x}^{T}A\overline{x}\nonumber \\&= G(x)+\overline{x}^{T}A\overline{x}, \end{aligned}$$

(4)

where $G(x)=\overline{x}^{T}P^{T}M^{T}EMP\overline{x}$.

Since $A$ is symmetric, we have

$$\begin{aligned} \overline{x}^{T}A\overline{x}=\sum _{u=1}^{n}\sum _{v=1}^{n}a_{u,v}x_{u}x_{v} =\sum _{u=1}^{n}a_{u,u}x_{u}^{2} =\sum _{u=1}^{n}a_{u,u}x_{u}. \end{aligned}$$

(5)

By (4) and (5), $F'(x)$ is EA-equivalent to $G(x)$. As for $G(x)$, we have

$$\begin{aligned} G(x)=\overline{x}^{T}P^{T}M^{T}EMP\overline{x}=\overline{y}^{T}M^{T}EM\overline{y}=F(y), \end{aligned}$$

where $\overline{y}=(y_{1},y_{2},\ldots ,y_{n})^{T}=P\overline{x}$. So $G(x)$ is affine equivalent to $F(x)$. Thus $F'(x)$ is EA-equivalent to $F(x)$. $\square$

We need the following result (Theorem 2.3 in [22]) when proving Lemma 3.

Lemma 2

[22] Let $\{\theta _{1},\theta _{2},\ldots ,\theta _{n}\}$ be any given basis of $\mathbb {F}_{2^{n}}$ over $\mathbb {F}_{2}$, and let $L(x)$ be a linearized polynomial over $\mathbb {F}_{2^{n}}$. Then there exists a unique vector $(\beta _{1},\beta _{2},\ldots ,\beta _{n})\in \mathbb {F}_{2^{n}}^{n}$ such that

$$\begin{aligned} L(x)=\sum \limits _{j=1}^{n}\mathrm{Tr}(\theta _{j}x)\beta _{j}= \sum \limits _{i=1}^{n}\left( \sum \limits _{j=1}^{n}\beta _{j}\theta _{j}^{2^{i-1}}\right) x^{2^{i-1}}. \end{aligned}$$

Moreover, let $k$ be an integer such that $0 \le k \le n$, then $\mathrm{dim}_{\mathbb {F}_{2}}(\mathrm{Ker}(L))=k$ if and only if $\mathrm{{Rank}_{\mathbb {F}_{2}}}\{\beta _{1},\beta _{2},\ldots ,\beta _{n}\}=n-k$.

Lemma 3

With notation as in Lemma 2. Every quadratic function $Q(x)\in \mathbb {F}_{2^{n}}[x]$ with $Q(0)=0$ can be denoted as

$$\begin{aligned} Q(x)&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x) \mathrm{Tr}(\theta _{v}x)(\eta _{u,v}+\eta _{v,u})\nonumber \\&{}+\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\eta _{u,u} \end{aligned}$$

(6)

$$\begin{aligned}&= \sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}}+\mathrm{Lin}(x), \end{aligned}$$

(7)

where

$$\begin{aligned} c_{i,t}&= \sum \limits _{1\le u,v \le n}\theta _{u}^{2^{i-1}}\theta _{v}^{2^{t-1}}(\eta _{v,u}+\eta _{u,v}),\\ \mathrm{Lin}(x)&= \sum _{1 \le v<u \le n}(\eta _{u,v}+\eta _{v,u})\mathrm{Tr} (\theta _{u}\theta _{v}x^{2})\\&{}+\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\eta _{u,u}, \end{aligned}$$

and

$$\begin{aligned} \eta _{u,v}\,\, (1\le u,v \le n) \text{ are } \text{ some } \text{ elements } \text{ in } \mathbb {F}_{2^{n}}. \end{aligned}$$

Proof

According to Lemma 2, every quadratic function without constant term can be denoted as $Q(x)=\sum _{t=1}^{n}L'_{t}(x)x^{2^{t-1}}$, where $L'_{t}(x)=\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\omega _{u,t}$ and $\omega _{u,t}\in \mathbb {F}_{2^n}$ for all $1\le u,t \le n$. Then we have $Q(x)=\sum _{u=1}^{n}L_{u}(x)\mathrm{Tr}(\theta _{u}x)$, where $L_{u}(x)=\sum _{t=1}^{n}\omega _{u,t}x^{2^{t-1}}$. Again, according to Lemma 2, we have $L_{u}(x)=\sum _{v=1}^{n}\mathrm{Tr}(\theta _{v}x)\eta _{v,u}$, where $\eta _{v,u}\in \mathbb {F}_{2^n}$ such that $\omega _{u,t}=\sum _{v=1}^{n}\theta _{v}^{2^{t-1}}\eta _{v,u}$. Hence we have

$$\begin{aligned} Q(x)&= \sum _{u=1}^{n}L_{u}(x)\mathrm{Tr}(\theta _{u}x) \\&= \sum _{u=1}^{n}\left( \sum _{v=1}^{n}\mathrm{Tr}(\theta _{v}x)\eta _{v,u})\mathrm{Tr}(\theta _{u}x\right) \\&= \sum \limits _{1\le u,v \le n}\mathrm{Tr}(\theta _{u}x)\eta _{u,v}\mathrm{Tr}(\theta _{v}x) \\&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)(\eta _{u,v}+\eta _{v,u})\\&{}+\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\eta _{u,u}\\&= \sum \limits _{1\le v <u \le n}\sum _{i=1}^{n}(\theta _{u}x)^{2^{i-1}} \sum _{t=1}^{n}(\theta _{u}x)^{2^{t-1}} (\eta _{u,v}+\eta _{v,u})\\&{}+\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\eta _{u,u} \\&= \sum \limits _{1\le v <u \le n}\sum \limits _{1\le i,t \le n}\left( (\eta _{u,v} +\eta _{v,u})\theta _{u}^{2^{i-1}}\theta _{v}^{2^{t-1}}x^{2^{i-1}+2^{t-1}}\right) +\sum _{u=1}^{n}\mathrm{Tr}(\theta _{u}x)\eta _{u,u} \\&= \sum \limits _{1\le t < i \le n}\sum \limits _{1\le v < u \le n}\left( (\eta _{u,v}+ \eta _{v,u})\left( \theta _{u}^{2^{i-1}}\theta _{v}^{2^{t-1}} +\theta _{u}^{2^{t-1}}\theta _{v}^{2^{i-1}}\right) x^{2^{i-1}+2^{t-1}}\right) +\mathrm{Lin}(x) \\&= \sum \limits _{1\le t < i \le n}\left( \sum \limits _{1\le u,v \le n}\theta _{u}^{2^{i-1}}\theta _{v}^{2^{t-1}}\left( \eta _{v,u} +\eta _{u,v}\right) \right) x^{2^{i-1}+2^{t-1}}+\mathrm{Lin}(x) \\&= \sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}}+\mathrm{Lin}(x) \end{aligned}$$

$\square$

With the help of Lemma 3, the following result can be proved.

Theorem 3

Let $H=(h_{u,v })\in \mathbb {F}_{2^n}^{n\times n}$ be a symmetric matrix with main diagonal elements all zeros, and $L$ be a linear permutation on $\mathbb {F}_{2^n}$. Let $H'=(h'_{u,v })\in \mathbb {F}_{2^n}^{n\times n}$ such that $h'_{u,v}=L(h_{u,v})$ for all $1 \le u,v \le n$. Then the quadratic functions defined by $H$ and $H'$ relative to $\alpha$ are EA-equivalent. In particular, $H$ is a QAM if and only if $H'$ is a QAM.

Proof

Let the corresponding functions of $H$ and $H'$ be $F(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}x^{2^{i-1}+2^{t-1}}$ and $F'(x)=\sum \limits _{1 \le t < i \le n}c_{i,t}'x^{2^{i-1}+2^{t-1}}$ respectively.

Let $C_F$ be the same as in Sect. 2. Then $H=M^{T} C_F M$. Hence $C_F=(M^{T})^{-1}HM^{-1}=M_{\theta } H M_{\theta }^{t}$, where $\theta$ is the dual basis of $\alpha$, see Sect. 2.1. So

$$\begin{aligned} c_{i,t}=\sum \limits _{1\le u,v \le n}\theta _{u}^{2^{i-1}}\theta _{v}^{2^{t-1}}h_{u,v}. \end{aligned}$$

Choose $\eta _{u,v}\in \mathbb {F}_{2^n}$ such that $\eta _{u,v}+\eta _{v,u}=h_{u,v}$ for all $1\le u,v \le n$, and let $\eta _{u,u}=0$ for all $1\le u \le n$. Define a quadratic function $Q(x)$ over $\mathbb {F}_{2^n}$ as follows:

$$\begin{aligned} Q(x)&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)h_{u,v} \\&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)(\eta _{u,v}+\eta _{v,u}). \end{aligned}$$

Then from the proof of Lemma 3, we have

$$\begin{aligned} Q(x)=F(x)+\mathrm{Lin}(x), \end{aligned}$$

(8)

for some linear function $\mathrm{Lin}(x)$ over $\mathbb {F}_{2^n}$.

Furthermore we define $Q'(x)$ by

$$\begin{aligned} Q'(x)=\sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)h'_{u,v}. \end{aligned}$$

(9)

Using the same reasoning as $Q(x)$ and $F(x)$, we get $Q'(x)=F'(x)+\mathrm{Lin'}(x)$ for some linear function $\mathrm{Lin'}(x)$ over $\mathbb {F}_{2^n}$.

Thus we have

$$\begin{aligned} Q'(x)&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)h'_{u,v}\nonumber \\&= \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)L(h_{u,v}) \nonumber \\&= L\left( \sum \limits _{1\le v <u \le n}\mathrm{Tr}(\theta _{u}x)\mathrm{Tr}(\theta _{v}x)h_{u,v}\right) \nonumber \\&= L(Q(x)). \end{aligned}$$

(10)

By (8), (9) and (10), it deduces that $F(x)$ and $F'(x)$ are EA-equivalent. $\square$

Remark 1

Let $H=(h_{u,v})_{n\times n}$ and $H'=(h'_{u,v})_{n\times n}$ be two $n\times n$ matrices, and $L$ be a linear permutation on $\mathbb {F}_{2^n}$, then $H'=L(H)$ means that $h'_{u,v}=L(h_{u,v})$ for all $1 \le u,v \le n$.

Based on Theorem 2 and Theorem 3 we can obtain the following corollaries.

Corollary 1

Let $F(x)$ and $F'(x)$ be two quadratic homogeneous functions, and $H$ and $H'$ be their corresponding matrices, respectively. Then $F(x)$ is EA-equivalent to $F'(x)$ if $H'=L(P^{t}HP)$, where $P$ is an $n \times n$ invertible matrix over $\mathbb {F}_{2}$, and $L$ is a linear permutation over $\mathbb {F}_{2^n}$.

Remark 2

Let $F(x)$ and $F'(x)$ be two quadratic homogeneous functions, and $H$ and $H'$ be their corresponding matrices, respectively. We refer to [18, 19] for a characterization for EA-equivalence of $F$ and $F'$.

Up to now, we have introduced the main theoretical results of the paper which are the theoretical bases of Algorithm 1 in the next section.

4 Constructing quadratic APN functions from a given QAM

In this section, we will give an algorithm to construct QAMs, from which we can get lots of new quadratic APN functions. Our algorithm can be summarized as guess and determine, which means we modify the elements of a known QAM to get a new matrix, and then determine whether the new matrix is a QAM. With the help of previous results, the data complexity of constructing new quadratic APN functions can be greatly reduced.

4.1 Properties of matrices over $\mathbb {F}_{2^n}$

In this subsection, we will give several results on matrices over $\mathbb {F}_{2^n}$ which are useful for designing effective algorithms for constructing quadratic APN functions.

Lemma 4

Let $H\in \mathbb {F}_{2^n}^{n\times n}$ be a symmetric matrix with main diagonal elements all zero. Then every nonzero linear combination over $\mathbb {F}_2$ of the $n$ rows of $H$ has rank at most $n-1$.

Proof

Obviously, $H[i]$ has rank at most $n-1$ for any $1 \le i \le n$. Suppose $\mu =H[i_{1}]+H[i_{2}]+\cdots +H[i_{t}]$, where $2\le t\le n$ and $\{i_{1},i_{2},\ldots ,i_{t}\}$ is a subset of $\{1,2,\ldots ,n\}$. Then we have $\mu [i_{1}]+\mu [i_{2}]+\cdots +\mu [i_{t}]=0$, so $\mathrm Rank_{\mathbb {F}_{2}}(\mu )\le n-1$, which implies this proposition. $\square$

For the convenience of our discussions, we give the following definition:

Definition 6

Let $H\in \mathbb {F}_{2^n}^{m\times k}$ ($m,k \le n$). $H$ is called proper if every nonzero linear combination over $\mathbb {F}_2$ of the $m$ rows of $H$ has rank at least $k-1$.

First, we give the following lemma.

Lemma 5

Let $A\in \mathbb {F}_{2^n}^{r \times c}$ ($1 \le r < c \le n$), and $A'=AP$, where $P\in \mathbb {F}_{2}^{c\times c}$ is invertible. Then $A$ is proper implies that $A'$ is also proper.

Proof

Let $S=\{\sum _{i=1}^{r}\lambda _{i}A[i]: (\lambda _{1},\ldots ,\lambda _{r})\in \mathbb {F}_{2}^{r}\backslash \{0\} \}$, and $S'=\{\sum _{i=1}^{r}\lambda _{i}A'[i]: (\lambda _{1},\ldots ,\lambda _{r})\in \mathbb {F}_{2}^{r}\backslash \{0 \}$. Let $S''=\{sP:s \in S\}$. Then $S'=S''$, and since $P$ is invertible, we have $\mathrm{{Rank}_{\mathbb {F}_{2}}}(s)=\mathrm{{Rank}_{\mathbb {F}_{2}}}(sP)$. $\square$

Now we can prove the following theorem:

Theorem 4

Let $A=(a_{i,j})\in \mathbb {F}_{2^n}^{r \times c}$ ($1 \le r < c \le n$) with $a_{i,j}=a_{j,i}$ and $a_{i,i}=0$ for $1\le i,j \le r$. Let $A[\cdot ,k]$ be the $k$-th column of $A$, and $b=\sum _{k=1}^{c}\lambda _{k}A[\cdot ,k]$, where $0\not =(\lambda _{1},\ldots ,\lambda _c)\in \mathbb {F}_{2}^c$. Assume $t=\mathrm{Rank}_{\mathbb {F}_{2}}\{b[1],b[2],\ldots ,b[r]\}$. If $A$ is proper, then we have:

(i) If $(\lambda _{r+1},\ldots ,\lambda _{c})=0$, then $t=r-1$;

(ii) If $(\lambda _{r+1},\ldots ,\lambda _{c})\ne 0$, then $t=r$.

Proof

• (i) Assume $(\lambda _{r+1},\ldots , \lambda _{c})=0$. Then $b=\sum _{k=1}^{r}\lambda _{k}A[\cdot ,k]$. By Lemma 4, $t\le r-1$. Let $B=\mathrm{Submatrix}(A,1,1,r,r)$, by the definition of $A$, we have

  $$\begin{aligned} \mathrm{Rank}_{\mathbb {F}_{2}}\left( \sum _{k=1}^{r}\lambda _{k}A[\cdot ,k]\right)&= \mathrm{Rank}_{\mathbb {F}_{2}}\left( \sum _{k=1}^{r}\lambda _{k}B[\cdot ,k]\right) \\&= \mathrm{Rank}_{\mathbb {F}_{2}}\left( \sum _{k=1}^{r}\lambda _{k}B[k]\right) . \end{aligned}$$

  If $t < r-1$, then we have $\mathrm{Rank}_{\mathbb {F}_{2}}(\sum _{k=1}^{r}\lambda _{k}A[k])<r-1 + (c-r)=c-1$, which contradicts with $A$ being proper. Thus $t=r-1$.

• (ii) Suppose $(\lambda _{r+1},\ldots , \lambda _{c})\ne 0$. Without loss of generality, let $\lambda _{c}=1$. Then substitute $A[\cdot ,c]$ with $b$, we get a new $r\times c$ matrix $A'$. If $t<r$, then there exists $0\not =(\lambda _{1}',\ldots ,\lambda _{r}')\in \mathbb {F}_2^r$ such that $\lambda _{1}'A'[1,c]+\lambda _{2}'A'[2,c]+\cdots +\lambda _{r}'A'[r,c]=0$. Without loss of generality, suppose $\lambda _{1}'\ne 0$. Next we perform the following operations step by step, first, substitute $A'[1]$ with $\sum _{i=1}^{r}\lambda _{i}'A'[i]$ and get a new matrix $A''$; second, substitute $A''[\cdot ,1]$ with $\sum _{i=1}^{r}\lambda _{i}'A''[\cdot ,i]$ and get a new matrix $A'''$. By Lemma 5 and the definition of the proper, it implies that $A'$, $A''$ and $A'''$ are also proper. However, after these changes, we have $A'''[1,1]=A'''[1,c]=0$, which contradicts with $A'''$ being proper. Thus $t<r$ is not true, so $t=r$.$\square$

According to Theorem 4, we get the following corollary.

Corollary 2

Let $H=(h_{u,v})_{n \times n}$ be an $n\times n$ symmetric matrix over $\mathbb {F}_{2^n}$, and $A=\mathrm{Submatrix}(H,1,1,r,c)$ with $r<c$. Suppose $B=A^{T}=\mathrm{Submatrix}(H,1,1,c,r)$. Then $A$ is proper implies that $B$ is also proper.

Corollary 2 will be useful to speed up our algorithm for constructing QAMs. The key point is that every submatrix of a QAM must be proper (see Definition 6), so if a matrix has a submatrix which is not proper, it cannot be a QAM. Based on this corollary, we can exclude some improper candidates in advance when we haven’t known the whole values of the matrix. We know that every QAM is symmetric, so we will know the values of $A=\mathrm{Submatrix}(H,1,1,r,c)$ and $B=A^{T}=\mathrm{Submatrix}(H,1,1,c,r)$ at the same time. According to Corollary 2, we need only to check whether $A$ is proper. Thus some unnecessary checking can be avoided in our searching algorithm.

4.2 How to construct QAMs

In this section, we will introduce a problem, and then show how to construct QAMs through solving this problem.

Problem 1

Let $e_{i}$ be a vector of length $n$ with $e_{i}[i]=1$ and $e_{i}[j]=0$ for $j \ne i$. The problem is, how to find $\overrightarrow{x}=(x_{1},\ldots ,x_{n-1})\in \mathbb {F}_{2^{n}}^{n-1}$ satisfying

$$\begin{aligned} \lambda _1x_1+ \cdots + \lambda _{n-1}x_{n-1} \in S_{\lambda _{1}e_{1}+\cdots +\lambda _{n-1}e_{n-1}}, \end{aligned}$$

(11)

for all $(\lambda _{1},\ldots ,\lambda _{n-1}) \in \mathbb {F}_{2}^{n-1}\backslash \{0\}$, where $S_{\lambda _{1}e_{1}+\cdots +\lambda _{n-1}e_{n-1}}$ are some subsets of $\mathbb {F}_{2^{n}}$.

(11) consists of $2^{n-1}-1$ conditions, we need to find all the qualified $\overrightarrow{x}$. As a matter of fact, all the constructions of QAMs can be reduced to Problem 1. Details are described as follows.

Given an $n\times n$ QAM matrix $H$ over $\mathbb {F}_{2^{n}}$, we wish to reassign the values of the last column of $H$ to get some new QAMs. Let $A=\mathrm{Submatrix}(H,1,1,n-1,n-1)$, it is easy to see that $A$ is proper. By Lemma 4, any nonzero linear combination of the $n-1$ rows of $A$ has rank $n-2$.

Let $c=(x_1,\ldots ,x_{n-1})^t$, and $H'=\left( \begin{array}{ll}A&{}c\\ c^t&{}0\\ \end{array}\right) .$ We want to choose suitable $c$ to make $H'$ a QAM. Actually, by Theorem 4 (ii), we need only to choose $c=(x_1,\ldots ,x_{n-1})^t$ to satisfy (11), where $S_{\lambda _{1}e_{1}+\cdots +\lambda _{n-1}e_{n-1}}=\mathbb {F}_{2^{n}}\backslash \mathrm{Span}(\lambda _{1}A[1]+\cdots +\lambda _{n-1}A[n-1])$.

We can shrink $S_{e_1}$ in (11). Let $V=\mathrm{Span}$($A[1,1]$, $A[1,2]$, $\ldots$, $A[1,n-1]$), in (11), $S_{e_{1}}=\mathbb {F}_{2^{n}}\backslash V$, which equals to $(V+a_1) \cup (V+a_2) \cup (V+a_3)$ for some $a_i\in \mathbb {F}_{2^n}$, $1\le i \le 3$ because of $\mathrm{dim}(V)=n-2$. Since $x_1\in S_{e_{1}}$, there exists $y\in V$ such that $x_1=y+a_i$ for some $i$, i.e., $a_i=x_1+y$. Since $y\in V$ and $A[1,1]=0$, $y=\lambda _2 A[1,2]+\cdots +\lambda _{n-1} A[1,n-1]$ for some $\lambda _i\in \mathbb {F}_2$, $i=2,\ldots ,n-1$. So we may perform suitable column transformations to change $x_1$ into $a_i$, and perform the corresponding row transformations to change $H'[n,1]$ into $a_i$. Since we consider only to find CCZ-inequivalent functions, so by Theorem 2, we may take $S_{e_{1}}=\{a_{1},a_{2},a_{3}\}$. Because in the above transformation, we do not use the first column, therefore based on the same reason as the $S_{e_1}$, we may take $S_{e_2}=\{b_1,\ldots ,b_l\}$, where $l=2^{n-1}-2^{n-3}$.

Further, given a QAM $H$, we may also reassign the values of the last two columns of $H$ to get some new QAMs. This can also be reduced to Problem 1, the difference is that we must apply the problem twice. Similarly, we can reassign more columns of $H$, so this method can generate almost all CCZ-inequivalent quadratic APN functions if we change enough columns.

In view of the above discussions, an algorithm for solving Problem 1 is important for our approach for constructing new quadratic functions. We give a recursive algorithm as Algorithm 1. It needs to run $\mathrm {GenerateQAM}(1,H,S)$ to solve Problem 1.

In the following, we give an example to illustrate the above algorithm.

Example 1

Let $n=4$ and we work on $\mathbb {F}_{2^4}$, and

$$\begin{aligned} H=\left( \begin{array} {*{4}{c}} 0 &{}\quad H[1,2] &{}\quad H[1,3] &{}\quad \mathbf {x_{1}} \\ H[2,1] &{}\quad 0 &{}\quad H[2,3] &{}\quad \mathbf {x_{2}} \\ H[3,1] &{}\quad H[3,2] &{}\quad 0&{}\quad \mathbf {x_{3}} \\ \mathbf {x_{1}} &{}\quad \mathbf {x_{2}}&{}\quad \mathbf {x_{3}}&{}\quad 0\\ \end{array}\right) . \end{aligned}$$

Suppose A = Submartix($H,1,1,3,3$) is proper. The above algorithm is about how to keep $H$ proper when assigning values for $x_{1}$, $x_{2}$ and $x_{3}$. The basic idea is, if $x_{1} \in \mathrm{Span}(A[1])$, then $H$ is not proper. So $x_1$ must be chosen such that $x_1\in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1])$. Similarly, if $x_{1}+x_{2} \in \mathrm{Span} (A[1]+A[2])$, then $H$ is not proper, thus $x_{1}+x_{2} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1]+A[2])$. With the same reasoning, $H$ is proper if and only if

$$\begin{aligned} \left\{ \begin{array}{*{1}{l}} x_{1} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1]),\\ x_{2} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[2]),\\ x_{3} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[3]),\\ x_{1}+x_{2} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1]+A[2]),\\ x_{1}+x_{3} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1]+A[3]),\\ x_{2}+x_{3} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[2]+A[3]),\\ x_{1}+x_{2}+x_{3} \in \mathbb {F}_{2^4}\backslash \mathrm{Span}(A[1]+A[2]+A[3]).\\ \end{array} \right. \end{aligned}$$

The above algorithm is a generalization of this example.

4.3 Experimental results

We have implemented the algorithm of this paper. In this subsection we will report experimental results running our algorithm.

• (i) Dillon [13] listed 18 classes of CCZ-inequivalent APN functions over $\mathbb {F}_{2^{7}}$. Edel [16] found a new class of APN function and this list expanded to 19 classes. With the method of this paper, firstly, we construct a $7\times 7$ QAM $H$ from $x^3$, then reassign the values $H[3,6]$, $H[3,7]$, $H[4,5]$, $H[4,6]$, $H[4,7]$, $H[5,6]$, $H[5,7]$ and $H[6,7]$ (during this process, we must keep $H$ symmetric). Using this idea we can get more than 470 classes of CCZ-inequivalent quadratic APN functions, these functions are all CCZ-inequivalent to the known ones. Similar method can be used on $\mathbb {F}_{2^6}$. According to Edel’s results [15], there is only 13 classes of CCZ-inequivalent quadratic APN functions on $\mathbb {F}_{2^6}$. Our algorithm shows that we need only to change 8 $(2\times 4)$ elements of of a QAM and get all 13 classes of CCZ-inequivalent quadratic APN functions.

• (ii) We must change the last two columns (and rows) of a known QAM to get new QAMs when $n\ge 8$. On $\mathbb {F}_{2^{8}}$, it needs about 24 h to find a new APN function in a personal computer. Fortunately, Algorithm 1 can be implemented in parallel, and we are running our programs in several computers now. Up to know, we have found about 2252 CCZ-inequivalent quadratic APN functions on $\mathbb {F}_{2^{8}}$, and they are all CCZ-inequivalent to the 23 classes of known ones introduced by Dillon [13] and Edel and Pott [16]. We have checked all these new APN functions with the method introduced in [5], none of them is CCZ-equivalent to a permutation. We refer the readers to [25] for detailed experimental results, where we list all newly found APN functions in polynomial forms.

5 Conclusion

A one to one correspondence between quadratic homogeneous APN functions and QAMs is presented. In view of this correspondence, we propose the notion of the proper for matrices over a finite field. The most important part of our algorithm is how to keep the matrix proper during the construction process. Algorithm 1 is the core part of our searching program.

Up to now, we have found 471 and 2252 new CCZ-inequivalent quadratic APN functions on $\mathbb {F}_{2^7}$ and $\mathbb {F}_{2^8}$ respectively (see the appendices in [25]). We think our lists are not complete, especially the list on $\mathbb {F}_{2^8}$. Much related work can be done in the future, such as, finding some QAMs whose corresponding functions are APN on $\mathbb {F}_{2^n}$ for infinitely many $n$, generalizing the matrix approach to construct PN functions, and finding better methods to construct QAMs, etc.