Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

06.04.2020 | Ausgabe 5/2020 Open Access

Cryptography and Communications 5/2020

On the EA-classes of known APN functions in small dimensions

Zeitschrift:
Cryptography and Communications > Ausgabe 5/2020
Autor:
Marco Calderini
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, S-boxes) 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 S-boxes in the design of block ciphers.
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 EA-equivalence and CCZ-equivalence. Since EA-equivalence is a particular case of CCZ-equivalence, it is possible to partition the space of all functions \({\mathbb {F}}_{2^{n}}\to {\mathbb {F}}_{2^{m}}\) into CCZ-equivalence classes and then partition each CCZ-equivalence class into EA-equivalence classes. For brevity, we will refer to these as “EA-class” and “CCZ-class”. It was shown by Budaghyan et al. [ 3] that for quadratic APN functions CCZ-equivalence is more general than EA-equivalence together with taking inverses of permutations. In [ 7] the authors investigate further the relation between CCZ-equivalence and EA-equivalence with inverse transformation. While, in [ 9] the authors give a characterization of CCZ-equivalence in terms of twisting functions. Despite this, CCZ-equivalence is not yet fully well understood and, to the best of our knowledge, partitioning the CCZ-class of a function into its EA-classes 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 CCZ-classification 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 EA-equivalence and CCZ-equivalence. For the case of n = 6, the classification of the known APN functions is given only up to CCZ-equivalence. The classification up to EA-equivalence is not known.
In this work, we use the procedure introduced in [ 7] for investigating the EA-classes contained in a CCZ-class 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 EA-classes contained in the CCZ-class of a function F is upper bounded by the number of simplex codes contained in a linear code associated to F.
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 EA-classes 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 EA-classes 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 non-Gold APN power functions). In these dimensions checking EA-equivalence, 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 EA-classes. Moreover, for the case of non-Gold APN power functions we can determine the exact number of the EA-classes.

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
$$ F(x)=\sum\limits_{i=0}^{2^{n}-1} c_{i} x^{i}, \quad c_{i}\in {\mathbb{F}}_{2^{n}}. $$
For any i, 0 ≤ i ≤ 2 n − 1, the 2-weight of i is the (Hamming) weight of its binary representation. The algebraic degree of a function F is equal to the maximum 2-weight 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}^{n-1} c_{i} x^{2^{i}}\). We denote the trace function by
$$ Tr(x) = x + x^{2} + {\dots} + x^{2^{n-1}}. $$
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
$$ \mathcal{W}_{F}(a,b)=\sum\limits_{x\in {\mathbb{F}}_{2^{n}}}(-1)^{Tr(ax+bF(x))}. $$
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)=\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^{n-1}-\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 (EA-equivalent) 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;
  • Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) 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 EA-equivalence, and it is also well known that EA-equivalence is a particular case of CCZ-equivalence and every permutation is CCZ-equivalent to its inverse [ 10].
Recently, Yoshiara [ 20] and Dempwolff [ 12] have shown, independently, that two power APN functions are CCZ-equivalent if and only if they are EA-equivalent or one is EA-equivalent to the inverse of the second one. Moreover, for the case of quadratic APN functions, CCZ-equivalence coincides with EA-equivalence [ 19].

3 Properties and remarks on the CCZ-equivalence

