数理解析研究所講究録
第 1687 巻 2010 年 118-130

118

On some Representations of Quadratic APN Functions andDimensional Dual Hyperovals
Yves Edel *Department of Pure Mathematics and Computer Algebra
Ghent University, Krijgslaan 281, S22
B-9000 Ghent, Belgium

1. Introduction
APN functions (see Definition 1) have become a quite popular area of research and especially quadratic APN
functions have links to various other mathematical areas. One link is to geometry, namely dimensional dual
hyperovals (see Definition 2). Quadratic APN functions are equivalent to certain subspaces of the alternating
bilinear forins, and most examples of dual hyperoval are, or can be, constructed from certain subspaces of thebilinear foi ms.
As consequence different related publications use substantially different notation. The present manuscript isba.scd on l,he aut hors
to providc an explicit tran.slat,ion or t,hc not at ion
in several papers on APNfunctions and dual hypeiovals by Nakagawa, Taniguchi and Yoshiara, into his own notation and back.
The focus of } $iis$ manuscript are the representations. An other important point, the question of equivalence
is not touched. We refer to $|14]$ for the characterization of the dual hyperovals that ai ise fiom quadratic APN
functions via the constructioii as described in Proposition 6, for the correspondence of their mutual equivalenceclasses as well as for an explicit construction of the APN function, given an “APN-dual hyperoval”.
Furtherinore we restrict ourselves to the binary case, although some results hold also in more generality. Firstly
as most results on APN functioiis are only for this case, secondly as the notation often gets substantially lesscomplicated. For rnore extensive references, overviews over actual or more general results, open problenis andmotivations we refer to some recent overview aiticles 8, 9, 16, 22 .
$cIr_{oi\cdot 1.S}$$ro\iota ind$

$t$

$[$

$]$

This manuscript is organized as follows: In the next section APN functions are iiitroduced and several conditions
for being quadratic are giveii. Section 3 deals with several ways of representing (alternating) bilinear forms aswell as with representations of subspaces of this forms. Section 4 gives some characterizations of APN functions
illof these subspaces. In Section 5 dimensional dual hyperovals will be introduced aiid characterized in
terrns of (alternating) bilinear foriiis. This section concludes with an alternative proof of Taniguchi’s result [21,Theorem 11]. Ill the Appendix the trace representation of vector spaces of (alternating) bilinear forins will be
discussed and the alternating subspaces, in this representation, coming from APN functions are treated in detail.
$tei\cdot nis$

2. Quadratic APN functions
Definition 1. Let$\mathbb{F}_{p}$be the finite field with$p$elements,$\forall(a\in \mathbb{F}_{\rho}^{m}\backslash \{0\})\forall(b\in \mathbb{F}_{p}^{n})$:$p$prime. A function$)$

which satisfies$|\{x\in \mathbb{F}_{p}^{m}|f(x+a)-f(x)=b\}|\leq d$with $d=1$ , is called perfect nonlinear (PN) or planar. The function
APN
equal.zon with $d=2$ .
$($$f:\mathbb{F}_{p}^{m}\mapsto \mathbb{F}_{p}^{n}$$f$

is called almost perfect nonlinear$\uparrow\int ztsa\ell i_{\backslash }s[\downarrow eslhe$

PN functions do not exist in even characteristic. Due to the existence of PN functions in odd charactei istic,
APN functions ale mostly only studied in characteristic 2 and the majority of papers on APN functions only deal
with the (extremal) case $m=\cdot n$ . However there exist also some results in an even more general setting, obtainedby replacing the vector spaces in Definition 1 by arbitrary abelian groups (see e.g. [10, 18]).
A function:
can be repiesented bypolynomials(also called booleaninfunctions, in the case $p=2$ ). What is referred as (algebraic) degree of an APN function is maxiinum
$f$

’

$n$

$F_{p}^{m}arrow \mathbb{F}_{\rho}^{n}$$f_{i}$$\mathbb{F}_{\rho}[X_{1}, \ldots, X_{m}]$The rescarch of this author takes placc within IIC projcct “ Linear codes and cryptography” of thc Research Foundation –Flandcrs(FWO) (Projcct nr
031706), and is supportcd by thc Intcruniversitary Attraction Polcs Programme-Belgian State-Belgian
Scierice Policy: project $P6/26$ -Bcrypt.
$t$

$G$

119
among the algebraic degreesof the corresponding polynomials in $m$ variables, i.e. the maximal number ofvariables, in a monomial with non vanishing coefficient, of the algebraic normal form of one of the .
Quadratic APN functions are APN functions of degree 2. We will restrict us to quadratic APN functions.
$d^{o}(f_{i})$$f_{i}$

If $n=m$ the same mapping considered as:
can be represented as an univariate polynomial.
Let the p-weight of an integer be the sum of its coefficients in its p-adic representation, i.e:$f$$\mathbb{F}_{p^{m}}arrow \mathbb{F}_{p^{m}}$$f\in \mathbb{F}_{p^{m}}[X]$$w_{p}( \sum_{i=0}^{\iota}a_{i}p^{i}):=\sum_{l=0}^{\iota}a_{i}\in \mathbb{Z}$with $0\leq a_{i}<p$

The p-weight of a univariate polynomial is defined as$uj_{P}( \sum_{i=0}^{l}u_{t}X^{i})$$:= \max\{w_{p}(i)|u_{i}\neq 0\}$The p-weight of the univariate polynomial equals the algebraic degree of the same map written as multivariate
polynomial. This can be found e.g. in [9, Section 1.1], for $p=2$ , in more detail.
Univariate polynomials of p-weight 1 are called linearized polynomials, these are all-linear maps.
$\mathbb{F}_{p}$The (additive) derivate in (in direction $a\neq 0$ )$D_{a}f$

is dcfiincd as$D_{a} \int(x)=f(x+a)-\int(x)$APN functions are defined by properties of their derivate (Definition 1). The derivate is not symmetric in, we will define a symmetric version.

$x$

and

$a$

$\delta_{v}f(x):=f(x+y)-f(x)-f(y)-f(0)$Uircct verification shows that$\delta_{T}k$$\delta_{x_{2}}f(x_{1})=\sum_{I\subseteq\{1,..k\}}.,(-1)^{k-|J|}f(\sum_{i\in I}x_{i})$For coiistant the derivate $D_{a}(f)$ andtlierefore will lead to equivaleiit definitions.
$a$$\delta_{a}f$.

differ only by a constant. Substituting $D_{a}f$ by$\delta_{a}f$in Definition 1

In the following we will always assume that $p=2$ .

.
.
.

Proposition 1. The following characterization of a quadratic function are equivalent:$\circ$.

$\int has$

algebraic degree $d^{o}( \int)=2$ .

For $n=m$ .

$f$

has 2-weight $w_{\rho}(f)=2$ .

For all $a\neq 0$ D.

$f$

is

$\mathbb{F}_{2}$-linear $(rightarrow additiverightarrow d^{o}(D_{a}f)\leq 1)$$B_{f}(x, y)=\delta_{v}f(x)=f(x+y)+f(x)+f(y)+f(O)$ is an alternating bilinear function.

$\delta_{z}\delta_{y}f(x)=f(x+y+z)+f(x+y)+f(y+z)+f(z+x)+f(x)+f(y)+f(z)+f(O)$ is constant zero.

Proof. The argumentation relays on the (unproven) property that for a non-constant function , the algebraic, viewed as function in , is smaller than the algebraic degree of $f$ and is (exactly) d’ $f-1$ , ifdegree of$d^{o}f>1$ . The verification of tliis remark is straiglit forward but lengtlily aiid therefore omitted.
Direct verification shows that $B_{f}(x, y)$ is symmetric and $B_{f}(x, x)=0$ .
Assume is quadratic. The above remark states that $B_{f}(x, y)$ is linear as function in . By symmetry it isbilinear.
is a constant (as derivate of a linear function). Choose $x=y=z=0$ . This show that thisconstant is zero.
Now assume that the algebraic degree of $f$ is larger than 2. By the remark we have that $B_{f}(x, y)$ is not linear$f$$\delta_{y}f(x)$

$x$

$f$

$x$

$\delta_{z}\delta_{y}\int(x)$

in

$x$

and

$\delta_{z}\delta_{y}f(x)$not constant.

$\square$120
3. On the vector space of (alternating) bilinear forms
3.1. Bilinear forms
We now look on different (unique) representations for a bilinear form A bilinear form is a map$b(x, y)$ :$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}\mapsto \mathbb{F}_{2}$for which $b(x+x’, y)=b(x, y)+b(x’, y)$ and $b(x, y+y’)=b(x, y)+b(x, y’)$ .

, a bilinear form $b(x, y)$ is called alternating if additionally, for all
In casethat $b(x, y)=b(y_{i}x))$ .
and write anas $x= \sum_{1=1}^{u}x_{t}e_{i},$Choose some basisof$l=\tau r\iota$$e_{1},$$\ldots,$$x_{1}\in \mathbb{F}_{2}$$x\in \mathbb{F}_{2}^{u}$$\mathbb{F}_{2}^{u}$$e_{u}$$x\in \mathbb{F}_{2}^{m},$$b(x, x)=0$ (this implies.

3.1.1. The matrix representation.
The perhaps most basic representation of a bilinear form is by a matrix$b(x.y)=x^{t}$ My$= \sum_{i=1}^{l}\sum_{g=1}^{m}\prime r.m.,j\uparrow/J$

’

where

$Mf\in \mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}$.
(1)$m_{1},J=b(e_{1}, e_{j})\in \mathbb{F}_{2}$An alternating form $(l=rr\iota)$ is given by a symmetric matrix $(m_{t_{I}g}=rn_{J},.)$ with main diagonal zero$(7’\downarrow i_{1}=0)$.

