On relations between CCZ- and EA-equivalences

Abstract

In the present paper we introduce some sufficient conditions and a procedure for checking whether, for a given function, CCZ-equivalence is more general than EA-equivalence together with taking inverses of permutations. It is known from Budaghyan et al. (IEEE Trans. Inf. Theory 52.3, 1141–1152 2006; Finite Fields Appl. 15(2), 150–159 2009) that for quadratic APN functions (both monomial and polynomial cases) CCZ-equivalence is more general. We prove hereby that for non-quadratic APN functions CCZ-equivalence can be more general (by studying the only known APN function which is CCZ-inequivalent to both power functions and quadratics). On the contrary, we prove that for power non-Gold APN functions, CCZ equivalence coincides with EA-equivalence and inverse transformation for n ≤ 8. We conjecture that this is true for any n.

1 Introduction

Given n and m two positive integers, a function F from the finite field with 2ⁿ elements to the finite field with 2^m elements is called a vectorial Boolean function, or an (n, m)-function and it is simply called Boolean function when m = 1. Boolean functions and vectorial Boolean functions are useful objects since they have many applications in mathematics and information theory; in particular they are one of the fundamental entities investigated in cryptography. Nowadays it is of fundamental importance to exchange and store information in an efficient, secure and reliable manner and cryptographic primitives are indeed used to protect information against eavesdropping, unauthorized changes and other misuses. In symmetric cryptography the design of ciphers is based on an appropriate composition of nonlinear Boolean functions. For example, in block ciphers the security depends on S-boxes which are (n, m)-functions. Among the attacks that can be performed on a block cipher, one of the most efficient is the differential attack, introduced by Biham and Shamir [1]. It is based on the study of how differences in an input can affect the resulting difference at the output. To minimize the success probability of this attack, the theory of vectorial Boolean functions has identified an ideal property for the S-box when n = m, that is, to be Almost Perfect Non-linear (APN).

The role of APN functions is not just related to cryptography. There are indeed applications of APN functions in coding theory, projective geometry and theory of commutative semifields. For these reasons many different works have been focused on finding and constructing new families of APN functions.

The APN property is preserved by some transformations of functions, which define equivalence relations between vectorial Boolean functions. There are mainly two such equivalence notions, called extended affine equivalence (EA-equivalence) and Carlet-Charpin-Zinoviev equivalence (CCZ-equivalence). EA-equivalence is a particular case of CCZ-equivalence and any permutation is CCZ-equivalent to its inverse.

It is investigated in [5, 8] when CCZ-equivalence could produce more functions than applying only EA-equivalence and the inverse transformation. In particular, in [5], Budaghyan proves that for the Gold functions it is possible to construct, using EA-equivalence and the inverse transformation, a function which is not EA-equivalent to the starting function and its inverse. In [6, 8], the authors show that for quadratic APN functions (in particular Gold functions and x³ + Tr(x⁹)) CCZ-equivalence is more general than EA-equivalence with the inverse transformation.

In this work, we focus on investigating this problem for the case of non-quadratic APN functions. In particular, we characterize some linear permutations on $({\mathbb F}_{2^n})^{2}$ which imply that CCZ-equivalence between two functions, F and F^′ can be obtained via EA-equivalence and inverse transformation. We also introduce a procedure that, at least in small dimensions, permits to verify whether a sufficient condition for CCZ-equivalence to be restricted to EA-equivalence and inverse transformation holds. Using this procedure we are able to verify that also for APN functions CCZ-inequivalent to quadratic functions CCZ-equivalence is more general than EA-equivalence together with the inverse. With the same procedure we verify that, for contrary, up to dimension 8 for all non-Gold power APN functions and the inverse function CCZ-equivalence coincides with EA-equivalence together with the inverse transformation. This leads us to a conjecture that for all non-Gold power APN functions and for the inverse function CCZ-equivalence coincides with EA-equivalence together the inverse transformation. We conclude the paper with some observations on CCZ-equivalence classes for functions with linear structures.

2 Preliminaries

Let n ≥ 2, we denote by ${\mathbb F}_{2^n}$ the finite field with 2ⁿ elements, by ${\mathbb F}_{2^n}^{*}$ 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ⁿ − 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ⁿ − 1, the 2-weight of i is the (Hamming) weight of its binary representation. It is well known that 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}}$. A well known example of a linear function is the trace function

$$Tr(x) = x + x^{2} + {\dots} + x^{2^{n-1}},$$

in particular, the trace is a Boolean function, i.e $Tr:{\mathbb F}_{2^n}\to {\mathbb F}_{2}$. Besides, for any m ≥ 1 such that m|n we can define the linear function from ${\mathbb F}_{2^n}$ to ${\mathbb F}_{2^m}$

$$ T{r_{n}^{m}}(x)=\sum\limits_{i=0}^{n/m-1}x^{2^{im}}. $$

