Equivalence Algorithms
The hierarchy of equivalences
Given two vectorial boolean functions [math]\displaystyle{ f,g : F_2^n \rightarrow F_2^n }[/math] there are various ways to define equivalence between [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math]. 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 [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] we want to determine if there exist Linear permutations [math]\displaystyle{ A_1 }[/math] and [math]\displaystyle{ A_2 }[/math] such that [math]\displaystyle{ f = A_2 \circ g \circ A_1 }[/math].
The to and from algorithm
This algorithm is presented at eurocrypt 2003 [1]. This algorithm is mainly intended for when the boolean functions are permutation, and we will start by assuming [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] are permutations.
The idea of the algorithm is to go use information gather about [math]\displaystyle{ A_1 }[/math] to deduce information about [math]\displaystyle{ A_2 }[/math] and the other way around. To see how this can work let's say we know some values of [math]\displaystyle{ A_1 }[/math], lets say [math]\displaystyle{ A_1(x_1)=y_1, A_2(x_2) = y_2,..., A_1(x_n) = y_n }[/math].
- ↑ Biryukov, Alex, et al. "A toolbox for cryptanalysis: Linear and affine equivalence algorithms." Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22. Springer Berlin Heidelberg, 2003.