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 was 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 gathered 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 value of [math]\displaystyle{ A_1 }[/math], lets say [math]\displaystyle{ A_1(x) = y }[/math]. We of course also know the value of [math]\displaystyle{ G }[/math] at [math]\displaystyle{ y }[/math] so lets say that [math]\displaystyle{ G(y) = z }[/math]. Then we know that [math]\displaystyle{ F(x) = A_2 \circ G \circ A_1(x) = A_2 \circ G(y) = A_2(z) }[/math]. So we now know that [math]\displaystyle{ A_2(z) }[/math] must be equal to [math]\displaystyle{ G(y) }[/math].
For the other way around let's say we know some value of [math]\displaystyle{ A_2 }[/math], lets say [math]\displaystyle{ A_2(x) = y }[/math]. We know the value of [math]\displaystyle{ F^{-1} }[/math] at y, lets say [math]\displaystyle{ F^{-1}(y) = z }[/math]. Then we know that [math]\displaystyle{ F(z) = y = A_2 \circ G \circ A_1(z) }[/math] so we see that [math]\displaystyle{ A_2 \circ G \circ A_1(z) = y }[/math]. Since we know that [math]\displaystyle{ A_2(x) = y }[/math] we need [math]\displaystyle{ G \circ A_1(z) = x }[/math], which must mean that [math]\displaystyle{ A_1(z) = G^{-1}(y) }[/math].
So we now showed how we can deduce information knowing either a value of [math]\displaystyle{ A_1 }[/math] or [math]\displaystyle{ A_2 }[/math]. Now lets say we now the values of [math]\displaystyle{ A_1 }[/math] at a set of points. Since [math]\displaystyle{ A_1 }[/math] is linear we also know it's value at any linear combinations of these points so we can just assume that we know the values at [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ k }[/math] linear independent points, which means that we know the value of [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ 2^k }[/math] points. If we now somehow gain value of a point of [math]\displaystyle{ A_1 }[/math] which is not in the span of the already known points then we can deduce the value of [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ 2^k }[/math] new points using any linear combination of points including this new point. Then we can use all of these new points and try to deduce points of [math]\displaystyle{ A_2 }[/math] as explained before. We will now explain the complete algorithm before giving the psudocode.
Given two permutations [math]\displaystyle{ F,G : F_2^n \rightarrow F_2^m }[/math] we construct the linear permutations $A_1,A_2$. The algorithm is a backtracking algorithm, and whenever we discover a contradiction we backtrack to the last guess. We first guess two values of [math]\displaystyle{ A_1(x) }[/math]. Since we now know two values of [math]\displaystyle{ A_1 }[/math] we can two values of [math]\displaystyle{ A_2 }[/math], which means we can deduce a third value by linearity. Using this third value we can deduce a value of [math]\displaystyle{ A_1 }[/math], if this value is not in the span of the already known values of [math]\displaystyle{ A_1 }[/math] we can deduce two more values of [math]\displaystyle{ A_1 }[/math] and use this to deduce values of [math]\displaystyle{ A_1 }[/math] and so on. If we ever run out of values before we have finished we will have to make additional guesses. If we ever encounter that a situation where we deduce a value of [math]\displaystyle{ A_1 }[/math] or [math]\displaystyle{ A_2 }[/math], but we have already set them to be something else, we must backtrack to the last guess.
Here is the psudocode:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: f = x0*x1*x2*x3 + x0*x2*x3 + x1*x2*x3 + x0*x1 + x0*x3 + x1*x2 + x3 + 1
sage: F = BooleanFunction(f)
sage: F.algebraic_degree()
4
- ↑ 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.