Let $\lambda \in {\mathbb F}_{2^n}^{*}$ and F be a function from ${\mathbb F}_{2^n}$ to itself, we define the λ-component of F as the Boolean function $F_{\lambda }:{\mathbb F}_{2^n}\to {\mathbb F}_{2}$ with F_λ(x) = Tr(λ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

$$ \mathscr{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

$$ \mathscr{W}_{f}(a)=\sum\limits_{x\in {\mathbb F}_{2^n}}(-1)^{Tr(ax)+f(x)}. $$

With Walsh spectrum we refer to the set of all possible values of the Walsh transform. A Boolean function f is called bent if its Walsh spectrum corresponds to the set {± 2^n/2}. Since $\mathscr{W}_{f}(a)$ is an integer bent functions can exist only for even n. If $\mathscr{W}_{f}(0)=0$ then the Boolean function is called balanced. Note that a bent function cannot be balanced. For any function $F:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$ it is well know that F is a permutation if and only if all its component functions are balanced.

We denote the derivative of F in the direction of $a\in {\mathbb F}_{2^n}^{*}$ by D_aF(x) = F(x + a) + F(x) and the image of F by $\Im (F) = \{F(x) | x \in {\mathbb F}_{2^n}\}$. A function F is called almost perfect nonlinear (APN) if for every a≠ 0 and every b in ${\mathbb F}_{2^n}$, the equation D_aF(x) = b admits at most 2 solutions, or equivalently |I(D_aF)| = 2^n− 1.

There are several equivalence relations of functions for which the APN property is preserved. Two functions F and F^′ from ${\mathbb F}_{2^n}$ to itself are called:

• affine equivalent if F^′ = A₁ ∘ F ∘ A₂ 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^′ = F^″ + A, where the mappings $A:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$ is affine and F^″ is affine equivalent to F;

• Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent) if for some affine permutation $\mathscr{L}$ of ${\mathbb F}_{2^n}\times {\mathbb F}_{2^n}$ the image of the graph of F is the graph of F^′, that is, $\mathscr{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, 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 [11]. The algebraic degree of a function (if it is not affine) is invariant under EA-equivalence but, in general, it is not preserved by CCZ-equivalence. In general, neither EA-equivalence nor CCZ-equivalence preserve the permutation property.

There are six known infinite families of power APN functions. They are presented in Table 1.

Table 1 Known APN power functions x^d over $\mathbb {F}_{2^{n}}$

Since these power functions have different algebraic degree they are EA-inequivalent. Instead CCZ-inequivalence is not so straightforward, but also for this case it was possible to prove some inequalities. In both [24] and [13] Yoshiara and Dempwolff show that two APN power functions are CCZ-equivalent if and only if they are cyclotomic-equivalent, i.e. they are EA-equivalent or one is EA-equivalent to the inverse of the second one. To be more precise if we consider x^k and x^l defined over $\mathbb {F}_{2^{n}}$ the functions are cyclotomic-equivalent if there exists an integer 0 ≤ a < n such that l ≡ k2^a mod (2ⁿ − 1) or kl ≡ 2^a mod (2ⁿ − 1), when k is coprime with 2ⁿ − 1. Earlier, some results on CCZ-inequivalence between the functions in Table 1 were proven in [7].

Among these power functions, only for the Gold power function $x^{2^{i}+1}$, it was shown that CCZ-equivalence is more general than applying EA-equivalence and the inverse transformation in [8]. For the other power functions it is an open problem.

3 Remarks on CCZ-equivalence

In this section we will report some remarks regarding CCZ-equivalence that will be useful in the investigation of the relation between EA-equivalence and CCZ-equivalence. Without loss of generality, we assume that the affine permutation in the definition of CCZ-equivalence is linear. It means that using affine permutations instead of linear one we simply make a shift by a constant in the input and output of the resulting function as it is shown in the lemma below.

Lemma 3.1

Let$L_{1}, L_{2}:({\mathbb F}_{2^n})^{2}\to {\mathbb F}_{2^n}$belinear maps and$a, b\in {\mathbb F}_{2^n}$, such that$\mathscr{L}(x,y)=(L_{1}(x,y)+a,L_{2}(x,y)+b)$isa permutation. LetF andF^′be CCZ-equivalent functions such that$\mathscr{L}$mapsthe graph ofF to the graph ofF^′. Then the linear part$\mathscr{L}^{\prime }$of$\mathscr{L}$mapsthe graph ofF to the graph ofF^″(x) = F^′(x + a) + b.

Proof

Indeed, if for an affine permutation $\mathscr{L}(x,y)=(L_{1}(x,y)+a,L_{2}(x,y)+b)$, where $L_{1}, L_{2}:({\mathbb F}_{2^n})^{2}\to {\mathbb F}_{2^n}$ are linear and $a, b\in {\mathbb F}_{2^n}$, the image of the graph of a function F is the graph of a function F^′, then by denoting F₁(x) = L₁(x, F(x)) and F₂(x) = L₂(x, F(x)) we get

$$F^{\prime} (x)= F_{2} \circ [F_{1}(x)+a]^{-1}= F_{2} \circ F_{1}^{-1}(x+a)+b$$

(since F₁ must be a permutation [8]). Hence, neglecting a and b we get a function F^″ affine equivalent to F^′, that is, F^″(x) = F^′(x + a) + b. □

We can describe a linear map $\mathscr{L}$ as a formal matrix

$$\mathscr{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

$$\mathscr{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)

We can make the following straightforward but important observations about F₁.

Observation 3.2

The functionF₁in (1) is a permutation if and only if all its componentsare balanced. In terms of Walsh transforma we have thatF₁is a permutation if and onlyif

$$ \mathscr{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}^{*}. $$

Denoting byL^∗the adjoint operator of a linear mapL(i.e. Tr(yL(x)) = Tr(xL^∗(y)) for all$x,y\in {\mathbb F}_{2^n}$), we have

$$ \mathscr{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))}=\mathscr{W}_{F}(A_{1}^{*}(\lambda),A_{2}^{*}(\lambda))=\mathscr{W}_{F_{A_{2}^{*}(\lambda)}}(A_{1}^{*}(\lambda))=0. $$

(3)

In particular, we have that$\text {Ker}(A_{1}^{*})\cap \text {Ker}(A_{2}^{*})=\{0\}$and for all$\lambda \in \mathrm {Ker(A_{1}^{*})}\setminus \{0\}$, the$A_{2}^{*}(\lambda )$-component ofF, $F_{A_{2}^{*}(\lambda )}$, has to be balanced. Moreover, it is easy to observe from equality (3) that ifFhas no balanced components thenA₁has to be a linear permutation on${\mathbb F}_{2^n}$.

4 CCZ-equivalence and EA-equivalence

In [8], it is proved that for quadratic APN functions CCZ-equivalence is strictly more general than EA-equivalence and inverse transformation. Such a result has been obtained by exhibiting APN functions which are CCZ-equivalent to Gold functions $F (x) = x^{2^{i}+1}$.

In this section we provide a procedure which allows, at least in small dimensions, to investigate if CCZ-equivalence leads to more functions than applying EA-equivalence and inverse transformation.

Given a function $F:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$ we want to construct a possible linear permutation

$$\mathscr{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 some function F^′. In particular, we want to construct the linear functions A₁ and A₂ on ${\mathbb F}_{2^n}$ so that F₁(x) = L₁(x, F(x)) = A₁(x) + A₂ ∘ F(x) is a permutation.

For any $\lambda \in {\mathbb F}_{2^n}$ we define the set

$$ \mathcal{Z}\mathcal{W}(\lambda)=\{a \in {\mathbb F}_{2^n} : \mathscr{W}_{F_{\lambda}}(a)=0\}. $$

Then we can define the following set

$$ S_{F}=\{\lambda\in {\mathbb F}_{2^n}^{*} : \mathcal{Z}\mathcal{W}(\lambda)\ne \emptyset\}\cup \{0\}. $$

(4)

Remark 4.1

It is easy to see that the set$\Im (A_{2}^{*})$iscontained inS_F(see (3)).

Along this section we denote by Span(v₁,…,v_m) the vector (sub)space over ${\mathbb F}_{2}$ generated by the elements $v_{1},\dots ,v_{m} \in {\mathbb F}_{2^n}$.

Now, to construct the possible functions F₁ we should consider all the vector subspaces of S_F. Let U be a fixed subspace contained in S_F, this will be a possible candidate for $\Im (A_{2}^{*})$.

Observation 4.2

Without loss of generality, fixing any basis{u₁,…,u_k} ofU (where k is the dimension of U) and fixing a basis{β₁,...,β_n} of${\mathbb F}_{2^n}$(asa vector space over${\mathbb F}_{2}$),we can suppose that$A_{2}^{*}(\beta _{i})=u_{i}$fori = 1,...,kand$\text {Ker}(A_{2}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})$.

Indeed, suppose$A_{2}^{*}$issuch that$A_{2}^{*}(w_{i})=u_{i}$fori = 1,...,kand$\text {Ker}(A_{2}^{*})=\text {Span}(w_{k+1},...,w_{n})$forsomew₁,...,w_nlinearly independent. Then, there exists a unique linearpermutation$\bar {L}$suchthat$\bar {L}^{*}(\beta _{i})=w_{i}$forall i. Now, ifF₁(x) = A₁(x) + A₂(F(x)) is a permutation, we can consider$F_{1}^{\prime }=\bar {L}\circ F_{1}$, which is again a permutation, and$\bar {A_{2}}^{*}=(\bar {L}\circ A_{2})^{*}$iss.t.$\bar {A_{2}}^{*}(\beta _{i})=u_{i}$fori = 1,...,kand$\text {Ker}(\bar {A_{2}}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})$.

