On the properties of the Boolean functions

associated to the differential spectrum of general

APN functions and their consequences∗
Claude Carlet,
University of Bergen, Norway and University of Paris 8 (LAGA laboratory), France.

E-mail: claude.carlet@gmail.com

Abstract
We initiate a study, when F is a general APN function, of the Boolean
function γF related to the differential spectrum of F (and which is known
to be bent if and only if F is almost bent). We first list many open
questions about it. We study its algebraic normal form and its bivariate
representation. We characterize its linear structures and specify nonexis-
tence cases; we show, for n even, their relation with the bent components
of F . We pose three related open problems. We characterize further in
terms of γF the fact that a component function of F is bent and study if
the number of bent components can be optimal. We consider in particular
two classes, one of which is that of APN power functions. We study more
deeply the relation between the Walsh transform of γF and the Walsh
transform of F . By applying the Titsworth relation to the Walsh trans-
form WγF , we deduce a new relation satisfied by WF2 , which is as simple
as Chabaud-Vaudenay’s characterization by the fourth moment of the
Walsh transform (which is in fact a particular case of the new relation),
and provides more information. From this new relation, we deduce, for
a sub-class of APN functions, a lower bound on the nonlinearity, which
is significantly stronger than nl(F ) > 0 (the only general known bound).
This sub-class of APN functions includes all known APN functions. The
question (which is another open problem that we state) arises whether
this sub-class equals that of all APN functions, but our bound provides
at least a beginning of explanation why all known APN functions have
non-weak nonlinearity. We finally show how the nonlinearities of γF and
F are related by a simple formula; this leads to a last open problem.
∗ The research of the author is partly supported by the Trond Mohn Foundation.

1
1 Introduction
Almost perfect nonlinear functions [23] are those functions F : Fn2 7→ Fn2 (called
(n, n)-functions) such that
δF := max (|{x ∈ Fn2 ; F (x) + F (x + a) = b}|; a ∈ Fn2 , b ∈ Fn2 , a 6= 0n )
is equal to 2 (the smallest possible value), where 0n is the zero element of Fn2 .
They have been much studied since the 1990’s.
Characterizations of APN functions (and of more general differentially δ-uniform
functions) are known by the Walsh transform (see [17, 11]) and by other means
as well (see the surveys [3] and [13, Chapter 11]), but after thirty years, we must
admit that little is known on general APN functions.
It has been proved in [15] that, given F : Fn2 7→ Fn2 , the Boolean function
γF (a, b) over Fn2 × Fn2 taking value 1 if and only if a 6= 0n and the set {x ∈
Fn2 ; F (x) + F (x + a) = b} is non-empty, is bent (i.e. lies at the optimal Ham-
ming distance 22n−1 − 2n−1 from the vector space of affine 2n-variable Boolean
functions) if and only if F is almost bent (that is, for every nonzero v ∈ Fn2 ,
the so-called component function v · F , where “·” is an inner product in Fn2 , lies
n−1
at the Hamming distance 2n−1 − 2 2 from the set of affine n-variable Boolean
functions; n must then be odd). Recall that almost bent functions are APN and
that the converse is not true in general. Very little is known on γF when F is
APN without being almost bent. Since almost bent functions are very peculiar
functions in odd dimension n (and are shown in [7] not to be good choices as
substitution boxes in block ciphers - see also [12] - even if they are bijective,
while APN (n, n)-permutations in even number n of variables would be very
good choices if some could be found for n = 8), it seems useful to determine
more precisely the characteristics of the γF functions associated to general APN
functions.
Function γF has a few known properties that we shall recall below, but it is
clearly not a general 2n-variable Boolean function having such properties, and
it seems then necessary to learn more about it, thanks to a systematic search
for new properties and a study of the consequences of the known relation be-
tween the Walsh transforms of F and γF . We shall deduce a new characteristic
relation on the Walsh transform of APN functions, which seems similar to the
characterizations obtained in [11], but is in fact quite different and will have an
interesting consequence.
A puzzling observation on APN functions is that no one is known with a bad
nonlinearity (that is, with a component function lying close to affine functions),
which leads to asking whether APN functions with low nonlinearity can exist.
The only known lower bound on the nonlinearity of general APN functions is
its strict positivity [9]. Using the new relation found on the Walsh transform of
general APN functions, we derive a lower bound on the nonlinearity of a large
class of APN functions that includes all known APN functions. This does not
answer the question on the nonlinearity of general APN functions mentioned
above, but it gives at least an explanation why all known APN functions have
a not so bad nonlinearity (such explanation has been missing since the early

2
nineties for non-power functions; a lower bound is known from [11] for power
3n−3 3n−2
functions: nl(F ) ≥ 2n−1 − 2 4 for n odd and nl(F ) ≥ 2n−1 − 2 4 for n
even). The new lower bound tells us what kind of APN functions need to be
avoided when searching for APN functions with bad nonlinearity (whose discov-
ery would probably have little practical interest but would be quite illuminating,
theoretically).
The paper is organized as follows. After preliminaries in Section 2, we make
in Section 3 some observations, some of which are new, about the Boolean func-
tion γF (a, b), for general APN functions, and we mention many open questions.
We briefly study in Section 4 the ANF and the bivariate representation of γF ,
and in Section 5, we tackle the question of the (non)existence of its linear struc-
tures. We solve (negatively) the problem when n is odd and, for n even, when
the linear structure is 1-valued or of the form (α, β) with α 6= 0n . We character-
ize in terms of bent components v · F of F the 0-valued linear structures of the
form (0n , β), for n even, and we leave open the problem of their existence; we
address negatively some particular cases. We observe that a component function
of an APN function is bent if and only if, for every a ∈ Fn2 , the Boolean function
b 7→ γF (a, b) + v · b is balanced; we deduce that APN power functions cannot
have an optimal number of bent components. In Section 6, we recall the relation
between the Walsh transforms of γF and F and we study the relations on each,
which can be deduced from the classical relations on the other. By applying
the Titsworth relation to the Walsh transform of γF , we derive a new relation
satisfied by the Walsh transform of F , which is astonishingly simple. We de-
duce a lower bound on the nonlinearity of the subclass of those APN functions
F such that the minimum Hamming distance between the component functions
v · F (v nonzero), and affine Boolean functions is achieved more than once. We
show that all known APN functions belong to this subclass and leave open the
questions of determining whether all APN functions do too, and of finding a
better bound which would completely explain why all known APN functions
have rather good nonlinearity. We eventually show a relation expressing the
nonlinearity of γF as a strictly increasing degree-2 function of the nonlinearity
of F . This relation shows again the equivalence between “F is almost bent”
and “γF is bent”, but it also extends the relation to APN functions that are
not necessarily almost bent. We state a last open problem which includes as a
sub-problem an open question posed in [5].

2 Preliminaries
For a given positive integer n, we shall denote by 0n (resp. 1n ) the zero vector
(resp. the all-1 vector) of length n and by ei the i-th vector of Hamming weight
1, that is, of the canonical basis of the vector space Fn2 . We denote by wH (x)
the Hamming weight of an element x of Fn2 , that is, the size of its support
{i ∈ {1, . . . , n}; xi = 1}.
The vector space Fn2 will sometimes be endowed with the structure of the
field F2n (this field being an n-dimensional vector space over F2 , each of its

3
elements can be identified with the binary vector of length n of its coordinates
relative to a fixed basis). We shall simply denote by 0 the null element in this
field (whose vector of coordinates is 0n ).
We shall denote by Bn the 2n -dimensional F2 -vector space of n-variable
Boolean functions (from Fn2 to F2 ). For a given n-variable pseudo-Boolean
function ϕ, that is, a function from Fn2 to R, the Fourier-Hadamard transform
of ϕ (see e.g. [13, Section 2.3]) equals the pseudo-Boolean function ϕ b defined
on Fn2 by: X
ϕ(u)
b = ϕ(x) (−1)u·x ; u ∈ Fn2 , (1)
x∈Fn
2

where “·” is somePchosen inner product in Fn2 (for instance, the usual inner
n n
product u · x = i=1 ui xi , or, if F2 is endowed with the structure of F2n ,
Pn−1 2i
the inner product u · x = trn (ux), where trn (x) = i=0 x is the so-called
absolute trace function). This transformation is an R-linear bijective mapping.
The pseudo-Boolean function ϕ is identically null if and only if its Fourier-
Hadamard transform is identically null (see e.g. [13, Subsection 2.3.3]).
Given an n-variable Boolean function f , we can apply the Fourier-Hadamard
transform to f itself viewed as a pseudo-Boolean function, which gives fb(u) =
u·x
, where supp(f ) = {x ∈ Fn2 ; f (x) = 1}, or to the so-called
P
x∈supp(f ) (−1)
sign
P function ϕ = (−1)f , which gives the Walsh transform of f : Wf (u) =
f (x)+u·x
x∈Fn (−1)
2
. The two transforms are closely related by the formula:

Wf (u) = 2n δ0 (u) − 2fb(u), (2)

where δ0 is the Dirac (or Kronecker) symbol. Note that f is then balanced (that
is, has Hamming weight 2n−1 ) if and only if Wf (0n ) = 0. The Walsh transform
satisfies the so-called inverse Walsh transform relation:
X
Wf (u)(−1)u·v = 2n (−1)f (v) , ∀v ∈ Fn2 , (3)
u∈Fn
2

which comes essentially from the fact that, if ` is a nonzero linear form over Fn2 ,
then: X
(−1)`(u) = 0, (4)
x∈Fn
2

the Parseval relation: X

Wf2 (u) = 22n , (5)
u∈Fn
2

the Titsworth relation:

X
Wf (u)Wf (u + v) = 0, ∀v 6= 0n , (6)
u∈Fn
2

and the Wiener-Khintchine formula which expresses that the Fourier-Hadamard

transform of Wf2 equals 2n times the autocorrelation function of f :
X X
Wf2 (u)(−1)u·a = 2n (−1)Da f (x) , (7)
u∈Fn
2 x∈Fn
2