3.1.2. Representation using the tensor product, Variant 1, with the tensor productldentify thecan be uniquely written using a linear map$(x, y)\in \mathbb{F}_{2}^{\iota}x\mathbb{F}_{2}^{n\tau}$$(x \infty y)=\sum_{1}\cdot Jx_{1}y_{j}(c_{t}\otimes c_{j})\in \mathbb{F}_{2}^{l}\infty \mathbb{F}_{2}^{m}$$\mathbb{F}_{2}^{n}\otimes \mathbb{F}_{2}^{\mathfrak{n}}arrow \mathbb{F}_{2}$$\gamma$. Any bilinear form

(this is the so called universal property of the tensor

product).
$b(x, y)=(x8y)^{\gamma}= \sum_{z,j}x_{i}y_{j}(e_{i}\otimes e_{J})^{\gamma}=\sum_{i,j}x.y_{J}m_{i,j}$, where $m_{1,j}=(e$.

$\otimes e_{j})^{\gamma}=b(e_{i}, e_{j})\in \mathbb{F}_{2}$By the same
. The
oning an alternating bilinear forrri can be given through a liiiear map .
generated by the eleiiients $(e_{1}\otimes e_{j})+(e_{j}\otimes e.)=$ :can be viewed as the subspace of
vectoi space. Observe $(x\wedge?/)=0$ alld $(x\wedge?/)=(\uparrow/\wedge x)$ . We get:$1^{\cdot}e_{C}\gamma_{S}$$\gamma$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}$$\mathbb{F}_{2}^{l11}\otimes \mathbb{F}_{2}^{m}$$(e_{t}\wedge e_{j})$$b(x, y)=(x A y)^{\gamma}=\sum_{<j}(x_{I}?1_{J}+x_{j}?/1)(e_{i}\wedge\rho_{g})^{\gamma}=\sum_{{}^{t}J}(x_{\iota^{1}}/j+x_{J}y_{1})m_{i,j}$, where $m_{\iota,j}=(e_{1}$ A $(’ j)^{\gamma}=b(e_{i},$$e_{j})\in \mathbb{F}_{2}$3.1.3. Representation using the tensor product, Variant 2
has tlie same dimeiision overObserving that the vector space of all bilinear form
bilinear form can be identified with an element (or equivalently a l-dimensional subspace) ofvector space isoinoi phisn We will use:$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{n1}arrow \mathbb{F}_{2}$$\mathbb{F}_{2}$as$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$, a
by fixing a$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$$\downarrow$$\sum_{1j}u_{1,j}(e, \otimes e_{2})rightarrow b(x, y)=\sum_{1,j}x_{1}y_{J}u_{\iota,g}$.

Proceeding analogously for alternating bilinear forrns gives:$\sum_{i<j}u_{\iota,g}(e_{1}\wedge e_{j})rightarrow b(x, y)=\sum_{l<J}(x_{1}y_{J}+x_{g}y_{\iota})u{}^{t}J$.

Then there is a nice correspondence between Variant 1 and Variant 2. An element $\sum_{1},Ju.,j(e_{1}\infty c_{j})$ corresponds. And every linear map .
.
to the map
dchines thc clci}ientsame bilinear form is obtained if we apply the image under this corespondents in the respective variant.
For alternating bilinear forms we proceed analogously.
$\gamma$$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{n\iota}arrow \mathbb{F}_{2}$$(c_{1}\otimes c_{J})\mapsto u_{1},J$$\gamma$$\sum_{\mathfrak{i},j}(c_{i}\otimes c_{j})^{\gamma}(e\iota\otimes e_{j})$$T\}_{1}e$3.1.4. Representation as polynomial in$x_{1},$$y_{z}$.

Any function $b(x, y)$ :can be written as $polynon\iota$ ial in $F_{2}[x_{1}, , x\iota, y_{1} y_{m}]$ . The function is, as well as with respect to the variables
bilinear, if its algebraic degree with respect to the variables.
,,
is one. I. . (again) we have that$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}\mapsto \mathbb{F}_{2}$$x_{1}$$y_{1}$$y_{m}$)$x_{l}$$e$$b(x, y)= \sum_{1.j}rr{}^{t}Jx_{1}y_{j}$ :

.

where

$r_{1},J=b(e_{1}, e_{J})\in \mathbb{F}_{2}$$b(x, y)$ is an alternating form if $m_{1},J=m_{J},$ and $m_{t,1}=0$ . This is just the matrix representation under a different
point of view.

121
3.1.5. The trace representation
Let $l=m$ . Consider $x,$ now as elements of the field
be uniquely given in the form$y$$\mathbb{F}_{2^{m}}$. The$b(x, y)=tr(l(x)y)$ with$(\mathbb{F}_{2})$-bilinear form $b(x, y)$ :$\mathbb{F}_{2^{m}}\cross \mathbb{F}_{2^{m}}\mapsto \mathbb{F}_{2}$

can
(2)

$l(x)= \sum_{k=0}^{m-1}\alpha_{k}x^{2^{k}}$This representation is usually dedicated to Delsarte and Goethals [12]. It will be refered in the following as thetrace representation of a bilinear form.
which defines the linearized polynomial 1.
We also identify $b(x, y)$ with the element$(\alpha_{0}, .

.

, \alpha_{m-1})\in(\mathbb{F}_{2^{m}})^{m}$

For alternating bilinear forms, the same representation as in Equation 2 is obtained, only the linearized polynomial is of special form:$l$$\alpha_{0}=0$,$\alpha k=\alpha_{m-k}^{2^{k}}$,Especially if $m=2r$ :$\alpha_{r}=\alpha_{r}^{2^{r}},$

$i.e$

.

$\alpha_{r}\in \mathbb{F}_{2^{r}}$So the trace representation of an alternating form is determined by the element$(\alpha_{1}, \ldots\alpha_{r})\in\{\begin{array}{ll}(\mathbb{F}_{2^{m}})^{r-1}x\mathbb{F}_{2^{r}} if m=2r(\mathbb{F}_{2^{m}})^{r} if m=2r+1\end{array}$

Details on the trace representation, and explicit conversions to the other representations have been transferredto the Appendix , as they need some room.
$A$

3.2. Vector spaces of bilinear forms
3.2.1. Basic definitions
The bilinear forms $b(x, y)$ :Defiiic a scalar product:$\langle,$$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}$form a lm-dimensional vector space which will be denoted as$\rangle:\mathcal{B}(x, y)\cross \mathcal{B}(x, y)arrow \mathbb{F}_{2}$,The alternating bilinear forms $b(x, y)$. We define a scalar product on
denoted as$\langle\sum_{i,j}m_{\tau,j}x_{i}y_{j}$$\mathbb{F}_{2}^{m}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}$$\mathcal{A}(x, y)$$\langle,$,$\mathcal{A}(x, y)$.

$\mathcal{B}(x, y)$.

$\sum_{i,j}m_{\mathfrak{i},j}’x_{i}y_{j}\rangle:=\sum_{1,j}m_{i,j}m_{i,j}’$form a$(\begin{array}{l}m2\end{array})$-dimensional vector space which will be:$\rangle_{a}:\mathcal{A}(x, y)\cross \mathcal{A}(x, y)arrow \mathbb{F}_{2}$$\langle\sum_{\mathfrak{i}<j}m_{i,j}(x_{i}y_{j}, +x_{j}y_{i}),$$\sum_{i<j}rr\iota_{i,j}’(x_{i}y_{j}, +x_{j}y_{i})\rangle_{a}:=\sum_{i<j}rr\iota_{i,j}m_{j\prime}^{\dot{\prime}}$

