# Difference between revisions of "Equivalence Relations"

m |
m |
||

Line 31: | Line 31: | ||

* 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>], <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 multiplier group ℳ(𝐺<sub>𝐹</sub>) is CCZ-invariant. | * For APN maps, the 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>). |

## Revision as of 15:34, 2 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 .

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 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(𝐺_{𝐹}).