06.04.2020  Ausgabe 5/2020 Open Access
On the EAclasses of known APN functions in small dimensions
 Zeitschrift:
 Cryptography and Communications > Ausgabe 5/2020
Wichtige Hinweise
This article is part of the Topical Collection: Boolean Functions and Their Applications IV
Guest Editors: Lilya Budaghyan and Tor Helleseth
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Symmetric cryptographic primitives and in particular block ciphers use substitution boxes (in brief, Sboxes) to bring “confusion” into the systems. Such confusion is necessary to prevent known attacks.
Given
n and
m two positive integers, the functions from
\({\mathbb {F}}_{2^{n}}\) to
\({\mathbb {F}}_{2^{m}}\) are called vectorial Boolean functions. Such functions are used as Sboxes in the design of block ciphers.
Anzeige
Among the properties that these functions have to satisfy we have a low differential uniformity (see definitions in Section
2) to allow resistance to the differential attack [
2] and high nonlinearity to resist the linear attack [
18]. The lowest differential uniformity for a vectorial Boolean function is 2. Functions reaching such lower bound are called Almost Perfect Nonlinear (APN).
The APN property (in general the differential uniformity) is preserved by different forms of equivalences between (vectorial) Boolean functions, such as EAequivalence and CCZequivalence. Since EAequivalence is a particular case of CCZequivalence, it is possible to partition the space of all functions
\({\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{m}}\) into CCZequivalence classes and then partition each CCZequivalence class into EAequivalence classes. For brevity, we will refer to these as “EAclass” and “CCZclass”. It was shown by Budaghyan et al. [
3] that for quadratic APN functions CCZequivalence is more general than EAequivalence together with taking inverses of permutations. In [
7] the authors investigate further the relation between CCZequivalence and EAequivalence with inverse transformation. While, in [
9] the authors give a characterization of CCZequivalence in terms of twisting functions. Despite this, CCZequivalence is not yet fully well understood and, to the best of our knowledge, partitioning the CCZclass of a function into its EAclasses is an hard task.
Classification of APN functions is, as well, a hard open problem. Complete classification for APN functions over
\({\mathbb {F}}_{2^{n}}\) is known only for
n ≤ 5 [
4], and for
n = 6 the CCZclassification of APN functions with algebraic degree at most 3 is known [
15]. For
n ≤ 5, in [
4], the authors give a classification of the APN functions up to EAequivalence and CCZequivalence. For the case of
n = 6, the classification of the known APN functions is given only up to CCZequivalence. The classification up to EAequivalence is not known.
In this work, we use the procedure introduced in [
7] for investigating the EAclasses contained in a CCZclass of a given function. In order to do that, in Section
3 we give some propositions that can be used to improve the the procedure given in [
7] and filter some of the results obtained from this procedure. We also obtain that the number of EAclasses contained in the CCZclass of a function
F is upper bounded by the number of simplex codes contained in a linear code associated to
F.
Anzeige
In Section
4, we discuss relations between the different equivalence concepts for vectorial Boolean functions and code equivalence. We also introduce a new linear code that can be defined for the case of bijective maps that can be used to verify affine equivalence between two permutations, see Theorem 6.
For the case
n = 6, in Section
5, we are able to give all the EAclasses of the known APN functions. We also studied further the case of the only APN permutation in even dimension [
6]. For such a function we give the representatives of the EAclasses which contain a permutation and we also give the representatives of the affine classes (containing a permutation).
In Section
6, we extend our study also to dimension 7, 8 and 9 (for this last case we focus only on nonGold APN power functions). In these dimensions checking EAequivalence, which is based on some code equivalence, requires an amount of computing which is huge, but we are able to give an upper bound on the number of EAclasses. Moreover, for the case of nonGold APN power functions we can determine the exact number of the EAclasses.
2 Preliminaries
Let
n ≥ 2, we denote by
\({\mathbb {F}}_{2^{n}}\) the finite field with 2
^{n} elements, by
\({\mathbb {F}}_{2^{n}}^{\star }\) its multiplicative group and by
\({\mathbb {F}}_{2^{n}}[x]\) the polynomial ring defined over
\({\mathbb {F}}_{2^{n}}\). Any function
\(F:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\) can be represented as a univariate polynomial of degree at most 2
^{n} − 1 in
\({\mathbb {F}}_{2^{n}}[x]\), that is
For any
i, 0 ≤
i ≤ 2
^{n} − 1, the
2weight of
i is the (Hamming) weight of its binary representation. The algebraic degree of a function
F is equal to the maximum 2weight of the exponent
i such that
c
_{i}≠ 0. Functions of algebraic degree 1 are called
affine and of degree 2
quadratic. Linear functions are affine functions without the constant term and they can be represented as
\(L(x)={\sum }_{i=0}^{n1} c_{i} x^{2^{i}}\). We denote the
trace function by
$$ F(x)=\sum\limits_{i=0}^{2^{n}1} c_{i} x^{i}, \quad c_{i}\in {\mathbb{F}}_{2^{n}}. $$
$$ Tr(x) = x + x^{2} + {\dots} + x^{2^{n1}}. $$
Let
\(\lambda \in {\mathbb {F}}_{2^{n}}^{\star }\) and
F be a function from
\({\mathbb {F}}_{2^{n}}\) to itself, the
λcomponent of
F is the Boolean function
\(F_{\lambda }:{\mathbb {F}}_{2^{n}}\to \mathbb {F}_{2}\) with
F
_{λ}(
x) =
T
r(
λ
F(
x)).
For any function
\(F:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\) we denote the
Walsh transform in
\(a,b\in {\mathbb {F}}_{2^{n}}\) by
For any Boolean function
\(f:{\mathbb {F}}_{2^{n}}\to \mathbb {F}_{2}\) the Walsh transform in
\(a\in {\mathbb {F}}_{2^{n}}\) is given by
$$ \mathcal{W}_{F}(a,b)=\sum\limits_{x\in {\mathbb{F}}_{2^{n}}}(1)^{Tr(ax+bF(x))}. $$
$$ \mathcal{W}_{f}(a)=\sum\limits_{x\in {\mathbb{F}}_{2^{n}}}(1)^{Tr(ax)+f(x)}. $$
The
Walsh spectrum of a function
F is the set of all possible values of the Walsh transform. The Walsh spectrum of a (vectorial) Boolean function
F is strictly related to the notion of nonlinearity of
F, denoted by
\({\mathcal{N}}{\mathcal{L}}(F)\), indeed we have
$$ \mathcal{N}\mathcal{L} (F)=2^{n1}\frac{ 1}{2} \max_{a\in{\mathbb{F}}_{2^{n}},b\in{\mathbb{F}}_{2^{n}}^{\star}}\mathcal{W}_{F}(a,b). $$
If
\({\mathcal{W}}_{f}(0)=0\) then the Boolean function is called balanced. For any function
\(F:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\) it is well know that
F is a bijection if and only if all its component functions are balanced.
The concept of differential uniformity of a function
F is related to the number of solutions of the equation
F(
x +
a) +
F(
x) =
b for
\(a\in {\mathbb {F}}_{2^{n}}^{\star }\) and
\(b\in {\mathbb {F}}_{2^{n}}\).
Definition 1
For a function
F from
\({\mathbb {F}}_{2^{n}}\) to itself, and any
\(a\in {\mathbb {F}}_{2^{n}}^{\star }\) and
\(b\in {\mathbb {F}}_{2^{n}}\), we denote by
δ
_{F}(
a,
b) the number of solutions of the equation
F(
x +
a) +
F(
x) =
b. The maximum value
δ among the
δ
_{F}(
a,
b)’s is called the differential uniformity of
F, and
F is said to be differentially
δuniform. A function
F is called almost perfect nonlinear (APN) if
δ = 2.
There are several equivalence relations of functions for which the differential uniformity (and thus the APN property) is preserved. Two functions F and
\(F^{\prime }\) from
\({\mathbb {F}}_{2^{n}}\) to itself are called:

affine equivalent if \(F^{\prime } = A_{1} \circ F \circ A_{2}\) where the mappings \(A_{1},A_{2}:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\) are affine permutations;

extended affine equivalent (EAequivalent) if \(F^{\prime } =F^{\prime \prime } + A\), where the mappings \(A:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\) is affine and \(F^{\prime \prime }\) is affine equivalent to F;