Observeis not the restriction of , onviewed as subspace of . An adapted scalar product for the tracerepiesentation is defined in Appendix A.
$y))$ define the dual subspace $B^{\perp}(x.y)$ as
For a subspace $B(x, y)\subseteq \mathcal{B}(x, y)$ resp $B(x,$$\langle,$$\rangle_{a}$$\}$$\langle$$y)\subseteq \mathcal{A}(x,$$($$B^{\perp}(x, y)$$=$$B^{\perp}(x, y)$$.=$$\mathcal{B}$$\mathcal{A}$$\{b’(x.

y)\in \mathcal{B}(x, y)|\forall b\in B : \langle b’(x, y), b(x, y)\rangle=0\}\subseteq \mathcal{B}$$\{b’(x, y)\in \mathcal{A}(x, y)|\forall b\in B : \langle b’(x, y), b(x, y)\rangle_{0}=0\}\subseteq \mathcal{A}$Dual subspaces in the trace representation are teated in Appendix A.2.
$y)$ ), is the subspace(resp.
left radical IR $(b),$$T\}_{1}e$$b\in \mathcal{B}(x, y)$$|R(b)$$\mathcal{A}(x,$$:=\{x\in \mathbb{F}_{2}^{l}|\forall y\in \mathbb{F}_{2}^{m} :.

(b(x, y)=0)\}\subseteq \mathbb{F}_{2}^{l}$$y)$ ) is defined as
The right radical $rR$ is defined analogously. The rank rank $(b)$ of $b(x, y)\in B(x, y)$ (resp.
the codimension of the left radical. The rank of $b(x, y)= \sum_{i,j}rn_{t,j}x_{t}y_{j}$ equals the rank of the matrix $(m_{i,j})$ .
Hence the rank of $b(x, y)$ also equals the codimension of the right radical.
$\mathcal{A}(x,$A well known property of alternating forms is that every$b\in \mathcal{A}(x, \tau/)$

has even rank.

$y)$ ),(respfor any chosen
The straight forward inethod of giving a n-dimensional subspace ofrepresentation of bilinear forms, is to give a basis
or a generator set of the subspace (or its dual).
(or of aiiy n-dimensional subspace $V$ ) the subspace
By choosing a basis
can be associated with theof$\mathcal{B}(x, \tau))$$\mathcal{A}(x,$$b_{\mathfrak{i}}$$f_{i}$$l3$$\mathbb{F}_{2}^{n}$bilinear map$B(x, y)$ :$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}^{n}$,$B(x, y)$ $:= \sum_{i=1}^{n}f_{l}b_{i}(x, y)$

(3)

122
Reversing the process gives us, from a bilinear map $B(x, y)$ .
(resp$\mathcal{A}(x,$$y)$$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}^{n}$, a n-dimensional subspace of$\mathcal{B}(x, y)$).

In the special case $l=m$ , the alternating bilinear map $B_{f}(x, y)$ :can be represented by$f$ (see Proposition 1).
From [14, Lemma 4,5] follows that $f$ can be reconstructed, up toequivalence, fromand that equivalent alternating bilinear forms
lead to EA-equivalent quadratic
functions and $f’$ and vice versa (the APN condition is not used in the proof).
A geometric characterization quadratic APN functions (and hence also of the corresponding alternating bi) will be given in Proposition 6. More details are to be found in [14].
linear form$\mathbb{F}_{2}^{m}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}^{n}$a quadratic function$B_{f}$$B_{f},$ $B_{f’}$

$f$

$f$

$B_{f}$In the case that $l=m$ , the n-dimensional subspace of , resp.
can also be represented in terms of the trace
representation. If $l=m=n$ the subspace can be given by an-linear or linearized polynomial in two variables. This will be done in Appendix A.
$B$$\mathcal{A}$$\mathbb{F}_{2}$$\mathbb{F}_{2^{m}}[X, Y]$

3.2.2. On representations of subspaces of bilinear forms using the tensor notation
If we use the tensor notation for bilinear forms as introduced in Sections 3.1.2 and 3.1.3, we have two further
possibilities.
Variant 2: This is based on Variant 2 for the forms (see Section 3.1.3). There, a bilinear form $b\in B$ (resp.
(resp), hence a subspace
was identified with an element of) will simply be(resp.
(resp). Explicitly:
identified with a subspace of$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$$\mathcal{A})$$S$

Observe that$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$$B(x, y)$$;=$$B(x, y)$$;=$$B\subseteq \mathcal{B}$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$$\{b(x, y)=\sum_{j:}m_{i,j}x.y_{j}|\sum_{1,j}m_{i,j}(e$.

$\otimes e_{j})\in S\}\subseteq \mathcal{B}$$\{b(x, y)=\sum_{i<j}m_{1j}(\tau_{\iota/j}r+x_{j}y_{i})|\sum_{\mathfrak{i}<j}m.,j(r_{\vee i}\wedge e_{j})\in S\}\subseteq \mathcal{A}$(with respect to the standard scalai product) gives us this way$S^{\perp}$$\mathcal{A}$$B^{\perp}(x, \uparrow/)$.

Variant 1: This is based on Variant 1 for the forms (see Section 3.1.2). Let
be a n-dirriensional subspaceoverand a surjective linear map:
resp.
. The map can be used to givean (alternating) bilinear map :resp. :
, which car bc dcfi $licd$ aiialog to Scctioii
3.1.2 asresp.
$\beta(x, y)=(x\otimes y)^{\Gamma}=\sum_{l,j}x_{i},$$V$$\Gamma$$\mathbb{F}_{2}$$\Gamma$$\beta$$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}\mapsto V$$\mathbb{F}_{2}^{l}\cross \mathbb{F}_{2}^{m}\mapsto V$$($$\beta$$y_{j}(e\iota\otimes e_{j})^{I^{\neg}}$$\Gamma$$($$\Gamma$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{n\iota}\mapsto V)$$\mathbb{F}_{2}^{l}\wedge \mathbb{F}_{2}^{m}\mapsto V)$

$1$

$($

$(x \wedge y)^{\Gamma}=\sum_{l,j}(x_{i}y_{j}+x_{j}y_{\iota})(e_{i}\wedge e_{j})^{\Gamma})$This, essentially, already gives us a n-dimensional subspace $B$ of (alternating) bilinear forrns and of(resp.
), but let’s do it explicitly.
.. ,, thenChoose a basis
of $V$ overresp.
for some : ::A$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$$f_{1},$.

$f_{n}$$\mathbb{F}_{2}$$F_{2}^{l}\otimes \mathbb{F}_{2}^{m}\mapsto \mathbb{F}_{2}$$\Gamma=\sum_{i}f_{l}\gamma_{\mathfrak{i}}$$\gamma$$($$\mathbb{F}_{2}^{m}$$\gamma_{i}$$\mathbb{F}_{2}^{m}\mapsto \mathbb{F}_{2})$.

It is equivalent:.

$\Gamma$

is a surjcctive map.

The projcct ion of$\Gamma$on any l-dimensional subspacc of$eV$ and the space spanned by the$\gamma_{1}$$V$

is non-trivial.

have equal dimension.

Identify the linear maps
(as in Section 3.1.3). The
span a n-dimensionalwith the elements(resp.
subspace of). Using Variant 2” gives us now a vector space of bilinear forms.
$\overline{\gamma}\iota\in \mathbb{F}_{2}^{\iota}\otimes \mathbb{F}_{2}^{m}$$\overline{\gamma}\iota$$\gamma_{i}$$\tilde{\Gamma}$$\mathbb{F}_{2}^{l}\otimes \mathbb{F}_{2}^{m}$$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$“

It will turn out useful for Corollary 4 to observe that for $ker(\Gamma)$ , the kernel of$\Gamma$, we have

Proposition 2.

kcr$(\Gamma)=\overline{\Gamma}^{\perp}$

Proof. As observed in Section 3.1.3 we have that$\overline{\gamma}_{k}=\sum_{Jt_{I}}(e_{1}\otimes e_{j})^{\gamma_{k}}(e_{1}\otimes e_{J})$

Hence for any$\sum_{1,j}$IL$i.g(e_{1}\otimes c_{j})\in l^{\tilde{\urcorner}\perp}$

and $fo1$ all $1\leq k\leq\eta$ ,.

$0= \langle\sum_{1,j}u{}^{t}J(e_{1}\otimes e_{j}),\overline{\gamma}_{k}\rangle=\sum_{l,j}u_{\iota},J(e_{i} \copyright e_{j})^{\gamma_{k}}=(\sum_{i_{J}}\iota\iota_{1},J(e$$\otimes e_{j}))^{\gamma_{k}}$123, and so also in the kcrnel ofby definition of duality. IIcncc
is in the kernel of each, henceis the full Kernel.
If is suijective, then the dimension ofis the codimension of$\Gamma^{\perp}$$\Gamma=\sum_{\iota}f_{i}\gamma_{i}$$\gamma_{k}$$V$$\Gamma$.

$\Gamma^{\perp}$$\Gamma^{\perp}$

For the alternating case we have the analog proof.

$\square$

As a subspace is unequally determined by its dual this implies that the subspace of bilinear forms given by isuiiiqucly dctcrmiiied by tlie kernel of the 11]ap . This charactei ization via the kei nel of is $cg$ . $fouJ$ id in [20, 22].
$\Gamma$$\Gamma$$\Gamma$