In this section we will recall the procedure given in [ 7] and give some remarks and properties regarding CCZ-equivalence that will be useful in the investigation of the EA-classes contained in a CCZ-class.
Since we are interested in the EA-classes, without loss of generality, we assume that the affine permutation in the definition of CCZ-equivalence 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 CCZ-equivalent 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
$$ \mathcal{L}=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right] $$
where A i are linear maps over \({\mathbb {F}}_{2^{n}}\) for 1 ≤ i ≤ 4, and
$$ \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)). $$
In particular,
$$ F_{1}(x) = L_{1}(x,F(x))=A_{1}(x)+A_{2}\circ F(x) $$
(1)
and
$$ F_{2}(x) = L_{2}(x,F(x))=A_{3}(x)+A_{4}\circ F(x). $$
(2)
From the definition of CCZ-equivalence we have that a linear permutation \({\mathcal{L}}\) is admissible for producing a CCZ-equivalent function from F if and only if F 1( x) is a permutation. In terms of Walsh coefficients we have the following observation.
Observation 1 ( Observation 3.2 in [ 7])
The function F 1 in ( 1) is a permutation if and only if all its component are balanced, that is
$$ \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}. $$
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}(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 CCZ-equivalence and EA-equivalence together with the inverse transformation (when applicable). Using this procedure it is possible, at least in small dimensions, to investigate the EA-classes contained in the CCZ-class of a given function.
The procedure given in [ 7] is useful for constructing linear permutations
$$ \mathcal{L}=\left[\begin{array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end{array}\right] $$
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 2F( 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.
We are focusing on the EA-classes that are contained in the CCZ-class 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 EA-equivalent 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 EA-equivalent.
This means that for all possible L 1, for covering the EA-classes 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
$$ \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] $$
be two linear permutations over \(({\mathbb {F}}_{2^{n}})^{2}\) such that F 1( x) = L 1( x, F( x)) = A 1( x) + A 2F( 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 EA-equivalent.
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 EA-equivalent.
Now,
$$ \mathcal{L}^{\prime\prime}=\left[\begin{array}{cc} L&0\\ 0&I \end{array}\right]\cdot \mathcal{L}, $$
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. □
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
$$ \mathcal{Z}\mathcal{W}(\lambda)=\{a \in {\mathbb{F}}_{2^{n}} : \mathcal{W}_{F_{\lambda}}(a)=0\}. $$
Then we can define the following set
$$ S_{F}=\{\lambda\in {\mathbb{F}}_{2^{n}}^{\star} : \mathcal{Z}\mathcal{W}(\lambda)\ne \emptyset\}\cup \{0\}. $$
(4)
Note that if L 1( x, y) is such that F 1( x) = L 1( x, F( x)) = A 1( x) + A 2F( 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}^{*})\).
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}}\).
Procedure 2 ( Procedure 4.4 in [ 7])
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 ≤ ik and \(A_{2}^{*}(\beta _{i})=0\) if k + 1 ≤ in.
For any uU ∖{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 k-tuple \(a_{1}\in \mathcal {Z}\mathcal {W}(u_{1}),...,a_{k}\in \mathcal {Z}\mathcal {W}(u_{k})\) such that
  • (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.
These a 1,..., a k will be the images by \(A_{1}^{*}\) of β 1,..., β k, respectively.
After that, for any of these k-tuples, we need to determine all possible ( nk)-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
$$ \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), $$
where \(a+\mathcal {Z}\mathcal {W}(u)=\{a+v : v\in \mathcal {Z}\mathcal {W}(u)\}\).
In the following we will give some observations in order to see how it is possible from Procedure 2 to obtain the EA-classes contained in the CCZ-class of a given function.
Observation 3 ( Observation 4.2 in [ 7])
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 EA-class 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 nk 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 nk, 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 ≤ ik, and \(A_{1}^{*}(\beta _{j})=a_{j}\), \(A_{1}^{\prime *}(\beta _{j})=a^{\prime }_{j}\) for k + 1 ≤ jn.
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 ≤ ik and \({L}^{*}(\beta _{j})=(A_{1}^{*}|_{V})^{-1}(a_{j}^{\prime })\) for k + 1 ≤ jn (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) = LA 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 EA-class 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
$$ \left( \begin{array}{c} F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
Then, if Span(Im( A 2F)) = Im( A 2) the functions defined by the graphs \({\mathcal{L}}(G_{F})\) and \({\mathcal{L}}^{\prime }(G_{F})\) are EA-equivalent.
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 LA 2F = A 2F and \(L\circ A_{1}=A_{1}^{\prime }\). Moreover, we have that Span(Im( A 2F)) = 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 2F( x 1),..., A 2F( 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 LA 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 EA-equivalent. □
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 EA-equivalence.
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 EA-equivalent.
Proof
Consider the matrix of size 2 n × 2 n with columns the vectors
$$ M=\left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
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
$$ \left( \begin{array}{c} F_{1}(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}, $$
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
$$ \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}}}. $$
Since \({\mathcal{C}}_{F_{1}}={\mathcal{C}}_{{F}_{1}^{\prime }}\) we have that there exists a linear permutation L such that
$$ \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}}}, $$
and then
$$ \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}}}. $$
From the unicity of L 1 and \(L_{1}^{\prime }\) we obtain that \(L_{1}^{\prime }=L\circ L_{1}\). □
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 EA-classes contained in the CCZ-class 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
$$ \left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}^{\star}}. $$
Then, the number of EA-classes contained in the CCZ-class of F is upper bounded by the number of the simplex codes contained in \({\mathcal{C}}(F)\).

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 size of the matrix is (2 n + 1) × 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 size of the matrix is (2 n + 1) × (2 n+ 1 − 1).
  • 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 size of the matrix is (2 n + 1) × (2 n+ 1 + 2 n − 2).
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 CCZ-equivalence between two functions. The codes \({\mathcal{C}}_{2}\) and \({\mathcal{C}}_{3}\) were introduced in [ 13] for the case of the EA- and affine-equivalence. 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 CCZ-equivalent to G iff \({\mathcal{C}}_{1}(F)\) and \({\mathcal{C}}_{1}(G)\) are equivalent ([ 5, Theorem 6.2]).
  • F is EA-equivalent 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 affine-equivalent to G iff the codes \({\mathcal{C}}_{3}(F)\) and \({\mathcal{C}}_{3}(G)\) are equivalent. If F is a permutation, F is affine-equivalent 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 affine-equivalent 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
