# Some known Equivalence Relations

Two vectorial Boolean functions ${\displaystyle F,F':\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}}$ are called

• affine (linear) equivalent if there exist ${\displaystyle A_{1},A_{2}}$ affine (linear) permutations of ${\displaystyle \mathbb {F} _{2}^{m}}$ and ${\displaystyle \mathbb {F} _{2}^{n}}$ respectively, such that ${\displaystyle F'=A_{1}\circ F\circ A_{2}}$;
• extended affine equivalent (shortly EA-equivalent) if there exists ${\displaystyle A:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}}$ affine such that ${\displaystyle F'=F''+A}$, with ${\displaystyle F''}$ affine equivalent to ${\displaystyle F}$;
• Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation ${\displaystyle {\mathcal {L}}}$ of ${\displaystyle \mathbb {F} _{2}^{n}\times \mathbb {F} _{2}^{m}}$ such that the image of the graph of ${\displaystyle F}$ is the graph of ${\displaystyle F'}$, i.e. ${\displaystyle {\mathcal {L}}(G_{F})=G_{F'}}$ with ${\displaystyle G_{F}=\{(x,F(x)):x\in \mathbb {F} _{2}^{n}\}}$ and ${\displaystyle G_{F'}=\{(x,F'(x)):x\in \mathbb {F} _{2}^{n}\}}$.

Clearly, it is possible to estend such definitions also for maps ${\displaystyle F,F':\mathbb {F} _{p}^{n}\rightarrow \mathbb {F} _{p}^{m}}$, for π a general prime number.

## Connections between different relations

Such equivalence relations are connected to each other. Obviously affine equivalence is a general case of linear equivalence and they are both a particular case of the EA-equivalence. Moreover, EA-equivalence is a particular case of CCZ-equivalence and each permutation is CCZ-equivalent to its inverse.

In particular we have that CCZ-equivalence coincides with

• EA-equivalence for planar functions,
• linear equivalence for DO planar functions,
• EA-equivalence for all Boolean functions,
• EA-equivalence for all bent vectorial Boolean functions,
• EA-equivalence for two quadratic APN functions.

# Invariants

• The algebraic degree (if the function is not affine) is invariant under EA-equivalence but in general is not preserved under CCZ-equivalence.
• The differential uniformity is invariant under CCZ-equivalence. (CCZ-equivalence relation is the most general known equivalence relation preserving APN and PN properties)

## Invariants in even characteristic

We consider now functions over π½2π.

• The nonlinearity and the extended Walsh spectrum are invariant under CCZ-equivalence.
• The Walsh spectrum is invariant under affine equivalence but in general not under EA- and CCZ-equivalence.
• For APN maps we have also that Ξ- and Ξ-ranks are invariant under CCZ-equivalence.
To define such ranks let consider πΉ a (π,π)-function and associate a group algebra element πΊπΉ in π½[π½2πΓπ½2π], ${\displaystyle G_{F}=\sum _{v\in \mathbb {F} _{2}^{n}}(v,F(v)).}$
We have that for πΉ APN there exist some subset π·πΉβπ½2πΓπ½2πβ{(0,0)} such that ${\displaystyle G_{F}\cdot G_{F}=2^{n}\cdot (0,0)+2\cdot D_{F}.}$
For the incidence structure dev(πΊπΉ) with blocks ${\displaystyle G_{F}\cdot (a,b)=\{(x+a,F(x)+b):x\in \mathbb {F} _{2}^{n}\},}$
for π,πβπ½2π, the related incidence matrix is constructed, indixed by points and blocks, as follow:
the (π,π΅)-entry is 1 if point π is incident with block π΅, is 0 otherwise.
The same can be done for π·πΉ.
Hence we have that
* the Ξ-rank is the rank of the incidence matrix of dev(πΊπΉ) over π½2,
* the Ξ-rank is the π½2-rank of an incidence matrix of dev(π·πΉ).
Equivalently the Ξ-rank is the dimension of the ideal generated by πΊπΉ in π½2[π½2πΓπ½2π] and the Ξ-rank is the dimension of the ideal generated by π·πΉ in π½2[π½2πΓπ½2π].

• For APN maps, the multiplier group β³(πΊπΉ) is CCZ-invariant.
The multiplier group β³(πΊπΉ) of dev(πΊπΉ) is the set of automorphism Ο of π½22π such that Ο(πΊπΉ)=πΊπΉβ(π’,π£) for some π’,π£βπ½2π. Such automorphisms form a group contained in the automorphism group of dev(πΊπΉ).