Equivalence Algorithms: Difference between revisions
No edit summary |
|||
| (16 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
= The hierarchy of equivalences = | = 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> | 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 = | = Linear Equivalence = | ||
Given two vectorial boolean functions <math> | 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== | ==The to and from algorithm== | ||
| Line 20: | Line 20: | ||
Given two permutations <math>F,G : F_2^n \rightarrow F_2^m </math> we construct the linear permutations <math>A_1,A_2</math>. 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. | Given two permutations <math>F,G : F_2^n \rightarrow F_2^m </math> we construct the linear permutations <math>A_1,A_2</math>. 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. | ||
===Runtime=== | ===Runtime=== | ||
| Line 42: | Line 33: | ||
The representative for a function is the lexicographic smallest linear equivalent function. To see why this work assume <math>F,G</math> are affine equivalent with <math>F = A_1 \circ G \circ A_2 </math> where <math>A_1 = L_1 + a_1</math> and <math>A_2 = L_2+a_2 </math>. Then the functions <math>F(x+a_1)</math> will be linear equivalent with <math>G(x)+a_2</math>. If we have found the minimal linear representative <math>F'</math> of <math>F(x+a_1)</math> then since <math>G(x)+a_2</math> is linear equivalent with <math>F</math> it is also linear equivalent with <math>F'</math> so the minimal linear representative of <math>G(x)+a_2</math> is at least smaller than <math>F'</math>. Using this argument the other way around we get that their linear representatives have to be the same function. | The representative for a function is the lexicographic smallest linear equivalent function. To see why this work assume <math>F,G</math> are affine equivalent with <math>F = A_1 \circ G \circ A_2 </math> where <math>A_1 = L_1 + a_1</math> and <math>A_2 = L_2+a_2 </math>. Then the functions <math>F(x+a_1)</math> will be linear equivalent with <math>G(x)+a_2</math>. If we have found the minimal linear representative <math>F'</math> of <math>F(x+a_1)</math> then since <math>G(x)+a_2</math> is linear equivalent with <math>F</math> it is also linear equivalent with <math>F'</math> so the minimal linear representative of <math>G(x)+a_2</math> is at least smaller than <math>F'</math>. 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 <math>F</math> we do the following. We want to construct <math>F'</math>, the minimal permutation which is linear equivalent with <math>F</math>. We start by guessing the value of <math>A_1</math> at the smallest element of <math>F_2^n</math>. Let say <math>A_1(x) = y</math>. | To actually compute the minimal representative of a function <math>F</math> we do the following. We want to construct <math>F'</math>, the minimal permutation which is linear equivalent with <math>F</math>. We start by guessing the value of <math>A_1</math> at the smallest element of <math>F_2^n</math>. Let say <math>A_1(x) = y</math>. We now do the same as before with going back and forth between <math>A_1 </math> and <math>A_2</math>, the only difference we always pick the lowest possible value of <math>A_1</math> to deduce a value of <math>A_2</math> and vise versa. Also whenever we need the value of a undefined point of <math>F'</math>, we simply set to it to the lowest available. | ||
==Rank Algorithm== | |||
This algorithm <ref name ="rank">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.</ref> 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 <math>F: F_2^n \rightarrow F_2 </math>. We are going to consider this object algebraically using the ANF (algebraic normal form). <math>F = \sum_{u \in F_2^n }\alpha_ux^u </math>. We can look at <math>F</math> as a vector spanned by all monomials <math>x^u = x_1^{u_1}...x_n^{u_n} </math>. Let <math>F_{\geq d}</math> be the polynomial containing all monomials of <math>F</math> with degree at least <math>d</math>. Now given a vectorial boolean functions <math>F=(F_1,...,F_m)</math> we define the symbolic rank of <math>F</math> as the rank of the vectors <math> \{F_i\}</math> (where we view <math>F_i</math> as a vector). Denote this as <math>SR(F)</math>. | |||
We compose functions symbolically as <math>F \circ A_1 = \sum \alpha_u \cdot (M_u \circ A_1 ) </math>. We have that <math>deg(F \circ A_1) \leq deg(F) </math>. We can also compose <math>A_2 \circ F </math> where we replace <math>x_i</math> in <math>A_2</math> by <math>F_i</math>. Let <math>A : F_2^{n-1} \rightarrow F_2^n </math> be an affine transformation with <math>A(x) = L(x) + a</math>. The range of <math>A</math> is an affine <math>n-1</math> dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector <math>h</math>. We call <math>h</math> the half space mask (HSM), since it partitions the space into 2 halves. <math>h \cdot a </math> is the half space free coefficient (HSC). Given an HSM and HSC <math>h</math> and <math>c</math> there is a canonical affine transformation <math>C_{|_{h,c}} : F_2^{n-1} \rightarrow F_2^n </math>. | |||
We can now define the rank table of <math>F</math> with respect to some constant <math>d</math>. For any <math>h \in F_2^n </math> we calculate <math>u = SR((F \circ C_{|_{h,0}})_{\geq d} )</math> and <math>v = SR((C_{|_{h,1}})_{\geq d}) </math>. The rank table entry for <math>h</math> then becomes <math>(max(u,v),min(u,v))</math>. For any specific tuple <math>(u,v)</math> the rank group is all <math>h</math> such that the rank table entry for <math>h</math> is <math>(u,v)</math>. The rank histogram is a mapping for each <math>(u,v)</math> 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 <math>h \in F_2^n </math>. The rank histogram of <math>h</math> with respect to the rank group <math>(u,v)</math> is defined the following way. Add <math>h</math> to all elements of the rank group <math>(u,v)</math> to get a set <math>U \subset F_2^n </math>. For each element <math>h'</math> of <math>U</math> we look at the rank group containing <math>h'</math>, let's say it's <math>(u',v')</math>. The multi set containing the tuples <math>(u',v')</math> for each element <math>h' \in U </math> is the rank histogram of <math>h</math> with respect to <math>(u,v)</math>. The rank group <math>(u,v) </math> with respect to <math>(u',v')</math> is the multiset rank histogram of each element <math>h</math> of the group <math>(u,v)</math> with respect to the group <math>(u',v')</math>. | |||
===Algorithm=== | |||
The main idea of the algorithm is that if <math>F</math> and <math>G</math> are affine equivalent, then <math>SR(F_{\geq d}) = SR(G_{\geq d}) </math>. If <math>F</math> and <math>G</math> are affine equivalent with <math>F = A_2 \circ G \circ A_1 </math> we are going to start by trying to reconstruct <math>A_1</math>. Do do this the idea is that for any element of the rank table of <math>(u,v)</math> of <math>G </math>. So if we find a entry <math>(u,v) </math> which contains only 1 element we know one point of <math>A_1</math>. Now the rank groups can be large so only doing this may still result in a lot of guesses. For some group <math>(u,v)</math> we are going to pick another group <math>(u',v')</math> and calculate the rank group of <math>(u,v)</math> with respect to <math>(u',v')</math>. If this multiset contains an unique element, then the element <math>h</math> of <math>(u,v)</math> corresponding to this element must be matched to the corresponding element of <math>G</math> (Due to the linearity of <math>A_1</math>). 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 <math>A_1</math>. | |||
===Runtime=== | |||
The algorithm is estimated to be <math>O(n^32^n)</math> for a random permutation. This is based to some assumption about the distribution of the rank tables of random functions. | |||
=EA equivalence= | =EA equivalence= | ||
Given two boolean functions <math>F,G : F_2^n \rightarrow F_2^m </math> find two affine permutations <math>A_1,A_2</math> and an affine transformation <math>A_3</math> such that <math>F = A_2 \circ G \circ A_1 + A_3 </math> | Given two boolean functions <math>F,G : F_2^n \rightarrow F_2^m </math> find two affine permutations <math>A_1,A_2</math> and an affine transformation <math>A_3</math> such that <math> F = A_2 \circ G \circ A_1 + A_3 </math> | ||
==Jacobian algorithm== | ==Jacobian algorithm== | ||
This algorithm can decide EA equivalence for quadratic functions only. | |||
<ref name="jacobian">Canteaut, Anne, Alain Couvreur, and Léo Perrin. "Recovering or testing extended-affine equivalence." IEEE Transactions on Information Theory 68.9 (2022): 6187-6206.</ref> | <ref name="jacobian">Canteaut, Anne, Alain Couvreur, and Léo Perrin. "Recovering or testing extended-affine equivalence." IEEE Transactions on Information Theory 68.9 (2022): 6187-6206.</ref> | ||
===The Jacobian=== | ===The Jacobian=== | ||
Given a vectorial boolean function, and any element <math>a \in F_2^n</math> the deriviative in direction <math>a</math> is defined by <math> D_a F(x) = F(x+a) + F(x) </math>. The Jacobian for a vectorial boolean function is defined as <math>J F(x) = \begin{pmatrix} | Given a vectorial boolean function, and any element <math>a \in F_2^n</math> the deriviative in direction <math>a</math> is defined by <math> D_a F(x) = F(x+a) + F(x) </math>. The Jacobian for a vectorial boolean function <math>F(x) = (F_1(x),...,F_m(x)) </math> is defined as <math>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} </math> where <math>e_i</math> is the i-th basis vector of <math>F_2^n</math>. We denote the linear part of the jacobian by <math>J_{lin}F(x)</math>. | ||
===The algorithm=== | |||
The algorithm is based on the following two facts that if <math>F</math> and <math>G</math> are EA equivalent quadratic functions with <math>F = A_2 \circ G \circ A_1 + A_3 </math> we can assume that <math>A_1</math> and <math>A_3</math> are linear. So we have just <math> A_2(x) = L_2(x) + a_2 </math>. The other fact is that <math>J_{lin}F(x) = L_2\cdot J_{lin}G(A_1(x)) \cdot A_1 </math>. This allows the us to start by searching for pairs <math>(L_2,A_1) </math> first, and deduce the other values later. | |||
To deduce possible pairs <math>(L_2,A_1)</math> the algorithm does the following. We are first gonna try to find <math>A_1</math>. Using the fact that the rank of the matrix<math>Jac_{lin}F(x) </math> equals the rank of <math>Jac_{lin}G(A_1(x)) </math> since all of the matrices/transformations are permutations. This means that <math>A_1(x)</math> can only be mapped to elements which results in the rank being the same. So we are going to compute all possible ranks of <math>Jac_{lin}F(x)</math> and <math>Jac_{lin}G(x)</math>. We are then going to look at the least common rank of these tables, let say this value is <math>k</math>. Let <math>S_F</math> be all inputs such that <math>Jac_{lin} F(x) </math> has rank <math>k</math> and <math>S_G</math> all <math>x</math> such that <math>Jac_{lin}G(x)</math> has rank <math>k</math>. We then know by the previous observation that <math>A_1</math> has to map elements from <math>S_F</math> to elements of <math>S_G</math>. If these sets <math>S_F</math> and <math>S_G</math> 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 <math>A_1</math> of some elements of <math>S_F</math>. | |||
Having guessed some values of <math>A_1</math> we are going to deduce values of <math>L_2</math>. If we have guessed that <math>A_1u = w</math>. Then the pair <math>(L_2,A_1) = (X,Y)</math> is a solution to the linear system of equations | |||
<math>X\cdot Jac_{lin}F(v) - Jac_{lin}F(w) \cdot Y = 0 </math> | |||
<math>Y \cdot v = 0 </math> | |||
We are going to guess enough values of <math>A_1</math> so that this system has an unique solution (Since each guess gives us more equations). Having done this and found a pair <math>(L_2,A_1)</math> we can deduce <math>A_3</math> and <math>a_2</math> with basic linear algebra. Lets now describe the algorithm in more detail. | |||
1. Compute the rank table of <math>F</math>. <math>R(F)[j] = \{x \in F_2^n | rank(Jac_{lin}F(x)) = j \} </math>. Do the same for <math>G</math> | |||
2. Let <math>s</math> be the number of guesses of <math>A_1</math> we are going to make. Let <math>i = \min |R(F)[j]| </math>. Pick <math>s</math> elements of <math>R(F)[i]</math>. We are then gonna guess all possible values of <math>A_1</math> on these points. But we only have to guess values inside <math>R[G][i]</math>. Let's say we made the guesses <math>A_1u_1 = w_1,...,A_1u_s = w_s</math>. | |||
3. Try to solve the <math>s</math> system of equations <math>X \cdot Jac_{lin}F(v_i) - Jac_{lin}F(w_i)\cdot Y,\: Y \cdot v_i = 0 </math>. If this system has to many solutions make another guess (increase the value of <math>s</math> temporary). | |||
4. When the system of equations does not have to many solutions find all solutions <math>(L_2,A_1)</math>. Then deduce the rest of the values <math>A_3</math>, <math>a_2</math>. 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 <math>R = \min R(F)[j] </math>. Then we will at worst have to make around <math>R^s</math> guesses. For each such guess we will have to solve some linear equations which can be done in around <math>(n^2+m^2)^w</math> where <math>w</math> is a matrix multiplication constant. In total we get a time of <math>O(max(n,m)^w2^n + R^s(m^2+n^2)^w)</math>, where the first part is for computing the rank table. Note that when <math>F</math> is APN all the values have the same rank, so <math>R = 2^n</math>. Which is the worst case for this algorithm. | |||
=References= | =References= | ||
Latest revision as of 00:48, 23 November 2024
The hierarchy of equivalences
Given two vectorial boolean functions there are various ways to define equivalence between and . 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 and we want to determine if there exist Linear permutations 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_2 } 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 } .
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 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 permutations.
The idea of the algorithm is to go use information gathered about to deduce information about 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 } and the other way around. To see how this can work let's say we know some 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 } , lets say 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) = y } . We of course also know 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 G} at 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} so lets say that . Then we know 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(x) = A_2 \circ G \circ A_1(x) = A_2 \circ G(y) = A_2(z) } . So we now know 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_2(z) } must be equal to 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(y) } .
For the other way around let's say we know some 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_2 } , lets say 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) = y } . We know the value of at y, lets say 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^{-1}(y) = z } . Then we know 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(z) = y = A_2 \circ G \circ A_1(z) } so we see 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_2 \circ G \circ A_1(z) = y } . Since we know 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_2(x) = y } we need 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 \circ A_1(z) = x } , which must mean that .
So we now showed how we can deduce information knowing either a 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 } or 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} . Now lets say we now the 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 } at a set of points. Since 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 } 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 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} at 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} linear independent points, which means that we know the value of at 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 2^k} points. If we now somehow gain value of a point 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} which is not in the span of the already known points then we can deduce 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 } at 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 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 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} as explained before. We will now explain the complete algorithm before giving the psudocode.
Given two permutations we construct the linear permutations 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,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 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) } . Since we now know two 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 can two 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_2} , which means we can deduce a third value by linearity. Using this third value we can deduce a 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} , if this value is not in the span of the already known values of we can deduce two more 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 } and use this 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 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 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 } or 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 } , 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 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 O(n^32^{2n})} (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 O(n^32^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 find affine permutations 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,A_2} 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 } . We can also write this 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 F \circ A_1^{-1} = A_2 \circ G } . 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 A_1(x) = L_1(x) +a_1 , A_2(x) = L_2(x)+a_2 } then 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+a_1)} is linear equivalent 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 G(x) + a_2} . So we can guess any affine constants and check whether or not 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+a_1)} is linear equivalent 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 G(x)+a_2} using any linear equivalence algorithm. This will add a multiplicative factor 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 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 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 2^n} to the runtime. Instead of comparing 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+a_1)} to for every possible 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,a_2} we will instead find a representative function 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 F(x+a)} for every 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} and then a representative function 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(x) + a} for every possible 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} . 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 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,G} are affine equivalent with 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 A_1 = L_1 + 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_2 = L_2+a_2 } . Then the functions 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+a_1)} will be linear equivalent 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 G(x)+a_2} . If we have found the minimal linear representative 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'} 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(x+a_1)} then since is linear equivalent 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} it is also linear equivalent 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'} so the minimal linear representative 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 G(x)+a_2} is at least smaller than 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'} . 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 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} we do the following. We want to construct 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'} , the minimal permutation which is linear equivalent with . We start by guessing the value of at the smallest element of . Let say . We now do the same as before with going back and forth between 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_2} , the only difference we always pick the lowest possible 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} to deduce a 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_2} and vise versa. Also whenever we need the value of a undefined point 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'} , 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 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: F_2^n \rightarrow F_2 } . We are going to consider this object algebraically using the ANF (algebraic normal form). . We can look at as a vector spanned by all monomials . Let be the polynomial containing all monomials 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} with degree at least 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} . Now given a vectorial boolean functions 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=(F_1,...,F_m)} we define the symbolic 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 F} as the rank of the vectors (where we view 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_i} as a vector). Denote this as .
We compose functions symbolically as . We have that . We can also compose where we replace in by . Let be an affine transformation with . The range of is an affine 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 n-1} dimensional subspace so it's orthogonal subspace is 1 dimensional, so spanned by a single vector 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 h} . We call 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 h} the half space mask (HSM), since it partitions the space into 2 halves. 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 h \cdot a } is the half space free coefficient (HSC). Given an HSM and HSC 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 h} and there is a canonical affine transformation 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 C_{|_{h,c}} : F_2^{n-1} \rightarrow F_2^n } .
We can now define 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} with respect to some constant 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} . For any 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 h \in F_2^n } we calculate 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 u = SR((F \circ C_{|_{h,0}})_{\geq d} )} and . The rank table entry 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 h} then becomes . For any specific tuple 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 (u,v)} the rank group is 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 h} such that the rank table entry 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 h} 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 (u,v)} . The rank histogram is a mapping for each 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 (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 . The rank histogram 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 h} with respect to the rank group 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 (u,v)} is defined the following way. Add 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 h} to all elements of the rank group 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 (u,v)} to get a set 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 U \subset F_2^n } . For each element 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 U} we look at the rank group containing 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 h'} , let's say it's 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 (u',v')} . The multi set containing the tuples for each element is the rank histogram of with respect to 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 (u,v)} . The rank group with respect to is the multiset rank histogram of each element of the group with respect to the group .
Algorithm
The main idea of the algorithm is 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 affine equivalent, then 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 SR(F_{\geq d}) = SR(G_{\geq d}) } . 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 affine equivalent 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 } we are going to start by trying to reconstruct 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} . Do do this the idea is that for any element of 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 (u,v)} 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 G } . So if we find a entry 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 (u,v) } which contains only 1 element we know one point of . Now the rank groups can be large so only doing this may still result in a lot of guesses. For some group 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 (u,v)} we are going to pick another group 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 (u',v')} and calculate the rank group 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 (u,v)} with respect to 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 (u',v')} . If this multiset contains an unique element, then the 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 h} of corresponding to this element must be matched to the corresponding element 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 G} (Due to the linearity 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 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 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} .
Runtime
The algorithm is estimated to be 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 O(n^32^n)} 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 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,G : F_2^n \rightarrow F_2^m } find two affine permutations and an affine transformation 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} 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. [3]
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 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 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 are linear. So we have just . 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 be all inputs such that 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 so that this system has an unique solution (Since each guess gives us more equations). Having done this and found a pair we can deduce and with basic linear algebra. Lets now describe the algorithm in more detail.
1. Compute the rank table of . . 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}
![{\displaystyle R(F)[j]=\{x\in F_{2}^{n}|rank(Jac_{lin}F(x))=j\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3db7cfe35d03e91cb057853fa6a592c481e0285e)
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 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_2} . 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 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 = \min R(F)[j] } . Then we will at worst have to make around 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^s} guesses. For each such guess we will have to solve some linear equations which can be done in around 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 (n^2+m^2)^w} 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 w} is a matrix multiplication constant. In total we get a time 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 O(max(n,m)^w2^n + R^s(m^2+n^2)^w)} , where the first part is for computing the rank table. Note that when is APN all the values have the same rank, so 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 = 2^n} . Which is the worst case for this algorithm.
References
- ↑ 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.
- ↑ 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.
- ↑ Canteaut, Anne, Alain Couvreur, and Léo Perrin. "Recovering or testing extended-affine equivalence." IEEE Transactions on Information Theory 68.9 (2022): 6187-6206.