Equivalence Algorithms

The hierarchy of equivalences

Given two vectorial boolean functions <math>F,G : F_2^n \rightarrow F_2^n </math> there are various ways to define equivalence between <math> f </math> and <math>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>f </math> and <math> g </math> we want to determine if there exist Linear permutations <math> A_1</math> and <math>A_2 </math> such that <math> F = A_2 \circ G \circ A_1 </math>.

The to and from algorithm

This algorithm was presented at eurocrypt 2003 . This algorithm is mainly intended for when the boolean functions are permutation, and we will start by assuming <math>F </math> and <math>G </math> are permutations.

The idea of the algorithm is to go use information gathered about <math>A_1 </math> to deduce information about <math>A_2 </math> and the other way around. To see how this can work let's say we know some value of <math>A_1 </math>, lets say <math>A_1(x) = y </math>. We of course also know the value of <math>G</math> at <math>y</math> so lets say that <math>G(y) = z </math>. Then we know that <math> 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>A_2(z) </math> must be equal to <math>G(y) </math>.

For the other way around let's say we know some value of <math>A_2 </math>, lets say <math>A_2(x) = y </math>. We know the value of <math> F^{-1} </math> at y, lets say <math>F^{-1}(y) = z </math>. Then we know that <math>F(z) = y = A_2 \circ G \circ A_1(z) </math> so we see that <math>A_2 \circ G \circ A_1(z) = y </math>. Since we know that <math>A_2(x) = y </math> we need <math>G \circ A_1(z) = x </math>, which must mean that <math>A_1(z) = G^{-1}(y)</math>.

So we now showed how we can deduce information knowing either a value of <math>A_1 </math> or <math>A_2</math>. Now lets say we now the values of <math>A_1 </math> at a set of points. Since <math>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>A_1</math> at <math>k</math> linear independent points, which means that we know the value of <math>A_1</math> at <math>2^k</math> points. If we now somehow gain value of a point of <math>A_1</math> which is not in the span of the already known points then we can deduce the value of <math>A_1 </math> at <math>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>A_2</math> as explained before. We will now explain the complete algorithm before giving the psudocode.

Given two permutations <math>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>A_1(x) </math>. Since we now know two values of <math>A_1 </math> we can two values of <math>A_2</math>, which means we can deduce a third value by linearity. Using this third value we can deduce a value of <math>A_1</math>, if this value is not in the span of the already known values of <math>A_1 </math> we can deduce two more values of <math>A_1 </math> and use this to deduce values of <math>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>A_1 </math> or <math>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