Difference between revisions of "Equivalence Relations"

From Boolean Functions
Jump to: navigation, search
(Created page with "=Some known Equivalence Relations = Two vectorial Boolean functions <math>F,F':\mathbb{F}_2^n\rightarrow\mathbb{F}_2^m</math> are called * affine (linear) equivalent if there...")
 
(β†’β€ŽInvariants in even characteristic)
Line 40: Line 40:
 
The same can be done for 𝐷<sub>𝐹</sub>.
 
The same can be done for 𝐷<sub>𝐹</sub>.
 
Hence we have that
 
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 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>).
+
-- the Ξ”-rank is the 𝔽<sub>2</sub>-rank of an incidence matrix of dev(𝐷<sub>𝐹</sub>).

Revision as of 14:41, 2 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 .

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 Ξ”- and Ξ“-ranks 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 exist some subset π·πΉβˆˆπ”½2𝑛×𝔽2π‘›βˆ–{(0,0)} such that

For the incidence structure 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 𝐷𝐹. 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(𝐷𝐹).