Equivalence Relations

Some known Equivalence Relations

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

• affine (linear) equivalent if there exist $A_{1},A_{2}$ affine (linear) permutations of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{2}^{m}} and $\mathbb {F} _{2}^{n}$ respectively, such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'=A_{1}\circ F\circ A_{2}} ;
• extended affine equivalent (shortly EA-equivalent) if there exists Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A:\mathbb {F} _{2}^{n}\rightarrow \mathbb {F} _{2}^{m}} affine such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F'=F''+A} , with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F''} affine equivalent to $F$;
• Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation ${\mathcal {L}}$ of Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \mathbb {F} _{2}^{n}\times \mathbb {F} _{2}^{m}} such that the image of the graph of $F$ is the graph of $F'$, i.e. Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {L}}(G_{F})=G_{F'}} with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{F}=\{(x,F(x)):x\in \mathbb {F} _{2}^{n}\}} and Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{F'}=\{(x,F'(x)):x\in \mathbb {F} _{2}^{n}\}} .

Clearly, it is possible to estend such definitions also for maps Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 𝔽₂^𝑛.

• 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𝑛], Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{F}=\sum _{v\in \mathbb {F} _{2}^{n}}(v,F(v)).}

We have that for 𝐹 APN there exists some subset 𝐷𝐹∈𝔽2𝑛×𝔽2𝑛∖{(0,0)} such that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G_{F}\cdot G_{F}=2^{n}\cdot (0,0)+2\cdot D_{F}.}

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𝑛].
Equivalently 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(𝐷𝐹).
For the incidence structure dev(𝐺𝐹) with blocks Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 𝐷𝐹.

• 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(𝐺𝐹).