Remark 4.3

As stated in [21, Theorem 2.3] for any linear polynomialL(x) we have that,given a basis {β₁,...,β_n} of${\mathbb F}_{2^n}$, thereexist unique𝜃₁,...,𝜃_nin${\mathbb F}_{2^n}$suchthat$L(x)={\sum }_{i=1}^{n} \text {Tr}(\beta _{i}x)\theta _{i}$. Then, we can constructthe linear polynomial$A_{2}^{*}$fromthe image of the basis {β₁,...,β_n} by solving the linear system

$$\begin{array}{l} {\sum}_{i=1}^{n} \text{Tr}(\beta_{1} \beta_{i})\theta_{i}=A_{2}^{*}(\beta_{1})\\ \vdots\\ {\sum}_{i=1}^{n} \text{Tr}(\beta_{n} \beta_{i})\theta_{i}=A_{2}^{*}(\beta_{n}). \end{array} $$

Now, we have fixed U and our function $A_{2}^{*}$ (using Observation 4.2 and Remark 4.3) and we want to construct all possible $A_{1}^{*}$ such that F₁(x) = A₁(x) + A₂ ∘ F(x) is a permutation. In the following we report the procedure to construct the matrices $A_{1}^{*}$ (for fixed $A_{2}^{*}$). The steps of this procedure will be explained in the proof of Proposition 4.5.

Procedure 4.4

For anyu ∈ U ∖{0} we considerthe set$\mathcal {Z}\mathcal {W}(u)$, as definedbefore. To constructA₁we need to determine the images 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})$suchthat

• (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.

Thesea₁,...,a_kwill be theimages by$A_{1}^{*}$ofβ₁,...,β_k, respectively.

After that, for any of these k-tuples, we need to determine all possible(n − k)-tuples ofelementsa_k+ 1,...,a_nsatisfying:

• (P2)a_k+ 1,...,a_nare linearly independent;

• (P3)for anya ∈ 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}$.

Condition (P3) is equivalent to have

$$ \text{Span}(a_{k+1},...,a_{n})\subseteq \bigcap\limits_{\lambda_{1},...,\lambda_{k}\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)\}$.

Let us note that if we include the case a = 0 in Condition (P3), then it would imply also Condition (P1). However, verifying (P1) after the selection of a₁,...,a_k will help in filtering the elements for which (P3) is not satisfied.

Proposition 4.5

LetU be a subspace contained inS_F, whereF is a function from${\mathbb F}_{2^n}$toitself andS_Fdefined as in (4). Then, there exists a permutationof${\mathbb F}_{2^n}$F₁(x) = A₁(x) + A₂ ∘ F(x), withA₁andA₂linear and$\Im (A_{2}^{*})=U$, if and only if Procedure 4.4 applied to the spaceU is successful.

Proof

Let us suppose that F₁(x) = A₁(x) + A₂ ∘ F(x) is a permutation and $\Im (A_{2}^{*})=U$. From the Observation 4.2 without loss of generality we can suppose that $A_{2}^{*}(\beta _{i})=u_{i}$ for i = 1,...,k and $\text {Ker}(A_{2}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})$, where {u₁,…,u_k} is a basis of U fixed for the procedure. Then, we need to show that $A_{1}^{*}$ is generated by the procedure. That is, we need to show that (P1), (P2) and (P3) are satisfied.

Let $a_{i}=A_{1}^{*}(\beta _{i})$ for 1 ≤ i ≤ n. Suppose that (P1) is not satisfied, then there exist λ₁,…,λ_k in ${\mathbb F}_{2}$, not all zero, such that ${\sum }_{i=1}^{k}\lambda _{i}a_{i}\notin \mathcal {Z}\mathcal {W}({\sum }_{i=1}^{k} \lambda _{i}u_{i})$, which means that $\mathscr{W}_{F}({\sum }_{i=1}^{k}\lambda _{i}a_{i},{\sum }_{i=1}^{k}\lambda _{i}u_{i})\ne 0$. Since

$$\mathscr{W}_{F}(\sum\limits_{i=1}^{k}\lambda_{i}a_{i},\sum\limits_{i=1}^{k}\lambda_{i}u_{i})=\mathscr{W}_{F}(A_{1}^{*}(\sum\limits_{i=1}^{k}\lambda_{i}\beta_{i}),A_{2}^{*}(\sum\limits_{i=1}^{k}\lambda_{i}\beta_{i}))=\mathscr{W}_{F_{1}}(0,\sum\limits_{i=1}^{k}\lambda_{i}\beta_{i})$$

(see Observation 3.2) and F₁ is a permutation, this is not possible.

If (P2) is not satisfied we have that there exist λ_k+ 1,…,λ_n in ${\mathbb F}_{2}$, not all zero, such that ${\sum }_{i=k+1}^{n}\lambda _{i}a_{i}=0$. Then, ${\sum }_{i=k+1}^{n}\lambda _{i}\beta _{i}\in \text {Ker}(A_{1}^{*})\cap \text {Ker}(A_{2}^{*})$ and from Observation 3.2 this is not possible.

The last condition (P3) is similar to (P1). Indeed, suppose that there exist λ₁,…,λ_n in ${\mathbb F}_{2}$ such that ${\sum }_{i=1}^{k} \lambda _{i}a_{i}+{\sum }_{i=k+1}^{n}\lambda _{i}a_{i}\notin \mathcal {Z}\mathcal {W}({\sum }_{i=1}^{k} \lambda _{i}u_{i})$. Then, we have

$$\begin{array}{ll} \mathscr{W}_{F_{1}}(0,\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i})&=\mathscr{W}_{F}(A_{1}^{*}(\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i}),A_{2}^{*}(\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i}))\\ &=\mathscr{W}_{F}(A_{1}^{*}(\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i}),A_{2}^{*}(\sum\limits_{i=1}^{k}\lambda_{i}\beta_{i}))\ne 0, \end{array}$$