4
where Da f (x) = f (x) + f (x + a) is called a derivative of f .
Given an (n, m)-function F , that is, a function from Fn2 to Fm 2 , the Walsh
transform at (u, v) ∈ Fn2 × Fm2 equals by definition the Walsh transform at u of
the component function v · F , where “·” is an inner product in Fm 2 (this is then
an abuse of notation, since we denote by the same symbol two inner products).
We say that F is plateaued with a single amplitude if there exists some integer
λ (called the amplitude) such that, for every u ∈ Fn2 and v ∈ Fm 2 , v 6= 0m , we
have WF (u, v) ∈ {0, ±λ}. We say that F is plateaued if, for all u ∈ Fn2 and
v ∈ Fm2 , v 6= 0m , we have WF (u, v) ∈ {0, ±λv } for some integers λv depending
only on v. According to the Parseval relation, λv equals then a power of 2 for
n+kv
every v; more precisely, it equals 2 2 where kv has the same parity as n.
In this paper, we shall be interested in 2n-variable Boolean functions γF re-
lated to (n, n)-functions F . Let us then specify what are the Fourier-Hadamard
and Walsh transforms for such a 2n-variable Boolean function, say γ: the in-
n
put can be P viewed as a pairu·a+v·b
(a, b) of elements of FP 2 or of F2n , and we have
γ
b(u, v) = (a,b)∈supp(γ) (−1) , and Wγ (u, v) = a,b∈Fn (−1)γ(a,b)+u·a+v·b .
2
The nonlinearity of a Boolean function f equals its minimum Hamming
distance to affine Boolean functions u · x + , u ∈ Fn2 ,  ∈ F2 . It equals then:
1
nl(f ) = 2n−1 − max |Wf (u)|. (8)
2 u∈Fn2
n
It is bounded above by 2n−1 − 2 2 −1 , according to the covering radius bound
which is a direct consequence of the Parseval relation (see e.g. [13, Section 2.3])
and f is called bent if it achieves this value with equality. Bent functions exist
n
for n even only, and they are characterized by the fact that Wf (u) ∈ {±2 2 } for
n
every u. The Boolean function fe such that Wf (u) = 2 2 (−1)f (u) is called the
e

dual of f (and is bent too). The nonlinearity of an (n, m)-function F equals

the minimum nonlinearity of its component functions v · F , v ∈ Fm 2 \ {0m }. It
equals then
1
nl(F ) = 2n−1 − max |WF (u, v)|. (9)
2 u∈Fn
m
2
v∈F2 ,v6=0m

n
It is of course bounded above by 2n−1 − 2 2 −1 as well and F is called bent if it
achieves this value with equality. As shown in [22], bent functions exist if and
n−1
only if m ≤ n2 and n is even. For m = n, nl(F ) is bounded above by 2n−1 −2 2 ,
according to the Sidelnikov-Chabaud-Vaudenay (SCV) bound (see [17], or see
[13, Theorem 6]) and F is called almost bent (AB) if it achieves this value with
n+1
equality (n must be then odd). Equivalently, F is AB if WF (u, v) ∈ {0, ±2 2 },
for every u ∈ Fn2 and every nonzero v ∈ Fn2 . Bent and almost bent functions are
plateaued with a single amplitude. Given F plateaued with WF (u, v) ∈ {0, ±λv }
for all u, v, v 6= 0n , the nonlinearity of F equals 2n−1 − 21 maxv6=0n λv .
Any (n, m)-function can be uniquely represented by its algebraic normal

5
form (ANF):
!
X Y X
F (x) = aI xi = aI xI , (10)
I⊆{1,...,n} i∈I I⊆{1,...,n}

where aI belongs to Fm 2 . The global degree of the ANF is called the algebraic
degree of F and denoted by dalg (F ). It equals the maximum algebraic degree of
the component functions of F . Affine functions are those functions of algebraic
degree at most 1. We call quadratic those functions of algebraic degree at most
2. A quadratic n-variable Boolean function is bent if and only if it has Hamming
n
weight 2n−1 ± 2 2 −1 . The algebraic degree of an n-variable Boolean function f
equals n if and only if its Hamming weight is odd and, Pin the case the algebraic
degree is smaller than n, it equals n − 1 if and only if x∈Fn xf (x) 6= 0n . The
2 P
algebraic degree of an (n, m)-function F equals n if and only if x∈Fn F (x) 6=
2
0m . For all these results, we refer to the recent monograph [13]. If Fn2 is
endowed with the structure of F2n , then any (n, n)-function (and then, every
(n, m)-functions where m divides n, in particular, any Boolean functions) can
be uniquely represented by its univariate representation:
n
2X −1
n
F (x) = ui xi ∈ F2n [x]/(x2 + x). (11)
i=0

The algebraic degree of F equals then the largest Hamming weight of the binary
expansion of those exponents i whose coefficients ui are nonzero. The functions
whose univariate expression is a monomial are called power functions.
An (n, m)-function F is called differentially δ-uniform, for a given positive
integer δ, if for every a ∈ Fn2 \ {0n } and every b ∈ Fm 2 , the equation F (x) +
F (x + a) = b has at most δ solutions. We denote the minimum of these integers
δ by δF and call it the differential uniformity of F . For every (n, m)-function
F , we have δF ≥ max(2, 2n−m ). It is shown in [22] that for m < n, equality can
happen for bent functions only, and we know that such functions exist if and
only if n is even and m ≤ n2 .
Note that we can have δF = 2 only when n ≥ m. An (n, n)-function F
is called almost perfect nonlinear (APN) if it is differentially 2-uniform, that
is, if for every a ∈ Fn2 \ {0n } and every b ∈ Fn2 , the equation F (x) + F (x +
a) = b has 0 or 2 solutions (i.e. the derivative Da F (x) = F (x) + F (x + a)
is 2-to-1). Equivalently, |{Da F (x), x ∈ Fn2 }| = 2n−1 . Still equivalently, for
distinct elements x, y, z, t of Fn2 , the equality x + y + z + t = 0n implies F (x) +
F (y) + F (z) + F (t) 6= 0n , that is, the restriction of F to any 2-dimensional flat
(i.e. affine plane) of Fn2 is non-affine. There are several characterizations of
APN functions (see [13, Chapter 11]): by the numbers of solutions of systems
of equations, by the function γF defined in introduction, and as proved by
Chabaud and Vaudenay in [17] by the fourth moment of the Walsh transform:
4 4n+1
− 23n+1 and other relations involving the Walsh
P
u,v∈F2n W F (u, v) = 2
v6=0n
transform [11].

6
 A subclass of APN functions is that of AB functions, that we defined already
n−1
(they are the (n, n)-functions, n odd, whose nonlinearity equals 2n−1 −2 2 , and
n+1
this is equivalent to saying that their Walsh transform takes values {0, ±2 2 }).

3 Generalities on γF
Recall from [15] the definition of the Boolean function γF associated to any
(n, n)-function F :

1 if a 6= 0n and ∃x ∈ Fn2 ; F (x) + F (x + a) = b,


∀a, b ∈ Fn2 , γF (a, b) =
0 otherwise.

In other words, the support of the function b ∈ Fn2 7→ γF (a, b) equals the empty
set for a = 0n and the image set of Da F for a 6= 0n (we shall denote it by
Im(Da F )). Still equivalently, denoting by GF the graph {(x, F (x)), x ∈ Fn2 } of
F , the support of γF equals (GF + GF ) \ {(0n , 0n )}. Function F is APN if and
only if γF has Hamming weight 22n−1 − 2n−1 , and we have more precisely for
F APN that the Boolean function b 7→ γF (a, b) is balanced if a 6= 0n and is null
if a = 0n . The definition of γF from F makes it rather difficult to study.
A property of γF is that, for every nonzero a ∈ Fn2 , b∈Fn b γF (a, b) equals
P
2
the same value in Fn2 , equal to
P
x∈Fn F (x). Indeed, let Ea be any linear
2P P
hyperplane not containing a, we have b∈Fn b γF (a, b) = x∈Ea Da F (x) =
P P P 2

x∈Ea F (x) + x∈Ea F (x + a) = x∈Fn2

F (x).
If F is a permutation then, since F −1 is also APN and γF −1 (a, b) = γF (b, a),
because F −1 (x) + F −1 (x + a) = −1 −1
Pb is equivalent to F (F (x)) + F (F (x) + b) =
a, we deduce that the sum a∈Fn γF (a, b) calculated in Z (i.e. the Ham-
2
ming weight of the restriction of γF obtained by fixing b) equals 2n−1 and
a γF (a, b) equals the same value in Fn2 for every b 6= 0n , this value being
P
a∈Fn
2
equal to x∈Fn F −1 (x). But if F is not a permutation, then it is difficult to
P
2 P
see the specificities of a∈Fn a γF (a, b), and even those of the Hamming weight
P 2

a∈Fn γF (a, b) of the restriction of γF obtained by fixing b, as can already

2
be seen for n even with the simplest APN functions over F2n , that are the
j
Gold APN functions F (x) = x2 +1 , where gcd(j, n) = 1: for b 6= 0n , we have
j j
{a ∈ F2n ; γF (a, b) = 1} = {a ∈ F2n \ {0n }; ∃x ∈ F2n ; a2 +1 (x2 + x + 1) =
j
b
b} = {a ∈ F2n ; ∃x ∈ F2n \ (F4 \ F2 ); a2 +1 = x2j +x+1 } = {a ∈ F2n ; ∃y ∈
j
F2n \ {0}; trn (y) = 0, a2 +1 = yb }, and we know (as proved by Dobbertin for
every APN power function in even dimension, and reported for instance in [13,
j
Proposition 165]) that a2 +1 ranges over the set of cubes of F2n when a ranges
j
over F2n and a 7→ a2 +1 is 3-to-1 over F∗2n . This leads to determining those
b
cubes which equal y with trn (y) = 0.

Remark. By using the Poisson summation formula (see e.g. [13, Corollary 3]),
it is possible to relate the Hamming weight of any restriction of γF obtained

7
by fixing a, respectively b, to the Fourier-Hadamard transform of γF (or to its
Walsh transform), that is related as shown in [15] (see also Section 6 in the
present paper) to the Walsh transform of F . We shall not give the details of
the calculation, but we could check that this gives with no surprise that the
Hamming weight of the restriction of γF obtained by fixing a 6= 0n equals 2n−1 .
It also gives that the Hamming weight of the restriction of γF obtained by fixing
b 6= 0n equals 2−(n+1) v∈Fn WF2 (0n , v)(−1)b·v (this could also be shown by us-
P
2
ing the Wiener-Khintchine formula, see e.g. [13, Relation 2.53]). We find again
2n−1 in the case of a permutationP since we have then WF (0n , v) = 0 for every
v 6= 0n . For non-permutations, v∈Fn WF2 (0n , v)(−1)b·v clearly depends on b.
2

Another property of γF is that, for every a, a0 , b ∈ Fn2 where a and a0 are