4. Different characterizations of APN functions
For a quadratic APN function$f$the derivate$B_{f}(x, s/)=\delta_{y}f(x)=\int(x+y)+\int(x)+\int(y)+\int(O)$. Let the alternating bilinear function given by ais an alternating bilinear function $B(x, y)$ :linear function , so $B(x, a)=(x\wedge a)^{\Gamma}$ (see Section 3.2.2, Variant 1).
$\mathbb{F}_{2^{m}}\cross \mathbb{F}_{2^{m}}arrow \mathbb{F}_{2^{n}}$$\Gamma$A (quadratic) functionis APN if and only if for all $a\neq 0$ the only nonzero solution of $B(x, a)$ is $x=a$ .
for $x\neq 0,$ .
Observe $(0\wedge a)=(a\wedge a)=0\in A$ and$x\neq 0,$, is in the kernel
As $B(x, a)=$ cc A a , we have that is APN if and only if no vector of the form
$x$

$f$

$0\neq(x\wedge a)\in \mathcal{A}$of$x\wedge a,$$f$$)^{\Gamma}$$($$\Gamma$

$a$

$a$

.

Following Nakagawa [20] call an element $x\wedge y,$ $0\neq x\neq y\neq 0$ , a pure element offollowing characterization of APN functions:
Proposition 3.

$f$

is $APN$ if and only if the kemel of 1“ contains no pure element ($rightarrow no$$\mathcal{A}$. This leads to thepure l-dim subspace).

It will be useful to have soine more notation for subsets of , introduced by Delsarte aiid Goethals [12], and for
subsets of introduced by Delsarte in [11]. We specialize the definitions, which were given in [11, 12] for subsets
resp. , heie to subspaces and mostly focusof.
$\mathcal{A}$$\mathcal{B}$$011\mathcal{A}$$\mathcal{B}$$\mathcal{A}$q-distance $d(b, b’)\cdot=$ rank $(b-b’)$ for elements in
is introduced. Also define the q-weightrank $(b)$ . (Perhaps we should call it heie the 2-weight and 2-distance).
A subspacehave q-weight greater then $t[11]$ . Asis called a t-design if all nonzeio eleiments ofa code in of
Delsarte himself stresses the analogy with error correction codes it would be natural to nameminimal distance $t+1$ .
A subspace of alternating bilinear forms
is called in [12] a $(m, d)$ -set if all nonzero
elements of $B$ have q-weight at least $2d$ (so if it is a“code” of minimal distance $2d$ ).
The cardinality of a $(m, d)$ -set $B$ is bounded by$b,$ $b’\in \mathcal{B}$$I_{11}[11]t1_{1}e$$?l)(b)$ $:=$

$B^{\perp}$$B\in \mathcal{B}$$B^{\perp}$$\mathbb{F}_{2}^{m}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2},$$|B|\leq 2^{()\frac{(r-d+1)}{r}}m2$$\mathcal{B}$$B\in \mathcal{A}$with$r= \lfloor\frac{rn}{2}\rfloor$

A $(m, d)$ -set obtaining this bound is called maximal [12].
(resp (
) of
) is defined
For subspaces of andthe weight distribution $(a_{0}, a_{m})$ of
by $a_{t}=|\{b\in B|\omega t(b)=i\}|)$ (resp. by $a_{i}=|\{b\in B|wt(b)=2i\}|$ ).
For subspaces, the weight distribution ofis uniquely deterinined by the weight distribution of $B$ alld canbe computed with a MacWilliams-like” transformation.
The weight distribution of maxiinal $(?1, d)$ -sets is uniquely deteimined [12, Theorein 4.ii], and for subspaces thedual of a maximal $(m, d)$ -set is a (maximal) $(m, r-d+2)$ -set [12, Theorem 5]. An OA-like characterization of a
( $ie$ . of the “dual code”) is given by Munemasa [19, Theorem 1]
t-design in
Analog results for subsets of can be found in [11].
$B\in \mathcal{B}$$\mathcal{A}$$\mathcal{B}$$a_{0)}$$a_{r}$$B\in \mathcal{A}$$B^{\perp}$‘$\mathcal{A}$$\mathcal{B}$

Next we want to give the APN condition in the case that $B$ is given in terrris of subspaces of $A$ (see Section
3.2.2, Vai iant 2).
Proposition 4.

$f$

is $APN$ if and only if$B^{\perp}\subseteq \mathcal{A}$is a $(m.2)$ -set ($rightarrow B^{\perp}is$a“code ” of distance 4).

Proof We start froiri Proposition 3 aiid use Proposition 2. That kcr $(\Gamma)=B^{\perp}$ is a $(m, 2)$ -set is equivalent to:that for all non-zero
the rank $(b)\geq 4$ , ie. (as bilinear forms of $A$ have even iank) that there is no withrank $(b)=2$ . Hence it only remains to show that for an alternating bilinear form it is equivalent:$b\in B^{\perp}$

.
.

$b$

$b$

$b(x, y)$hat rang 2$b(xy)$ corresponds to a pure element of$\mathbb{F}_{2}^{m}\wedge \mathbb{F}_{2}^{m}$

124

This follows by Proposition 5 below.

$\square$Proposition 5. The elements of rank $2r$ inwhich are linearly independent.

$\mathcal{A}$are the elements$\sum_{1=1}^{r}(x_{1}\wedge y_{1})$with some$x_{1}$,,$x_{r},$$y_{1}$,,$?/r\in \mathbb{F}_{2}^{m}$.

Proof The generic alternating bilinear form of rank $2r$ is $B(x, y)= \sum_{l}^{r}=1x_{2i-1}y_{2}$ $+x_{2i}y_{2\iota-1}$ which corresponds.
to the element
Any other alternating bilinear form of rank $2r$ can be obtained by a base change i.e. by the substitution $x’=Lx$ ,a$y=Ly$ , withmatrix of full rank. Hence $B’(x_{1}y)=B(x’, y’)=B(Lx, Ly)$ . The corresponding elernent
in
is $\sum_{i=1}^{r}(Le_{2_{1}-1}\wedge Le_{2}.)$ .
As is nonsingular, we have that the $2r$ elements
are arbitrary linear independent elements.
$\sum_{=1}^{\dot{r}}$$L$$(e_{2_{1}-1} A e_{2i})\in \mathcal{A}$$m\cross\uparrow\eta$$\mathcal{A}$$L$$\square$$Le_{i}\in \mathbb{F}_{2}^{m}$

Observe that for odd $m$ , if $\eta 1=n$ , the $(m, 2)$ -set$B^{\perp}$

Corollary 1. Let $m=2r+1$ . Then $f$ :if and only if all $0\neq b\in B$ have rank $n-1$ .

$\mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}^{m}$in Proposition 4 is maximal, with [12, Theorem 5] we get

is $APN$ if and only if$B\in \mathcal{A}$is a $(m, r)$ -set, or equivalently,

5. Dual Hyperovals
Definition 2. A set
dual hyperoval if

Hl For any$V$of $d+1$ -dimensional subspaces in a vector space over$V\neq V’\in \mathcal{V},$H3$|\mathcal{V}|=2^{d+1}$

is called a ( -dimensional)$d$is l-dimensional.

$V\cap V’$

H2 Any three mutudly different$\mathbb{F}_{2}$intersect in zero.

$V_{1}\in \mathcal{V}$.

The space panned by the subspaces of$s$$\mathcal{V}\iota s$

called the ambient space.

Thei is a construction of $(m-1)$ -dimensional dual hyperovals with help of a biliiiear riiap B.
due to Yoshiara [23] (see also [18]). Define;$e$$\mathcal{V}_{D}=\{V_{a}|a\in \mathbb{F}_{2}^{m}\}$The ambient space is$\mathbb{F}_{2}^{n+m}$(if

is surjective).

$B$,$\mathcal{V}_{B}$$\mathbb{F}_{2}^{m}\cross \mathbb{F}_{2}^{11}\mapsto \mathbb{F}_{2}^{n}$(4)$V_{a}=\{(x, I;(.\iota, a))|x\in \mathbb{F}_{2}^{n\iota}\}$fulfills coiidition H3 by construction.

Let $B_{f}(x, y)=\delta_{y}f(x)=f(x+y)+f(x)+f(y)+f(0)\subseteq \mathcal{A}$ . We have the following characterization of quadratic
APN functions (straight forward, see e.g. [14, 18, 23])
Proposition 6.

$\mathbb{F}_{2}^{m}\cross \mathbb{F}_{2}^{m}\mapsto \mathbb{F}_{2}^{n}$$\int$

is a quadratic $APN$ function if an only if$V_{B_{f}}$is a dual hyperoval.

For
therefore it is } $iandy$ to give conditions Bl and B2, in terms of the bilinear map $B$ , which are equivalent
to the defining conditions Hl and H2 of a dual hyperoval. Let:$\mathcal{V}_{B}$Bl For any $y\neq 0$ the rriap
B2 The inap$\sigma$$M_{v}$$x\mapsto B_{\mathcal{V}}(x, y)$$y\mapsto ke77\downarrow el(At_{y})$has rank $m-1$ .