$A_{2}^{*}({\sum }_{i=1}^{k}\lambda _{i}\beta _{i})=A_{2}^{*}({\sum }_{i=1}^{n}\lambda _{i}\beta _{i})$ since $\text {Ker}(A_{2}^{*})=\text {Span}(\beta _{k+1},...,\beta _{n})$).

Vice versa, if we are successful on generating, at least, one matrix $A_{1}^{*}$ with Procedure 4.4, then from Condition (P1), (P2) and (P3) it is easy to verify that for any λ₁,…,λ_n in ${\mathbb F}_{2}$, not all zero,

$$\mathscr{W}_{F_{1}}(0,\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i})=\mathscr{W}_{F}(A_{1}^{*}(\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i}),A_{2}^{*}(\sum\limits_{i=1}^{n}\lambda_{i}\beta_{i}))=\mathscr{W}_{F}(\sum\limits_{i=1}^{n}\lambda_{i}a_{i},\sum\limits_{i=1}^{n}\lambda_{i}u_{i})=0.$$

Indeed, from Condition (P1) we have $\mathscr{W}_{F_{1}}(0,{\sum }_{i=1}^{n}\lambda _{i}\beta _{i})=0$, for all possible λ₁,…,λ_k not all zero and λ_k+ 1 = ⋯ = λ_n = 0. From Condition (P2) we have that for all possible λ_k+ 1,…,λ_n not all zero and λ₁ = ⋯ = λ_k = 0, $\mathscr{W}_{F_{1}}(0,{\sum }_{i=1}^{n}\lambda _{i}\beta _{i})=0$. The last condition, (P3), guarantees that $\mathscr{W}_{F_{1}}(0,{\sum }_{i=1}^{n}\lambda _{i}\beta _{i})=0$ when both λ₁,…,λ_k are not all zero and λ_k+ 1,…,λ_n are not all zero. □

On the other hand, if we cannot construct a matrix A₁ for all spaces U ⊆ S_F, we have that all the CCZ-transformations that we can apply to F are a composition of EA- and inverse transformations. Before proving it, we recall the following remark from [8]. Further, in Lemma 4.8 we extend Proposition 3 of [8].

Remark 4.6 (Remark 2 in [8])

For a function$F:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$, if$\mathscr{L}=(L_{1},L_{2})$and$\mathscr{L}^{\prime }=(L_{1},L_{2}^{\prime })$arepermutations such that the functionL₁(x, F(x)) is a permutation, then the functions defined by thegraphs$\mathscr{L}(G_{F})$and$\mathscr{L}^{\prime }(G_{F})$areEA-equivalent.

Remark 4.7

Proposition 4.5 implies that if we apply Procedure 4.4 to a subspaceU inS_F, for a given functionF, then we obtain all the possible mapsA₁(and thusL₁(x, y) = A₁(x) + A₂(y))such thatA₁(x) + A₂ ∘ F(x) is a permutation andA₂is a fixed map as in Observation 4.2 forwhich$\Im (A_{2}^{*})=U$.

Consider the set of all the functionsL₁’sobtained from Procedure 4.4 applied to all the subspaceU inS_F. From Observation 4.2 and Remark 4.6, in order to cover all EA-inequivalentfunctions in the CCZ-class of F, it is sufficient to determine a singleL₂for each of theL₁constructed before, and apply the transformation$\mathscr{L}=(L_{1},L_{2})$toG_F.

In Proposition 3 of [8], the authors characterized which type of linear maps $\mathscr{L}$, admissible for a CCZ-transformation, gives us EA-equivalence of a function F^′ to a function F or to its inverse (if it exists). That is, they studied the linear maps, $\mathscr{L}$, that applied to the graph of F permit to obtain the graph of F^′ in the following cases

$$ F^{\prime}\sim_{EA} F\quad\text{ and} \quad F^{\prime}\sim_{EA} F^{-1}\overset{\text{inv}}{\rightarrow} F. $$

In the following lemma we extend this characterization to the case when we apply, again, an EA-transformation and the inverse transformation (if it is possible). That is, we study the maps, $\mathscr{L}$, that maps the graph of F onto the graph F^′ when

$$ F^{\prime}\sim_{EA} G\overset{\text{inv}}{\rightarrow} G^{-1} \sim_{EA}F $$

(5)

and

$$ F^{\prime}\sim_{EA} G\overset{\text{inv}}{\rightarrow} G^{-1} \sim_{EA}F^{-1}\overset{\text{inv}}{\rightarrow} F, $$

(6)

for some permutation G.

Note that for applying the inverse transformation it is necessary that the function (in this case G) is a permutation. Indeed, for a given permutation $\mathscr{L}$ that is suitable for CCZ-equivalence (i.e. F₁(x) = A₁(x) + A₂ ∘ F(x) is a permutation) it may be possible to decompose $\mathscr{L}$ in several iterations of maps which represent EA-equivalence and the inverse transformation, but if we apply the inverse transformation to the graph of a non invertible function the obtained set is no more a graph of a function.

Lemma 4.8

Let$F,F^{\prime }:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$. The functionF^′is EA-equivalent to the functionF or to the inverseofF (if it exists) if and only if there exists a linearmap$\mathscr{L}=(L_{1},L_{2})$suchthat$\mathscr{L}(G_{F})=G_{F^{\prime }}$andL₁depends only in one variable, i.e.L₁(x, y) = A₁(x) orL₁(x, y) = A₂(y). In particular, in the first caseA₁,A₄are permutations and in the second caseA₂,A₃are permutations.

While, we have the case (5), for somepermutation G, if and only if there exists a linearpermutation$\mathscr{L}=(L_{1},L_{2})$suchthat$\mathscr{L}(G_{F})=G_{F^{\prime }}$andL₁(x, y) = A₁(x) + A₂(y) withA₂a permutation of${\mathbb F}_{2^n}$. In particular, ifA₁ = 0 we would obtain the identity map for EA-equivalence on the right side of (5).

Moreover, ifF^− 1exists, then we have (6), for some permutation G, if and only if there exists alinear permutation$\mathscr{L}=(L_{1},L_{2})$suchthat$\mathscr{L}(G_{F})=G_{F^{\prime }}$andL₁(x, y) = A₁(x) + A₂(y) withA₁a permutation of${\mathbb F}_{2^n}$. In particular, ifA₂ = 0 we would obtain the identity map for EA-equivalence in the middle of (6) andthus the inverse transformations cancel.

Proof

The first part is Proposition 3 in [8]. Note that the condition A₁,A₄ permutations (and similarly A₂,A₃ permutations) is equivalent to $\mathscr{L}=(L_{1},L_{2})$ being a permutation.