$$ 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}} $$
of size (2 n + 1) × (2 n+ 1 + 2 n − 1).
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
$$ 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), $$
applying a permutation on the columns, the last matrix is C 4( G).
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
$$ M=\left( \begin{array}{ccc} c&{\mathbf d}& {\mathbf e}\\ a&L_{1}& L_{2}\\ b&L_{3}&L_{4} \end{array}\right) $$
and a permutation matrix P such that MC 4( F) = C 4( G) ⋅ P. Thus, permuting the columns of MC 4( F) we would be able to obtain the matrix C 4( G). Now,
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 + dz and ey have weight 2 n− 1, so c + dx + eF( x) needs to be of weight 2 n. Let S = { y : ey = 0}, which is a subspace of dimension n − 1. A column relative to any yS 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 yS, 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 : ey = 0}. Thus L 2( y) = 0 if yS and L 2( y) = r for some fixed r if yS. 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
$$ 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). $$
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.
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 MC 4( F) we would have all columns equals to b. Since we want to permute the columns of MC 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 MC 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 2S 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,
$$ 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), $$
and thus
$$ \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, $$
for some permutation matrix P, that is, \(L_{4}(F(L_{1}^{-1}(x)+L_{1}^{-1}(a))=G(x)\). □
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 affine-equivalence 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 EA-classes 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 EA-equivalence was tested using the linear code \({\mathcal{C}}_{2}(F)\).
In dimension 6 there are 14 known APN functions (13 are quadratics) up to CCZ-equivalence and they are listed in Table  1. In Table  1 we give also the number of EA-classes contained in the CCZ-class of each function, together with the degrees of the functions in the EA-classes. All the representatives of the EA-classes can be found in Appendix 1 of [ 8].
Table 1
CCZ-inequivalent APN functions over \(\mathbb {F}_{2^{6}}=\langle {\zeta }\rangle \)
N.
function
# EA-classes
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 + ζ 6x 5 + ζ 19 x 7 + ζ 28 x 11 + ζ 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 CCZ-equivalence.
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 CCZ-class of the Dillon’s APN permutation we have 13 EA-classes 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} $$
and
$$ \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 CCZ-class can be represented by F 1, the EA-classes containing a permutation can be given by F 1 and \(F_{1}^{-1}\), and the affine-classes (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 affine-equivalent 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 multi-set
{* {* -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 EA-classes 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 EA-class. However, checking EA-equivalence with the code equivalence require a huge amount of computations. Corollary 1 gives us an upper bound on the number of EA-classes based on the simplex codes contained in
$$ \left( \begin{array}{c} x\\ F(x) \end{array}\right)_{x\in{\mathbb{F}}_{2^{n}}}. $$
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].

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
CCZ-inequivalent APN functions over \(\mathbb {F}_{2^{7}}\) given in [ 14]
N.
function
# EA-classes ≤
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 EA-classes. Indeed, the two simplex subcodes individuated for each ones are those generated by
$$ \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}}}. $$
The representatives of the EA-classes 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 CCZ-class and and the EA-class 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 EA-equivalent. Thus for x 13 we have 2 EA-classes in the CCZ-class.

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 4-differentially uniform in this case.
Table 3
CCZ-inequivalent APN functions over \(\mathbb {F}_{2^{8}}\) given in [ 14] and the inverse function
N.
function
# EA-classes ≤
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 EA-class. As in dimension 7 for the inverse function x 127 we have two simplex codes and these are generated by
$$ \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}}}. $$
These codes are relative to the class of F and of F − 1, thus we can conclude as before that the CCZ-class contains only one EA-class.