CarletCharpinZinoviev equivalent (CCZequivalent) if for some affine permutation \({\mathcal{L}}\) of \({\mathbb {F}}_{2^{n}}\times {\mathbb {F}}_{2^{n}}\) the image of the graph of F is the graph of \(F^{\prime }\), that is, \({\mathcal{L}}(G_{F}) = G_{F^{\prime }}\), where \(G_{F} = \{(x,F(x)) : x \in {\mathbb {F}}_{2^{n}}\}\) and \(G_{F^{\prime }} = \{(x,F^{\prime }(x)) : x \in {\mathbb {F}}_{2^{n}}\}\).
Obviously, the affine equivalence is included in EAequivalence, and it is also well known that EAequivalence is a particular case of CCZequivalence and every permutation is CCZequivalent to its inverse [
10].
Recently, Yoshiara [
20] and Dempwolff [
12] have shown, independently, that two power APN functions are CCZequivalent if and only if they are EAequivalent or one is EAequivalent to the inverse of the second one. Moreover, for the case of quadratic APN functions, CCZequivalence coincides with EAequivalence [
19].
3 Properties and remarks on the CCZequivalence
In this section we will recall the procedure given in [
7] and give some remarks and properties regarding CCZequivalence that will be useful in the investigation of the EAclasses contained in a CCZclass.
Since we are interested in the EAclasses, without loss of generality, we assume that the affine permutation in the definition of CCZequivalence is linear. Indeed, using affine permutations instead of linear one we simply obtain a shift by a constant in the input and output of the resulting function (see for instance [
7]).
Lemma 1 (Lemma 3.1 in
7)
Let
\(L_{1}, L_{2}:({\mathbb {F}}_{2^{n}})^{2}\to {\mathbb {F}}_{2^{n}}\) be linear maps and
\(a, b\in {\mathbb {F}}_{2^{n}}\), such that
\({\mathcal{L}}(x,y)=(L_{1}(x,y)+a,L_{2}(x,y)+b)\) is a permutation. Let
F and
\(F^{\prime }\) be CCZequivalent functions such that
\({\mathcal{L}}\) maps the graph of
F to the graph of
\(F^{\prime }\). Then the linear part
\({\mathcal{L}}^{\prime }\) of
\({\mathcal{L}}\) maps the graph of
F to the graph of
\(F^{\prime \prime }(x)=F^{\prime }(x+a)+b\).
A linear map
\({\mathcal{L}}\) defined over
\(({\mathbb {F}}_{2^{n}})^{2}\) can be described as a formal matrix
where
A
_{i} are linear maps over
\({\mathbb {F}}_{2^{n}}\) for 1 ≤
i ≤ 4, and
In particular,
and
$$ \mathcal{L}=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right] $$
$$ \mathcal{L}(x,y)=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right]\cdot\left[\begin{array}{c} x\\ y \end{array}\right]= (A_{1}(x)+A_{2}(y),A_{3}(x)+A_{4}(y)). $$
$$ F_{1}(x) = L_{1}(x,F(x))=A_{1}(x)+A_{2}\circ F(x) $$
(1)
$$ F_{2}(x) = L_{2}(x,F(x))=A_{3}(x)+A_{4}\circ F(x). $$
(2)
From the definition of CCZequivalence we have that a linear permutation
\({\mathcal{L}}\) is
admissible for producing a CCZequivalent function from
F if and only if
F
_{1}(
x) is a permutation. In terms of Walsh coefficients we have the following observation.
The function
F
_{1} in (
1) is a permutation if and only if all its component are balanced, that is
Denoting by
L
^{∗} the adjoint operator of a linear map
L (i.e.
T
r(
y
L(
x)) =
T
r(
x
L
^{∗}(
y)) for all
\(x,y\in {\mathbb {F}}_{2^{n}}\)), we have
$$ \mathcal{W}_{F_{1}}(0,\lambda)= \sum\limits_{x\in {\mathbb{F}}_{2^{n}}} (1)^{\text{Tr}(\lambda A_{1}(x)+\lambda A_{2}\circ F(x))}=0, \quad \text{ for all }\lambda\in{\mathbb{F}}_{2^{n}}^{\star}. $$
$$ \mathcal{W}_{F_{1}}(0,\lambda)= \sum\limits_{x\in {\mathbb{F}}_{2^{n}}} (1)^{\text{Tr}(A_{1}^{*}(\lambda)x+A_{2}^{*}(\lambda) F(x))}=\mathcal{W}_{F}(A_{1}^{*}(\lambda),A_{2}^{*}(\lambda))=\mathcal{W}_{F_{A_{2}^{*}(\lambda)}}(A_{1}^{*}(\lambda))=0. $$
(3)
In [
7], the authors introduce a procedure that permits to investigate the relation between CCZequivalence and EAequivalence together with the inverse transformation (when applicable). Using this procedure it is possible, at least in small dimensions, to investigate the EAclasses contained in the CCZclass of a given function.
The procedure given in [
7] is useful for constructing linear permutations
mapping the graph of
F onto the graph of another function
\(F^{\prime }\). In particular, the procedure constructs the linear functions
A
_{1} and
A
_{2} defined over
\({\mathbb {F}}_{2^{n}}\) so that
F
_{1}(
x) =
L
_{1}(
x,
F(
x)) =
A
_{1}(
x) +
A
_{2} ∘
F(
x) is a permutation. Indeed, if we are able to construct
L
_{1} with such a property, then it is always possible to determine
L
_{2} in order to have
\({\mathcal{L}}\) a linear permutation.
$$ \mathcal{L}=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right] $$
We are focusing on the EAclasses that are contained in the CCZclass of some given function
F. In the following, we will show some properties that permit to determine whether from two admissible permutation
\({\mathcal{L}}\) and
\({\mathcal{L}}^{\prime }\) we can obtain EAequivalent functions.
Remark 1 (Remark 2 in
3)
For a function
\(F:{\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{n}}\), if
\({\mathcal{L}}=(L_{1},L_{2})\) and
\({\mathcal{L}}^{\prime }=(L_{1},L_{2}^{\prime })\) are permutations such that the function
L
_{1}(
x,
F(
x)) is a permutation, then the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime }(G_{F})\) are EAequivalent.
This means that for all possible
L
_{1}, for covering the EAclasses of a given function
F, we need to construct a single
L
_{2}.
Remark 1 can be easily extended with the following proposition.
Proposition 1
Let
F be a function over
\({\mathbb {F}}_{2^{n}}\) and let
be two linear permutations over
\(({\mathbb {F}}_{2^{n}})^{2}\) such that
F
_{1}(
x) =
L
_{1}(
x,
F(
x)) =
A
_{1}(
x) +
A
_{2} ∘
F(
x) and
\(F_{1}^{\prime }(x) = L_{1}^{\prime }(x,F(x))=A^{\prime }_{1}(x)+A^{\prime }_{2}\circ F(x)\) are permutations. If
\(L_{1}^{\prime }(x,y)=L\circ L_{1}(x,y)\) for some linear permutation
L, then the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime }(G_{F})\) are EAequivalent.
$$ \mathcal{L}=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right], \quad\mathcal{L}^{\prime}=\left[\begin{array}{cc} A_{1}^{\prime}&A_{2}^{\prime}\\ A_{3}^{\prime}&A_{4}^{\prime} \end{array}\right] $$
Proof
Let
L
_{2}(
x,
y) =
A
_{3}(
x) +
A
_{4}(
y). Since
\(L_{1}^{\prime }(x,y)=L\circ L_{1}(x,y)\) then also
\({\mathcal{L}}^{\prime \prime }=(L_{1}^{\prime },L_{2})\) is a linear permutation and from Remark 1 we have that the functions defined by the graphs
\({\mathcal{L}}^{\prime }(G_{F})\) and
\({\mathcal{L}}^{\prime \prime }(G_{F})\) are EAequivalent.
Now,
where
I is the identity map, which implies that the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime \prime }(G_{F})\) are affine equivalent. □
$$ \mathcal{L}^{\prime\prime}=\left[\begin{array}{cc} L&0\\ 0&I \end{array}\right]\cdot \mathcal{L}, $$
We will show, now the procedure introduced in [
7]. From now on, we consider a fixed basis {
β
_{1},...,
β
_{n}} of
\({\mathbb {F}}_{2^{n}}\) as vector space over
\(\mathbb {F}_{2}\).
For any
\(\lambda \in {\mathbb {F}}_{2^{n}}\) we define the set
Then we can define the following set
Note that if
L
_{1}(
x,
y) is such that
F
_{1}(
x) =
L
_{1}(
x,
F(
x)) =
A
_{1}(
x) +
A
_{2} ∘
F(
x) is a permutation then
\(\text {Im}(A_{2}^{*})\subseteq S_{F}\). So, any subspace
U in
S
_{F} could be a possible candidate for
\(\text {Im}(A_{2}^{*})\).
$$ \mathcal{Z}\mathcal{W}(\lambda)=\{a \in {\mathbb{F}}_{2^{n}} : \mathcal{W}_{F_{\lambda}}(a)=0\}. $$
$$ S_{F}=\{\lambda\in {\mathbb{F}}_{2^{n}}^{\star} : \mathcal{Z}\mathcal{W}(\lambda)\ne \emptyset\}\cup \{0\}. $$
(4)
Along this section we will denote by
\(\text {Span}(v_{1},\dots ,v_{m})\) the vector (sub)space over
\({\mathbb {F}}_{2}\) generated by the elements
\(v_{1},\dots ,v_{m} \in {\mathbb {F}}_{2^{n}}\).
Let
\(U\subseteq S_{F}\) be a subspace of dimension
k. Let {
u
_{1},...,
u
_{k}} be a fixed basis of
U. Let
A
_{2} be such that
\(A_{2}^{*}(\beta _{i})=u_{i}\) if 1 ≤
i ≤
k and
\(A_{2}^{*}(\beta _{i})=0\) if
k + 1 ≤
i ≤
n.
For any
u ∈
U ∖{0} we consider the set
\(\mathcal {Z}\mathcal {W}(u)\), as defined before. To construct
A
_{1} we need to determine the images, with the adjoint operator
\(A_{1}^{*}\), of the vectors
β
_{i}’s. In order to do that, we need to select any possible
ktuple
\(a_{1}\in \mathcal {Z}\mathcal {W}(u_{1}),...,a_{k}\in \mathcal {Z}\mathcal {W}(u_{k})\) such that
These
a
_{1},...,
a
_{k} will be the images by
\(A_{1}^{*}\) of
β
_{1},...,
β
_{k}, respectively.