We will show the last two claims. Suppose F^′ is EA-equivalent to the function G which inverse is EA-equivalent to F, that is

$$F^{\prime}\sim_{EA} G\overset{\text{inv}}{\rightarrow} G^{-1} \sim_{EA}F.$$

Recalling that in the inverse transformation we are applying the linear permutation over $({\mathbb F}_{2^n})^{2}$ given by Inv(x, y) = (y, x), from the first part of the lemma we can construct the permutation $\mathscr{L}$ given by

$$ \begin{array}{@{}rcl@{}} &&(A^{\prime}_{1}(x),A^{\prime}_{3}(x)+A^{\prime}_{4}(y))\circ(A_{3}(x)+A_{4}(y),A_{1}(x))=\\ &=&(A^{\prime}_{1}\circ A_{3}(x)+A^{\prime}_{1}\circ A_{4}(y),A^{\prime}_{3}\circ A_{3}(x)+A^{\prime}_{3}\circ A_{4}(y)+A^{\prime}_{4}\circ A_{1}(x)), \end{array} $$

where $(A^{\prime }_{1}(x),A^{\prime }_{3}(x)+A^{\prime }_{4}(y))$ maps G_G onto $G_{F^{\prime }}$ and (A₃(x) + A₄(y),A₁(x)) maps G_F onto G_G. Since $A^{\prime }_{1}$ and A₄ are permutations also $A^{\prime }_{1}\circ A_{4}$ is a permutation.

Vice versa, let $\mathscr{L}(x,y)=(A_{1}(x)+A_{2}(y),A_{3}(x)+A_{4}(y))$ be a linear permutation of $({\mathbb F}_{2^n})^{2}$ such that $\mathscr{L}(G_{F})=G_{F^{\prime }}$ and A₂ is permutation of ${\mathbb F}_{2^n}$. Consider the linear map $\mathscr{L}^{\prime }(x,y)=(A_{1}(x)+A_{2}(y),x)$. $\mathscr{L}^{\prime }$ is a linear permutation of $({\mathbb F}_{2^n})^{2}$ since A₂(x) and x are permutations. Moreover F₁(x) = A₁(x) + A₂(F(x)) is a permutation since $\mathscr{L}(G_{F})=G_{F^{\prime }}$. Then, F₁ is a permutation EA-equivalent to F and the function G defined by the graph $\mathscr{L}^{\prime }(G_{F})$, that is $F_{1}^{-1}$, is such that G^− 1 is EA-equivalent to F. From Remark 4.6 we obtain that F^′ and G are also EA-equivalent.

The case when G^− 1 is equivalent to F^− 1 is similar. Indeed, suppose

$$F^{\prime}\sim_{EA} G\overset{\text{inv}}{\rightarrow} G^{-1} \sim_{EA}F^{-1}\overset{\text{inv}}{\rightarrow} F,$$

using the first part of the lemma we can construct the permutation $\mathscr{L}$ given by

$$ \begin{array}{@{}rcl@{}} &&(A^{\prime}_{1}(x),A^{\prime}_{3}(x)+A^{\prime}_{4}(y))\circ(A_{3}(x)+A_{4}(y),A_{2}(y))=\\ &&(A^{\prime}_{1}\circ A_{3}(x)+A^{\prime}_{1}\circ A_{4}(y),A^{\prime}_{3}\circ A_{3}(x)+A^{\prime}_{3}\circ A_{4}(y)+A^{\prime}_{4}\circ A_{2}(y)), \end{array} $$

where $(A^{\prime }_{1}(x),A^{\prime }_{3}(x)+A^{\prime }_{4}(y))$ maps G_G onto $G_{F^{\prime }}$ and (A₃(x) + A₄(y),A₂(y)) maps G_F onto G_G. Since $A^{\prime }_{1}$ and A₃ are permutations also $A^{\prime }_{1}\circ A_{3}$ is a permutation.

Conversely, suppose $\mathscr{L}(x,y)=(A_{1}(x)+A_{2}(y),A_{3}(x)+A_{4}(y))$ is a linear permutation of $({\mathbb F}_{2^n})^{2}$ such that $\mathscr{L}(G_{F})=G_{F^{\prime }}$ with A₁ a permutation of ${\mathbb F}_{2^n}$.

As before, we can consider $\mathscr{L}^{\prime }(x,y)=(A_{1}(x)+A_{2}(y),y)$, which is a permutation of $({\mathbb F}_{2^n})^{2}$. Let G be defined by the graph $\mathscr{L}^{\prime }(G_{F})$, that is $G(x)=F\circ F_{1}^{-1}(x)$ with F₁(x) = A₁(x) + A₂ ∘ F(x). Since F is a permutation also G is a permutation and we obtain that $G_{G^{-1}}=Inv\circ \mathscr{L}^{\prime }(G_{F})$. From the first part of the lemma we have that G^− 1 is EA-equivalent to F^− 1 since $Inv\circ \mathscr{L}^{\prime }(x,y)=(y,A_{1}(x)+A_{2}(y))$. □

Let us denote by $\mathscr{A}$ an EA-transformation and Inv the inverse transformation, then in Lemma 4.8 we have obtained the followingcharacterization:

• $\mathscr{A}$: $\left [\begin {array}{cc} A_{1}&0\\ A_{3}&A_{4} \end {array}\right ]$, A₁ and A₄ permutations.

• $\mathscr{A} Inv$: $\left [\begin {array}{cc} 0&A_{2}\\ A_{3}&A_{4} \end {array}\right ]$, A₂ and A₃ permutations.

