Equivalence Relations: Difference between revisions

From Boolean
Jump to navigation Jump to search
Line 30: Line 30:
* The Walsh spectrum is invariant under affine equivalence but in general not under EA- and 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.
* 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 𝐺<sub>𝐹</sub> in 𝔽[𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub><sup>𝑛</sup>]
To define such ranks let consider 𝐹 a (𝑛,𝑛)-function and associate a group algebra element 𝐺<sub>𝐹</sub> in 𝔽[𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub><sup>𝑛</sup>]<math>G_F=\sum_{v\in\mathbb{F}_2^n}(v,F(v)).</math>
<center><math>G_F=\sum_{v\in\mathbb{F}_2^n}(v,F(v)).</math></center>
We have that for 𝐹 APN there exist some subset 𝐷<sub>𝐹</sub>∈𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub> <sup>𝑛</sup>∖{(0,0)} such that <math>G_F\cdot G_F =2^n\cdot(0,0)+2\cdot D_F.</math>
We have that for 𝐹 APN there exist some subset 𝐷<sub>𝐹</sub>∈𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub><sup>𝑛</sup>∖{(0,0)} such that
For the incidence structure with blocks   <math>G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \},</math>
<center><math>G_F\cdot G_F =2^n\cdot(0,0)+2\cdot D_F.</math></center>
for 𝑎,𝑏∈𝔽<sub>2</sub><sup>𝑛</sup>, the related incidence matrix is constructed, indixed by points and blocks, as follow:
For the incidence structure with blocks  
the (𝑝,𝐵)-entry is 1 if point 𝑝 is incident with block 𝐵, is 0 otherwise.
<center><math>G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \},</math></center>
The same can be done for 𝐷<sub>𝐹</sub>.
for 𝑎,𝑏∈𝔽<sub>2</sub><sup>𝑛</sup>, the related incidence matrix is constructed, indixed by points and blocks, as follow:
Hence we have that
the (𝑝,𝐵)-entry is 1 if point 𝑝 is incident with block 𝐵, is 0 otherwise.
  * the Γ-rank is the rank of the incidence matrix of dev(𝐺<sub>𝐹</sub>) over 𝔽<sub>2</sub>,
The same can be done for 𝐷<sub>𝐹</sub>.
* the Δ-rank is the 𝔽<sub>2</sub>-rank of an incidence matrix of dev(𝐷<sub>𝐹</sub>).
Hence we have that
  -- the Γ-rank is the rank of the incidence matrix of dev(𝐺<sub>𝐹</sub>) over 𝔽<sub>2</sub>,
-- the Δ-rank is the 𝔽<sub>2</sub>-rank of an incidence matrix of dev(𝐷<sub>𝐹</sub>).

Revision as of 13:43, 2 October 2019

Some known Equivalence Relations

Two vectorial Boolean functions [math]\displaystyle{ F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m }[/math] are called

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

Clearly, it is possible to estend such definitions also for maps [math]\displaystyle{ F,F':\mathbb{F}_p^n\rightarrow\mathbb{F}_p^m }[/math], 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𝑛],  [math]\displaystyle{ G_F=\sum_{v\in\mathbb{F}_2^n}(v,F(v)). }[/math]
We have that for 𝐹 APN there exist some subset 𝐷𝐹∈𝔽2𝑛×𝔽2 𝑛∖{(0,0)} such that  [math]\displaystyle{ G_F\cdot G_F =2^n\cdot(0,0)+2\cdot D_F. }[/math]
For the incidence structure with blocks   [math]\displaystyle{ G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \}, }[/math]
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(𝐷𝐹).