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 was 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 gathered 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 value of $A_{1}$, lets say $A_{1}(x)=y$. We of course also know the value of $G$ at $y$ so lets say that $G(y)=z$. Then we know that $F(x)=A_{2}\circ G\circ A_{1}(x)=A_{2}\circ G(y)=A_{2}(z)$. So we now know that $A_{2}(z)$ must be equal to $G(y)$.

For the other way around let's say we know some value of $A_{2}$, lets say Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A_{2}(x)=y} . We know the value of $F^{-1}$ at y, lets say $F^{-1}(y)=z$. Then we know that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F(z)=y=A_{2}\circ G\circ A_{1}(z)} so we see that $A_{2}\circ G\circ A_{1}(z)=y$. Since we know that Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A_{2}(x)=y} we need $G\circ A_{1}(z)=x$, which must mean that $A_{1}(z)=G^{-1}(y)$.

So we now showed how we can deduce information knowing either a value of $A_{1}$ or $A_{2}$. Now lets say we now the values of $A_{1}$ at a set of points. Since $A_{1}$ 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 $A_{1}$ at $k$ linear independent points, which means that we know the value of $A_{1}$ at Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{k}} points. If we now somehow gain value of a point of $A_{1}$ which is not in the span of the already known points then we can deduce the value of $A_{1}$ at $2^{k}$ 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 $A_{2}$ as explained before. We will now explain the complete algorithm before giving the psudocode.

Given two permutations $F,G:F_{2}^{n}\rightarrow F_{2}^{m}$ 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 $A_{1}(x)$. Since we now know two values of $A_{1}$ we can two values of $A_{2}$, which means we can deduce a third value by linearity. Using this third value we can deduce a value of $A_{1}$, if this value is not in the span of the already known values of $A_{1}$ we can deduce two more values of $A_{1}$ and use this to deduce values of $A_{1}$ 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 $A_{1}$ or $A_{2}$, but we have already set them to be something else, we must backtrack to the last guess.

Runtime

It can be hard to estimate the runtime of this algorithm as it is hard to know how many guesses we have to make. Initially we will have to make two guesses (or just 1 if the s-boxes do not map 0 to 0) to get the algorithm started. Assuming we do not have to make any more guesses the algorithm runs in time $O(n^{3}2^{2n})$ ($O(n^{3}2^{n})$ if the s-boxes do not map 0 to 0). This assumption seems to hold for random functions, but there are bad cases for example when the functions differ in very few points. In general it seems hard to prove any good runtime guarantee for this algorithm.

Affine Equivalence

Given vectorial boolean functions $F,G:F_{2}^{n}\rightarrow F_{2}^{m}$ find affine permutations $A_{1},A_{2}$ such that $F=A_{2}\circ G\circ A_{1}$. We can also write this as $F\circ A_{1}^{-1}=A_{2}\circ G$. If $A_{1}(x)=L_{1}(x)+a_{1},A_{2}(x)=L_{2}(x)+a_{2}$ then $F(x+a_{1})$ is linear equivalent with $G(x)+a_{2}$. So we can guess any affine constants $a_{1},a_{2}$ and check whether or not $F(x+a_{1})$ is linear equivalent with $G(x)+a_{2}$ using any linear equivalence algorithm. This will add a multiplicative factor of $2^{2n}$ to the runtime, but will give us an affine equivalence algorithm.

The to and from algorithm (Affine)

We can adapt the To and from algorithm to the affine case and only add a multiplicative factor of $2^{n}$ to the runtime. Instead of comparing $F(x+a_{1})$ to $G(x)+a_{2}$ for every possible $a_{1},a_{2}$ we will instead find a representative function for $F(x+a)$ for every $a$ and then a representative function for $G(x)+a$ for every possible $a$. We will then compare to see if any of these representative functions are equal.

The representative for a function is the lexicographic smallest linear equivalent function. To see why this work assume $F,G$ are affine equivalent with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle F=A_{1}\circ G\circ A_{2}} where $A_{1}=L_{1}+a_{1}$ and $A_{2}=L_{2}+a_{2}$. Then the functions $F(x+a_{1})$ will be linear equivalent with $G(x)+a_{2}$. If we have found the minimal linear representative $F'$ of $F(x+a_{1})$ then since $G(x)+a_{2}$ is linear equivalent with $F$ it is also linear equivalent with $F'$ so the minimal linear representative of $G(x)+a_{2}$ is at least smaller than $F'$. Using this argument the other way around we get that their linear representatives have to be the same function.