nonzero and distinct, if γF (a, b) = 1 then there exists b0 such that γF (a0 , b0 ) =
γF (a + a0 , b + b0 ) = 1. Indeed, there exists x ∈ Fn2 such that b = Da F (x) and
taking b0 = Da0 F (x), we have b + b0 = Da+a0 F (x + a).
Since APN functions are rare, it seems obvious that γF cannot be any 2n-
variable Boolean function having the properties described above, but little is
known on γF for general APN functions F , which would make it easier to
distinguish when a general 2n-variable Boolean function having such properties
can be a γF function. After the investigation we shall make in the present paper,
the Walsh transform will appear as the most efficient way of selecting functions
likely to be γF functions (see Section 6).
Quadratic APN functions have a well-known additional property, which
makes them easier (but still hard) to find than general APN functions: the
equation Da F (x) = b being linear, APNness reduces for them to the con-
dition that, for every a 6= 0n , the homogeneous linear equation ϕF (a, x) :=
Da F (x) + Da F (0n ) = F (x) + F (x + a) + F (0n ) + F (a) = 0n has exactly two
solutions1 , which are 0n and a. Note that ϕF is bilinear (more precisely, sym-
plectic). Quadratic APN functions are probably rare among all APN functions,
but they are rather numerous among known APN functions. The γF functions of
quadratic APN functions have also well-known additional properties: for every
a 6= 0n , the support Im(Da F ) of the function b 7→ γF (a, b) is an affine hyper-
plane, and since for every a, a0 , the function Da Da0 F (x) takes constant value and
this value equals Da Da0 F (0n ) = ϕF (a, a0 ), then for every a, a0 6= 0n , Im(Da F ) is
stable under translation by ϕF (a, a0 ), since Da F (x)+Da Da0 F (x) = Da F (x+a0 )
belongs to Im(Da F ). And as observed in [4], since for a 6= 0n , the sup-
port of the function b 7→ γF (a, b) is an affine hyperplane (i.e. a linear hy-
perplane or its complement), γF is a (Maiorana-McFarland) function of the
form γF (a, b) = G(a) · b + h(a), with G(0n ) = 0n , h(0n ) = 0 and G(a) 6= 0n for
a 6= 0n .
The general expression of the algebraic normal form or the univariate rep-
resentation of γF has never been studied (the latter has been given only for
the main examples of known almost bent functions, see [4]). We briefly address
them in Section 4.
1 This generalizes to plateaued APN functions, see [10, 13].

8
 No real study of the algebraic degree of γF when F is a general APN func-
tion has been made (and for some known APN functions, it is not even easy to
determine the algebraic degree of their γF function).
When F is almost bent, then we know that since γF is bent, it has algebraic
degree at most n (see e.g. [13, Theorem 13] for the fact that any 2n-variable
bent function has algebraic degree at most n), but what is the lowest possible
algebraic degree is unknown (and what are all the particularities of this bent
function is also not clear).
The possible values of the algebraic degree of γF function for general APN func-
tion F are even more of a mystery. They can be as large as 2n − 4 (at least
n
for n odd) since when F is the multiplicative inverse function
F (x) = x2 −2 ,
1
which is APN for n odd, we have (see [15]) γF (a, b) = trn ab + 1 + δ0 (a) +
δ0 (b) + δ0 (a)δ0 (b) + δ0 (ab + 1) and the algebraic degree of this function is
1


2n − 4, since the algebraic degree of trn ab and of δ0 (a)δ0 (b) + δ0 (ab + 1) =
n n n P2n −2 n n
(a2 −1 + 1)(b2 −1 + 1) + (ab + 1)2 −1 + 1 = i=0 (ab)i + a2 −1 + b2 −1 equals
2n − 2 and these two functions have the same terms of algebraic degree 2n − 2,
no term of algebraic degree 2n − 3 and different terms of algebraic degree 2n − 4.
Can the algebraic degree be larger than 2n−4? This is not clear (but we know it
cannot equal 2n since γF has an even Hamming weight).P It equals 2n − 1 if and
only if F has algebraic degree n, since we have seen that b∈Fn b γF (a, b) equals
P 2
the same value x∈Fn F (x) for every a 6= 0n and is zero for a = 0n , and this im-
P 2 P
plies a,b∈Fn (a, b) γF (a, b) = (0n , x∈Fn F (x)). We know (see Section 2) that
2 2
the nullity of these two sums is equivalent to the facts that, respectively, γF has
degree less than 2n−1 and F has degree less than n. Determining whether there
exist APN (n, n)-functions of algebraic degree n is an open problem (proofs of
non-existence are given in [5] within some general classes of functions).

Remark. According to the observations above, we have also that the algebraic
degree of an APN function F equals n if and only if at least one (equivalently,
any) of the functions fa (b) = γF (a, b), a 6= 0n , has algebraic degree n − 1. 

What can be the lowest possible algebraic degree of γF functions is also un-
known. We know it cannot be 0 or 1 because of the Hamming weight of γF .
Note that McEliece’s theorem [19] does not give more information: it tells us
that the Hamming weights of 2n-variable Boolean functions of algebraic degree
2d r e−1 . Since the Hamming weight of γF is not divis-
2n
at most r are divisible by
ible by 2n , we have 2n
 
r − 1 < n and this only gives dalg (γF ) > 1. Considering
the Hamming weight of restrictions does not seem to give information either:
for instance, given a 6= 0n , the restriction of γF to the (n + 1)-dimensional
subspace {0n , a} × Fn2 has Hamming weight 2n−1 , which only tells that the al-
gebraic degree is at least 2.
Note however that if γF is quadratic, then it is bent, and F is then almost
bent (and n is odd), according to the result of [15] recalled in the introduction.
The existence of APN functions F such that γF is quadratic reduces then to
the existence of almost bent functions having this property, and the minimum

9
algebraic degree of γF when F is an APN (n, n)-function with n even is at least
3. No (almost bent) function is known with a quadratic γF function for n ≥ 5
j
(even for the quadratic Gold APN functions F (x) = x2 +1 , gcd(j, n) = 1, we
n j
have γF (a, b) = 1 + trn (1 + ba2 −2 −2 ) as observed in [15] and the algebraic
degree of γF is then n − 2). We leave open the question of the determination of
the possible values of the algebraic degrees of the γF functions of APN (n, n)-
functions, respectively, of almost bent (n, n)-functions, and in particular of their
minimum values.
Nothing seems to be known either on the linear structures of γF , that is,
those nonzero pairs (α, β) ∈ (Fn2 )2 such that D(α,β) γF (a, b) = γF (a, b) + γF (a +
α, b + β) is constant (even if we restrict ourselves to 0-valued linear structures,
that is, those such that D(α,β) γF (a, b) is the zero function - the others being
called 1-valued). The study of linear structures is often one of the simplest
studies to be done on Boolean functions. However, for γF functions, the question
seems wide open, while knowing the linear structures on the γF functions of
general APN functions F would tell much on F . We obtain partial results in
Section 5 and deduce corollaries in Subsection 5.2.
What is known from [21] is that, for every APN (n, n)-function F with n even,
there exists v 6= 0n such that the component function v·F has no (nonzero) linear
structure, that is, admits no a 6= 0n such that the Boolean function v · (Da F )
is constant. This is equivalent to saying that, for every nonzero a ∈ Fn2 , the
set {b ∈ Fn2 ; γF (a, b) = 1} is neither included in {0, v}⊥ nor disjoint from this
hyperplane. In other words, {b ∈ Fn2 ; γF (a, b) = 1} is neither equal to {0, v}⊥
nor equal to its complement. This is good to know but it is rather thin as a
piece of information on γF .
We shall see in Subsection 6.3 that the nonlinearity of γF is closely related
to that of F itself; many questions remain open about them. We shall provide
a lower bound in Subsection 6.2 thanks to results obtained in Subsections 6 and
6.1.
It is difficult to make conjectures about the questions evoked above, since
all known APN functions, except a sporadic one due to Edel and Pott [18], are
either power functions or quadratic functions, and seem then peculiar.

4 On the algebraic normal form and univariate

representation of γF
Let F be known by its ANF:
X Y
F (x) = uI xi ; uI , x ∈ Fn2 .
I⊆{1,...,n} i∈I

Let us denote by f1 , . . . , fn the coordinate functions of F . Denoting uI =

(uI,1 , . . . , uI,n ), we have that, for every j = 1, . . . , n, the ANF of fj writes:
X Y
fj (x) = uI,j xi .
I⊆{1,...,n} i∈I

10
For every a ∈ Fn2 , we have:
 