(P1) \({\sum }_{i=1}^{k}\lambda _{i}a_{i}\in \mathcal {Z}\mathcal {W}({\sum }_{i=1}^{k} \lambda _{i}u_{i})\text { for any }\lambda _{1},...,\lambda _{k}\in \mathbb {F}_{2}\), not all zero.
After that, for any of these
ktuples, we need to determine all possible (
n −
k)tuples of elements
a
_{k+ 1},...,
a
_{n} satisfying:

(P2) a _{k+ 1},..., a _{n} are linearly independent;

(P3) for any a ∈Span( a _{k+ 1},..., a _{n})∖{0}, \(a+{\sum }_{i=1}^{k} \lambda _{i}a_{i}\in \mathcal {Z}\mathcal {W}({\sum }_{i=1}^{k} \lambda _{i}u_{i})\), for any \(\lambda _{1},\dots ,\lambda _{k}\in \mathbb {F}_{2}\).
Remark 2
Condition
(P3) is equivalent to have
where
\(a+\mathcal {Z}\mathcal {W}(u)=\{a+v : v\in \mathcal {Z}\mathcal {W}(u)\}\).
$$ \text{Span}(a_{k+1},...,a_{n})\subseteq \bigcap_{\lambda_{i}\in\mathbb{F}_{2}}\sum\limits_{i=1}^{k} \lambda_{i}a_{i}+\mathcal{Z}\mathcal{W}\left( \sum\limits_{i=1}^{k} \lambda_{i}u_{i}\right), $$
In the following we will give some observations in order to see how it is possible from Procedure 2 to obtain the EAclasses contained in the CCZclass of a given function.
Let
\(\{u_{1},\dots ,u_{k}\}\) be any fixed basis of
U (where
k is the dimension of
U), we can suppose that
\(A_{2}^{*}(\beta _{i})=u_{i}\) for
i = 1,...,
k and
\({\ker }(A_{2}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})\).
Indeed, suppose
\(A_{2}^{*}\) is such that
\(A_{2}^{*}(w_{i})=u_{i}\) for
i = 1,...,
k and
\(\ker (A_{2}^{*})=\text {Span}(w_{k+1},...,w_{n})\) for some
w
_{1},...,
w
_{n} linearly independent. Then, we can consider the linear permutation
L such that
L
^{∗}(
β
_{i}) =
w
_{i} for all
i. Now, if
F
_{1}(
x) =
A
_{1}(
x) +
A
_{2}(
F(
x)) is a permutation, we can consider
\(F_{1}^{\prime }={L}\circ F_{1}\), which is again a permutation, and
\({A_{2}^{\prime }}^{*}=({L}\circ A_{2})^{*}\) is s.t.
\({A_{2}^{\prime }}^{*}(\beta _{i})=u_{i}\) for
i = 1,...,
k and
\({\ker }({A_{2}^{\prime }}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})\).
From the previous observation we have that if
L
_{1} is such that
\(\text {Im}(A_{2}^{*})=U\), then from the procedure applied to the subspace
U, with some fixed basis, we obtain at least one function
\({L}_{1}^{\prime }\) such that
\(L_{1}=L\circ L_{1}^{\prime }\) for some linear permutation
L. Thus, from Proposition 1 we obtain the same EAclass of
L
_{1} from
\(L_{1}^{\prime }\).
Observation 4
From the procedure we can see that in (P3) we need to check the subspaces of dimension
n −
k contained in
\(\bigcap _{\lambda _{i}\in \mathbb {F}_{2}}{\sum }_{i=1}^{k} \lambda _{i}a_{i}+\mathcal {Z}\mathcal {W}\left ({\sum }_{i=1}^{k} \lambda _{i}u_{i}\right )\). If we have
\(W\subseteq \bigcap _{\lambda _{i}\in \mathbb {F}_{2}}{\sum }_{i=1}^{k} \lambda _{i}a_{i}+\mathcal {Z}\mathcal {W}\left ({\sum }_{i=1}^{k} \lambda _{i}u_{i}\right )\), of dimension
n −
k, then we can consider only one basis of
W for constructing the elements
a
_{k+ 1},...,
a
_{n} in Procedure 2. Indeed, let {
a
_{k+ 1},...,
a
_{n}} and
\(\{a^{\prime }_{k+1},...,a^{\prime }_{n}\}\) be two basis of
W. Let
A
_{1} and
\(A^{\prime }_{1}\) constructed from the procedure applied to a fixed space
U (and so also
A
_{2} is fixed), such that
\(A_{1}^{*}(\beta _{i})=A_{1}^{\prime *}(\beta _{i})=a_{i}\) for 1 ≤
i ≤
k, and
\(A_{1}^{*}(\beta _{j})=a_{j}\),
\(A_{1}^{\prime *}(\beta _{j})=a^{\prime }_{j}\) for
k + 1 ≤
j ≤
n.
Let
V = Span(
β
_{k+ 1},...,
β
_{n}), the restriction of
\(A_{1}^{*}\) and
\(A_{1}^{\prime *}\) over
V,
\(A_{1}^{*}_{V}\) and
\(A_{1}^{\prime *}_{V}\), are bijections from
V to
W and thus
\((A_{1}^{*}_{V})^{1}\),
\((A_{1}^{\prime *}_{V})^{1}\) are well defined. Let
L be a linear permutation such that
L
^{∗}(
β
_{i}) =
β
_{i} for 1 ≤
i ≤
k and
\({L}^{*}(\beta _{j})=(A_{1}^{*}_{V})^{1}(a_{j}^{\prime })\) for
k + 1 ≤
j ≤
n (note that
\((A_{1}^{*}_{V})^{1}(a_{j}^{\prime })\in V\) and they form a basis for
V, so
L is a permutation). Now it is easy to check that
\(A^{\prime }_{1}(x)=L\circ A_{1}(x)\) and that
A
_{2}(
y) =
L ∘
A
_{2}(
y) implying that
\(A^{\prime }_{1}(x)+A_{2}(y)=L(A_{1}(x)+A_{2}(y))\) and from Proposition 1 we will obtain the same EAclass from these functions.
From the same function
A
_{2} we could obtain several
L
_{1}’s. We will show how it is possible to filter some of the
L
_{1} obtained from the procedure.
Proposition 2
Let
F be a function defined over
\({\mathbb {F}}_{2^{n}}\) with no linear monomials. Let
\({\mathcal{L}}=(L_{1},L_{2})\) and
\({\mathcal{L}}^{\prime }=({L}_{1}^{\prime },L^{\prime }_{2})\) be two linear permutations over
\(({\mathbb {F}}_{2^{n}})^{2}\) with
L
_{1}(
x,
y) =
A
_{1}(
x) +
A
_{2}(
y) and
\({L}_{1}^{\prime }(x,y)=A^{\prime }_{1}(x)+A_{2}(y)\). Suppose
F
_{1}(
x) =
L
_{1}(
x,
F(
x)) and
\({F}_{1}^{\prime }(x)={L}_{1}^{\prime }(x,F(x))\) are permutations and the linear codes
\({\mathcal{C}}_{F_{1}}\) and
\({\mathcal{C}}_{{F}_{1}^{\prime }}\) are equal, where the code
\({\mathcal{C}}_{F}\) is generated by the matrix having as columns the vectors
Then, if Span(Im(
A
_{2} ∘
F)) = Im(
A
_{2}) the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime }(G_{F})\) are EAequivalent.
$$ \left( \begin{array}{c} F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
Proof
Since
\({\mathcal{C}}_{F_{1}}={\mathcal{C}}_{{F}_{1}^{\prime }}\) then there exists a linear permutations over
\({\mathbb {F}}_{2^{n}}\) such that
\(F_{1}^{\prime }(x)=L\circ F_{1}(x)\). In particular, since
F has no linear monomials then
L ∘
A
_{2} ∘
F =
A
_{2} ∘
F and
\(L\circ A_{1}=A_{1}^{\prime }\). Moreover, we have that Span(Im(
A
_{2} ∘
F)) = Im(
A
_{2}). This means that there exist
x
_{1},...,
x
_{k} such that
F(
x
_{1}),...,
F(
x
_{k}) are linearly independent and
A
_{2} ∘
F(
x
_{1}),...,
A
_{2} ∘
F(
x
_{k}) form a basis for Im(
A
_{2}). Then,
\(\text {Span}(\{F(x_{1}),...,F(x_{k})\})\oplus \ker (A_{2})={\mathbb {F}}_{2^{n}}\) and thus
L ∘
A
_{2}(
y) =
A
_{2}(
y) for all
\(y\in {\mathbb {F}}_{2^{n}}\). From this, we can conclude that
\(L_{1}^{\prime }=L\circ L_{1}\) and from Proposition 1 it follows that the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime }(G_{F})\) are EAequivalent. □
For the case of functions
F having nonlinearity different from zero we have that
\({\mathcal{C}}_{F_{1}}={\mathcal{C}}_{{F}_{1}^{\prime }}\) is sufficient to guarantee EAequivalence.
Proposition 3
Let
F be a function defined over
\({\mathbb {F}}_{2^{n}}\) with
\({\mathcal{N}}{\mathcal{L}}(F)\ne 0\) (
F(0) = 0). Let
\({\mathcal{L}}=(L_{1},L_{2})\) and
\({\mathcal{L}}^{\prime }=({L}_{1}^{\prime },L^{\prime }_{2})\) be two linear permutations over
\(({\mathbb {F}}_{2^{n}})^{2}\) with
L
_{1}(
x,
y) =
A
_{1}(
x) +
A
_{2}(
y) and
\({L}_{1}^{\prime }(x,y)=A^{\prime }_{1}(x)+A_{2}(y)\). Suppose
F
_{1}(
x) =
L
_{1}(
x,
F(
x)) and
\({F}_{1}^{\prime }(x)={L}_{1}^{\prime }(x,F(x))\) are permutations. If
\({\mathcal{C}}_{F_{1}}={\mathcal{C}}_{{F}_{1}^{\prime }}\), where the code
\({\mathcal{C}}_{F}\) is defined as in Proposition 2, then the functions defined by the graphs
\({\mathcal{L}}(G_{F})\) and
\({\mathcal{L}}^{\prime }(G_{F})\) are EAequivalent.
Proof
Consider the matrix of size 2
n × 2
^{n} with columns the vectors
Since
\({\mathcal{N}}{\mathcal{L}}(F)\ne 0\) then the rows of this matrix are linear independent. Now, since
F
_{1} is a permutation, the rows of
are linear independent and for any row there exists a unique way of combining the rows of
M to get it. Thus, there exist a unique linear function
L
_{1}(
x,
y) such that
Since
\({\mathcal{C}}_{F_{1}}={\mathcal{C}}_{{F}_{1}^{\prime }}\) we have that there exists a linear permutation
L such that
and then
From the unicity of
L
_{1} and
\(L_{1}^{\prime }\) we obtain that
\(L_{1}^{\prime }=L\circ L_{1}\). □
$$ M=\left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
$$ \left( \begin{array}{c} F_{1}(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}, $$
$$ \left( \begin{array}{c} F_{1}(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}= \left( \begin{array}{c} L_{1}(x,F(x)) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
$$ \left( \begin{array}{c} L\circ F_{1}(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}=\left( \begin{array}{c} F_{1}^{\prime}(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}, $$
$$ \left( \begin{array}{c} L\circ L_{1}(x,F(x)) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}=\left( \begin{array}{c} L_{1}^{\prime}(x,F(x)) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
Remark 3
For the case of APN functions we have that the
\({\mathcal{N}}{\mathcal{L}}(F)\ne 0\) and so we can use this last proposition for filtering the functions obtained from Procedure 2.
Recalling that a simplex code (defined over
\(\mathbb {F}_{2}\)) is a linear code of length 2
^{n} − 1 dimension
n and all non zero codewords of hamming weight 2
^{n− 1}, we have the following upper bound on the number of EAclasses contained in the CCZclass of a function
F.
Corollary 1
Let
F be a function defined over
\({\mathbb {F}}_{2^{n}}\) with
\({\mathcal{N}}{\mathcal{L}}(F)\ne 0\) (
F(0) = 0). Let
\({\mathcal{C}}(F)\) be the code generated by
Then, the number of EAclasses contained in the CCZclass of
F is upper bounded by the number of the simplex codes contained in
\({\mathcal{C}}(F)\).
$$ \left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}^{\star}}. $$
4 Equivalence relations and linear codes
The main cryptographic properties (e.g. the APN property, the nonlinearity, etc.) can be interpreted as conditions on some binary linear codes, as first shown in [
10].
Let
F be a vectorial Boolean function then we can define the following codes related to
F.

The code \({\mathcal{C}}_{1}(F)\) which is generated by$$ C_{1}(F):=\left( \begin{array}{c} 1\\ x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}, $$

The code \({\mathcal{C}}_{2}(F)\) which is generated by$$ C_{2}(F):=\left( \begin{array}{cc} 1&0\\ x&0\\ F(x)&y \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}},y\in{\mathbb{F}}_{2^{n}}^{\star}} $$

The code \({\mathcal{C}}_{3}(F)\) which is generated by$$ C_{3}(F):=\left( \begin{array}{ccc} 1&0& 0\\ x&0& z\\ F(x)&y&0 \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}, y,z\in{\mathbb{F}}_{2^{n}}^{\star}} $$
The equivalence between two functions
F and
G can be expressed in terms of linear codes. In particular, the code
\({\mathcal{C}}_{1}\) was introduced in [
5] for determining the CCZequivalence between two functions. The codes
\({\mathcal{C}}_{2}\) and
\({\mathcal{C}}_{3}\) were introduced in [
13] for the case of the EA and affineequivalence. We summarize the results of [
5] and [
13] in the following theorem.
Theorem 5
Let
F and
G be two vectorial Boolean functions. Then we have:

F is CCZequivalent to G iff \({\mathcal{C}}_{1}(F)\) and \({\mathcal{C}}_{1}(G)\) are equivalent ([ 5, Theorem 6.2]).

F is EAequivalent to G iff \({\mathcal{C}}_{2}(F)\) and \({\mathcal{C}}_{2}(G)\) are equivalent ([ 13, Theorem 10]).

If F is not a permutation, F is affineequivalent to G iff the codes \({\mathcal{C}}_{3}(F)\) and \({\mathcal{C}}_{3}(G)\) are equivalent. If F is a permutation, F is affineequivalent to G or G ^{− 1} iff the codes \({\mathcal{C}}_{3}(F)\) and \({\mathcal{C}}_{3}(G)\) are equivalent ([ 13, Theorem 11]).
From the previous theorem when
F and
G are permutations we cannot distinguish if they are affine equivalent to each other or one is equivalent to the inverse of the other.
A necessary and sufficient condition for affine equivalence between permutations is the following.
Theorem 6
Let
F and
G be two permutations over
\({\mathbb {F}}_{2^{n}}\), with
n ≥ 3.
F is affineequivalent to
G if and only if the codes
\({\mathcal{C}}_{4}(F)\) and
\({\mathcal{C}}_{4}(G+b)\) are equivalent for some
\(b \in {\mathbb {F}}_{2^{n}}\), where
\({\mathcal{C}}_{4}(F)\) is generated by
of size (2
n + 1) × (2
^{n+ 1} + 2
^{n} − 1).
$$ C_{4}(F):=\left( \begin{array}{ccc} 1&0& 1\\ x&0& z\\ F(x)&y&0 \end{array}\right)_{x,z\in{\mathbb{F}}_{2^{n}}, y\in{\mathbb{F}}_{2^{n}}^{\star}} $$
Proof
Suppose that
F is affine equivalent to
G. Then,
B(
F(
A
x +
a)) +
b =
G(
x) for some
A,
B linear permutations and
\(a,b\in {\mathbb {F}}_{2^{n}}\). Suppose that
b = 0, otherwise we can consider the function
\(G^{\prime }=G+b\).
Considering
L
_{1} =
A
^{− 1},
L
_{2} =
B linear permutations and
\(a^{\prime }=A^{1}a\) we have
applying a permutation on the columns, the last matrix is
C
_{4}(
G).
$$ M\cdot C_{4}(F)=\left( \begin{array}{ccc} 1&0& 0\\ a^{\prime}&L_{1}& 0\\ 0&0&L_{2} \end{array}\right)\times\left( \begin{array}{ccc} 1&0& 1\\ x&0& z\\ F(x)&y&0 \end{array}\right)=\left( \begin{array}{ccc} 1&0& 1\\ L_{1}(x)+a^{\prime}&0& L_{1}(z)+a^{\prime}\\ L_{2}(F(x))&L_{2}(y)&0 \end{array}\right), $$
Vice versa, suppose that the code
\({\mathcal{C}}_{4}(F)\) is equivalent to
\({\mathcal{C}}_{4}(G^{\prime })\), for some
\(G^{\prime }=G+b\). We can suppose that
\(G^{\prime }=G\) otherwise we will obtain the affine equivalence to
\(G^{\prime }\) which is equivalent to
G.
Then, there exists a matrix
and a permutation matrix
P such that
M ⋅
C
_{4}(
F) =
C
_{4}(
G) ⋅
P. Thus, permuting the columns of
M ⋅
C
_{4}(
F) we would be able to obtain the matrix
C
_{4}(
G). Now,
$$ M=\left( \begin{array}{ccc} c&{\mathbf d}& {\mathbf e}\\ a&L_{1}& L_{2}\\ b&L_{3}&L_{4} \end{array}\right) $$
×
In the following we will refer to the different nine parts of the matrix as the left upper (LU) part, left center (LC) part, left bottom (LB) part, middle upper (MU) part, middle center (MC) part, middle bottom (MB) part, right upper (RU) part, right center (RC) part and right bottom (RB) part.
Now, we want to understand how we can permute the columns of the matrix above so that we can obtain
C
_{4}(
G). From that, we will be able to determine the structure of the matrix
M.
First of all, note that the first row of the matrix must have the same weight as the first row of
C
_{4}(
G), that is 2
^{n+ 1}. Suppose
d,
e≠ 0. Then
c +
d ⋅
z and
e ⋅
y have weight 2
^{n− 1}, so
c +
d ⋅
x +
e ⋅
F(
x) needs to be of weight 2
^{n}. Let
S = {
y :
e ⋅
y = 0}, which is a subspace of dimension
n − 1. A column relative to any
y ∈
S needs to have
L
_{2}(
y) = 0, because for obtaining
C
_{4}(
G) we cannot move this column in the left or right part. Thus, rank(
L
_{2}) ≤ 2.
Moreover, all the columns of the
y’s not in
S need to be moved in the left or right part since the first row in the middle part has to be equal to zero. For any column relative to some
y∉
S, we have that
L
_{2}(
y) =
r for some fixed
r. But, in the LC and RC part we should obtain two times all the nonzero elements of
\({\mathbb {F}}_{2^{n}}\), which would be not possible.
Suppose
d = 0,
e≠ 0. As before, let
S = {
y :
e ⋅
y = 0}. Thus
L
_{2}(
y) = 0 if
y ∈
S and
L
_{2}(
y) =
r for some fixed
r if
y∉
S. Again, the columns of the
y’s not in
S need to be moved in the left or right part, and we cannot obtain all the nonzero elements of
\({\mathbb {F}}_{2^{n}}\) repeated two times in the center part.
Suppose that
d≠ 0,
e = 0 then we obtain only 2
^{n} 1’s on the first row, which is not possible.
Then,
c = 1 and
d =
e = 0 and
$$ M\cdot C_{4}(F)=\left( \begin{array}{ccc} 1&0& 1 \\ L_{1}(x)+L_{2}(F(x))+a&L_{2}(y)& L_{1}(z)+a\\ {L_{3}(x)+L_{4}(F(x))+b}&{L_{4}(y)}&{L_{3}(z)+b} \end{array}\right). $$
Now, we have that for obtaining
C
_{4}(
G) we cannot permute the columns related to the middle part, involving the variable
y, with the columns of the other parts. Thus
L
_{2} ≡ 0 and
Moreover, since in the MB part we should have all the nonzero elements of
\({\mathbb {F}}_{2^{n}}\), and in the LC and RC part all the elements of
\({\mathbb {F}}_{2^{n}}\), we have that
L
_{1} and
L
_{4} need to be permutations.
$$ M\cdot C_{4}(F)=\left( \begin{array}{ccc} 1&0& 1 \\ L_{1}(x)+a&0& L_{1}(z)+a\\ L_{3}(x)+L_{4}(F(x))+b&L_{4}(y)&L_{3}(z)+b \end{array}\right). $$
We need now to prove that
L
_{3}(
z) +
b is constantly equal to 0. First, note that if
L
_{3}(
z) +
b =
b≠ 0 for all
z, then in the RB part of
M ⋅
C
_{4}(
F) we would have all columns equals to
b. Since we want to permute the columns of
M ⋅
C
_{4}(
F) in order to obtain
C
_{4}(
G) (which has all zero columns on the RB part) this means that all the columns of the left part of
M ⋅
C
_{4}(
F) should be permuted with the columns of the right part, implying
L
_{3}(
x) +
L
_{4}(
F(
x)) +
b ≡ 0, which is not possible. Similarly if
L
_{3}(
z) +
b is a permutation.
Suppose, then, that
L
_{3}(
z) +
b is not null (and not constantly equal to
b) or a permutation, which implies
\(\ker (L_{3})\ne \{0\},{\mathbb {F}}_{2^{n}}\). Then, in order to obtain
C
_{4}(
G) we should permute at least all the columns of the right part that are nonzero in the RB part (that involving
L
_{3}(
z) +
b) with some columns of the left part of the matrix for which
L
_{3}(
x) +
L
_{4}(
F(
x)) +
b is zero.
Now, let
\(S=\{z : L_{3}(z)+b\ne 0\}={\mathbb {F}}_{2^{n}}\setminus \{z : L_{3}(z)+b= 0\}\). Denoting by
A(
x) =
L
_{3}(
x) +
b, since
\(\ker (L_{3})\ne \{0\},{\mathbb {F}}_{2^{n}}\) we have that for a given non zero element
c in Im(
A) there exist at least two elements
z
_{1},
z
_{2} ∈
S such that
A(
z
_{1}) =
A(
z
_{2}) =
c. Since for obtaining
C
_{4}(
G) we should permute (with the left part) all the columns of the right part related to the elements of
S, we would obtain in the LB part two columns with the same value. But since both
F and
G are permutations then we cannot have repeated column here. Then,
L
_{3}(
x) +
b needs to be constantly equal to 0.
So,
and thus
for some permutation matrix
P, that is,
\(L_{4}(F(L_{1}^{1}(x)+L_{1}^{1}(a))=G(x)\). □
$$ M\cdot C_{4}(F)=\left( \begin{array}{ccc} 1&0& 1 \\ L_{1}(x)+a&0& L_{1}(z)+a\\ L_{4}(F(x))&L_{4}(y)&0 \end{array}\right), $$
$$ \left( \begin{array}{c} 1\\ L_{1}(x)+a\\ L_{4}(F(x)) \end{array}\right)=\left( \begin{array}{c} 1\\ x\\ G(x) \end{array}\right)\cdot P, $$
These theorems on the relation between the equivalences defined for Boolean functions and the related codes are quite useful. For instance, the computer algebra package MAGMA implements a function for checking code equivalence, hence for small values of
n can be possible to distinguish the different types of equivalence. Note that for the case of the affineequivalence in [
1] it is given an algorithm for checking it. We do not compare the complexity of checking the affine equivalence with codes and the algorithm given in [
1]. However, the implementation with the code equivalence is very easy in MAGMA.
5 EAclasses in dimension 6
In this section we give the analysis carried out for the known APN functions in dimension 6. We used Procedure 2 for obtaining the admissible linear functions
L
_{1}. Then, comparing the codes relative to
L
_{1}(
x,
F(
x)) we used Proposition 3 for filtering the maps
L
_{1}. After that EAequivalence was tested using the linear code
\({\mathcal{C}}_{2}(F)\).
In dimension 6 there are 14 known APN functions (13 are quadratics) up to CCZequivalence and they are listed in Table
1. In Table
1 we give also the number of EAclasses contained in the CCZclass of each function, together with the degrees of the functions in the EAclasses. All the representatives of the EAclasses can be found in Appendix 1 of [
8].
Table 1
CCZinequivalent APN functions over
\(\mathbb {F}_{2^{6}}=\langle {\zeta }\rangle \)
N.

function

# EAclasses

Degrees


1

x
^{3}

3

{⋆2,3,4⋆}

2

x
^{3} +
ζ
^{11}
x
^{6} +
u
x
^{9}

3

{⋆ 2, 3, 4 ⋆}

3

ζ
x
^{5} +
x
^{9} +
ζ
^{4}
x
^{17} +
ζ
x
^{18} +
ζ
^{4}
x
^{20} +
ζ
x
^{24} +
ζ
^{4}
x
^{34} +
ζ
x
^{40}

19

{⋆ 2, 3̂̂15, 4̂̂3 ⋆}

4

ζ
^{7}
x
^{3} +
x
^{5} +
ζ
^{3}
x
^{9} +
ζ
^{4}
x
^{10} +
x
^{17} +
ζ
^{6}
x
^{18}

13

{⋆2, 3̂̂9, 4̂̂3 ⋆}

5

x
^{3} +
ζ
x
^{24} +
x
^{10}

13

{⋆2, 3̂̂5, 4̂̂7 ⋆}

6

x
^{3} +
ζ
^{17}(
x
^{17} +
x
^{18} +
x
^{20} +
x
^{24})

91

{⋆2, 3̂̂66, 4̂̂24 ⋆}

7

x
^{3} +
ζ
^{11}
x
^{5} +
ζ
^{13}
x
^{9} +
x
^{17} +
ζ
^{11}
x
^{33} +
x
^{48}

19

{⋆2, 3̂̂15, 4̂̂3 ⋆}

8

ζ
^{25}
x
^{5} +
x
^{9} +
ζ
^{38}
x
^{12} +
ζ
^{25}
x
^{18} +
ζ
^{25}
x
^{36}

85

{⋆2, 3̂̂66, 4̂̂18 ⋆}

9

ζ
^{40}
x
^{5} +
ζ
^{10}
x
^{6} +
ζ
^{62}
x
^{20} +
ζ
^{35}
x
^{33} +
ζ
^{15}
x
^{34} +
ζ
^{29}
x
^{48}

91

{⋆2, 3̂̂63, 4̂̂27 ⋆}

10

ζ
^{34}
x
^{6} +
ζ
^{52}
x
^{9} +
ζ
^{48}
x
^{12} +
ζ
^{6}
x
^{20} +
ζ
^{9}
x
^{33} +
ζ
^{23}
x
^{34} +
ζ
^{25}
x
^{40}

91

{⋆2, 3̂̂66, 4̂̂24 ⋆}

11

x
^{9} +
ζ
^{4}(
x
^{10} +
x
^{18}) +
ζ
^{9}(
x
^{12} +
x
^{20} +
x
^{40})

86

{⋆2, 3̂̂69, 4̂̂16 ⋆}

12

ζ
^{52}
x
^{3} +
ζ
^{47}
x
^{5} +
ζ
x
^{6} +
ζ
^{9}
x
^{9} +
ζ
^{44}
x
^{12} +
ζ
^{47}
x
^{33} +
ζ
^{10}
x
^{34} +
ζ
^{33}
x
^{40}

92

{⋆2, 3̂̂69, 4̂̂22 ⋆}

13

ζ(
x
^{6} +
x
^{10} +
x
^{24} +
x
^{33}) +
x
^{9} +
ζ
^{4}
x
^{17}

85

{⋆2, 3̂̂66, 4̂̂18 ⋆}

x
^{3} +
ζ
^{17}(
x
^{17} +
x
^{18} +
x
^{20} +
x
^{24}) +
ζ
^{14}(Tr(
ζ
^{52}
x
^{3} +
ζ
^{6} ∗
x
^{5} +
ζ
^{19}
x
^{7} +
ζ
^{28}
x
^{1}1 +
ζ
^{2}
x
^{13}) +


14

(
ζ
^{2}
x)
^{9} + (
ζ
^{2}
x)
^{18} + (
ζ
^{2}
x)
^{36} +
x
^{21} +
x
^{42})

25

{⋆ 3̂̂10, 4̂̂15 ⋆}

5.1 Classification results for Dillon’s APN permutation
Further analysis was done for the case of the Kim function
x
^{3} +
ζ
x
^{24} +
x
^{10}. Indeed, this function is equivalent to a permutation [
6]. This is the only known example of APN function equivalent to a permutation in even dimension.
In this case we studied also the affine equivalence classes. The reason why we are interested in this classification is that some characteristics of the vectorial Boolean functions, interesting for designing block ciphers, such as to be a permutation, the boomerang uniformity [
11], the threshold implementation [
17], etc., are invariants with respect the affine equivalence but not with respect to EA and CCZequivalence.
Thus, classification of (bijective) vectorial Boolean functions up to affine equivalence is an important task.
Using the code equivalence we can see that in the CCZclass of the Dillon’s APN permutation we have 13 EAclasses with two of them containing a permutation, while the number of affine classes containing a permutation is 4.
Let
$$ \begin{array}{@{}rcl@{}} F_{1}(x)&=&\zeta^{57}x^{60}+ \zeta^{56}x^{58}+ \zeta^{43}x^{57}+ \zeta^{31}x^{56}+ \zeta^{29}x^{53}+ \zeta^{27}x^{52}+\zeta^{28}x^{51}+ \zeta^{35}x^{50}+ \zeta^{54}x^{49} +\\ && \zeta^{51}x^{48}+ \zeta x^{46}+ \zeta^{54}x^{44}+ \zeta^{50}x^{43}+ \zeta^{50}x^{42}+ \zeta^{32}x^{41}+ \zeta^{49}x^{40}+ \zeta^{36}x^{39}+ \zeta^{14}x^{38}+ \zeta^{16}x^{37}+\\ && \zeta^{15}x^{35}+ \zeta^{43}x^{34}+ \zeta^{23}x^{33}+ \zeta^{7}x^{32}+ \zeta^{7}x^{30}+\zeta^{57}x^{29}+ \zeta^{11}x^{26}+ \zeta^{49}x^{25}+\zeta^{36}x^{24}+ \zeta^{42}x^{23}+ \\ && \zeta^{40}x^{22}+ \zeta^{34}x^{21}+ \zeta^{9}x^{20}+ \zeta^{28}x^{19}+ \zeta^{4}x^{18}+ \zeta^{50}x^{17}+ \zeta^{58}x^{16}+ \zeta x^{15}+\zeta^{48}x^{14}+ \zeta^{33}x^{13}+\\ && \zeta^{31}x^{12}+ \zeta^{43}x^{11}+ \zeta^{14}x^{10}+ \zeta^{5}x^{9}+ \zeta^{45}x^{8}+ \zeta^{60}x^{7}+ \zeta^{31}x^{6}+ \zeta^{42}x^{5}+ \zeta^{10}x^{4}+ \zeta^{10}x^{3}+ \zeta^{48}x, \end{array} $$
$$ \begin{array}{@{}rcl@{}} F_{2}(x)&=&\zeta^{3}x^{60}+ \zeta^{33}x^{58}+ \zeta^{18}x^{57}+ \zeta^{8}x^{56}+ \zeta^{38}x^{53}+ \zeta^{28}x^{52}+ \zeta^{5}x^{51}+ \zeta^{37}x^{50}+ \zeta^{9}x^{49}+ \zeta^{45}x^{48}+ \\ && \zeta^{10}x^{46}+ \zeta^{54}x^{44}+ \zeta^{25}x^{43}+ \zeta^{50}x^{42}+ \zeta^{55}x^{41}+ \zeta^{30}x^{40}+ \zeta^{45}x^{39}+ \zeta^{41}x^{38}+ \zeta^{14}x^{37}+\zeta^{49}x^{36}+\\ && \zeta^{31}x^{35}+ x^{34}+ \zeta^{46}x^{33}+ \zeta^{20}x^{32}+ \zeta^{47}x^{30}+ \zeta^{32}x^{29}+\zeta^{57}x^{28}+ \zeta^{47}x^{26}+ \zeta^{44}x^{25}+ \zeta^{17}x^{24}+\\ && \zeta^{19}x^{23}+ \zeta^{61}x^{22}+ \zeta^{31}x^{21}+ \zeta^{31}x^{20}+ \zeta^{48}x^{19}+ \zeta^{58}x^{18}+ \zeta^{21}x^{17}+ x^{16}+ \zeta^{39}x^{15}+\zeta^{44}x^{14}+\\ && \zeta^{35}x^{13}+ \zeta^{21}x^{12}+ \zeta^{15}x^{11}+ \zeta^{54}x^{10}+ \zeta^{62}x^{9}+ \zeta^{42}x^{8}+ \zeta^{62}x^{7}+ \zeta^{14}x^{6}+ \zeta^{3}x^{5}+ \zeta^{29}x^{4}+ \\ && \zeta^{34}x^{3}+ \zeta^{5}x^{2}+ \zeta^{46}x, \end{array} $$
$$ \begin{array}{@{}rcl@{}} F_{3}(x)&=&\zeta^{61}x^{60}+ \zeta^{60}x^{58}+ \zeta^{49}x^{57}+ \zeta^{24}x^{56}+ \zeta^{21}x^{54}+ \zeta^{16}x^{53}+\zeta^{36}x^{52}+ \zeta^{35}x^{51}+ \zeta^{17}x^{50}+ \\ && \zeta^{28}x^{49}+ \zeta^{14}x^{48}+ \zeta^{62}x^{46}+ \zeta^{9}x^{45}+ \zeta^{21}x^{44}+ \zeta^{29}x^{43}+ \zeta^{22}x^{42}+ \zeta^{35}x^{41}+ \zeta^{41}x^{40}+ \\ && \zeta^{51}x^{39}+ \zeta^{46}x^{38}+ \zeta^{37}x^{37}+ \zeta^{7}x^{36}+ \zeta^{32}x^{35}+ \zeta^{45}x^{34}+ \zeta^{16}x^{33}+ \zeta^{55}x^{32}+ \zeta^{11}x^{30}+\\ && \zeta^{8}x^{29}+ \zeta^{29}x^{28}+ \zeta^{6}x^{27}+ \zeta^{58}x^{26}+ \zeta^{28}x^{24}+ \zeta^{15}x^{23}+ \zeta^{44}x^{22}+ \zeta^{35}x^{21}+ \zeta^{32}x^{20}+ \\ && \zeta^{53}x^{19}+ \zeta^{42}x^{18}+ \zeta^{50}x^{17}+ x^{16}+ \zeta^{12}x^{15}+ \zeta^{27}x^{14}+ \zeta^{30}x^{13 }+\zeta^{7}x^{12}+ \zeta^{52}x^{11}+ \\ && \zeta^{43}x^{10}+\zeta^{7}x^{9}+ \zeta^{17}x^{8}+ \zeta^{5}x^{7}+ \zeta^{17}x^{6}+ \zeta^{43}x^{5}+ \zeta^{13}x^{4}+ \zeta^{57}x^{3}+ \zeta^{35}x^{2}+ \zeta^{49}x. \end{array} $$
Then, the CCZclass can be represented by
F
_{1}, the EAclasses containing a permutation can be given by
F
_{1} and
\(F_{1}^{1}\), and the affineclasses (always with a permutation) are represented by
\(F_{1},F_{1}^{1},F_{2}\) and
F
_{3}. Note that with the code equivalence of the code
\({\mathcal{C}}_{3}(F)\) we would obtain only 3 functions since
F
_{1} is not affine equivalent to its inverse, while using
\({\mathcal{C}}_{4}(F)\) we can distinguish the two functions.
Remark 4
F
_{2} and
F
_{3} are affineequivalent to their inverses.
For all the APN permutations we have that the degree of their components are
{* 3^^7, 4^^56 *}
and the Walsh spectrum of the single components is given by the multiset
{*
{* 16, 8^^22, 0^^12, 8^^26, 16^^3 *}^^21,
{* 16^^2, 8^^20, 0^^12, 8^^28, 16^^2 *}^^21,
{* 16^^3, 8^^18, 0^^12, 8^^30, 16 *}^^7,
{* 16^^6, 0^^48, 16^^10 *}^^7,
{* 8^^24, 0^^12, 8^^24, 16^^4 *}^^7
*}
6 On the EAclasses of functions in dimension 7,8 and 9
For dimension 7 and 8 it is still possible to implement Procedure 2. Thus we can obtain at least one representative of each EAclass. However, checking EAequivalence with the code equivalence require a huge amount of computations. Corollary 1 gives us an upper bound on the number of EAclasses based on the simplex codes contained in
Using MAGMA we are able to provide the upper bound for all the known functions in
n = 7,8. Note that in dimension 7 and 8 we have a huge list of APN functions from [
21]. For space reason here we give the upper bound only for the functions listed in [
14].
$$ \left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
6.1 n = 7
In dimension 7, in [
14] the authors listed 19 APN functions in Table
2, in [
21] the authors found 471 new functions more. For the computer results on all these APN functions see Appendix 2 in [
8].
Table 2
CCZinequivalent APN functions over
\(\mathbb {F}_{2^{7}}\) given in [
14]
N.

function

# EAclasses ≤


1

x
^{3}

256

2

x
^{5}

256

3

x
^{9}

256

4

x
^{13}

2

5

x
^{57}

2

6

x
^{63}(
i
n
v
e
r
s
e)

2

7

x
^{3} + Tr(
x
^{9})

184

8

x
^{34} +
x
^{18} +
x
^{5}

184

9

x
^{20} +
x
^{6} +
x
^{3}

324

10

x
^{66} +
x
^{34} +
x
^{20} +
x
^{17} +
x
^{3}

184

11

x
^{34} +
x
^{33} +
x
^{17} +
x
^{3}

184

12

x
^{34} +
x
^{33} +
x
^{10} +
x
^{5} +
x
^{3}

296

13

x
^{66} +
x
^{18} +
x
^{9} +
x
^{3}

212

14

x
^{33} +
x
^{17} +
x
^{12} +
x
^{3}

240

15

x
^{66} +
x
^{34} +
x
^{20} +
x
^{3}

184

16

x
^{72} +
x
^{40} +
x
^{12} +
x
^{3}

184

17

x
^{72} +
x
^{40} +
x
^{34} +
x
^{6} +
x
^{3}

184

18

x
^{34} +
x
^{33} +
x
^{12} +
x
^{6} +
x
^{5} +
x
^{3}

240

19

x
^{72} +
x
^{40} +
x
^{34} +
x
^{6} +
x
^{3} +
ζ
^{27}(Tr(
ζ
^{20}
x
^{3} +
ζ
^{94}
x
^{5} +
ζ
^{66}
x
^{9}))

216

Remark 5
For the
x
^{13},
x
^{57} and
x
^{63} we can derive the exact number of EAclasses. Indeed, the two simplex subcodes individuated for each ones are those generated by
The representatives of the EAclasses that are related to these codes are
F and
F
^{− 1}. For
x
^{57} and
x
^{63} we have that they are cyclotomic equivalent (and thus affine equivalent) to their inverse, implying that the CCZclass and and the EAclass coincide. For the case of
x
^{13}, its inverse is given by
x
^{88}. Since the cyclotomic classes of these two functions are distinct we can conclude that they are not EAequivalent. Thus for
x
^{13} we have 2 EAclasses in the CCZclass.
$$ \left( \begin{array}{c} F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}} \quad \text{ or }\quad \left( \begin{array}{c} x \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
6.2 n = 8
In dimension 8 we have 23 functions in the table given in [
14], see Table
3 (in [
21] the authors found 8157 new functions more). We extend the computation also to the case of the inverse function that is 4differentially uniform in this case.
Table 3
CCZinequivalent APN functions over
\(\mathbb {F}_{2^{8}}\) given in [
14] and the inverse function
N.

function

# EAclasses ≤


1

x
^{3}

256

2

x
^{9}

256

3

x
^{57}

1

4

ζ
^{15}
x
^{48} +
ζ
^{16}
x
^{33} +
ζ
^{16}
x
^{18} +
x
^{17} +
x
^{3}

256

5

x
^{3} +
T
r(
x
^{9})

256

6

x
^{9} +
T
r(
x
^{3})

256

7

ζ
^{21}
x
^{144} +
ζ
^{183}
x
^{66} +
ζ
^{245}
x
^{33} +
x
^{3}

256

8

ζ
^{135}
x
^{144} +
ζ
^{120}
x
^{66} +
ζ
^{65}
x
^{18} +
x
^{3}

256

9

ζ
^{67}
x
^{192} +
ζ
^{182}
x
^{132} +
ζ
^{24}
x
^{6} +
x
^{3}

256

10

x
^{160} +
x
^{132} +
x
^{80} +
x
^{68} +
x
^{6} +
x
^{3}

464

11

x
^{66} +
x
^{40} +
x
^{18} +
x
^{5} +
x
^{3}

368

12

x
^{130} +
x
^{66} +
x
^{40} +
x
^{12} +
x
^{3}

400

ζ
^{189}
x
^{192} +
ζ
^{143}
x
^{144} +
ζ
^{22}
x
^{132} +
ζ
^{21}
x
^{129} +
ζ
^{133}
x
^{96} +
ζ
^{239}
x
^{72} +
ζ
^{229}
x
^{66} +
ζ
^{31}
x
^{48} +


13

ζ
^{187}
x
^{36} +
ζ
^{185}
x
^{33} +
ζ
^{68}
x
^{24} +
ζ
^{236}
x
^{18} +
ζ
^{75}
x
^{12} +
ζ
^{91}
x
^{9} +
ζ
^{97}
x
^{6} +
ζ
^{160}
x
^{3}

256

ζ
^{100}
x
^{192} +
ζ
^{12}
x
^{160} +
ζ
^{15}
x
^{144} +
ζ
^{243}
x
^{136} +
ζ
^{234}
x
^{132} +
ζ
^{33}
x
^{130} +
ζ
^{39}
x
^{129} +
ζ
^{139}
x
^{96} +


ζ
^{51}
x
^{80} +
ζ
^{229}
x
^{72} +
ζ
^{39}
x
^{68} +
ζ
^{17}
x
^{66} +
ζ
^{189}
x
^{65} +
ζ
^{126}
x
^{48} +
ζ
^{198}
x
^{40} +
ζ
^{238}
x
^{36} +
ζ
^{192}


14

x
^{34} +
ζ
^{217}
x
^{33} +
ζ
^{122}
x
^{24} +
ζ
^{144}
x
^{20} +
ζ
^{169}
x
^{18} +
ζ
^{141}
x
^{17} +
ζ
^{236}
x
^{12} +

400

ζ
^{117}
x
^{10} +
ζ
^{183}
x
^{9} +
ζ
^{184}
x
^{6} +
ζ
^{231}
x
^{5} +
ζ
^{228}
x
^{3}


15

ζ
^{155}
x
^{192} +
ζ
^{96}
x
^{144} +
ζ
^{223}
x
^{132} +
ζ
^{77}
x
^{129} +
ζ
^{88}
x
^{96} +
ζ
^{232}
x
^{72} +
ζ
^{69}
x
^{66} +
ζ
^{142}
x
^{48} +

256

ζ
^{168}
x
^{36} +
x
^{33} +
ζ
^{145}
x
^{24} +
ζ
^{234}
x
^{18} +
ζ
^{202}
x
^{12} +
ζ
^{94}
x
^{9} +
ζ
^{189}
x
^{6} +
ζ
^{241}
x
^{3}


16

ζ
^{126}
x
^{192} +
ζ
^{119}
x
^{144} +
ζ
^{221}
x
^{132} +
ζ
^{222}
x
^{129} +
ζ
^{79}
x
^{96} +
ζ
^{221}
x
^{72} +
ζ
^{187}
x
^{66} +

256

ζ
^{148}
x
^{48} +
ζ
^{187}
x
^{36} +
ζ
^{237}
x
^{24} +
ζ
^{231}
x
^{12} +
ζ
^{119}
x
^{9} +
ζ
^{244}
x
^{6} +
ζ
^{236}
x
^{3}


17

ζ
^{151}
x
^{192} +
ζ
^{13}
x
^{144} +
ζ
^{58}
x
^{132} +
ζ
^{143}
x
^{129} +
ζ
^{110}
x
^{96} +
ζ
x
^{72} +
ζ
^{244}
x
^{66} +
ζ
^{26}
x
^{48} +

256

ζ
^{180}
x
^{36} +
ζ
^{8}
x
^{33} +
ζ
^{69}
x
^{24} +
ζ
^{76}
x
^{18} +
ζ
^{201}
x
^{12} +
ζ
^{201}
x
^{9} +
ζ
^{19}
x
^{6} +
ζ
^{107}
x
^{3}


18

ζ
^{86}
x
^{192} +
ζ
^{224}
x
^{129} +
ζ
^{163}
x
^{96} +
ζ
^{102}
x
^{66} +
ζ
^{129}
x
^{48} +
ζ
^{102}
x
^{36} +
ζ
^{170}
x
^{33} +

256

ζ
^{14}
x
^{24} +
ζ
^{170}
x
^{18} +
ζ
^{101}
x
^{12} +
ζ
^{58}
x
^{6} +
ζ
^{254}
x
^{3}


19

ζ
^{95}
x
^{192} +
ζ
^{242}
x
^{144} +
ζ
^{195}
x
^{132} +
ζ
^{98}
x
^{129} +
ζ
^{84}
x
^{96} +
ζ
^{45}
x
^{72} +
ζ
^{234}
x
^{66} +
ζ
^{202}
x
^{48} +

256

ζ
^{159}
x
^{36} +
ζ
^{58}
x
^{33} +
ζ
^{23}
x
^{24} +
ζ
^{148}
x
^{18} +
ζ
^{230}
x
^{12} +
ζ
^{32}
x
^{9} +
ζ
^{54}
x
^{6} +
ζ
^{41}
x
^{3}


20

ζ
^{132}
x
^{192} +
ζ
^{37}
x
^{144} +
ζ
^{91}
x
^{132} +
ζ
^{188}
x
^{129} +
ζ
^{76}
x
^{96} +
ζ
^{162}
x
^{72} +
ζ
^{46}
x
^{66} +
ζ
^{252}
x
^{48} +

256

ζ
^{42}
x
^{36} +
ζ
^{81}
x
^{33} +
ζ
^{83}
x
^{24} +
ζ
^{13}
x
^{18} +
ζ
^{185}
x
^{12} +
ζ
^{163}
x
^{9} +
ζ
^{216}
x
^{6} +
ζ
^{181}
x
^{3}


21

ζ
^{91}
x
^{192} +
ζ
^{124}
x
^{144} +
ζ
^{214}
x
^{132} +
ζ
^{106}
x
^{129} +
ζ
^{59}
x
^{96} +
ζ
^{172}
x
^{72} +
ζ
^{138}
x
^{66} +

256

ζ
^{163}
x
^{48} +
ζ
^{58}
x
^{36} +
ζ
^{100}
x
^{33} +
ζ
^{32}
x
^{24} +
ζ
^{250}
x
^{18} +
ζ
^{45}
x
^{12} +
ζ
^{241}
x
^{6} +
ζ
^{157}
x
^{3}


22

ζ
^{25}
x
^{192} +
ζ
^{140}
x
^{144} +
ζ
^{59}
x
^{132} +
ζ
^{129}
x
^{129} +
ζ
^{42}
x
^{96} +
ζ
^{164}
x
^{72} +
ζ
^{149}
x
^{66} +
ζ
^{119}
x
^{48} +

256

ζ
^{74}
x
^{36} +
ζ
^{211}
x
^{33} +
ζ
^{9}
x
^{24} +
ζ
^{46}
x
^{18} +
ζ
^{130}
x
^{12} +
ζ
^{185}
x
^{9} +
ζ
^{147}
x
^{6} +
ζ
^{27}
x
^{3}


23

ζ
^{113}
x
^{192} +
ζ
^{56}
x
^{144} +
ζ
^{68}
x
^{132} +
ζ
^{155}
x
^{129} +
ζ
^{91}
x
^{96} +
ζ
^{78}
x
^{72} +
ζ
^{159}
x
^{66} +
ζ
^{30}
x
^{48} +

256

ζ
^{194}
x
^{36} +
ζ
^{14}
x
^{33} +
ζ
^{238}
x
^{24} +
ζ
^{91}
x
^{18} +
ζ
^{100}
x
^{12} +
ζ
^{96}
x
^{9} +
ζ
^{222}
x
^{6} +
ζ
^{178}
x
^{3}




x
^{127} (inverse)

2

Remark 6
For
x
^{57} we have only one simplex code, which implies that there is only one EAclass. As in dimension 7 for the inverse function
x
^{127} we have two simplex codes and these are generated by
These codes are relative to the class of
F and of
F
^{− 1}, thus we can conclude as before that the CCZclass contains only one EAclass.
$$ \left( \begin{array}{c} F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}} \quad \text{ or }\quad \left( \begin{array}{c} x \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
6.3 n = 9
For this dimension we consider only the nonGold APN power functions. We give the upper bound on the number of EAclasses in Table
4.
Table 4
CCZinequivalent APN functions over
\(\mathbb {F}_{2^{9}}\) given in [
14] and the inverse function
N.

function

# EAclasses ≤


1

x
^{13}

2

2

x
^{19}

2

3

x
^{241}

2

4

x
^{255}(
i
n
v
e
r
s
e)

2

Remark 7
As before for
x
^{13},
x
^{19} and
x
^{241} we have two simplex codes and two EAclasses for each function. For the inverse function
x
^{255} we have two simplex codes but only one EAclass.
In [
16] the authors investigate EAequivalence of the inverse function to a permutation. They concluded that for
n ≥ 5 the inverse function is EAequivalent to a permutation if and only if it is affine equivalent to it. As the authors state at the end of their paper, an interesting problem is whether or not there exists a permutation that is CCZequivalent to
x
^{− 1} but not affine equivalent. From our computational results we can conclude the following.
Theorem 7
Let 5 ≤
n ≤ 9. A permutation polynomial
F defined over
\({\mathbb {F}}_{2^{n}}\) is CCZequivalent to
x
^{− 1} if and only if
F is affineequivalent to
x
^{− 1}.
Proof
For 5 ≤
n ≤ 9 we obtain only the two simplex codes generated by
This implies that we have only the EAclass of
x
^{− 1} since it is an involution. Now, the permutations in the EAclass of
x
^{− 1} can be obtained only with the affine equivalence [
16]. □
$$ \left( \begin{array}{c} F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}} \quad \text{ or }\quad \left( \begin{array}{c} x \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
From this result we give the following conjecture.
Conjecture 1
For
n ≥ 5, a permutation polynomial
F defined over
\({\mathbb {F}}_{2^{n}}\) is CCZequivalent to
x
^{− 1} if and only if
F is affineequivalent to
x
^{− 1}.
Moreover, in [
7] the authors conjectured that the CCZclass of nonGold APN power functions can be obtained using iteratively EAequivalence together with the inverse transformation. In particular, using Procedure 2 they proved that for
n ≤ 8 the conjecture is true. From the results obtained here we were able to verify that this is true up to dimension 9 and in particular we have at most two EAclasses whose representatives are
F and
F
^{− 1}.
Theorem 8
Let
n ≤ 9 and
F(
x) =
x
^{d} be a nonGold APN function defined over
\({\mathbb {F}}_{2^{n}}\). Then the CCZclass of
F is partitioned in at most two EAclasses represented by
F and
F
^{− 1} (when it exists).
7 Conclusion
We gave the full classification, up to EAequivalence, of the known APN functions in dimension 6 (see Table
1). Moreover, for the case of the unique APN permutation in even dimension, we gave also the classification of the affine classes (containing a permutation). For this purpose, in Theorem 6 we introduced a new code linked to a vectorial Boolean function that permits to investigate the affine equivalence in the context of bijective maps.
For dimension 7, 8 and 9, since checking EAequivalence using the codes equivalence requires a huge amount of computing, we gave an upper bound on the number of the EAclasses of the known APN functions (in dimension 9 we consider only nonGold APN power functions), see Tables
2,
3 and
4. For the case of APN power mapping we observed that at most we have two EAclasses in the CCZclass, Theorem 8. Moreover, for the inverse function for 5 ≤
n ≤ 9 we obtained that the EAclass coincides with the CCZclass, implying that for these dimensions the inverse function is CCZequivalent to a permutation if and only if they are affine equivalent, Theorem 7.
Acknowledgements
Open Access funding provided by University of Bergen. The research of this paper was supported by Trond Mohn Foundation.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit
http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.