Equivalence Relations

Some known Equivalence Relations

Two vectorial Boolean functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m} are called

• affine (linear) equivalent if there exist Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,A_2} affine (linear) permutations of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^m} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^n} respectively, such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'=A_1\circ F\circ A_2} ;
• extended affine equivalent (shortly EA-equivalent) if there exists Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m} affine such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'=F''+A} , with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F''} affine equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} ;
• Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_2^n\times\mathbb{F}_2^m} such that the image of the graph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} is the graph of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F'} , i.e. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{L}(G_F)=G_{F'}} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 𝔽[𝔽₂^𝑛×𝔽₂^𝑛]

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_F=\sum_{v\in\mathbb{F}_2^n}(v,F(v)).}

We have that for 𝐹 APN there exist some subset 𝐷_𝐹∈𝔽₂^𝑛×𝔽₂^𝑛∖{(0,0)} such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_F\cdot G_F =2^n\cdot(0,0)+2\cdot D_F.}

For the incidence structure with blocks

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \},}

for 𝑎,𝑏∈𝔽₂^𝑛, 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 𝔽₂-rank of an incidence matrix of dev(𝐷_𝐹).