• $\mathscr{A} Inv\mathscr{A}$: $\left [\begin {array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end {array}\right ]$, A₂ a permutation and A₁ ≠ 0.

• $\mathscr{A} Inv\mathscr{A} Inv$: $\left [\begin {array}{cc} A_{1}&A_{2}\\ A_{3}&A_{4} \end {array}\right ]$, A₁ a permutation and A₂ ≠ 0.

In the following we will show that using Procedure 4.4 it is possible to investigate when we can obtain only these transformations for a given function F.

Theorem 4.9

LetF be a function from${\mathbb F}_{2^n}$toitself. If for any nonzero vector subspaceU inS_Fdifferent from${\mathbb F}_{2^n}$itis not possible to construct any matrix$A_{1}^{*}\ne 0$withProcedure 4.4, then any functionF^′CCZ-equivalent toF can be obtained fromF applying onlyEA-equivalence and inverse transformation (when applicable) iteratively.Moreover, the only maps suitable for CCZ-equivalence can be oftype$\mathscr{A}$, $\mathscr{A} Inv$and$\mathscr{A} Inv\mathscr{A}$(studiedin Lemma 4.8).

Proof

Using Procedure 4.4 we can obtain only functions L₁(x, y) = A₁(x) + A₂(y) such that A₂ is either the zero function, when U = {0}, or a permutation, when $U={\mathbb F}_{2^n}$. Otherwise, from Proposition 4.5 we cannot obtain L₁ such that L₁(x, F(x)) is a permutation of ${\mathbb F}_{2^n}$. Then, for any CCZ-transformation $\mathscr{L}$ such that $\mathscr{L}(G_{F})=G_{F^{\prime }}$ the function L₁ needs to satisfies one of the conditions in Lemma 4.8, implying that F^′ can be obtained from F applying only EA-equivalence and inverse transformation iteratively. □

When F is also a permutation we have the following.

Theorem 4.10

LetF be a permutation over${\mathbb F}_{2^n}$. If for any nonzero vector subspaceU inS_Fdifferent from${\mathbb F}_{2^n}$itis not possible to construct a matrix$A_{1}^{*}\ne 0$of$\text {rank}(A_{1}^{*})<n$withProcedure 4.4, then any functionF^′CCZ-equivalent toF can be obtained fromF applying only EA-equivalenceand inverse (when applicable) transformation iteratively. Moreover, theonly maps suitable for CCZ-equivalence are those studied in Lemma 4.8,i.e.$\mathscr{A}$, $\mathscr{A} Inv$, $\mathscr{A} Inv\mathscr{A}$and$\mathscr{A} Inv\mathscr{A} Inv$.

Proof

In this case, from Procedure 4.4 we could obtain a function L₁(x, y) = A₁(x) + A₂(y) for some space $U\ne \{0\}, {\mathbb F}_{2^n}$ in S_F. However, A₁ would be a permutation, and from the last part of Lemma 4.8 we have our claim. □

Applying Procedure 4.4, using the software MAGMA, from Theorem 4.8 we obtain the following corollary.

Corollary 4.11

Letn ≤ 8 andF(x) = x^dbe an APN power function defined over${\mathbb F}_{2^n}$, which is CCZ-inequivalent to a Gold function. Then, for the functionF CCZ-equivalence coincides with EA-equivalence together with the inversetransformation.

Corollary 4.12

Letn ≤ 8 be even. Then, for the inverse function$F(x)=x^{2^{n}-2}$CCZ-equivalencecoincides with EA-equivalence together with the inverse transformation.

Observation 4.13

From the computational results obtained for non-Gold APN power functions and the inverse function, we were able to observe that the class of CCZ-equivalence can be divided in at most two classes of EA-equivalence.

From these two results we conjecture the following.

Conjecture 4.14

LetF(x) = x^dbe a non-Gold APN power function or the inverse functionover${\mathbb F}_{2^n}$. Then, forF CCZ-equivalence coincides with EA-equivalence together with theinverse transformation (when applicable).

Applying Procedure 4.4 to the non-Gold APN power functions, we were able to obtain only linear permutations $\mathscr{L}$ that can be reduced to at most the case $\mathscr{A} Inv\mathscr{A}$, where we repeat the inverse transformation at most one time. However, note that there are cases different from ones described in Theorem 4.10. In general, if a CCZ-transformation of a given function can be decomposed into sequence of EA- and inverse transformations, then we may need to apply the inverse transformation more than one or two times. For example, let us consider n = 4. The full classification of all the bijective maps in 4-bit was obtained in [22]. We consider the following permutation

$$ \begin{array}{@{}rcl@{}} F(x)&= &u^{10}x^{14} + u^{5}x^{13} + u^{10}x^{12} + x^{11} + u^{8}x^{10} + u^{11}x^{9} + u^{12}x^{8}\\ &&+ u^{11}x^{7} + u^{4}x^{6} + u^{10}x^{5} + x^{4} + u^{10}x^{2} + u^{11}x, \end{array} $$

where u is a primitive element of $\mathbb F_{2^{4}}$. In the CCZ-class of F we have only five EA-classes containing a permutation, that is

$$ \begin{array}{@{}rcl@{}} &&EA_{1}\text{ represented by} \quad \quad~~~ ~~F_{1}(x)=u^{6}x^{14}+u^{5}x^{13}+u^{9}x^{12}+u^{11}x^{10}+u^{11}x^{9}+u^{3}x^{8}+\\ && \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad ~u^{7}x^{7}+u^{13}x^{5}+u^{4}x^{4}+u^{14}x^{3}+u^{6}x^{2}+u^{14}x,\\ &&EA_{2}\text{ represented by} \quad F_{2}(x)= u^{10}x^{14}+u^{5}x^{13}+u^{10}x^{12}+x^{11}+u^{8}x^{10}+u^{11}x^{9}+u^{12}x^{8}\\ && \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad{}+u^{11}x^{7}+u^{4}x^{6}+u^{10}x^{5}+x^{4}+u^{10}x^{2}+u^{11}x,\\ &&EA_{3}\text{ represented by}\quad~ F_{3}(x)= u^{6}x^{14}+u^{12}x^{13}+u^{2}x^{12}+u^{11}x^{11}+u^{9}x^{10}+ux^{9}+u^{3}x^{8}\\ &&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+u^{9}x^{7}+u^{10}x^{6}+u^{7}x^{4}+u^{5}x^{3}+u^{14}x^{2}+x,\\ &&EA_{4}\text{ represented by} \quad~~ F_{4}(x)=u^{6}x^{14}+u^{4}x^{13}+u^{14}x^{12}+ux^{11}+u^{6}x^{10}+u^{5}x^{9}+u^{7}x^{8}\\ && \qquad\qquad\qquad\qquad\qquad\qquad\quad\quad{} +u^{12}x^{7}+u^{8}x^{6}+u^{10}x^{5}+u^{8}x^{4}+u^{9}x^{3}+ux^{2}+u^{2}x,\\ &&EA_{5}\text{represented by} \quad~~~{} F_{5}(x)= u^{6}x^{14}+ux^{13}+ux^{12}+u^{8}x^{11}+u^{5}x^{10}+u^{7}x^{9}+u^{9}x^{8}+\\ && \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad~ u^{13}x^{7}+u^{3}x^{6}+u^{4}x^{5}+u^{8}x^{4}+u^{11}x^{3}+ux. \end{array} $$

If we consider the graph whose nodes are EA₁,EA₂,EA₃,EA₄ and EA₅ and we create an edge between two nodes EA_i and EA_j whenever there exists a permutation F^′ in EA_i such that F^′− 1 is in EA_j, then we obtain the relations between EA-equivalence classes presented in the graph of Fig. 1.

Fig. 1

Graph of connection between EA-classes through inverse transformation

Thus, any CCZ-transformation necessary for going from EA₁ to EA₅, in the decomposition in EA- and inverse transformations needs at least 4 inverse transformations.

5 On functions not equivalent to quadratic functions

For quadratic APN functions it is known that applying CCZ-equivalence it is possible to obtain functions which cannot be obtained using EA-equivalence and the inverse transformation only, see for instance [8], for the case of Gold functions, or also the APN permutation in dimension six introduced by Dillon et al. in [4] which was constructed by applying CCZ-equivalence to the so-called Kim function, which is quadratic (and inequivalent to a Gold function). In the following we provide an example which shows for the first time that CCZ-equivalence is more general than EA-equivalence together with inverse transformation also for non quadratic APN functions.

Let n = 6, and $F:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$ be

$$ \begin{array}{@{}rcl@{}} F(x)&=&x^{3} + u^{17}(x^{17} + x^{18} + x^{20} + x^{24}) +u^{14}((u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})+\\ &&(u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})^{2} + (u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})^{4}+\\ &&(u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})^{8} + (u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})^{16}+\\ &&(u^{52}x^{3} + u^{6}x^{5} + u^{19}x^{7} + u^{28}x^{11} + u^{2}x^{13})^{32} + (u^{2}x)^{9} + (u^{2}x)^{18} +(u^{2}x)^{36} +x^{21}+x^{42}), \end{array} $$