is an bijection on$\mathbb{F}_{2}^{m}\backslash \{0\}$.

We have tlie followi ig equivalences: V. $\cap V_{b}rightarrow B(x, a)=B(\tau. b)rightarrow r\in ker\Lambda I_{a+b}$ . Hl says that for all $n\neq b$
this kernel has to be l-diiiiensional, which is equivalent to Bl.
iiiutually
it if and oiily if $a+b,$ $b+c,$ $c+aalC$ inutually.
Obsei ve that $a,$andH2 says that for any mutually different $a,$
the kernels $ker11f_{a+b},$ $kerM_{b+c}$ and $kerM_{c+a}$ hence $\sigma(a+b)$ ,$\sigma(b+c)$ and $\sigma(c+a)$ have to be different. It follows thathas to be injective. As image andpreimage are finite and of equal size, this is equivalent to B2, so $H2arrow B2$ . On the other hand, if is bijective
we have that for mutually different $a,$also $\sigma(a+b),$ $\sigma(b+c)$ and $\sigma(c+a)$ are mutually different. $\sigma(a+b)$, so $B2arrow H2$ .
determines the intei section point of V. and$1$$b,$ $cd\uparrow C$$dif\dagger crci|t$$diHci\cdot c^{\backslash }l$$1tO||zc^{\backslash }ro$$b,$ $c$$\sigma\cdot \mathbb{F}_{2}^{m}\backslash \{0\}arrow \mathbb{F}_{2}^{m}\backslash \{0\}$$\sigma$$b,$ $c$$V_{b}$

Next we give all alternative condition for B2 which is of the form of Bl.
andbe defined $a6$ above. A ssume Bl holds, hence that for $y\neq 0$ the kemell-dimen6ional. Then the following stateme $ntsa7e$ equivalent:Lemma 2. Let$\Lambda\cdot t_{y}$$\sigma$

1. B2

2. B3:$Fo\tau$. any $x\neq 0$ the map $N_{x}\cdot y\mapsto B(x, y)$ has rank $m-1$ .

$ker(\Lambda[_{y})$

is

125
Proof. By assumption it is $B(\sigma(y), y)=0$ .

: Assume that is a permutation. Then, for fixed $x\neq 0$ , there is exactly one $(i.e. y=\sigma^{-1}(x))$ suchis the only non-zero element in $ker(N_{x})$ .
that $B(x, y)=0$ . So
: Assume that for $x\neq 0$ the kernel $ker(N_{x})$ is l-dimensional. Assume is no permutation. Then there
is an element $v\neq 0$ which is not an image of . Hence $B(v, y)\neq 0$ for all $y\neq 0$ , so $ker(N_{v})=0$ , a contradiction
to the assumption.
$1\Rightarrow 2$$y$$\sigma$$\sigma^{-1}(x)$$2\Rightarrow 1$$\sigma$$\sigma$$\square$For subspacesof a dual hyperoval$V\subseteq \mathbb{F}_{2}^{u}$$V$$\mathcal{V}^{\perp}$

the dual subspaceis defined as$V^{\perp}$

is defined as.

$V^{\perp}=\{v’\in \mathbb{F}_{2}^{u}|\forall v\in V\cdot\langle v, v’\rangle=0\}$. The dual

$V^{\perp}=\{V|V^{\perp}\in \mathcal{V}\}$

We now introduce some bilinear forms associated to the bilinear form . For one, as these bilinear forms are
sources of new dual hyperovals. For two, as we then can characterize dual hyperovals entirely natural” properties.
andof bilinear forms, i.e. get rid of the linear maps
$B$“

$N_{x}$$M_{y}$

Deflnition 3. Let $B$ be an n-dimensional vector space of bilinear forms
vector space isomorphisrn. $Dc$]$ine$ th l-dimensional vector space of bilinear forms$B:\mathbb{F}_{2}^{\iota}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}$$B^{\dagger}$$e$$B^{\dagger}:=\{b_{x}^{\dagger}|x\in \mathbb{F}_{2}^{l}\}$Different isomorphisms$\psi$,:

and$\psi$:$\mathbb{F}_{2}^{n}\cross \mathbb{F}_{2}^{m}arrow \mathbb{F}_{2}$$Barrow \mathbb{F}_{2}^{n}$aas$b_{x}^{\dagger}(z, y)=\psi^{-1}(z)(x, y)$lead to isomorphic vector spaces of bilinear forms$B^{\dagger}$

Define also.

$B^{\cdot}(y, x)=B(x, y)$Notation will get considerably more comfortable if we choose the right bases and always identify a vector spaceof bilinear forms with a bilinear map to a vector space of the same dimension.
, and a basis. Denote their dual bases (with respect to the standard scalarofof
Choose a basis. Choose as well a basis of $B$ .
product) as , resp.
. Then:as the map
Identify $B$ with the map $B(x, y)= \sum_{i}\overline{f}_{i}b_{f}(x, y)$ . Choose$\mathbb{F}_{2}^{l}$$f_{i}$$c_{t}$$\mathbb{F}_{2}^{n}$$b_{t}$$\overline{f}_{t}$$\overline{e}_{t}$$b_{i}\mapsto f_{i}$$\psi$$b_{x}^{\dagger}(Z, ?/)= \psi^{-1}(z)(x, \uparrow/)=\sum z_{2}b_{i}(T, ?/)=zB(x, y)$Choose$b_{c_{i}}^{\dagger}(z, y)$chose, for defining

as basis of$B^{\dagger\dagger}$$B^{\dagger}$. Identify, the isornorphisni$B(x, y)^{\dagger\dagger}$

$=$

$=$

$B^{\dagger}$.

with the map
and repeat the above process. Then$c_{i}rightarrow b$:$B(z, ?/)^{\dagger}= \sum_{t}\overline{e}_{t}b:(z, y)=\sum_{\iota}\overline{e}_{\iota}(zB(e_{i}, y))$. Finally$\sum_{j}\overline{f}_{j}(x\cdot B^{\dagger}(f_{j}, y))=\sum_{j}\overline{f_{j}}(\sum_{:}(x\cdot\overline{e}_{i})(f_{j}\cdot B(e_{i}, y)))$$\sum_{j}\sum_{:}x_{t}\overline{f}_{j}b_{j}(e_{i}, y))=\sum_{j}\sum\overline{f}_{j}b_{\dot{J}}(x_{i}e_{i}, y)=B(x, y)$Hence is a involution. Combinations of \dag er and can effect an arbitrary permutation of the roles $x,$ $y,$hence lead to 6 subspaces of bilinear forms respectively 6 bilinear maps:‘$\dagger$$B,$ $B,$$B^{\dagger}B^{\dagger}$“,$B^{\dagger}$“$\dagger=\angle i^{*\uparrow},$

$z$

and

$B^{*\uparrow}$

We have the following identities:$zB(x, y)=zB(y, x)=xB^{\dagger}(z, y)=xB^{\dagger}(y, z)=yB^{\dagger\cdot\dagger}(x, z)=y\cdot B^{*\dagger}(z.x)$$=b_{z}(x, y)=b_{z}(y, x)=b_{\tau}^{\dagger}(z, y)=b_{x}^{t*}(y.

If $n=m$ there is an interpi etation of$(x’, y’)\rangle:=xy’+x’y$ . Then:$B^{\dagger}$in terms$V_{B}$.

z)=b_{\nu}^{\dagger}$\dag er(5)$(x, z)=b_{v}^{t}(z, x)$. Chose in the definition of$\mathcal{V}_{B}^{\perp}$

the scalar product as$\langle(x, y),$$\langle(\tau, B(x, r\iota)),$$(x’, B^{\dagger}(lr’, a))\rangle=\tau’B(x, a)+xB^{\dagger}(x, a)$By Equation 5 it is $x’B(x, a)=xB^{\dagger}(x’, a)$ , hence:

Proposition 7.
$\mathcal{V}_{B\dagger}=\mathcal{V}_{B}^{\perp}$

We are now ready to give the defining conditions for dual hyperovals completely in terms of bilinear forms. The
following statements are equivalent.

.
.

$\forall z\in \mathbb{F}_{2}^{n}:zB(x, y)=0$$B(x, y)=0$

126

Therefore:$\sigma(y)$$\sigma 1(x)$$=$$ker(M_{y})$$=$$ker(N_{x})$$=$$rR(b_{v^{\uparrow}}(z, x))$

$=$

$=$

$rR(b_{x}^{\dagger}(z, y))$$=$IR
IR $(b_{x}^{1}(y, z))$$(b_{y}^{\uparrow\cdot\uparrow}(x, z))$With this observation Bl and B3 can be rewritten either in terms of the radicals of bilinear forms or as:
Corollary 3.

is a dual hyperoval if and only if:$\mathcal{V}_{B}$1. B4: Any$0\neq b\in\rho\cdot\uparrow has$(Equivalently: Any

2. B5: Any

rank $m-1$$0\neq b\in B^{\dagger\cdot\uparrow}has$$0\neq b\in B^{\dagger}$rank $m-1$ )has rank $m-1$ .

