Equivalence Algorithms

The hierarchy of equivalences

Given two vectorial boolean functions $f,g:F_{2}^{n}\rightarrow F_{2}^{n}$ there are various ways to define equivalence between $f$ and $g$. We will study the algorithms for determining Linear, Affine, Extended Affine and CCZ equivalence between vectorial boolean functions.

Linear Equivalence

Given two vectorial boolean functions $f$ and $g$ we want to determine if there exist Linear permutations $A_{1}$ and $A_{2}$ such that $f=A_{2}\circ g\circ A_{1}$.

The to and from algorithm

This algorithm is presented at eurocrypt 2003 . This algorithm is mainly intended for when the boolean functions are permutation, and we will start by assuming $f$ and $g$ are permutations.

The idea of the algorithm is to go use information gather about $A_{1}$ to deduce information about $A_{2}$ and the other way around. To see how this can work let's say we know some values of $A_{1}$, lets say $A_{1}(x_{1})=y_{1},A_{2}(x_{2})=y_{2},...,A_{1}(x_{n})=y_{n}$.