X X Y Y 
Da F (x) = uI  ai xi  ,
I⊆{1,...,n} J(I i∈I\J i∈J

 
X X Y Y
Da fj (x) = uI,j  ai xi  .
I⊆{1,...,n} J(I i∈I\J i∈J

For every a, b ∈ Fn2 ,

we have γF (a, b) = 1 if and only if a 6= 0n and ∃x ∈ Fn2 ; b =
Da F (x). Since the contrary of “∃x ∈ Fn2 ; b = Da F (x)” is “∀x ∈ Fn2 ; ∃j ∈
{1, . . . , n}; bj + Da fj (x) + 1 = 0” and a product of bits equals 1 if and only if
all its terms equal 1, and is null if and only if one of its terms is null, we have
then:
γF (a, b) =
  
Y Y n
(δ0 (a) + 1) 1 +  [bj + Da fj (x) + 1] + 1 =
x∈Fn
2 j=1
      
Y n
Y X X Y Y
(δ0 (a)+1) 1 +  bj + uI,j  ai xi  + 1  + 1   .
x∈Fn
2 j=1 I⊆{1,...,n} J(I i∈I\J i∈J

This expression is rather complex, but the situation simplifies if we con-

sider the univariate representation of F (leading to the bivariate expression of
γF (a, b)) instead of its ANF. Let:
n
2X −1
F (x) = ui xi ; ui , x ∈ F2n .
i=0
Y k k
2k , we have (x + a)i = (x2 + a2 ) =
P
For every a ∈ F2n and every i = k∈I
k∈I
2l 2k
X P P
a l∈I\J x k∈J and therefore:
J⊆I

n
2X −1 X
Da F (x) = ui ai−j xj ,
i=0 ji;j6=i

where j  i means that the binary expansion of j is covered by that of i. We

n
have δ0 (a) = a2 −1 + 1 and for every a, b ∈ F2n , γF (a, b) = 1 if a 6= 0 and
∃x
Q ∈ F2n ; b = Da F (x). The contrary of “∃x ∈ F2n ; b = Da F (x)” is then
n
“ x∈F2n (b + Da F (x))2 −1 = 1”. We have then, for every a, b ∈ F2n :

γF (a, b) =

11
  
n n
2 −1 
Y
−1
a2 1 + (b + Da F (x)) =
x∈F2n
  n
2n −1 
2X −1
n Y X
−1
a2 1 + b + ui ai−j xj  . (12)
 
x∈F2n i=0 ji;j6=i

Note that this expression of a and b has in general degree larger than 2n in
each variable a and b. The bivariate representation of γF (a, b) is obtained after
n n
reducing Relation (12) modulo a2 + a and b2 + b, that is, concretely, after:
- reducing modulo 2n − 1 each exponent of a (resp. b) which is not a multiple
of 2n − 1,
- replacing by 2n − 1 each nonzero exponent of a (resp. b) which is a multiple
of 2n − 1,
and this seems difficult to perform on the general expression.

5 On the linear structures of γF and their rela-

tion with bent components of F
We shall see in Subsection 5.2 that the study of 0-valued linear structures of the
form (0n , β) of APN functions is related to that of their bent components. Let
us first show that these linear structures are the only ones which could possibly
exist. In the next proposition, WγF denotes the Walsh transform of γF .
Proposition 1. Let n be any positive integer, F any APN (n, n)-function, α
and β any elements of Fn2 , and  ∈ F2 . Function γF admits (α, β) for -valued
linear structure if and only if:

∀u, v ∈ Fn2 , (α · u + β · v =  + 1) ⇒ WγF (u, v) = 0.

Function γF admits then no 1-valued linear structure and no (0-valued) linear

structure (α, β) such that α 6= 0n .
For every β ∈ Fn2 , (0n , β) is a 0-valued linear structure of γF if and only if all
the component functions v · F such that v 6∈ {0n , β}⊥ are bent.
No APN (n, n)-function with n odd has linear structures.
Proof. It is known (see e.g. [13, Proposition 29]) that any n-variable Boolean
function f admits e ∈ Fn2 for 0-valued (resp. 1-valued) linear structure if and
only if the support {u ∈ Fn2 ; Wf (u) 6= 0} of Wf is included in {0n , e}⊥ = {x ∈
Fn2 ; e · x = 0} (resp. in its complement). This proves the first part of the propo-
sition, after replacing n by 2n, f by γF and e by (α, β).
It is known (see [15], or Section 6 below) that, for every u, v ∈ Fn2 , WγF (u, v)
equals 2n if v = 0n , and 2n − WF2 (u, v) otherwise. Since WγF (u, v) is then
nonzero for every u if v = 0n , this shows that, if (α, β) is a linear structure of
γF , then the affine hyperplane {(u, v) ∈ (Fn2 )2 ; α · u + β · v =  + 1} has empty
intersection with the vector space Fn2 × {0n }, that is, the equation α · u =  + 1

12
has no solution, or equivalently,  = 0 (since if  = 1 then u = 0n is a solution)
and α = 0n (since if α 6= 0n then the equation has solutions). The rest of the
proposition is straightforward. 

Open problem 1: Address the (non)existence of the linear structures of γF

functions for general APN functions. Proposition 1 allows to restrict the study
to 0-valued linear structures of the form (0n , β) for n even.

Remark. Thanks to Proposition 1, determining whether, for a given APN

(n, n)-function F (n even), function γF has linear structures, is a sub-problem
of determining what is the maximum dimension of the affine spaces of bent
components of F . Indeed, if F admits a linear structure (0n , β), then the com-
plement, say H, of {0n , β}⊥ is an affine hyperplane of Fn2 such that all the
components v · F , v ∈ H, of F are bent, and conversely, if we have such an
affine hyperplane, then we have a linear structure. And it is easily seen (using
that any APN function has nonzero nonlinearity, as proved in [9] and recalled in
[13, Proposition 161]) that, for any APN function F , the dimension of an affine
subspace A of Fn2 equals the dimension of the affine subspace {v · F ; v ∈ A} of
Bn . The functions v · F , v ∈ H, above provide then an affine space of maxi-
mum dimension of bent components. This leads naturally to the following open
question: what is, for a given even n, the largest dimension of the affine spaces
of bent functions? All these questions seem difficult (probably more difficult,
but also more interesting from the viewpoint of bent functions, than determin-
ing the number of bent components of vectorial functions, see Subsection 5.2). 

Open problem 2: Determine, for every even positive integer n, the maximum
dimension of affine spaces of bent components of APN (n, n)-functions.

Open problem 3: Determine, for every even positive integer n, the maximum
dimension of affine spaces of bent n-variable Boolean functions.

Remark. Affine spaces of bent functions are addressed in [8], but not their max-
imum dimension. It is shown that k-dimensional affine spaces of bent Boolean
n-variable functions, with k even, correspond to bent functions in n+k variables
of a particular form: an affine space f + < f1 , . . . , fk > of Boolean functions
(where < f1 , . . . , fk > denotes the vector space over F2 spanned by F2 -linearly
independent functions f1 , . . . , fk ) contains only bent functions if and only if the
Boolean function:
k
2
X
h : (x, y) ∈ Fn2 × Fk2 7→ (y2i−1 ⊕ f2i−1 (x))(y2i ⊕ f2i (x)) ⊕ f (x)
i=1

is bent. Note that, since f is bent, then it has algebraic degree at most n2 and
since h is bent, it has algebraic degree at most n+k 2 . By applying the charac-
terization of [8] to the affine planes in this affine space, we deduce that any two
distinct functions f1 , f2 in the direction of any affine space of n-variable bent

13
functions have a product f1 (x)f2 (x) of algebraic degree at most n2 + 1. This
puts some constraint on the affine space and probably also on its dimension. 

Remark. An m-dimensional affine space of n-variable P bent functions (n even)

is a set of bent functions over Fn2 of the form f + i∈I gi where I ranges over
the subsets of {1, . . . m} and where the gi ’s are linearly independent Boolean
functions. Let us denote by G the (n, m)-function whose coordinate functions
are the gi ’s. The functions write then f + y · G where y ranges over Fm 2 and “·”
is the usual inner product. Note that the function h : (x, y) 7→ f (x) + y · G(x)
is a Maiorana-McFarland function (see [13]).
The function x 7→ f (x)+y ·G(x) is bent for every y ∈ Fm 2 if and only if, for every
n
nonzero a ∈ F2 and every y, the function D a f (x) + y · Da G(x) is balanced, that
is, x∈Fn (−1)Da f (x)+y·Da G(x) = 0, and using that a pseudo-Boolean function
P
2
is identically null if and only if its Fourier-Hadamard transform is identically
null, this is equivalent to:
X
∀a ∈ Fn2 , a 6= 0, ∀b ∈ Fm2 , (−1)Da f (x)+y·Da G(x)+b·y =
x∈Fn
2
y∈Fm
2

X
2m (−1)Da f (x) = 0.
x∈(Da G)−1 (b)

A necessary condition for all functions f (x) + y · G(x) to be bent is then that,
−1
for every nonzero a ∈ Fn2 and every b in Fm 2 , the size of the set (Da G) (b) is
−1
divisible by 4. Indeed, if for some a 6
= 0 and some b we have |(D a G) (b)| ≡2
(mod 4), the sum x∈(Da G)−1 (b) (−1)Da f (x) is the double of an odd integer, since
P

both the function Da f and the set (Da G)−1 (b) are invariant under translation
by a (in particular, if G is an APN (n, n)-function, then it is impossible that
the n-dimensional affine space of n-variable functions f (x) + y · G(x) is made of
bent functions, only).
Once the necessary condition is satisfied, a necessary and sufficient condition is
that, for every a 6= 0, function Da f is balanced on each pre-image by Da G. 

5.1 The difficulty of addressing 0-valued linear structures

of the form (0n , β) in general, for n even
Function γF admits (0n , β) for 0-valued linear structure (which, according to
Proposition 1, is the only possible case of linear structure of γF and needs that
n is even, which we assume in the rest of this section) if and only if, for every
(a, b) such that γF (a, b) = 1, we have γF (a, b + β) = 1 (indeed, the condition is
necessary, and it is sufficient since this implies that γF (a, b) = 1 is equivalent to
γF (a, b + β) = 1 and therefore, γF (a, b) = 0 is equivalent to γF (a, b + β) = 0,
and then D(0n ,β) γF (a, b) equals 0). Consequently, function γF admits (0n , β)
for 0-valued linear structure if and only if, for every nonzero a and every x in
Fn2 , there exists y ∈ Fn2 such that Da F (x) + Da F (y) = β. Thanks to the change
of variable b = x + y, this is equivalent to the fact that, for every nonzero a and

14
every x in Fn2 , there exists b ∈ Fn2 such that Da Db F (x) = β. Note that this may
be a weakness exploitable in attacks on cryptosystems using F as S-box, and
this is one more reason why studying the linear structures of γF . Note also that
if v 6∈ {0n , β}⊥ , then we have Da Db (v · F )(x) = v · β = 1. This does not seem
enough to conclude that Da (v · F ) is balanced, because b depends not only on
a but also on x, and this does not then allow to deduce a partition of Fn2 into
pairs such that Da (v · F ) takes both values 0 and 1 (i.e. is balanced) on each
pair, but we know that Da (v · F ) is balanced, since we know that v · F is bent,
thanks to Proposition 1.

Remark. Denoting ∆ = {(x, x); x ∈ Fn2 }, we have that F being APN, the func-
tion φ : (a, (x, y)) ∈ (Fn2 \ {0n }) × ((Fn2 )2 \ ∆) 7→ Da F (x) + Da F (y), involved
in this characterization, is such that, when fixing any two elements among a, x
and y, the corresponding restriction of φ is 2-to-1. Indeed, if we fix a 6= 0n and
x (or y), then this corresponds exactly to the definition of APNness, and if we
fix x and y such that x 6= y and consider two distinct elements a, a0 in Fn2 \ {0n },
then we have that Da F (x) + Da F (y) = Da0 F (x) + Da0 F (y) if and only if
Da F (x)+Da F (y)+Da0 F (x)+Da0 F (y) = Da+a0 F (x+a)+Da+a0 F (y+a) = 0 and
F being APN and x+y nonzero, this is equivalent to saying that x+y = a+a0 . 

It seems difficult to study the 0-valued linear structures of the form (0n , β)
of γF , in general. We have seen that handling γF in bivariate representation
is simpler than with the ANF. Let us then consider the expression in (12).
The pair (0, β) is a 0-valued linear structure of γF if and only if the bivariate
expression of γF (a, b) is invariant under translation of b by β, that is, according
to (12), if for every a 6= 0:
 n
2n −1
Y 2X −1 X
b + ui ai−j xj  ≡
x∈F2n i=0 ji;j6=i
 n
2n −1
2X −1
Y X n n
b + β + ui ai−j xj  [mod a2 + a, b2 + b].
x∈F2n i=0 ji;j6=i

It seems hard to go further with this method, when dealing with general APN
n n
functions; this would need to handle the reduction modulo a2 + a and b2 + b,
which is necessary before we can apply the uniqueness of the univariate repre-
sentation of an (n, n)-function.

Remark. 1. It is shown in [1] that the number of bent components of a

n+k
plateaued APN function of nonlinearity 2n−1 − 21 2 2 is at least 23 (2n − 1) +
1 k 2 n−1
3 (2 − 2 ). This number being, whatever is k, significantly larger than 2 ,
this may give some chances of existence, for some APN functions to be found,
of an (n − 1)-dimensional affine space of bent components and then of linear
structures of γF , according to Proposition 1.
n
2. Recall from [24] that 2n − 2 2 is the maximum possible number of bent

15
components of any (n, n)-function (we shall revisit this in Subsection 5.2). It
is proved in [20] that plateaued APN functions F cannot reach this maximum.
The idea of the proof is very simple: we know that, since F is APN, we have
WF4 (u, v) = 23n+1 (2n − 1) (see [17]), and since F is plateaued,
P
u,v∈Fn
2 ,v6=0n
we know that if a component function v · F is not bent,Pthat is, has am-
n
plitude 2 2 +k with k ≥ 1, then 4 n+2k
WF2 (u, v) =
P
u∈Fn W F (u, v) = 2 u∈Fn
2 2
n
3n+2k 3n+2 n
2 is divisible by 2 . If F has 2 − 2 2 bent components, then we have
n
4 n
− 2 2 ) 23n (mod 23n+2 ) ≡ 0 (mod 23n+2 ), a con-
P
n
u,v∈F2 ,v6=0n W F (u, v) ≡ (2
tradiction (assuming that n ≥ 4). This proof does not work for showing the
non-existence of (n − 1)-dimensional affine spaces of bent components of F ; it
only tells that if such affine space exists, there necessarily exist bent components
of F outside it. 

5.1.1 The case of APN power functions

APN power functions are easier to study. For F (x) = xd and a 6= 0, we
have γF (a, b) = γF (1, abd ), since Da F (ax) = ad D1 F (x). Then, (0, β) is a 0-
valued linear structure of γF if and only if, for every a 6= 0, aβd is a 0-valued
linear structure of the n-variable function γF (1, b). We know, according to the
Dobbertin result already recalled and recorded in [13, Proposition 165], that
when a ranges over F∗2n , ad ranges over the multiplicative group C of all cubes
of F∗2n . The existence of a (nonzero) 0-valued linear structure of the form (0, β)
for function γF would imply the invariance of the support of γF (1, b) under the
translation by any element of the coset b C, and then under translation by any
element of b < C > where < C > is the F2 -vector space spanned by C. It is
easily seen that, n being even, x3 + (x + 1)3 ranges over the vector space of all
elements of trace 0 (let us denote it by E) and then C + C includes C E, since
(ax)3 + (ax + a)3 = a3 (x3 + (x + 1)3 ), and therefore |C + C| > |E| = 2n−1 since
there are cubes of traces 0 and 1, and therefore < C >= Fn2 (since its dimension
is strictly larger than n − 1 and equals then n), and γF would be constant, a
contradiction. We have then:
Proposition 2. For any n and for any APN power (n, n)-function F , the γF
function has no (nonzero) linear structure.

Remark. Despite the result of Proposition 2, for every a 6= 0n , the Boolean

function b 7→ γF (a, b) may have linear structures. For instance in the case
j
of Gold APN functions over F2n : F (x) = x2 +1 , gcd(j, n) = 1, we have
that β is a linear structure of b 7→ γF (a, b) if and only if, for every x ∈
2j 2j 2j +1 j j
 y ∈ F2n such
F2n , there exists  that a x + ax + a + a2 y + ay 2 +
j
j j x+y 2
a2 +1 = a2 +1 x+y


a + a = β and this happens for every β such that
 
trn a2jβ+1 = 0, but there is no β 6= 0 which satisfies this condition for every
a 6= 0. 

16
5.1.2 Another class admitting no linear structure
Another case where the study of linear structures of γF is simplified (in fact, is
straightforward) is when F is plateaued with a single amplitude. Indeed, since,
according to Proposition 1, some component functions of F should be bent, all
should then be bent, that is, F should be bent, and we know from [22] that no
bent (n, n)-function exists.
It is possible to extend this observation: according to [10], F is plateaued with
a single amplitude if and only if the size of the set {(a, b) ∈ (Fn2 )2 ; Da Db F (x) =
w} does not depend on x ∈ Fn2 nor on w ∈ Fn2 when w 6= 0n . Let us show that
the condition “does not depend on x ∈ Fn2 ” is not necessary for proving the
non-existence of linear structures:
Proposition 3. Let n be any positive integer and F any APN (n, n)-function
such that, for some x ∈ Fn2 , the size of the set {(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w}
does not depend on w ∈ Fm 2 when w 6= 0n . Then γF admits no (nonzero) linear
structure.

Proof. According to Proposition 1, we can restrict ourselves to a 0-valued lin-

ear structure of the form (0n , β). Suppose that (0n , β) is such a linear struc-
ture of γF . Then, for every nonzero a and every x, there exists b ∈ Fn2 such
that Da Db F (x) = β. We have then |{(a, b) ∈ (Fn2 )2 ; Da Db F (x) = β}| ≥
2n − 1. Taking now for x one of the elements such that the size of the set
{(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w} does not depend on w ∈ Fm 2 when w 6= 0n ,
and using that Da Db F (x) equals 0 when a or b equals zero P or a = b, we de-
duce that |{(a, b) ∈ (Fn2 )2 ; a 6= 0n , b 6= 0n , a 6= b}| ≥ w∈Fn |{(a, b) ∈
2 \{0n }
(Fn2 )2 ; Da Db F (x) = w}| = (2n − 1) |{(a, b) ∈ (Fn2 )2 ; Da Db F (x) = β}| ≥
(2n − 1)2 , a contradiction since |{(a, b) ∈ (Fn2 )2 ; a 6= 0n , b 6= 0n , a 6= b}| =
(2n − 1)(2n − 2). 

Remark. The class of those APN functions such that, for some x, the size
|{(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w}| does not depend on w ∈ Fm 2 when w 6= 0n , is
larger than the class of plateaued APN functions with a single amplitude. Let us
give examples of such functions which are not plateaued with a single amplitude.
Let us take for instance x = 0n and restrict ourselves to those (n, n)-functions
F such that F (0n ) = 0n . Using Relations P (4) and (3), we have that |{(a, b) ∈
(Fn2 )2 ; Da Db F (0n ) = w}| is equal to 2−n a,b,v∈Fn (−1)v·(F (a)+F (b)+F (a+b)+w) =
2
00 0 00
2−4n a,b,v,u,u0 ,u00 ∈Fn WF (u, v)WF (u0 , v)WF (u00 , v)(−1)(u+u )·a+(u +u )·b+v·w =
P
2
2−2n v,u∈Fn WF3 (u, v)(−1)v·w and |{(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w}|, does not
P
2
depend on w 6= 0n if and only if u∈Fn WF3 (u, v) does not depend on v 6= 0n .
P
2
This is for instance the case of power permutations.
Note that the proof of Proposition 3 above does not work for general plateaued
functions: it is shown in [10] that F is plateaued if and only if the size of the
set {(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w} does not depend on x ∈ Fn2 ; but changing
x for another value does not change {(a, b) ∈ (Fn2 )2 ; Da Db F (x) = w} into a
disjoint set, contrary to changing w for another value (when F is quadratic, it

17
does not even change the set at all). Hence, we cannot have x playing the role
played by w in the proof above. 

5.1.3 Some more observations on the 0-valued linear structures of

the form (0n , β)
Let us assume without loss of generality (up to the composition of F by a
linear permutation on the right), that F admits for linear structure (0n , β),
where β = (0, . . . , 0, 1) = (0n−1 , 1). Using Proposition 1, let ϕ be the Boolean
function over Fn2 × Fn−1 2 such that, for every v = (w, 1), where w ∈ Fn−12 , the
Boolean function u 7→ ϕ(u, w) is the dual of the bent function v · F , that is,
n
WF (u, v) = 2 2 (−1)ϕ(u,w) for every u ∈ Fn2 . For every a ∈ Fn2 and b ∈ Fn−12 , we
have, denoting by fn the last coordinate function of F and by F 0 (x) the vector
obtained from F (x) by discarding its last coordinate fn (x):
n
X
Wϕ (a, b) = 2− 2 WF (u, (w, 1)) (−1)a·u+b·w
u∈Fn2
n−1
w∈F2

n
X 0
= 2− 2 (−1)u·(x+a)+w·(F (x)+b)+fn (x)

u,x∈Fn
2
n−1
w∈F2

3n
= 2 2 −1 δ0 (F 0 (a) + b) (−1)fn (a) , (13)

where δ0 is here the Dirac symbol over Fn−1 2 (i.e. the indicator function of
3n
the singleton {0n−1 }). Hence, ϕ is plateaued of amplitude 2 2 −1 , and since
3n
the Walsh transform of ϕ is divisible by 2 2 −1 , its algebraic degree is at most
3n n
(2n − 1) − ( 2 − 1) + 1 = 2 + 1, according to a well-known result recalled
in [13, Theorem 2], while each function u 7→ ϕ(u, w) has algebraic degree at
most n2 , since it is bent. The inverse Walsh transform relation (3) applied to
n P 0
ϕ gives (−1)ϕ(u,w) = 2− 2 a∈Fn (−1)fn (a)+u·a+w·F (a) , nothing more than the
2
definition of ϕ. The Parseval relation (5) applied to ϕ writes 24n−2 = 24n−2
and does not give any information either. The Titsworth relation (6) applied to
ϕ writes, for every nonzero (a0 , b0 ) ∈ Fn2 × Fn−1
2 :
X
Wϕ (a, b)Wϕ (a + a0 , b + b0 ) =
n−1
(a,b)∈Fn
2 ×F2
X
23n−2 (−1)Da0 fn (a) = 0,
a∈(Da0 F 0 )−1 (b0 )

since when b = F 0 (a), the relation b+b0 = F 0 (a+a0 ) is equivalent to Da0 F 0 (a) =
b0 . Note that if a0 6= 0n , then |(Da0 F 0 )−1 (b0 )| ∈ {0, 2, 4}, since F is APN.
Since Da0 fn (a) is invariant under translation by a0 , we deduce that necessarily,
|(Da0 F 0 )−1 (b0 )| ∈ {0, 4}.
Let us consider the two restrictions ϕw : u 7→ ϕ(u, w) and u ϕ : w 7→ ϕ(u, w).
We have, by definition of ϕ and application of the inverse Walsh transform and

18
by the fact that the dual of the dual of a bent function equals the bent function
n
itself, that Wϕw (a) = 2 2 (−1)v·F (a) , where v = (w, 1). Let us calculate Wu ϕ (b).
We have, by the inverse Walsh transform:
X X
Wu ϕ (b) = (−1)ϕ(u,w)+b·w = 2−(2n−1) Wϕ (a, c)(−1)a·u+(b+c)·w =
a∈Fn
w∈Fn−1
2 2
n−1
w,c∈F2

n
X X
2−n Wϕ (a, b)(−1)a·u = 2 2 −1 (−1)fn (a)+a·u
a∈Fn
2 a∈F 0 −1 (b)

(the last equality being deduced from Relation (13)). Hence, by [13, Theorem
2] again, the algebraic degree of u ϕ is at most n2 + 1, which gives no new
information.

5.2 On the bent component functions of APN functions

Since WγF (u, v) equals 2n − WF2 (u, v) if v 6= 0n , the component function v · F
of an APN function F is bent if and only if WγF (u, v) equals 0 for every u ∈
Fn2 . Now, since WγF (u, v) can be viewedPas the value at u of the Fourier-
Hadamard transform of the function a 7→ b∈Fn (−1)γF (a,b)+v·b , and since (as
2
already used), a pseudo-Boolean function is identically null if and only if its
Fourier-Hadamard transform is identically null, we have the following property,
which could be proved also by using the Wiener-Khintchine formula:
Proposition 4. Let F be any APN (n, n)-function. Then for every nonzero
v ∈ Fn2 , the component function v · F is bent if and only if, for every a ∈ Fn2 ,
the Boolean function b 7→ γF (a, b) + v · b is balanced.
Remark. In this proposition, v is assumed nonzero. If we take v = 0n and
if F is APN, then the Boolean function b 7→ γF (a, b) + v · b is balanced for
every a 6= 0n but not for a = 0n . We could have stated the proposition with a
nonzero instead of v nonzero since, if v 6= 0n , b 7→ γF (a, b)+v ·b is automatically
balanced for a = 0n . 

Remark. Replacing (−1)γF (a,b) P (respectively, (−1)v·b ) by 1 − 2γF (a, b) (respec-

tively, by 1 − 2v · b) in the sum b∈Fn (−1)γF (a,b)+v·b and using that b 7→ v · b
2
is balanced for v 6= 0n (respectively, b 7→ γF (a, b) is balanced for a 6= 0n ), we
have that, for every nonzero v, the component function v · F is bent if and
only if, for every nonzero a ∈ Fn2 , the Boolean function b 7→ v · b is balanced
on the set {b ∈ Fn2 ; γF (a, b) = 1} or its complement (respectively, the Boolean
function b 7→ γF (a, b) is balanced on the hyperplane of equation v · b = 1 or its
complement). 

Remark. Poposition 4 combined with Proposition 1 shows that (0n , β) is a

linear structure of γF if and only if, for every v 6∈ {0n , β}⊥ and every a ∈ Fn2 ,
the Boolean function b 7→ γF (a, b) + v · b is balanced. 

19
 It is shown in [24] that the number of bent components of any (n, n)-function
n n
is at most 2n −2 2 and that if an (n, n)-function F has 2n −2 2 bent components,
n
then the set of values of v such that v · F is not bent is an 2 -dimensional vector
space. In [20] (see also some precisions in the more recent reference [1]) is shown
(as we already recalled above) that the set of those (n, n)-functions having
n
2n − 2 2 bent components does not contain any APN plateaued function (that
is, as we recalled already, any APN function F satisfying ∀u, v ∈ Fn2 , WF (u, v) ∈
{0, ±λv } for some integers λv depending only on v), and then in particular any
quadratic APN function.
We have:
n
Corollary 1. For every even n, any APN (n, n)-function F has 2n − 2 2 bent
components if and only if there exists an n2 -dimensional vector subspace V of
Fn2 such that any pair (0n , β) with β ∈ V is a 0-valued linear structure of γF .
n
Proof. Let F have 2n − 2 2 bent components, and according to [24], let E
be the n2 -dimensional vector space such that v · F is bent for v 6∈ E. Let
us denote, for every a ∈ Fn2 , by fa the n-variable function b 7→ γF (a, b).
According to Proposition 4, for every a ∈ Fn2 , we have Wfa (v) = 0 for ev-
ery v 6∈ E. According to the inverse P Walsh transform relation (3), we have
2n (−1)fa (b) = v∈Fn Wfa (v)(−1)v·b = v∈E Wfa (v)(−1)v·b , ∀b ∈ Fn2 , and this
P
2
implies that, for every β ∈ E ⊥ := {x ∈ Fn2 ; v · x = 0, ∀v ∈ E} and every b ∈ Fn2 ,
we have fa (b + β) = fa (b). We have then, for every a, b ∈ Fn2 and every β ∈ E ⊥ ,
that γF (a, b+β) = γF (a, b) and (0n , β) is a 0-valued linear structure of γF . This
completes the proof in the direct sense since E ⊥ has dimension n2 . The converse
is similar, using that fa (b + β) = fa (b) for every b ∈ Fn2 and every β ∈ E ⊥ is
equivalent to Wfa (v) = 0 for every v 6∈ E. 

Proposition 2 and Corollary 1 show then:

Corollary 2. For every even n, any APN power (n, n)-function has strictly
n
less than 2n − 2 2 bent components.
The following problem is posed in [24, Question 8]: are there any APN func-
n
tions having 2n − 2 2 bent components? We leave it open.

6 On the Walsh transform of γF and its nonlin-

earity
As already shown in [15], for every APN (n, n)-function F , we have that γF (a, b),
−1
viewed as a pseudo-Boolean function, equals |(Da F2) (b)| − 2n−1 δ0 (a, b), and
then, by the linearity of the Fourier-Hadamard transform and by Relation (7),
1 X 1
we have: γc F (u, v) = (−1)u·a+v·Da F (x) − 2n−1 = WF2 (u, v) − 2n−1 .
2 n
2
a,x∈F2

20
According to Relation (2) applied with 2n in the place of n and (u, v) in the
place of u, we have then WγF (0n , 0n ) = 22n − WF2 (0n , 0n ) + 2n = 2n , and for
u 6= 0n , WγF (u, 0n ) = −WF2 (u, 0n ) + 2n = 2n , and for u 6= 0n and v 6= 0n ,
WγF (u, v) = −WF2 (u, v) + 2n , and then, for every u, v:
 n
2 if v = 0n ,
WγF (u, v) = (14)
2n − WF2 (u, v) if v 6= 0n .

This implies, as already observed in [15], that γF is bent if and only if F is

AB. Note that, since WγF (u, 0n ) = 2n for every u, this is the only case where
function γF can be plateaued.
This kind of relation between the Walsh transform of a 2n-variable Boolean
function and the Walsh transform of an (n, n)-function is remarkable. The fact
that the Walsh transform of this 2n-variable Boolean function has all its values
bounded above by 2n (like bent functions) and that 2n − WγF (u, v) is more-
over always a square is probably the most distinctive we know for functions γF
(with of course also the fact that each restriction b 7→ γF (a, b) is balanced for
a 6= 0n ). It would be interesting to make a computer investigation of those
2n-variable Boolean functions, say γ, such that all the values taken by 2n − Wγ ,
where Wγ is the Walsh transform of γ, are squares and are equal to 0 when
v = 0n . Note that this latter property implies that the n-variable function
b 7→ γ(a, b) is balanced for every a 6= 0n and null for a = 0n , since accord-
ing
P to the γ(a,b)
Poisson summation formula (or by a direct calculation), we have
−n u·a
P
n
b∈F2 (−1) = 2 n
u∈F2 (−1) Wγ (u, 0n ) and, when Wγ (u, 0n ) equals
constantly 2 , this latter expression equals 0 for a 6= 0n and 2n for a = 0n .
n

Once such functions γ are found, we can use for each of them the resulting
values of |WF (u, v)| and determine the possible signs so that F exists.

We study in the next subsections additional information on F , respectively

on γF , provided by Relation (14).

Remark. When F is a power function F (x) = xd , x ∈ F2n , it is well known

d
that, for u 6= 0, we have WF (u, v) = WF (1, uvd ) (since x∈F2n (−1)trn (vx +ux) =
P
trn ( vd xd +x)
). We have then WγF (u, v) = WγF (1, uvd ). Of course,
P
x∈F2n (−1)
u

this can also be checked directly. 

Remark. We have seen in Section 3 that, when F is a quadratic APN (n, n)-
function, γF has the Maiorana-McFarland formX γF (a, b) = G(a) · b + h(a).
Then, its Walsh transform WγF (u, v) equals (−1)(G(a)+v)·b+h(a)+u·a =
a,b∈Fn
2
X
n h(a)+u·a P h(a)+u·a
2 (−1) . Relation (14) shows then that a∈G−1 (v) (−1)
a∈G−1 (v)
is bounded above by 1. If |G−1 (v)| is even, then a∈G−1 (v) (−1)h(a)+u·a is even
P
too
P andPit is then bounded above by 0; moreover,
h(a)+u·a
P for v 6=h(a)+u·a
0n , we know that
u∈Fn −1
a∈G (v) (−1) equals 0, since u∈Fn (−1) equals 0 if
2 2

21
a 6= 0n and since 0n 6∈ G−1 (v). We deduce then that if |G−1 (v)| is even, then
G−1 (v) is empty (and v 6=P0n ).
If |G−1 (v)| is odd, then a∈G−1 (v) (−1)h(a)+u·a is nonzero for every u. This
means, according to Proposition 1, that γF has a 0-valued linear structure
(0n , β) if and only if G−1 (v) is empty for every v such that v · β = 1, that
is, if G is valued in {0n , β}⊥ . It is not clear whether this is possible. 

6.1 A new relation on the Walsh transform of APN func-

tions deduced from (14)
In this subsection, we shall review the known relations satisfied by one of the
functions WF and WγF , and see if this gives new information on the other.
- The inverse Walsh transform relation (3) applied to the component func-
tion v · F gives u∈Fn WF (u, v)(−1)u·w = 2n (−1)v·F (w) , which does not seem
P
2
to allow deducing any property
X on γF . The inverse Walsh Xtransform rela-
u·a+v·b n
tion applied to γF writes: (−1) WγF (u, v) = 2 (−1)u·a+v·b −
u,v∈Fn
2 u,v∈Fn
2
X
u·a+v·b
(−1) WF2 (u, v) 2n
= 2 (−1) γF (a,b)
, that is:
u,v∈Fn2
v6=0n

X
(−1)u·a+v·b WF2 (u, v) = 23n δ0 (a, b) − 22n (−1)γF (a,b) , (15)
u,v∈Fn2
v6=0n

or equivalently, using that (−1)γF (a,b) = 1 − 2 γF (a, b):

X
(−1)u·a+v·b WF2 (u, v) = 23n δ0 (a, b) + 22n+1 γF (a, b).
u,v∈Fn
2

This relation, which can also be deduced from Relation (7) applied to f = v · F ,
does not give new information.
- The Parseval relation (5) applied to the component function v · F writes:
∀v ∈ Fn2 , WF2 (u, v) = 22n , and implies:
P
u∈Fn2
X
∀v ∈ Fn2 , v 6= 0n , WγF (u, v) = 0.
u∈Fn
2

This relation can also be deduced by applying the Poisson summation formula
(see e.g. [13, Corollary 3]) to γF and using that the Boolean function b 7→
γF (a, b) is balanced for each a 6= 0n ; it then gives no new information either.
The Parseval relation on γF provides (again) the value ofPthe fourth moment
of the Walsh transform of an APN function, see [17]: u,v∈Fn WF4 (u, v) =
2
4n 3n+1
3·2 −2 .
- The Titsworth relation (6) applied to v · F does not seem to give anything
exploitable on γF . When applied to γF , it writes:
X
∀(u0 , v0 ) 6= (0n , 0n ), WγF (u, v)WγF (u + u0 , v + v0 ) = 0, (16)
u,v∈Fn
2

22
that is:
• If v0 = 0n (and u0 6= 0n ), then (by separating the case v = 0n from the
case v 6= 0n ):
X
23n + (2n − WF2 (u, v))(2n − WF2 (u + u0 , v)) = 0,
u,v∈Fn2
v6=0n

that is, by using the Parseval relation on the Boolean function v · F :

X
WF2 (u, v)WF2 (u+u0 , v) = −23n −23n (2n −1)+23n+1 (2n −1) = 24n −23n+1 .
u,v∈Fn2
v6=0n

• If v0 6= 0n (and u0 ∈ Fn2 ), then (by separating the cases “v = 0n or v = v0 ”

and “v 6= 0n , v0 ”):
 
X
2n+1  (2n − WF2 (u, v0 )) +
u∈Fn
2

X
(2n − WF2 (u, v))(2n − WF2 (u + u0 , v + v0 )) =
u,v∈Fn2
v6=0n ,v6=v0

X
(2n − WF2 (u, v))(2n − WF2 (u + u0 , v + v0 )) = 0,
u,v∈Fn2
v6=0n ,v6=v0

(by using again the Parseval relation on the Boolean function v · F ), that
is, :
X
WF2 (u, v))WF2 (u + u0 , v + v0 ) = −23n (2n − 2) + 23n+1 (2n − 2)
u,v∈Fn2
v6=0n ,v6=v0

= 24n − 23n+1 .

The
P characterization of APNness by the fourth moment of the Walsh transform
4 4n+1
n
u,v∈F2 W F (u, v) = 2 − 23n+1 , allows us to cover all cases in the following
v6=0n
statement:
Theorem 1. Any APN (n, n)-function F satisfies, for every (u0 , v0 ), that:
X
WF2 (u, v)WF2 (u + u0 , v + v0 ) = 24n − 23n+1 + 24n δ0 (u0 , v0 ).
u,v∈Fn2
v6=0n ,v6=v0

Of course, the converse is also true (i.e. this relation implies APNness) since
in the particular case u0 = v0 = 0n , we obtain the value of the fourth moment
of WF , which is characteristic of APNness. The relation of Theorem 1 looks like

23
those obtained in [11], but in fact, it is quite different, for (u0 , v0 ) 6= (0n , 0n ).
Indeed, these latter relations involve the values at (0n , 0n ) of the convolutional
products (of diverse orders) of the square of WF with itself, and cannot then
equal the expression of Theorem 1, which involves the value at a nonzero input
of the convolutional product of order 2 of the square of WF . The information
provided by Theorem 1 is then complementary of those obtained in [11]. It has
the advantage of being as simple as Chabaud-Vaudenay’s characterization by
the fourth moment of the Walsh transform, while it provides more information
(and we shall see in the next subsection that it is in fact more exploitable). For
instance, it tells us that, for every APN function F , there does not exist (u0 , v0 )
nonzero such that, for every (u, v), either WF (u, v) = 0 or WF (u+u0 , v+v0 ) = 0.
Of course, if the Walsh support of F has size larger than 22n−1 , this is obvious.
But in the case of, for instance, AB functions (whose Walsh support has size
smaller than 22n−1 ), it gives some information.

6.2 A lower bound on the nonlinearity of a large class of

APN functions including all known ones
In Theorem 1, if |WF (u, v)| takes its maximum at least twice (that is, at two
positions), then denoting by (u0 , v0 ) 6= (0n , 0n ) the difference between two val-
ues of (u, v) where this maximum
P is taken, we have since maxv6=0n ,u WF4 (u, v)
appears then at least twice in u,v∈Fn2
WF (u, v)WF2 (u + u0 , v + v0 ):
2
v6=0n ,v6=v0

Corollary 3. Let n be any positive integer and F any APN (n, n)-function such
that {|WF (u, v)|; u, v ∈ Fn2 , v 6= 0n } takes its maximum for at least two differ-
ent inputs (u, v) (i.e. the minimum Hamming distance between the component
functions of F and affine Boolean functions is achieved more than once), then
we have :
1p
nl(F ) ≥ 2n−1 −
4
24n−1 − 23n .
2
Indeed, we have, according to Theorem 1, that 2 maxv6=0n ,u WF4 (u, v) ≤
2 − 23n+1 , and Corollary 3 is then deduced from Relation (9).
4n

Note that all known APN functions satisfy the condition of Corollary 3. In-
deed, all APN power functions do2 because, for n odd, all component functions
trn (vxd ) are affine equivalent to each others, and for n even, any two compo-
nent functions trn (vxd ) and trn (v 0 xd ) are affine equivalent when vv0 is a cube.
All quadratic APN functions also satisfy the condition (more generally, all non-
affine plateaued functions do since each non-affine component function takes
its maximum Walsh absolute value at least twice) and the sporadic Edel-Pott
function having the same Walsh spectrum as the Gold functions, it does too.

Open problem 4: Determine whether all APN functions satisfy the condi-
tion of Corollary 3. If not, then characterize, and if possible determine, all the
2 But the bound of Corollary 3 is weaker than the bound from [11], which writes that
3n−3 3n−2
nl(F ) ≥ 2n−1 − 2 4 for n odd and nl(F ) ≥ 2n−1 − 2 4 for n even.

24
(n, m)-functions that do not satisfy the condition of this corollary.

Remark. In the proof ofPthe bound of Corollary 3, we take into account only
two terms from the sum u,v∈Fn
2
WF2 (u, v)WF2 (u + u0 , v + v0 ); we neglect all
v6=0n ,v6=v0
the others. Maybe is it impossible that all these other terms simultaneously
vanish, and the bound of Corollary 3 is then improvable. Note also that if some
APN function is found in the future which would not satisfy the hypothesis
of Corollary 3, this function would probably however satisfy almost the same
bound as in Corollary 3: this would be shown by taking for (u0 , v0 ) the differ-
ence between two pairs (u, v) where |WF (u, v)| takes, respectively, its maximum
and its next value in descending order, which would be probably close (unless
the maximum of |WF (u, v)| when u, v ∈ Fn2 , v 6= 0n , is significantly larger than
each of the other values, but it is not clear whether this can happen). 

Remark. Even for general (n, m)-functions, it is not that easy to build func-
tions that do not satisfy the condition of Corollary 3. The study is simplified
when considering those (n, m)-functions obtained by modifying the values of
an affine function L(x) + a (where L is linear over Fn2 ) over a set E of size
less than 2n−2 (which is favorable to a search of functions with low nonlinear-
ity), but even then, the condition is not straightforward. For such function
F , denoting for every x ∈ E by φ(x) the vector added to L(x) + a to obtain
F (x), by L∗ the adjoint operator of L, defined by v · L(x) = L∗ (v) · x, and
by δb the indicator function of the singleton {b} (that P is, the Dirac symbol at
∗
b), we have WF (u, v) = 2n (−1)v·a δL∗ (v) (u) − (−1)v·a x∈E (−1)(L (v)+u)·x +
∗
(−1)v·a x∈E (−1)(L (v)+u)·x+v·φ(x) .
P
Since |E| < 2n−2 , the value of max |WF (u, v)| is achieved for u =
u∈Fn m
2 ,v∈F2 \{0m }

L∗ (v) and equals 2n − |E| + maxv∈Fm v·φ(x)

P
2 \{0m } x∈E (−1) , which is reached
only for one value of (u, v) ∈ Fn2 × Fm
2 \ {0 }
m P under the necessary and sufficient
v·φ(x)
condition that the maximum maxv∈Fm 2 \{0m } x∈E (−1) is achieved by one
value of v only (this condition is always satisfied if m = 1, that is, for a Boolean
function, but
l it2nis not
m straightforward for m > 1, and in any case, the relation
2
|Im(F )| ≥ 3·2n −2 shown in [16, 14] on the image set size of every APN func-
tion and applied to F +L+a shows that, since |E| < 2n−2 , function F cannot be
APN). A larger class could be investigated: that of all the functions defined the
2n
same way but with |E| larger than 3·22n −2 ; characterizing that such a function
22n
does not satisfy the condition of Corollary 3 seems very complex, since 3·2n −2
is large. 

Note that the bound of Corollary 3 can be further improved if there ex-
ists (u0 , v0 ) 6= (0n , 0n ) for which there exist more than two values of (u, v)
such that both |WF (u, v)| and |WF (u + u0 , v + v0 )| achieve the maximum of
{|WF (u, v)|; u, v ∈ Fn2 , v 6= 0n }: according to Theoremq
1, if the number of these
1 24n −23n+1
values (u, v) equals t, then we have nl(F ) ≥ 2n−1 − 2
4
t .

25
 Note that the bound of Corollary 3 and its possible improvement have ap-
proximately the form nl(F ) ≥ λ2n−1 (where of course λ < 1) and a nonlinearity
more or less equal to λ · 2n−1 is asymptotically bad. It would be very interesting
to determine whether some APN functions (to be found) can approach it.

6.3 On the relation between the nonlinearities of γF and

of F
The nonlinearity of γF satisfies, thanks to Relation (8) (applied with 2n in the
place of n) and to Relation (14) and to the fact that WF (u, 0n ) = 0 for u 6= 0n :

 
1
2n−1 n n 2
nl(γF ) = 2 − max 2 , maxn |2 − WF (u, v)|
2 (u,v)∈Fn
2 ×(F2 \{0n })
 
1
= 22n−1 − max 2n , max |2n
− W 2
F (u, v)| .
2 (u,v)∈Fn n
2 ×F2 \{(0n ,0n )}

For being able to deduce the expression of nl(γF ) by means of nl(F ), we need
to look separately at the distances from γF to all linear 2n-variable Boolean
functions and to all of their complements:
- the former equals 22n−1 − 21 max 2n , max(u,v)∈Fn2 ×(Fn2 \{0n }) (2n − WF2 (u, v)) =

22n−1 − 2n−1 and is achieved by the zero linear function (among others),
- the latter equals 22n−1 − 12 max(u,v)∈Fn2 ×(Fn2 \{0n }) (WF2 (u, v) − 2n ).
We have max(u,v)∈Fn2 ×(Fn2 \{0n }) WF2 (u, v) ≥ 2n+1 , according to the SCV bound.
We have then:
1
nl(γF ) = 22n−1 − max W 2 (u, v) + 2n−1 , (17)
2 (u,v)∈Fn2 ×(Fn2 \{0n }) F
and the nonlinearity of γF equals the minimum Hamming distance between γF
and the complements of linear forms (and if F is not AB, then the best affine
approximations of γF are only with such complements).
Proposition 5. Let n be any positive integer and F any APN (n, n)-function
being not almost bent. The best approximations of γF by 2n-variable affine
Boolean functions are the functions `(a, b) = u · a + v · b + 1, v 6= 0n , such that
the Hamming distance between the component function v · F and the n-variable
affine Boolean function u · x + , is minimum for some  ∈ F2 .
The fact that the complexity of the linear attack on a block cipher using an
APN function F as a substitution box is related to that of the fast correlation
attack on a stream cipher in the filter model (see e.g. [13, Subsection 3.1.3])
using γF as nonlinear function, is interesting. Moreover, since the nonlinearity
of F equals 2n−1 − 21 max(u,v)∈Fn2 ×(Fn2 \{0n }) |WF (u, v)|, Relation (17) gives:
1
nl(γF ) = 22n−1 − (2n − 2nl(F ))2 + 2n−1 .
2
Hence:

26
Proposition 6. For every APN (n, n)-function, we have:

nl(γF ) = 2n+1 nl(F ) − 2(nl(F ))2 + 2n−1 . (18)

Note that the function x 7→ 2n+1 x−2x2 +2n−1 is strictly increasing from the
n−1
interval ]0, 2n−1 − 2 2 ] (within which the nonlinearity of an (n, n)-function is
located, according to the lower bound nl(F ) > 0 and to the SCV upper bound)
in the interval ]2n−1 , 22n−1 − 2n−1 ] (within which the nonlinearity of the 2n-
variable Boolean function γF is located, according to (18) and to the covering
radius bound). The value of nl(γF ) is then a strictly increasing function of
n−1
nl(F ) which matches it maximum 22n−1 − 2n−1 at 2n−1 − 2 2 and Proposition
6 can be viewed as a generalization and a clarification of the fact that γF is
bent if and only if F is almost bent. The puzzling question is that, while we
know the maximum of each of the two nonlinearities for n odd, we ignore the
minimum.
Note that, according to Proposition 6, the possible values of nl(γF ) are not all
the integers of the interval ]2n−1 , 22n−1 −2n−1 ]. For instance, for n = 5, if nl(F )
could take any value between 1 and 12, the nonlinearity of γF could take only
the values 78, 136, 190, 240, 286, 328, 366, 400, 430, 456, 478, 496. In fact, the
possible values of nl(F ) are all known3 , see [2], and they are not all the integers
between 1 and 12; indeed, there are only two possible values: the nonlinear-
ity 10 of the Dobbertin and inverse functions and the nonlinearity 12 of almost
bent functions; the nonlinearity of γF can then only take the values 456 and 496.

Open problem 5: Determine, for every n, which values are possible for nl(F )
when F is a general APN (n, n)-function, and therefore, determine which values
are possible for nl(γF ). There are several sub-problems: determine whether
nl(F ) can be an odd integer, which is equivalent to determining whether nl(γF )
can be congruent with 2 modulo 4; a positive reply would imply a positive reply
to the open problem whether the algebraic degree of F can be equal to n, al-
ready mentioned. Note that for general functions F , the fact that the algebraic
degree equals n does not necessarily imply that the nonlinearity is odd (take
for instance a linear function and modify one of its coordinate functions so that
its Hamming weight becomes odd, the algebraic degree equals then n while the
nonlinearity is zero); it is not clear whether we have the same situation when
restricting ourselves to APN functions (this provides then one more open prob-
lem).

Conclusion
In this paper, we have initiated a study of the 2n-variable Boolean function γF
(indicating for which (a, b) ∈ (Fn2 )2 , a 6= 0n , the equation F (x) + F (x + a) = b
has solutions x ∈ Fn2 ) when F is a general APN (n, n)-function. We have de-
scribed how the representations of γF can be obtained from those of F , and
shown the difficulty of studying γF , for instance through its linear structures.
We have shown that linear structures (α, β) can possibly exist only for α = 0n
3 Number 5 is the largest value of n for which they are.

27
and for n even, and we have related their existence to that of affine spaces of
bent Boolean functions. We have also shown how γF can be used for studying
F , and deduced a new relation satisfied by the Walsh transform of F , which
includes as a particular case the Chabaud-Vaudenay characterization of APN
functions, and gives more information. We have more deeply studied the re-
lationship between the nonlinearities of F and γF and derived a lower bound
on the nonlinearity of a large class of APN functions including all known ones,
which gives a beginning of explanation why the nonlinearity of all known APN
functions is rather good. More needs to be done in this direction. We have
posed five open problems (and a few sub-problems) (1) on the existence of lin-
ear structures of γF functions for n even, (2) on the largest dimension of affine
spaces of bent components of APN functions, (3) on the largest dimension of
affine spaces of bent Boolean functions, (4) whether all APN functions have
Walsh transforms taking their maximum absolute value for at least two differ-
ent nonzero inputs (whose positive answer would provide a lower bound on the
nonlinearity of all APN functions), and (5) on the possible values of nl(F ) and
nl(γF ) when F is APN. Further work is needed on these difficult problems and
on other questions on γF functions that we also listed, which have not been
tackled since the introduction of APN functions thirty years ago.

Acknowledgement
We thank Sihem Mesnager for her useful information and her kind help.

References
[1] N. Anbar, T. Kalaycı, W. Meidl and L. Mérai. On functions with the max-
imal number of bent components. arXiv preprint arXiv:2010.03801.

[2] M. Brinkmann and G. Leander. On the classification of APN functions up

to dimension five. Designs, Codes and Cryptography 49 , Issue 1-3, pp. 273-
288, 2008. Revised and extended version of a paper with the same title in
the Proceedings of the Workshop on Coding and Cryptography WCC 2007,
pp. 39-48, 2007.

[3] L. Budaghyan. Construction and Analysis of Cryptographic Functions. 168

pages. Springer 2014, ISBN 978-3-319-12990-7
[4] L. Budaghyan, C. Carlet and T. Helleseth. On bent functions associated
to AB functions. Proceedings of the IEEE Information Theory Workshop
ITW 2011.

[5] L. Budaghyan, C. Carlet, T. Helleseth, N. Li and B. Sun. On upper bounds

for algebraic degrees of APN functions. IEEE Transactions on Information
Theory 64 (6), pp. 4399-4411, 2018.

28
 [6] C. Boura, A. Canteaut, J. Jean and V. Suder. Two notions of differential
equivalence on Sboxes. Designs, Codes and Cryptography 87 (2-3), pp.185-
202, 2019.
[7] A. Canteaut and M. Videau. Degree of composition of highly nonlinear
functions and applications to higher order differential cryptanalysis. Pro-
ceedings of EUROCRYPT 2002, Lecture Notes in Computer Science 2332,
pp. 518-533, 2002.
[8] C. Carlet. A transformation on Boolean functions, its consequences on some
problems related to Reed-Muller codes. Proceedings of EUROCODE 1990,
Lecture Notes in Computer Science 514, pp. 42-50, 1991.

[9] C. Carlet. Vectorial Boolean Functions for Cryptography. Chapter of the

monograph Boolean Models and Methods in Mathematics, Computer Sci-
ence, and Engineering, Y. Crama and P. Hammer eds, Cambridge Univer-
sity Press, pp. 398-469, 2010.
[10] C. Carlet. Boolean and vectorial plateaued functions, and APN functions.
IEEE Transactions on Information Theory 61 (11), pp. 6272-6289, 2015.
[11] C. Carlet. Characterizations of the differential uniformity of vectorial func-
tions by the Walsh transform, IEEE Transactions on Information Theory
64 (9), pp. 6443-6453, 2018. (preliminary version available in IACR Cryp-
tology ePrint Archive http://eprint.iacr.org/ 2017/516, 2017).

[12] C. Carlet. Graph indicators of vectorial functions and bounds on the al-
gebraic degree of composite functions. IEEE Transactions on Information
Theory 66 (12), pp. 7702-7716, 2020.
[13] C. Carlet. Boolean Functions for Cryptography and Coding Theory. Mono-
graph in Cambridge University Press, 562 pages, 2021.
[14] C. Carlet. On the image set size of differentially uniform functions and
related bounds on their nonlinearity and their distance to affine functions.
IACR Cryptology ePrint Archive (http://eprint.iacr.org/) 2020/1529, 2020.
[15] C. Carlet, P. Charpin, and V. Zinoviev. Codes, bent functions and permu-
tations suitable for DES-like cryptosystems. Designs, Codes and Cryptog-
raphy, 15 (2), pp. 125-156, 1998.
[16] C. Carlet, A. Heuser and S. Picek. Trade-Offs for S-Boxes: Cryptographic
Properties and Side-Channel Resilience. Proceedings of ACNS 2017, Lecture
Notes in Computer Science 10355, pp. 393-414, 2017.

[17] F. Chabaud and S. Vaudenay. Links between Differential and Linear Crypt-
analysis. Proceedings of EUROCRYPT 1994, Lecture Notes in Computer
Science 950, pp. 356-365, 1995.

29
[18] Y. Edel and A. Pott. A new almost perfect nonlinear function which is not
quadratic. Advances in Mathematics of Communications 3 (1), pp. 59-81,
2009.
[19] R. J. McEliece. Weight congruence for p-ary cyclic codes. Discrete Mathe-
matics, 3, pp. 177-192, 1972.

[20] S. Mesnager, F. Zhang, C. Tang and Y. Zhou. Further study on the max-
imum number of bent components of vectorial functions. Designs, Codes
and Cryptography 87 (11), pp. 2597-2610, 2019. Also: arXiv:1801.06542.
[21] A. Musukwa and M. Sala. On the linear structures of balanced functions
and quadratic APN functions. Cryptography and Communications 12 (5),
pp. 859-880, 2020.
[22] K. Nyberg. Perfect non-linear S-boxes. Proceedings of EUROCRYPT 1991,
Lecture Notes in Computer Science 547, pp. 378-386, 1992.
[23] K. Nyberg. On the construction of highly nonlinear permutations. Proceed-
ings of EUROCRYPT 1992, Lecture Notes in Computer Science 658, pp.
92-98, 1993.
[24] A. Pott, E. Pasalic, A. Muratović-Ribić and S. Bajrić. On the Maximum
Number of Bent Components of Vectorial Functions. IEEE Transactions
on Information Theory 64(1), pp. 403-411, 2018.

30