(Equivalently: Any $0\neq b\in B^{\dagger}$has rank $m-1$ )the associated altemating bilinear map. We want to see when
Let $m=n,$ be an APN function and, hence (using Proposition 7)
the dual of the APN-dual hyperoval
is a dual hyperoval.
$f$$B_{f}\subset \mathcal{A}$$\mathcal{V}_{B_{f}}$$V_{B\}}$

Use B4 arid B5 as defining conditions. Hence$V_{B\}}$

is a dual hyperoval if and only if every nonzero$b\in B\}^{\dagger\cdot t}$

has rank $?n-1$ and every nonzero $b\in B\}^{t}$ has rank $rn-1$ .
As is an involution andis alternating, so $B_{f}=B_{f}$ , this simplifies to. Every nonzero inandhas
to have rank $m-1$ .
By assumption is APN, so by Proposition 6 we have thatis a dual hyperoval. Hence condition B5 holds. Therefore it only remains to show that every nonzero inforhas to have rank $m-1$ .
is altemating all $b\in B_{f}$ have even rank. This shows thatAs
cannot be a dual hyperoval if $m$ is even.
$\dagger$$b$$B_{f}$

$f$

$B\}$

$B_{f}$$\mathcal{V}_{B_{f}}$$b$$V_{B_{f}}$$B_{f}$$B_{f}$$\mathcal{V}_{B\}}$is a dual hyperoval. Thus we have an alternative proof (relaying essentiallyof Taniguchi’s result 21, Theorem 11 :If $m$ is odd Corollary 1 implies
on 12, Theorem 5
$[$

$])$

Corollary 4. Let$(=\mathcal{V}_{B_{f}}^{\perp})$$\mathcal{V}_{B\}}$

$]$

$[$

$f\cdot \mathbb{F}_{2}^{m}arrow F_{2}^{n\tau}$be an $APN$ function and $\Gamma?_{J}(y, x)=f(x+y)+f(x)+f(y)+f(0)$ . Then

$V_{B\}}$

is a dual hyperoval if and only if $rr$ is odd.

A. Appendix: Details on the trace representation
Any -bilinear function $B(x, y)$ :can be written as a polynomial in two variables, which islinearized with respect to each of the two variables, so as:$F_{2^{m}}\cross F_{2^{m}}\mapsto F_{2^{m}}$$F_{2}$$B(x, y)=. \sum_{*.j=0}^{m-1}a_{\iota,g}x^{2}y^{2^{J}}$(6)$a_{i,j}\in F_{2^{m}}$Call this a linearized polynomial in two variables.
can be written as the trace of a linearized polynornial inHence any bilinear function $b(x, y)$ :two variables, ie.
$F_{2^{m}}\cross F_{2^{m}}\mapsto F_{2}$$b(x, y)=tr(B(x.y))$However this representatioii of the biliiiear function is not unique.

As tr $(x)=$ tr $(x^{2})$ we can rnodify the

represeiitation of $b(x, y)$ in the following way.

$b(x, y)$$=$tr$( \sum_{1j=0}^{m-1}a_{t,g}x^{2^{i}}y^{2^{J}})=\sum_{1j=0}^{m-1}$tr$(a_{i,j}x^{2^{i}} t^{2^{J}})=\sum_{\mathfrak{i},j=0}^{m-1}$tr$(a_{j}^{2^{-g}}1,x^{2^{1-g}}\tau/)=$tr$( \sum_{1j=0}^{m-1}a_{i_{J}}2^{-g-J}x^{2}\cdot\uparrow/)$

So we have that$b(x, y)=tr(l(x)y)$ with$l(x)= \sum_{k=0}^{m-1}\alpha_{k}x^{2^{k}}$where$\alpha_{k}$(7)$:= \sum_{J^{=0}}^{m-1}a_{k+J,J}^{2^{-}}$of the
The indices are to be understood iiiodulo it . This representation is now unique (the dimension over
. This, which is also the dimension overof the -tuples invector space of bilinear functioris isrepiesentation is usually dedicated to Delsarte and Goethals [12]. We named this the trace representation ofa bilinear form.
which defines the linearized polynomial .
We also identify $b(x.y)$ with the elenient$\mathbb{F}_{2}$$\iota$$m^{2}$$\mathbb{F}_{2}$$(\alpha 0\cdot , \alpha_{m-1})\in(\mathbb{F}_{2^{m}})^{m}$$\alpha$$(\mathbb{F}_{2^{m}})^{m})$

$l$

127
The trace representation for alternating bilinear forms
A linearized polynomial $B(x, y)$ in two variables is called alternating if $B(x, x)=0$ (which again implies$B(x, y)=\mathcal{B}(y, x))$ . In Equation 6 we have therefore $a_{i,\iota}=0$ and $a_{z,j}=a_{j,i}$ .
Any alternating bilinear form can be written as the trace of an altemating linearized polynomial. This implies
for the trace representation of an alternating bilinear form (Equation 7)$=$$\alpha k$$\sum_{j=0}^{m-1}a_{-k+j,j}^{2^{-J}}=\sum_{j=0}^{m-1}a_{j,k+j}^{2^{-J-k}}=(\sum_{=J0}^{m-1}a_{j_{1}k+j}^{2^{-g}})^{2^{-k}}=(\sum_{j=0}^{m-1}a_{kj}^{2^{-g}}+J,)^{2^{-k}}=\alpha_{k}^{2^{-k}}$

So for alternating forms the following holds:$\alpha_{0}=0$,$\alpha_{k}=\alpha_{m}^{2^{k}}k$,

Especially if $m=2r$ we have$\alpha_{r}=\alpha_{r}^{2^{r}},$

$i.e$

.

$\alpha_{r}\in \mathbb{F}_{2^{r}}$.

So the trace representation of an alternating form is determined by the element$(\alpha_{1}, .

.

\alpha_{r})\in\{\begin{array}{ll}(\mathbb{F}_{2^{m}})^{r-1}x\mathbb{F}_{2^{m/2}} if rr\iota=2r(F_{2^{m}})^{r} if rn=2r+1\end{array}$A.l. Computing the coefficients of the trace representation
values $m.,j=$The representations of the a bilinear form, discussed in Section 3, were determined by the$b(e_{i}, e_{j})\in F_{2}$ . So these characterizations can be obtained from the trace representation by choosing a basisofoverand calculating $m_{n,j}=b(e_{i}, e_{j})=$ tr $(l(e_{i})e_{j})$ .
, in terms of theWe also want to provide the opposite direction, i.e. to give $l(x)$ , more precisely the values$m.,j=b(e_{i}, e_{j})\in \mathbb{F}_{2}$ . This will be done in two steps.
.
Identify
withby identifying $x=$with$m^{2}$$e_{i}$$\mathbb{F}_{2^{m}}$$\mathbb{F}_{2}$$\alpha_{k}$$(x_{1}, \ldots , x_{m})\in \mathbb{F}_{2}^{m}$$\mathbb{F}_{2^{m}}$$\mathbb{F}_{2}^{m}$

Step one:
We determine the linearized polynomialwith some $m\cross m$ matrix , ie$\sum x\iota e_{i}\in \mathbb{F}_{2^{m}}$cffcctiiig tlic sanie iiiap as $x\mapsto x^{t}U$$l_{U}(x)= \sum_{i=1}^{m}\alpha_{i}X^{2^{i}}$$U$$\tau^{f}U=\sum_{i,j}x,\uparrow r,,e^{1}=\sum_{j}\alpha_{J}(\sum_{\mathfrak{i}}\tau,e_{i})^{2}’=\sum_{i}\tau,$

So we get the$\alpha_{i}$as solution of the following$\mathbb{F}_{2^{m}}$$Ue=Ea$ , hence $a=E^{-1}Ue$ , with$\sum_{j}\alpha_{j}e_{t}^{27}$-linear equation:$E_{i,j}=e_{l}^{2^{J}}$,$e=$ $(e_{1}, . . , e_{m})^{t}$ ,$a=(\alpha_{1}, \ldots, \alpha_{m})^{t}$.

Note that $E$ has full rank (see e.g. [13, Bem 2.15.]).
Step two:over , withhas full rank.
$\mathbb{F}_{2}$Choosing$l$

Let $M=(m_{i,j})$ be the $m\cross m$ matrix, defined by $m_{i,j}=b(e_{i}, e_{j})\in \mathbb{F}_{2}$ . Let $C$ be the $m\cross m$ -matrix. $C$ is the Gram matrix with respect to the basis and the trace form and hence$c_{\text{ノ_{}l,j}}=tr(e\iota, e_{j})$$e_{t}$

as the linearized polynoniial$l_{MC^{-1}}$

gives the trace representation of $b(x, y)$ . Set$\prime c^{f}MC^{-1}=l(x)=\cdot\sum 1_{t}e_{1}$with this we see that:$tr(l(x)y)=tr(\sum_{t,j}1_{i}e_{t}y_{J}e_{j})=\sum_{t,j}1_{1}C_{t,j}y_{J}=ICy$$=x^{t}MC^{-1}Cy=b(x, y)$A.2. Dual subspaces in the trace representation
space of bilinear forms and its dual are denoted in the trace representation we use an adapted
In case thatof vectors
scalar product. Let a vector space of bilineai forms ] be given by a (generating) set
in
Define the dual subspacein teriris of vectoi
as$tI\iota e$$S_{B}$$\lrcorner$$(\mathbb{F}_{2)})^{m}$$B^{\perp}$$sS_{B\perp}$$S_{B^{\perp}}= \{ (\alpha_{1}’, \alpha_{m}’)\in(\mathbb{F}_{2^{m}})^{m}|\forall(c\iota_{1}.

And $fot$ alternating bilinear fornis, wheie$B$\alpha_{n\iota})\in S_{B}:tr(\sum_{?=1}^{m}\alpha,\alpha_{1}’)=0\}$

