Equivalence Algorithms

From Boolean

The hierarchy of equivalences

Given two vectorial boolean functions F,G:F2n→F2n 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 A1 and A2 such that F=A2∘G∘A1.

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 F and G are permutations.

The idea of the algorithm is to go use information gathered about A1 to deduce information about A2 and the other way around. To see how this can work let's say we know some value of A1, lets say A1(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)=A2∘G∘A1(x)=A2∘G(y)=A2(z). So we now know that A2(z) must be equal to G(y).

For the other way around let's say we know some value of A2, lets say A2(x)=y. We know the value of F−1 at y, lets say F−1(y)=z. Then we know that F(z)=y=A2∘G∘A1(z) so we see that A2∘G∘A1(z)=y. Since we know that A2(x)=y we need G∘A1(z)=x, which must mean that A1(z)=G−1(y).

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

Given two permutations F,G:F2n→F2m we construct the linear permutations A1,A2. The algorithm is a backtracking algorithm, and whenever we discover a contradiction we backtrack to the last guess. We first guess two values of A1(x). Since we now know two values of A1 we can two values of A2, which means we can deduce a third value by linearity. Using this third value we can deduce a value of A1, if this value is not in the span of the already known values of A1 we can deduce two more values of A1 and use this to deduce values of A1 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 A1 or A2, 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(n322n) (O(n32n) 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:F2n→F2m find affine permutations A1,A2 such that F=A2∘G∘A1. We can also write this as F∘A1−1=A2∘G. If A1(x)=L1(x)+a1,A2(x)=L2(x)+a2 then F(x+a1) is linear equivalent with G(x)+a2. So we can guess any affine constants a1,a2 and check whether or not F(x+a1) is linear equivalent with G(x)+a2 using any linear equivalence algorithm. This will add a multiplicative factor of 22n 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 2n to the runtime. Instead of comparing F(x+a1) to G(x)+a2 for every possible a1,a2 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 F=A1∘G∘A2 where A1=L1+a1 and A2=L2+a2. Then the functions F(x+a1) will be linear equivalent with G(x)+a2. If we have found the minimal linear representative F′ of F(x+a1) then since G(x)+a2 is linear equivalent with F it is also linear equivalent with F′ so the minimal linear representative of G(x)+a2 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 A1 at the smallest element of F2n. Let say A1(x)=y. We now do the same as before with going back and forth between A1 and A2, the only difference we always pick the lowest possible value of A1 to deduce a value of A2 and vise versa. Also whenever we need the value of a undefined point of F′, we simply set to it to the lowest available.

Rank Algorithm

This algorithm [2] is efficient also for non-permutations but only functions of high algebraic degrees.

Rank table

The algorithm is based on using the rank table of a boolean functions, which we will now introduce. Given a boolean function F:F2n→F2. We are going to consider this object algebraically using the ANF (algebraic normal form). F=∑u∈F2nαuxu. We can look at F as a vector spanned by all monomials xu=x1u1...xnun. Let F≥d be the polynomial containing all monomials of F with degree at least d. Now given a vectorial boolean functions F=(F1,...,Fm) we define the symbolic rank of F as the rank of the vectors {Fi} (where we view Fi as a vector). Denote this as SR(F).

We compose functions symbolically as F∘A1=∑αu⋅(Mu∘A1). We have that deg(F∘A1)≤deg(F). We can also compose A2∘F where we replace xi in A2 by Fi. Let A:F2n−1→F2n be an affine transformation with A(x)=L(x)+a. The range of A is an affine n−1 dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector h. We call h the half space mask (HSM), since it partitions the space into 2 halves. h⋅a is the half space free coefficient (HSC). Given an HSM and HSC h and c there is a canonical affine transformation C|h,c:F2n−1→F2n.

We can now define the rank table of F with respect to some constant d. For any h∈F2n we calculate u=SR((F∘C|h,0)≥d) and v=SR((C|h,1)≥d). The rank table entry for h then becomes (max(u,v),min(u,v)). For any specific tuple (u,v) the rank group is all h such that the rank table entry for h is (u,v). The rank histogram is a mapping for each (u,v) to the size of the rank group. One last thing we will need is the concept of the rank histogram with with respect to a given rank group. Fix an element h∈F2n. The rank histogram of h with respect to the rank group (u,v) is defined the following way. Add h to all elements of the rank group (u,v) to get a set U⊂F2n. For each element h′ of U we look at the rank group containing h′, let's say it's (u′,v′). The multi set containing the tuples (u′,v′) for each element h′∈U is the rank histogram of h with respect to (u,v). The rank group (u,v) with respect to (u′,v′) is the multiset rank histogram of each element h of the group (u,v) with respect to the group (u′,v′).

Algorithm

The main idea of the algorithm is that if F and G are affine equivalent, then SR(F≥d)=SR(G≥d). If F and G are affine equivalent with F=A2∘G∘A1 we are going to start by trying to reconstruct A1. Do do this the idea is that for any element of the rank table of (u,v) of G. So if we find a entry (u,v) which contains only 1 element we know one point of A1. Now the rank groups can be large so only doing this may still result in a lot of guesses. For some group (u,v) we are going to pick another group (u′,v′) and calculate the rank group of (u,v) with respect to (u′,v′). If this multiset contains an unique element, then the element h of (u,v) corresponding to this element must be matched to the corresponding element of G (Due to the linearity of A1). We can do this for any pair of groups, and if we find any element in the multiset of low cardinality we obtain a lot of information about possible matchings for A1.

Runtime

The algorithm is estimated to be O(n32n) for a random permutation. This is based to some assumption about the distribution of the rank tables of random functions.

EA equivalence

Given two boolean functions F,G:F2n→F2m find two affine permutations A1,A2 and an affine transformation A3 such that F=A2∘G∘A1+A3

Jacobian algorithm

This algorithm can decide EA equivalence for quadratic functions only. [3]

The Jacobian

Given a vectorial boolean function, and any element a∈F2n the deriviative in direction a is defined by DaF(x)=F(x+a)+F(x). The Jacobian for a vectorial boolean function F(x)=(F1(x),...,Fm(x)) is defined as JF(x)=(De1F1(x)De2F1(x)...DenF1(x)De1F2(x)De2F2(x)...DenF2(x)⋮⋮⋮⋮De1Fm(x)De2Fm(x)...DenFm(x)) where ei is the i-th basis vector of F2n. We denote the linear part of the jacobian by JlinF(x).

The algorithm

The algorithm is based on the following two facts that if F and G are EA equivalent quadratic functions with F=A2∘G∘A1+A3 we can assume that A1 and A3 are linear. So we have just A2(x)=L2(x)+a2. The other fact is that JlinF(x)=L2⋅JlinG(A1(x))⋅A1. This allows the us to start by searching for pairs (L2,A1) first, and deduce the other values later.

To deduce possible pairs (L2,A1) the algorithm does the following. We are first gonna try to find A1. Using the fact that the rank of the matrixJaclinF(x) equals the rank of JaclinG(A1(x)) since all of the matrices/transformations are permutations. This means that A1(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 JaclinF(x) and JaclinG(x). We are then going to look at the least common rank of these tables, let say this value is k. Let SF be all inputs such that JaclinF(x) has rank k and SG all x such that JaclinG(x) has rank k. We then know by the previous observation that A1 has to map elements from SF to elements of SG. If these sets SF and SG 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 A1 of some elements of SF.

Having guessed some values of A1 we are going to deduce values of L2. If we have guessed that A1u=w. Then the pair (L2,A1)=(X,Y) is a solution to the linear system of equations

X⋅JaclinF(v)−JaclinF(w)⋅Y=0

Y⋅v=0

We are going to guess enough values of A1 so that this system has an unique solution (Since each guess gives us more equations). Having done this and found a pair (L2,A1) we can deduce A3 and a2 with basic linear algebra. Lets now describe the algorithm in more detail.


1. Compute the rank table of F. R(F)[j]={x∈F2n|rank(JaclinF(x))=j}. Do the same for G

2. Let s be the number of guesses of A1 we are going to make. Let i=min⁡|R(F)[j]|. Pick s elements of R(F)[i]. We are then gonna guess all possible values of A1 on these points. But we only have to guess values inside R[G][i]. Let's say we made the guesses A1u1=w1,...,A1us=ws.

3. Try to solve the s system of equations Failed to parse (syntax error): {\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 s temporary).

4. When the system of equations does not have to many solutions find all solutions (L2,A1). Then deduce the rest of the values A3, a2. If this is possible we are done, otherwise go back to step 2 and make another guess.

Runtime

The runtime of this algorithm is related to the rank table which is related to the differential uniformity of the function. Let R=min⁡R(F)[j]. Then we will at worst have to make around Rs guesses. For each such guess we will have to solve some linear equations which can be done in around (n2+m2)w where w is a matrix multiplication constant. In total we get a time of O(max(n,m)w2n+Rs(m2+n2)w), where the first part is for computing the rank table. Note that when F is APN all the values have the same rank, so R=2n. Which is the worst case for this algorithm.

References

  1. ↑ 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.
  2. ↑ Dinur, Itai. "An improved affine equivalence algorithm for random permutations." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer International Publishing, 2018.
  3. ↑ Canteaut, Anne, Alain Couvreur, and Léo Perrin. "Recovering or testing extended-affine equivalence." IEEE Transactions on Information Theory 68.9 (2022): 6187-6206.