# Difference between revisions of "Equivalence Relations"

m |
m |
||

(2 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 Ξ- | + | * 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 | + | 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 dev(πΊ<sub>πΉ</sub>) 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>]. |

β | + | 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>. | ||

β | + | * For APN maps, the [[:File:MGF.txt|multiplier group β³(πΊ<sub>πΉ</sub>)]] is CCZ-invariant. | |

β | |||

β | |||

β | |||

β | |||

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 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>). |

## Latest revision as of 16:58, 11 October 2019

## Contents

# 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 π·_{πΉ}.

- For APN maps, the multiplier group β³(πΊ
_{πΉ}) is CCZ-invariant.

The multiplier group β³(πΊ_{πΉ}) of dev(πΊ_{πΉ}) is the set of automorphism Ο of π½_{2}^{2π}such that Ο(πΊ_{πΉ})=πΊ_{πΉ}β (π’,π£) for some π’,π£βπ½_{2}^{π}. Such automorphisms form a group contained in the automorphism group of dev(πΊ_{πΉ}).