To actually compute the minimal representative of a function $F$ we do the following. We want to construct $F'$, the minimal permutation which is linear equivalent with $F$. We start by guessing the value of $A_{1}$ at the smallest element of $F_{2}^{n}$. Let say $A_{1}(x)=y$. We now do the same as before with going back and forth between $A_{1}$ and $A_{2}$, the only difference we always pick the lowest possible value of $A_{1}$ to deduce a value of $A_{2}$ and vise versa. Also whenever we need the value of a undefined point of $F'$, we simply set to it to the lowest available.

EA equivalence

Given two boolean functions $F,G:F_{2}^{n}\rightarrow F_{2}^{m}$ find two affine permutations $A_{1},A_{2}$ and an affine transformation $A_{3}$ such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F = A_2 \circ G \circ A_1 + A_3 }

Jacobian algorithm

This algorithm can decide EA equivalence for quadratic functions only.

The Jacobian

Given a vectorial boolean function, and any element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in F_2^n} the deriviative in direction Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} is defined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_a F(x) = F(x+a) + F(x) } . The Jacobian for a vectorial boolean function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x) = (F_1(x),...,F_m(x)) } is defined as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J F(x) = \begin{pmatrix}D_{e_1}F_1(x) & D_{e_2}F_1(x) & ... & D_{e_n}F_1(x) \\ D_{e_1}F_2(x) & D_{e_2}F_2(x) & ... & D_{e_n}F_2(x) \\ \vdots & \vdots & \vdots & \vdots \\ D_{e_1}F_m(x) & D_{e_2}F_m(x) & ... & D_{e_n}F_m(x) \end{pmatrix} } where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_i} is the i-th basis vector of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_2^n} . We denote the linear part of the jacobian by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_{lin}F(x)} .

The algorithm

The algorithm is based on the following two facts that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} are EA equivalent quadratic functions with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F = A_2 \circ G \circ A_1 + A_3 } we can assume that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_3} are linear. So we have just Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_2(x) = L_2(x) + a_2 } . The other fact is that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle J_{lin}F(x) = L_2\cdot J_{lin}G(A_1(x)) \cdot A_1 } . This allows the us to start by searching for pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_2,A_1) } first, and deduce the other values later.

To deduce possible pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_2,A_1)} the algorithm does the following. We are first gonna try to find Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} . Using the fact that the rank of the matrixFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin}F(x) } equals the rank of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin}G(A_1(x)) } since all of the matrices/transformations are permutations. This means that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1(x)} can only be mapped to elements which results in the rank being the same. So we are going to compute all possible ranks of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin}F(x)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin}G(x)} . We are then going to look at the least common rank of these tables, let say this value is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_F} be all inputs such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin} F(x) } has rank Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_G} all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Jac_{lin}G(x)} has rank Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . We then know by the previous observation that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} has to map elements from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_F} to elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_G} . If these sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_F} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_G} are small (we can assume they are the same size) then the number of guesses we have will not be to large. To start with we will guess the value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} of some elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_F} .

Having guessed some values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} we are going to deduce values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_2} . If we have guessed that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1u = w} . Then the pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_2,A_1) = (X,Y)} is a solution to the linear system of equations

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X\cdot Jac_{lin}F(v) - Jac_{lin}F(w) \cdot Y = 0 }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y \cdot v = 0 }

We are going to guess enough values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} so that this system has an unique solution (Since each guess gives us more equations). Having done this and found a pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_2,A_1)} we can deduce Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_3} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2} with basic linear algebra. Lets now describe the algorithm in more detail.

1. Compute the rank table of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(F)[j] = \{x \in F_2^n | rank(Jac_{lin}F(x)) = j \} } . Do the same for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G}

2. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} be the number of guesses of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} we are going to make. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = \min |R(F)[j]| } . Pick Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R(F)[i]} . We are then gonna guess all possible values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} on these points. But we only have to guess values inside Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R[G][i]} . Let's say we made the guesses Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1u_1 = w_1,...,A_1u_s = w_s} .

3. Try to solve the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} system of equations Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \cdot Jac_{lin}F(v_i) - Jac_{lin}F(w_i)\cdot Y,\: Y \cdot v_i = 0 } . If this system has to many solutions make another guess (increase the value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} temporary).

4. When the system of equations does not have to many solutions find all solutions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (L_2,A_1)} . Then deduce the rest of the values Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_3} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_2} . If this is possible we are done, otherwise go back to step 2 and make another guess.