Difference between revisions of "Equivalence Relations"

From Boolean Functions
Jump to: navigation, search
(β†’β€ŽInvariants in even characteristic)
m
 
(4 intermediate revisions by the same user not shown)
Line 3: Line 3:
 
* affine (linear) equivalent if there exist <math>A_1,A_2</math> affine (linear) permutations of <math>\mathbb{F}_2^m</math> and <math>\mathbb{F}_2^n</math> respectively, such that <math>F'=A_1\circ F\circ A_2</math>;
 
* affine (linear) equivalent if there exist <math>A_1,A_2</math> affine (linear) permutations of <math>\mathbb{F}_2^m</math> and <math>\mathbb{F}_2^n</math> respectively, such that <math>F'=A_1\circ F\circ A_2</math>;
 
* extended affine equivalent (shortly EA-equivalent) if there exists <math>A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> affine such that <math>F'=F''+A</math>, with <math>F''</math> affine equivalent to <math>F</math>;
 
* extended affine equivalent (shortly EA-equivalent) if there exists <math>A:\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> affine such that <math>F'=F''+A</math>, with <math>F''</math> affine equivalent to <math>F</math>;
βˆ’
* Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_2^n\times\mathbb{F}_2^m</math> such that the image of the graph of <math>F</math> is the graph of <math>F'</math>, i.e. <math>\mathcal{L}(G_F)=G_{F'}</math> with <math>G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\}</math> and <math>G_{F'}=\{ (x,F'(x)) : x\in\mathbb{F}_2^n\}</math>.
+
* Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation <math>\mathcal{L}</math> of <math>\mathbb{F}_2^n\times\mathbb{F}_2^m</math> such that the image of the graph of <math>F</math> is the graph of <math>F'</math>, i.e. <math>\mathcal{L}(G_F)=G_{F'}</math> with <math>G_F=\{ (x,F(x)) : x\in\mathbb{F}_2^n\}</math> and <math>G_{F'}=\{ (x,F'(x)) : x\in\mathbb{F}_2^n\}</math> ([[:File:CCZeq2.txt|magma code]]).
  
 
Clearly, it is possible to estend such definitions also for maps <math>F,F':\mathbb{F}_p^n\rightarrow\mathbb{F}_p^m</math>, for 𝑝 a general prime number.
 
Clearly, it is possible to estend such definitions also for maps <math>F,F':\mathbb{F}_p^n\rightarrow\mathbb{F}_p^m</math>, for 𝑝 a general prime number.
Line 29: Line 29:
 
* The nonlinearity and the extended Walsh spectrum are invariant under CCZ-equivalence.
 
* 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.
 
* 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 [[:File:DeltaRank.txt|Ξ”-rank]] and [[:File:GammaRank.txt|Ξ“-rank]] 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>], <math>G_F=\sum_{v\in\mathbb{F}_2^n}(v,F(v)).</math>
+
  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>
βˆ’
  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 exists 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>
βˆ’
  For the incidence structure with blocks   <math>G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \},</math>
+
The Ξ“-rank is the dimension of the ideal generated by 𝐺<sub>𝐹</sub> in 𝔽<sub>2</sub>[𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub><sup>𝑛</sup>] and the Ξ”-rank is the dimension of the ideal generated by 𝐷<sub>𝐹</sub> in 𝔽<sub>2</sub>[𝔽<sub>2</sub><sup>𝑛</sup>×𝔽<sub>2</sub><sup>𝑛</sup>].
βˆ’
for π‘Ž,π‘βˆˆπ”½<sub>2</sub><sup>𝑛</sup>, the related incidence matrix is constructed, indixed by points and blocks, as follow:
+
Equivalently 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>).
 +
  For the incidence structure dev(𝐺<sub>𝐹</sub>) with blocks <math>G_F\cdot(a,b)=\{(x+a,F(x)+b) : x\in\mathbb{F}_2^n \},</math> for π‘Ž,π‘βˆˆπ”½<sub>2</sub><sup>𝑛</sup>, 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 (𝑝,𝐡)-entry is 1 if point 𝑝 is incident with block 𝐡, is 0 otherwise.
 
  The same can be done for 𝐷<sub>𝐹</sub>.
 
  The same can be done for 𝐷<sub>𝐹</sub>.
βˆ’
Hence we have that
+
* For APN maps, the [[:File:MGF.txt|multiplier group β„³(𝐺<sub>𝐹</sub>)]] is CCZ-invariant.
βˆ’
* the Ξ“-rank is the rank of the incidence matrix of dev(𝐺<sub>𝐹</sub>) over 𝔽<sub>2</sub>,
+
The multiplier group β„³(𝐺<sub>𝐹</sub>) of dev(𝐺<sub>𝐹</sub>) is the set of automorphism Ο† of 𝔽<sub>2</sub><sup>2𝑛</sup> such that Ο†(𝐺<sub>𝐹</sub>)=𝐺<sub>𝐹</sub>β‹…(𝑒,𝑣) for some 𝑒,π‘£βˆˆπ”½<sub>2</sub><sup>𝑛</sup>. Such automorphisms form a group contained in the automorphism group of dev(𝐺<sub>𝐹</sub>).
βˆ’
* the Ξ”-rank is the 𝔽<sub>2</sub>-rank of an incidence matrix of dev(𝐷<sub>𝐹</sub>).
 

Latest revision as of 15:58, 11 October 2019

Some known Equivalence Relations

Two vectorial Boolean functions are called

  • affine (linear) equivalent if there exist affine (linear) permutations of and respectively, such that ;
  • extended affine equivalent (shortly EA-equivalent) if there exists affine such that , with affine equivalent to ;
  • Carlet-Charpin-Zinoviev equivalent (shortly CCZ-equivalent) if there exists an affine permutation of such that the image of the graph of is the graph of , i.e. with and (magma code).

Clearly, it is possible to estend such definitions also for maps , 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 Ξ”-rank and Ξ“-rank are invariant under CCZ-equivalence.
To define such ranks let consider 𝐹 a (𝑛,𝑛)-function and associate a group algebra element 𝐺𝐹 in 𝔽[𝔽2𝑛×𝔽2𝑛], 
We have that for 𝐹 APN there exists some subset π·πΉβˆˆπ”½2𝑛×𝔽2π‘›βˆ–{(0,0)} such that 
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  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 𝐷𝐹.
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(𝐺𝐹).