Equivalence Relations

From Boolean
Revision as of 13:37, 2 October 2019 by Ivi062 (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision β†’ (diff)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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