where u is a primitive element of ${\mathbb F}_{2^n}$. The function F is the first (and only currently known) example of an APN function CCZ-inequivalent to quadratic functions and to power functions (see [3, 17]). Using the procedure described in the previous section it is possible to construct the functions A₁ and A₂ given by

$$ A_{1}(x)=u^{50}x^{32} + u^{51}x^{16} + u^{43}x^{8} + ux^{4} + u^{26}x^{2} + u^{26}x$$

and

$$ A_{2}(x)=u^{26}x^{32} + u^{17}x^{16} + u^{56}x^{8} + u^{9}x^{4} + u^{54}x^{2} + u^{46}x,$$

so that F₁(x) = L₁(x, F(x)) = A₁(x) + A₂ ∘ F(x) is a permutation of ${\mathbb F}_{2^n}$. Now considering the function F₂(x) = L₂(x, F(x)) = F(x) we have that F is CCZ-equivalente to $F^{\prime }=F_{2}\circ F_{1}^{-1}$ having univariate polynomial representation

$$ \begin{array}{@{}rcl@{}} F^{\prime}(x)&=&u^{41}x^{60}+ u^{29}x^{58}+ u^{46}x^{57}+ u^{3}x^{56}+ u^{39}x^{54}+ u^{47}x^{53}+ u^{3}x^{52}+ u^{62}x^{51}+ u^{54}x^{50}+\\ && u^{62}x^{49}+ u^{53}x^{48}+ u^{14}x^{46}+ u^{39}x^{45}+ u^{20}x^{44}+ u^{26}x^{43 } + u^{11}x^{42}+ u^{31}x^{41}+ u^{53}x^{40}+\\ && u^{59}x^{39}+ u^{53}x^{38}+ u^{41}x^{37}+ u^{19}x^{36}+ u^{58}x^{35}+ u^{2}x^{34}+ u^{7}x^{33}+ u^{39}x^{32}+ u^{15}x^{30}+ \\ &&u^{17}x^{29}+ u^{45}x^{28}+ u^{39}x^{27}+ u^{57}x^{26}+ u^{33}x^{25}+ u^{61}x^{24}+ u^{41}x^{23}+ u^{50}x^{22}+ u^{58}x^{21}+\\ && u^{55}x^{20}+ u^{26}x^{19}+ u^{17}x^{18}+ u^{37}x^{17}+ u^{30}x^{16}+ ux^{15}+ u^{46}x^{14}+ u^{21}x^{13}+ u^{13}x^{12}+ \\ &&u^{61}x^{11}+ u^{20}x^{10}+ x^{9}+ u^{61}x^{8}+ u^{32}x^{7}+ u^{44}x^{6} + u^{62}x^{5} + u^{16}x^{4} + u^{48}x^{3}+ u^{58}x^{2}+ u^{37}x. \end{array} $$

The function F^′ cannot be constructed from F via EA-equivalence and inverse transformation. Indeed $F\nsim _{EA}F^{\prime }$ since F has algebraic degree 3 and F^′ algebraic degree 4. Moreover, to apply the inverse transformation, at least once, we need F ∼_EAG with G a permutation, but since F has quadratic components, as for example

$$ \begin{array}{@{}rcl@{}} Tr(F(x))&=&u^{15}x^{48} + u^{60}x^{40} + u^{36}x^{36} + u^{51}x^{34} + u^{30}x^{33} + u^{39}x^{24} + u^{30}x^{20} + \\ &&u^{18}x^{18} + u^{57}x^{17} + u^{51}x^{12} + u^{15}x^{10} + u^{9}x^{9} + u^{57}x^{6} + u^{39}x^{5} + u^{60}x^{3}, \end{array} $$

this cannot be possible (see [9, Corollary 3.8]).

6 Some remarks on functions with linear structures

In the previous section we showed that also for functions CCZ-inequivalent to a quadratic function CCZ-equivalence is more general than EA-equivalence with the inverse transformation. Recall that the function studied in Section 5 has some quadratic components and any non bent quadratic function has at least one linear structure. In this section we will report some considerations that can explain why for functions with components having some linear structures it is more likely that CCZ-equivalence is more general than EA-equivalence with inverse transformation.

We recall that $\alpha \in {\mathbb F}_{2^n}$ is a c-linear structure, with $c\in {\mathbb F}_{2}$, of a Boolean function $f:{\mathbb F}_{2^n}\to {\mathbb F}_{2}$ if f(x + α) + f(x) = c for all $x\in {\mathbb F}_{2^n}$. For a vectorial Boolean function $F:{\mathbb F}_{2^n}\to {\mathbb F}_{2^n}$ we say that F has a linear structure if there exists a component Tr(γF), with γ≠ 0, of F which has a linear structure.

In [12], the authors study permutation polynomials (PP) of type G(x) + γTr(F(x)). In particular when G(x) is a linearized polynomial from the results in [12] we have directly the following.

Lemma 6.1

[12] Let$L,F : {\mathbb F}_{2^n} \to {\mathbb F}_{2^n}$withL a linear polynomial. Then we have the following properties:

• i)ifL(x) + γTr(F(x)) is PP thenL is a PP or is a 2-to-1 map.

• ii)IfL is a PP, thenL(x) + γTr(F(x)) is a PP if and only ifF(x) = R(L(x)) for some polynomial R andγis a 0-linear structure ofTr(R(x)) (and in particularL^− 1(γ) is a 0-linear structure ofTr(F(x))).

• iii)IfL is a 2-to-1 map with kernel{0,α},thenL(x) + γTr(F(x)) is a PP if and only ifγis not in the image ofL andαis a 1-linear structure ofTr(F(x)).