is giveii by a (geneiating) set$S_{B}\subseteq\{\begin{array}{ll}(\mathbb{F}_{2^{m}})^{\tau-1}\cross \mathbb{F}_{2^{m/2}} if 7n=2\tau.(\mathbb{F}_{2},,\dagger)^{r} if \mathfrak{m}=2r+1\end{array}$

There are two versions depending on the parity of $rn$ .

$S_{B}$,$(\alpha_{1}, , \alpha_{m})$128Case $m=2r$$S_{B} \perp=\{ (\alpha_{1}’, \alpha_{r}’)\in(\mathbb{F}_{2^{m}})^{r-1}\cross \mathbb{F}_{2^{m/2}}|\forall(\alpha_{1}, \alpha_{r})\in S_{B}\cdot tr(\sum_{1=1}^{r-1}\alpha_{1}\alpha_{l}’)+?\urcorner r(\alpha_{r}\alpha_{r}’)=0\}$

where tr and$\prime 1’ r$

are the absolute traces inrespectively$\mathbb{F}_{2^{m}}$$\mathbb{F}_{2^{r}}$Case $m=2r+1$$S_{B^{\perp}}= \{(\alpha_{1}’, .

)\alpha_{r}’)\in(\mathbb{F}_{2^{m}})^{r}|\forall(\alpha_{1)} \alpha_{r})\in S_{B}\cdot tr(\sum_{\iota=1}^{r}\alpha_{1}\alpha_{i}’)=0\}$

A.3. Starting from an quadratic (APN) function for $m=n$
Let

$f$

:

be a quadratic function with$\mathbb{F}_{2^{m}}\mapsto \mathbb{F}_{2}\cdot,1$$f(x)=x^{t}A_{f}x:= \sum_{<J}a.,j^{X^{2+2^{3}}}.+L(x)$is an upper triangular matrix with main diagonal zero andwhere:
is the linearized polynomial in two variables
associated bilinear map$A_{f}\in \mathbb{F}_{2^{m}}\cross \mathbb{F}_{2^{m}}$$B_{f}$$B_{f}$$L$is an affine function. The$F_{2^{m}}\cross \mathbb{F}_{2^{m}}\mapsto \mathbb{F}_{2^{m}}$with:$B_{f}(x, y).= \delta_{y}f(x)=f(x+y)+f(x)+f(x)+f(0)=x^{t}(A_{f}^{t}+A_{f})x=\sum_{:<j}a.,J(x^{2}.y^{2^{j}}+x^{2^{J}}y^{2})$Identify $B_{f}(x, y)$ with the m-dimensional vector space of alternating bilinear forms of, this vector space consists of the elements
called$F_{2^{m}}\cross \mathbb{F}_{2^{m}}\mapsto \mathbb{F}_{2}$, also$B_{f}$

tr$1)()fin(\tau t$$(A_{f}^{t}+A_{f})$he currenlly undefinedwith. Then the liiiearized polynoinial$\Omega_{1},J$$(\omega\Gamma i_{f}(x, y))$$i\geq\gamma$

with$\omega\in \mathbb{F}_{2^{m}}$.

, so as hc $co(’[fir\cdot i).of$ t,hc mal,rix by
by $0_{11}=0$ andcorrespoiiding to $tr(\omega B_{f}(x, y))$ has coefficients$0_{\iota,\gamma}=0_{J^{1}}$$t$$l_{\omega}= \cdot\sum_{k}\alpha_{k}^{(\omega)}x^{2^{k}}$$\alpha_{k}^{(\propto)}=\sum_{j=0}^{m-1}(\omega a_{k+J,j})^{2^{-g}}$.
asDenote the coefficicnt vector space of
can be expressed efficiently in terms of . Choose the scalaris used.
In Section 32.2 dual space of
product introduced for the trace repiesentation in Sectioii A 2.
$S_{B_{f}}=\{ (\alpha_{1}^{(\omega)}, , \alpha_{r}^{(\omega)})|\omega\in \mathbb{F}_{2},,1\}$$B_{f}$$B_{f}^{\perp}$$f$$B_{f}^{\perp}$

Case $m=2r+1$$S_{B_{f}^{\perp}}$$= \{ (\alpha_{1}’, \alpha_{r}’)\in(\mathbb{F}_{2^{m}})^{r}|\forall(\alpha_{1}, \alpha_{r})\in S_{B_{f}} tr(\sum_{7=1}^{r}\alpha_{1}’\alpha_{1})=0\}$

We rnodify the trace term:$0= tr(\sum_{i=1}^{r}\alpha_{l}’\sum_{=J0}^{\iota-1}(\omega a_{+gg})^{2} )=\sum_{=1J}^{r}’\sum_{=0}^{\tau t-1}tr(\alpha_{1}’(\omega a_{z+gg})^{2}7)=\sum_{t=1J}^{r}\sum_{=0}^{--1}tr(\omega\alpha_{l}^{\prime 2^{7}} a1+JJ)=tr(\omega\sum_{1=1J}^{r}\sum_{=0}^{n1-1}\alpha_{1}^{\prime 2’}a_{t+g,g})$. Dcfinc tlic liiicai izcd polyiiomials, hence is equivalent toThis holds for all$(A\}+A_{f})$ , i.e.
as the linearized po)ynomial whose coefficients are the i-th diagonal of$\sum_{=1}^{r}\sum_{J}^{m-}=0^{1}or_{l}^{\prime 2^{J}}\alpha_{+JJ}=0$$\omega\in \mathbb{F}_{2^{}}$$\lambda_{t}$$\lambda,$$( \iota)=\sum_{=J0}^{m-1}$

a$s+I\prime 3^{L^{2)}}$

We have shown:$S_{B_{f}^{\perp}}$$= \{ (\alpha_{1}’.

\alpha_{r}’)\in(\mathbb{F}_{2}, )^{r}|\sum_{?=1}\lambda_{7}(\alpha_{1}’)=0\}$

Case $m=2r$ Proceed as for odd $m$ . We only have to take special care $fo1$ the terin involving $a_{r+j,j}$ . So we$dli_{Cd}dy$ caii assuiii.
is.
that thc coiidi ion dcfi iiiiig$c$$tr(\omega\sum_{\iota=1}^{r-1}\lambda_{1}(\alpha_{1}’))+T\uparrow(c\iota_{r}’\sum_{J}^{m-}=0^{1}(\omega\alpha_{\tau+gg})^{2^{-g}})=0$$t$$S_{B_{f}^{1}}$129$\tau$

We now transform the $Tr$ Term. Use $a_{t,j}=a_{J}$ ,, and: $x\mapsto x^{2^{r}}+x)$ arid observe that tr.

$\alpha_{r}’\in \mathbb{F}_{2^{r}}$.

Let$\tau$