6.3 n = 9

For this dimension we consider only the non-Gold APN power functions. We give the upper bound on the number of EA-classes in Table  4.
Table 4
CCZ-inequivalent APN functions over \(\mathbb {F}_{2^{9}}\) given in [ 14] and the inverse function
N.
function
# EA-classes ≤
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 EA-classes for each function. For the inverse function x 255 we have two simplex codes but only one EA-class.
In [ 16] the authors investigate EA-equivalence of the inverse function to a permutation. They concluded that for n ≥ 5 the inverse function is EA-equivalent 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 CCZ-equivalent 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 CCZ-equivalent to x − 1 if and only if F is affine-equivalent to x − 1.
Proof
For 5 ≤ n ≤ 9 we obtain only the two simplex codes generated by
$$ \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}}}. $$
This implies that we have only the EA-class of x − 1 since it is an involution. Now, the permutations in the EA-class of x − 1 can be obtained only with the affine equivalence [ 16]. □
From this result we give the following conjecture.
Conjecture 1
For n ≥ 5, a permutation polynomial F defined over \({\mathbb {F}}_{2^{n}}\) is CCZ-equivalent to x − 1 if and only if F is affine-equivalent to x − 1.
Moreover, in [ 7] the authors conjectured that the CCZ-class of non-Gold APN power functions can be obtained using iteratively EA-equivalence 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 EA-classes whose representatives are F and F − 1.
Theorem 8
Let n ≤ 9 and F( x) = x d be a non-Gold APN function defined over \({\mathbb {F}}_{2^{n}}\). Then the CCZ-class of F is partitioned in at most two EA-classes represented by F and F − 1 (when it exists).

7 Conclusion

We gave the full classification, up to EA-equivalence, 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 EA-equivalence using the codes equivalence requires a huge amount of computing, we gave an upper bound on the number of the EA-classes of the known APN functions (in dimension 9 we consider only non-Gold APN power functions), see Tables  23 and  4. For the case of APN power mapping we observed that at most we have two EA-classes in the CCZ-class, Theorem 8. Moreover, for the inverse function for 5 ≤ n ≤ 9 we obtained that the EA-class coincides with the CCZ-class, implying that for these dimensions the inverse function is CCZ-equivalent 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.
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 5/2020

Cryptography and Communications 5/2020 Zur Ausgabe

Premium Partner