Corollary 6.2

IfL(x) + γTr(F(x)) is a PP thenF has a linear structure.

So, given a function F defined over ${\mathbb F}_{2^n}$ with a component having some linear structure, from Lemma 6.1 we can obtain some linear functions $L_{1}:({\mathbb F}_{2^n})^{2}\to {\mathbb F}_{2^n}$ such that F₁(x) = L₁(x, F(x)) is a permutation. Indeed, another direct consequence of Lemma 6.1 is the following.

Proposition 6.3

Let$F: {\mathbb F}_{2^n} \to {\mathbb F}_{2^n}$. Then there exists a linear functionL₁(x, y) = A₁(x) + A₂(y) such thatL₁(x, F(x)) is a permutation andA₂has rank 1 if and only ifF has at least one component with a linear structure.

Proof

Since A₂ has rank 1, then $\Im (A_{2})=\gamma {\mathbb F}_{2}$ for some $\gamma \in {\mathbb F}_{2^n}$. Moreover, any linear transformations from ${\mathbb F}_{2^n}$ to ${\mathbb F}_{2}$ is of the type Tr(λx) with $\lambda \in {\mathbb F}_{2^n}$. Thus, we can suppose that L₁(x, y) = A₁(x) + γTr(λy) for some $\gamma ,\lambda \in {\mathbb F}_{2^n}$ and from Corollary 6.2 we have that if F₁(x) = L₁(x, F(x)) is a permutation, then F has a linear structure.

Vice versa, suppose that γ is a 0-linear structure of the component Tr(λF(x)). Then, it follows from Lemma 6.1 that

$$ x+\gamma Tr(\lambda F(x)) $$

is a PP. Let now γ be a 1-linear structure of the component Tr(λF(x)). Then, similarly from Lemma 6.1 if Tr(γ) = 1 we have that

$$ x+\gamma Tr(\lambda F(x)+x) $$

is a PP (note that γ∉I(x + γTr(x))). If Tr(γ) = 0, then we can consider any element 𝜃 such that Tr(γ𝜃) = 1. Then, already for iii) of Lemma 6.1,

$$ x+\gamma Tr(\theta x)+\gamma Tr(\lambda F(x)) $$

is a PP. □

This result has been obtained, independently, in [10] Corollary 2 in terms of function twisting (introduced always in [10]).

From Proposition 6.3 we obtained a possible function L₁(x, y) = A₁(x) + A₂(y) such that F₁(x) = L₁(x, F(x)) is a permutation, when F has a linear structure. In the following, we will construct a function F^′ CCZ-equivalent to F, using this type of linear function L₁(x, y).

First of all, note that the functions constructed in Proposition 6.3

$$ F_{1}(x)=x+\gamma Tr(\lambda F(x)) $$

when γ is a 0-linear structure of the component Tr(λF(x)), and

$$ F^{\prime}_{1}(x)=x+\gamma Tr(\lambda F(x)+\theta x), $$

with 𝜃 as in Proposition 6.3, when γ is a 1-linear structure, are involutions. Indeed,

$$ \begin{array}{@{}rcl@{}} F_{1}\circ F_{1}(x)&=&x+\gamma Tr(\lambda F(x))+\gamma Tr(\lambda F(x+\gamma tr(\lambda F(x))))\\ &=&\left\{\begin{array}{cc} x &\text{ if } \ Tr(\lambda F(x))=0~.\\ x+\gamma Tr(\lambda F(x)+\lambda F(x+\gamma))=x &\text{ if}\ Tr(\lambda F(x))=1 \end{array}\right. \end{array} $$

It is similar for $F^{\prime }_{1}$, we just need to verify the cases (Tr(𝜃x),Tr(λF(x))) = (0,0),(1,0),(0,1) and (1,1).

Now, for the case F₁(x) = x + γTr(λF(x)), we have L₁(x, y) = x + γTr(λy) and, considering the linear function L₂(x, y) = y, we get the linear permutation $\mathscr{L}(x,y)=(L_{1}(x,y),L_{2}(x,y))$. Denoting F₂(x) = L₂(x, F(x)) = F(x), this permutation permits to obtain the equivalent function

$$ F^{\prime}(x)=F_{2}\circ F_{1}(x)=F(x+\gamma Tr(\lambda F(x))=F(x)+Tr(\lambda F(x))(F(x)+F(x+\gamma)). $$

(7)

Similarly, for $F^{\prime }_{1}(x)=x+\gamma Tr(\lambda F(x)+\theta x)$ we can consider L₂(x, y) = y + γTr(𝜃x), that is F₂(x) = F(x) + γTr(𝜃x) and

$$ \begin{array}{@{}rcl@{}} F^{\prime}(x) = F_{2}\circ F_{1}^{\prime}(x)\!&=&F(x+\gamma Tr(\lambda F(x)+\theta x))+\gamma Tr(x+\gamma Tr(\lambda F(x)+\theta x))\\ &=&F(x) + Tr(\lambda F(x) + \theta x)(F(x)\!+F(x+\gamma)+\gamma Tr(1))+\gamma Tr(\theta x).\\ \end{array} $$

(8)

We can note that in both cases we are multiplying the component Tr(λF(x)) with the derivative F(x) + F(x + γ), such a multiplication could change the degree of the resulting function. In the case of quadratic functions such a transformation could lead to a function of degree 3.

For the particular case of quadratic function, this has been also observed in [10] in terms of function twisting.

In [8], the authors constructed some permutation polynomials as those described in Proposition 6.3. Applying these polynomials to the Gold power functions $x^{2^{i}+1}$, they obtained, in the same way described for (7) and (8), functions EA-inequivalent to any power functions.

7 Conclusions

We have investigated the problem if for a given APN function F the class of CCZ-equivalent functions can be obtained by EA-equivalence and the inverse transformation (when applicable) only. Such a problem was investigated also in [5, 6, 8] for the case of quadratic APN functions, in particular for the Gold functions. We characterized some linear permutations on $({\mathbb F}_{2^n})^{2}$ which imply that the equivalence between two functions F and F^′ can be obtained via EA-equivalence and inverse transformation. We also gave a procedure to verify if a sufficient condition (Theorem 4.9), implying that CCZ-equivalence coincides with EA-equivalence and inverse transformation, holds. Using this procedure, we proved that also for APN functions CCZ-inequivalent to quadratic functions CCZ-equivalence can be more general than EA-equivalence and inverse. On the contrary, with the same procedure we were able to verify, up to dimension 8, that for the non-Gold APN power functions the class of CCZ-equivalent functions can be obtained using only EA-equivalence and the inverse transformation. This leads us to a conjecture that for all non-Gold APN power functions and the inverse function CCZ-equivalence coincides with EA-equivalence together with the inverse transformation.