be the trace from$\mathbb{F}_{2^{m}}$to$\mathbb{F}_{2^{r}}$(i.e.

$=?^{\urcorner}r\circ\tau$$Tr( \alpha_{r}’\sum_{j=0}^{m-1}(\omega a_{r+j,j})^{2^{-j}})=7\urcorner r(\alpha_{r}’\sum_{j=0}^{r-1}((\omega a_{r+j,j})^{2^{-j}}+(\omega a_{r+j+r,j+r})^{2^{-j-r}}))$$= \sum_{j=0}^{r-1}Tr(\alpha_{r}^{\prime 2^{j}}\tau(\omega a_{r+j,j}))=Tr(\tau(\sum_{j=0}^{r-1}\alpha_{r}^{\prime 2^{J}}\omega a_{r+j,j}))=tr(\omega\sum_{j=0}^{r-1}\alpha_{r}^{\prime 2^{J}}a_{r+j,j})$Hence our condition foris$S_{B_{f}^{\perp}}$$\forall\omega\in \mathbb{F}_{2^{m}}:0=tr(\omega(\sum_{i=1}^{r}\lambda_{1}(\alpha_{i}’)+\sum_{j=0}^{r-1}\alpha_{r}^{\prime 2^{j}}a_{r+j,j}))$$\Leftrightarrow$$0= \sum_{i=1}^{r}\lambda_{i}(\alpha_{i}’)+\sum_{j=0}^{r-1}\alpha_{r}^{\prime 2^{j}}a_{r+g,j}$Define thc linearizedl polynomial
(over
) as
condition for
as in the odd case. We summarize the above results:$\lambda_{r}$$\lambda_{r}(x)$$\mathbb{F}_{2}^{f}$$:= \sum_{j=0}^{r-1}a_{r+j,j}x^{2^{j}}$. With this we get forinally the same

$S_{B_{f}^{\perp}}$

Proposition 8. Let $f(x)= \sum_{i<j}a_{i,j}x^{2^{1}+2^{j}}+L(x)$ with altemating map $B_{f}(x, y)= \sum_{i<j}a_{i,j}(x^{2^{i}}y^{2^{j}}+x^{2^{j}}y^{2})$and$\lambda_{i}(x)$$:= \sum_{j=0}^{m1}a_{i+j,j}x^{2^{j}}$. For $m=2r+1$ it is$\iota 9_{B_{f}^{\perp}}:=\{(\alpha_{1}’, \ldots, \alpha_{f}’)\in(\mathbb{F}_{2^{m}})^{r}|\sum_{l=1}^{r}\lambda_{i}(\alpha’:)=0\}$

And for $m=2r$ , un th$\lambda_{r}(x)$$:= \sum_{j=0}^{r-1}a_{r+j,j}x^{2^{j}}$, it is$S_{B_{f}^{\perp}};= \{(\alpha_{1}’, \ldots, \alpha_{r}’)\in(\mathbb{F}_{2^{m}})^{r-1}\cross \mathbb{F}_{2^{r}}|\sum_{i=1}^{r}\lambda_{i}(\alpha_{l}’)=0\}$

Observe that $f$ (up to a affine function),, as well as the , are completely determiiied by. And thatthe knowledge of olle of $f,$or $(\lambda_{i}|1\leq i\leq r)$ is sufficient to reconstruct. In particular you can also write,:and $B$ in teriiis of$B_{f}$$\lambda$$A_{f}$$B_{f}$$A_{f}$$f$$t1_{1}e\lambda$$f(x)= \sum_{t=1}^{r}\lambda,$$(x^{2+1})$and$B_{f}(x.y)= \sum_{l=1}^{r}((\lambda_{z}(x^{2^{\iota}}y)+(\lambda,(xy^{2}’))$

A.3.1. Examples
of a monomial: For $f(x)=r,x^{(2^{i}+1)2^{J}},$ $i<j$ , only
is nonzero.
So the Gold function $f(x)=x^{2^{i}+1}$ has as equivalent condition.
The of the trace of a monomial: let $i\leq(n-1)/2$ and $f(x)=c$ tr $(x^{2^{i}+1})=c$ tr $(x^{(2+1)2^{\gamma}})=c \sum_{t=0}^{m-1}x^{(2^{I}+1)2^{1}}$Then the only non-zeroistr $(x)$ . (For $f(x)=$ tr $(cx^{2^{i}+1})$ we gettr $(cx).$ )In the case $\tau\iota=2r,$ $i=r$ we get the analog result by replacing tr by $Tr$ .
The$\lambda_{i}(x)=cx^{2^{j}}$$\lambda$$\alpha_{f}’=0$$\lambda$$\lambda_{*}$$\lambda_{i}(x)=\sum_{l\Rightarrow 0}^{m-1}x^{2^{l}}c=c$

Tliis enables us to give without efiort tlie definiiig coiidition for$\lambda_{i}(x)=$$S_{B_{f}^{\perp}}$, if the APN function is given in the form

, whereis one of the two cases discussed above.
E.g. for the APN function $f(x)=x^{3}+tr(x^{9})$ the defining condition is $c\iota_{1}’+tr(\alpha_{3})=0$ .

$f= \sum_{i=1}^{\lfloor n/2\rfloor}q_{i}$$q_{i}$

Most of the known quadratic APN have few terrris. APN functions for small $m$ can be found in [4, 15, 16]. We
also a list of tlic illfinite series (as far a currciitly kiiown to tlie author).

$piovidc^{\backslash }$130
References[1] J. Bierbrauer. A family of crooked functions. Designs, Codes and Cryptography, 50.235-241, 2009.
[2] C. Bracken, E. Byrne, N. Markin, and G. McGuire. A few more quadratic APN functions. http: $//arxiv$ .
$org/pdf/0804$ . 4799, 2008,[3] C. Bracken, E. Byrne, N. Markin, and G. McGuire. New families of quadratic almost perfect noiilinear
trinomials and multinomials. Finite Fields And Their Applications, 14(3):703-714, 2008.
[4] K. A. Browning, J. F. Dillon, R. E. Kibler, and M. T. McQuistan. APN polynomials and related codes.
submitted, 2008.

[5] L. Budaghyan and C. Carlet. Classes of Quadratic APN trinomials and Hexanomials and Related Structures.
IEEE 7Vansactions on Information Theory, 54(8):2354-2357, 2008.
[6] L. Budaghyan, C. Carlet, and G. Leander. Two classes of quadratic APN binoinials inequivalent to powerfunctions. IEEE Transactions on Information Theory, 54(9).4218-4229, 2008.

[7] L. Budaghyan, C. Carlet, and G. Leander. Constructing new APN functions from known ones. Finite Fields
And Their Applications, 15(2): 150-159, 2009.
[8] C. Carlet. Boolean Methods and Models, chapter Boolean functions for cryptography and error correcting
codes. Cambridge University Press, to appear.
[9] C. Carlet. Boolean Methods and Models, chapter Vectorial boolean functions for cryptography. Cambridge
University Press, to appear.

[10] R. S. Coulter and M. Henderson. A class of functions and their application in constructing semi-biplanes
and association schemes. Discrete Mathematics, $202(1):21-32$ , 1999.

[11] P. Delsart,e. Bilinear forms over a finite Field. with applicat,ions t,o coding heory. Joumal of Combinato rial
. Series A, $25(3)\cdot 226-241$ , 1978.
$|$$Theo\tau\cdot y$[12] P. Delsarte arid J. M. Goethals. Alternating bilinear forms over $GF(q)$ . Joumal of Combinatorial
Sertes , pages 26-50, 1975.

$T’\iota eor\cdot y$.

$\mathcal{A}$[13] Y. Edel. Eine Verallgemeinerung von BCH-Codes. PhD thesis, Univeistit\"at Heidelbeig, 1996 (http: $//www$ .
mathi. uni-heidelberg. de $/-yves/Papers/Di$ ss. html ).

[14] Y. Edel. On quadratic APN functions and dimensional dual hyperovals. Designs, Codes and Cryptography,
to appear,[15] Y. Edel, G. Kyureghyan, alld A. Pott. A new APN functioii whicli is not equivalent to a power rriapping,IEEE Transactions on lnformation Theory, 52 (2):744–747, 2006.

[16] Y. Edel and A. Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathernatics of Comrnunications, 3(1).59-81, 2009.

[17] R. Gold. Maximal recursive sequences with 3-valued recursive cross-correlation function. IEEE $Tr(\iota r|sac\ell ior|6$
on Infor rnation Theory, 14: 154-156, 1968.
pcrtcctiiicai fuiictioiis: A possilvlc gconicti ic cl]$)]J1$ oacli. In $Proceed?ngs$
ttiid . Pott.
.
II at The Royal Flernish Acaderny of Belgium
Cryptography
Theoryand
Coding
Forum
the
Co
ntact
of
Science and the Arts 2007, pages 75-100, 2007.

[18] F$Go_{0^{\cup}}b)1u$$\Lambda$$\Lambda liiiost$$11\cup 11$$fo\tau$[19] A. Munernasa. An arialogue of t-designs in association scheines of alternating bilinear fornis. Graphs andCombinatorics, 2(1) 259-267, 1986.
[20] N. Nakagawa. On the number of generalized quadratic APN functions. Slides for Fq9: http: //mathsci. ucd.
ie $/\sim gmg/Fq9Talks/Nakagawa$ . pdf.

[21] H. Taniguchi. On the duals of certain d-dimensional dual hypeiovals irl $PG(2d+1,$ 2).
Their Applications, 15673-681. 2009.

$\Gamma$inite $Field_{6}$ And

oceed[22] S. Yoshiai a. Dimensional dual arcs -a suivey. In Finite $Geo7ret\tau\cdot ies$ , Groups, and Cornputation.
ings of the Conference ‘Finite Geometries, Groups, and Cornputation, September 4-9, 2004 Pinqree Park,
Colorado, 2006.
$P_{7}$‘[23] S. Yoshiara. Diniensional dual hyperovals associated with quadratic APN functioiis. hmovations m $Inci(lence$
Geo metry, (8): 147-169, 2008.