Equivalence Algorithms: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
==The to and from algorithm== | ==The to and from algorithm== | ||
This algorithm | This algorithm was presented at eurocrypt 2003 <ref name="back">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. </ref>. This algorithm is mainly intended for when the boolean functions are permutation, and we will start by assuming <math>F </math> and <math>G </math> are permutations. | ||
The idea of the algorithm is to go use information gathered about <math>A_1 </math> to deduce information about <math>A_2 </math> and the other way around. To see how this can work let's say we know some value of <math>A_1 </math>, lets say <math>A_1(x) = y </math>. We of course also know the value of <math>G</math> at <math>y</math> so lets say that <math>G(y) = z </math>. Then we know that <math> F(x) = A_2 \circ G \circ A_1(x) = A_2 \circ G(y) = A_2(z) </math>. So we now know that <math>A_2(z) </math> must be equal to <math>G(y) </math>. | The idea of the algorithm is to go use information gathered about <math>A_1 </math> to deduce information about <math>A_2 </math> and the other way around. To see how this can work let's say we know some value of <math>A_1 </math>, lets say <math>A_1(x) = y </math>. We of course also know the value of <math>G</math> at <math>y</math> so lets say that <math>G(y) = z </math>. Then we know that <math> F(x) = A_2 \circ G \circ A_1(x) = A_2 \circ G(y) = A_2(z) </math>. So we now know that <math>A_2(z) </math> must be equal to <math>G(y) </math>. | ||
For the other way around let's say we know some value of <math>A_2 </math>, lets say <math>A_2(x) = y </math>. We know the value of <math> F^{-1} </math> at y, lets say <math>F^{-1}(y) = z </math>. Then we know that <math>F(z) = y = A_2 \circ G \circ A_1(z) </math> so we see that <math>A_2 \circ G \circ A_1(z) = y </math>. Since we know that <math>A_2(x) = y </math> we need <math>G \circ A_1(z) = x </math>, which must mean that <math>A_1(z) = G^{-1}(y)</math>. | |||
So we now showed how we can deduce information knowing either a value of <math>A_1 </math> or <math>A_2</math>. Now lets say we now the values of <math>A_1 </math> at a set of points. Since <math>A_1 </math> is linear we also know it's value at any linear combinations of these points so we can just assume that we know the values at <math>A_1</math> at <math>k</math> linear independent points, which means that we know the value of <math>A_1</math> at <math>2^k</math> points. If we now somehow gain value of a point of <math>A_1</math> which is not in the span of the already known points then we can deduce the value of <math>A_1 </math> at <math>2^k </math> new points using any linear combination of points including this new point. Then we can use all of these new points and try to deduce points of <math>A_2</math> as explained before. We will now explain the complete algorithm before giving the psudocode. | |||
Given two permutations <math>F,G : F_2^n \rightarrow F_2^m </math> we construct the linear permutations $A_1,A_2$. The algorithm is a backtracking algorithm, and whenever we discover a contradiction we backtrack to the last guess. We first guess two values of <math>A_1(x) </math>. Since we now know two values of <math>A_1 </math> we can two values of <math>A_2</math>, which means we can deduce a third value by linearity. Using this third value we can deduce a value of <math>A_1</math>, if this value is not in the span of the already known values of <math>A_1 </math> we can deduce two more values of <math>A_1 </math> and use this to deduce values of <math>A_1</math> and so on. If we ever run out of values before we have finished we will have to make additional guesses. If we ever encounter that a situation where we deduce a value of <math>A_1 </math> or <math>A_2 </math>, but we have already set them to be something else, we must backtrack to the last guess. | |||
Here is the psudocode: | |||
<div style="overflow:auto;"><syntaxhighlight lang="python"> | |||
sage: from sage.crypto.boolean_function import BooleanFunction | |||
sage: B.<x0, x1, x2, x3> = BooleanPolynomialRing(4) | |||
sage: f = x0*x1*x2*x3 + x0*x2*x3 + x1*x2*x3 + x0*x1 + x0*x3 + x1*x2 + x3 + 1 | |||
sage: F = BooleanFunction(f) | |||
sage: F.algebraic_degree() | |||
4 | |||
</syntaxhighlight></div> | |||
Revision as of 15:26, 19 November 2024
The hierarchy of equivalences
Given two vectorial boolean functions [math]\displaystyle{ F,G : F_2^n \rightarrow F_2^n }[/math] there are various ways to define equivalence between [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math]. We will study the algorithms for determining Linear, Affine, Extended Affine and CCZ equivalence between vectorial boolean functions.
Linear Equivalence
Given two vectorial boolean functions [math]\displaystyle{ f }[/math] and [math]\displaystyle{ g }[/math] we want to determine if there exist Linear permutations [math]\displaystyle{ A_1 }[/math] and [math]\displaystyle{ A_2 }[/math] such that [math]\displaystyle{ F = A_2 \circ G \circ A_1 }[/math].
The to and from algorithm
This algorithm was presented at eurocrypt 2003 [1]. This algorithm is mainly intended for when the boolean functions are permutation, and we will start by assuming [math]\displaystyle{ F }[/math] and [math]\displaystyle{ G }[/math] are permutations.
The idea of the algorithm is to go use information gathered about [math]\displaystyle{ A_1 }[/math] to deduce information about [math]\displaystyle{ A_2 }[/math] and the other way around. To see how this can work let's say we know some value of [math]\displaystyle{ A_1 }[/math], lets say [math]\displaystyle{ A_1(x) = y }[/math]. We of course also know the value of [math]\displaystyle{ G }[/math] at [math]\displaystyle{ y }[/math] so lets say that [math]\displaystyle{ G(y) = z }[/math]. Then we know that [math]\displaystyle{ F(x) = A_2 \circ G \circ A_1(x) = A_2 \circ G(y) = A_2(z) }[/math]. So we now know that [math]\displaystyle{ A_2(z) }[/math] must be equal to [math]\displaystyle{ G(y) }[/math].
For the other way around let's say we know some value of [math]\displaystyle{ A_2 }[/math], lets say [math]\displaystyle{ A_2(x) = y }[/math]. We know the value of [math]\displaystyle{ F^{-1} }[/math] at y, lets say [math]\displaystyle{ F^{-1}(y) = z }[/math]. Then we know that [math]\displaystyle{ F(z) = y = A_2 \circ G \circ A_1(z) }[/math] so we see that [math]\displaystyle{ A_2 \circ G \circ A_1(z) = y }[/math]. Since we know that [math]\displaystyle{ A_2(x) = y }[/math] we need [math]\displaystyle{ G \circ A_1(z) = x }[/math], which must mean that [math]\displaystyle{ A_1(z) = G^{-1}(y) }[/math].
So we now showed how we can deduce information knowing either a value of [math]\displaystyle{ A_1 }[/math] or [math]\displaystyle{ A_2 }[/math]. Now lets say we now the values of [math]\displaystyle{ A_1 }[/math] at a set of points. Since [math]\displaystyle{ A_1 }[/math] is linear we also know it's value at any linear combinations of these points so we can just assume that we know the values at [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ k }[/math] linear independent points, which means that we know the value of [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ 2^k }[/math] points. If we now somehow gain value of a point of [math]\displaystyle{ A_1 }[/math] which is not in the span of the already known points then we can deduce the value of [math]\displaystyle{ A_1 }[/math] at [math]\displaystyle{ 2^k }[/math] new points using any linear combination of points including this new point. Then we can use all of these new points and try to deduce points of [math]\displaystyle{ A_2 }[/math] as explained before. We will now explain the complete algorithm before giving the psudocode.
Given two permutations [math]\displaystyle{ F,G : F_2^n \rightarrow F_2^m }[/math] we construct the linear permutations $A_1,A_2$. The algorithm is a backtracking algorithm, and whenever we discover a contradiction we backtrack to the last guess. We first guess two values of [math]\displaystyle{ A_1(x) }[/math]. Since we now know two values of [math]\displaystyle{ A_1 }[/math] we can two values of [math]\displaystyle{ A_2 }[/math], which means we can deduce a third value by linearity. Using this third value we can deduce a value of [math]\displaystyle{ A_1 }[/math], if this value is not in the span of the already known values of [math]\displaystyle{ A_1 }[/math] we can deduce two more values of [math]\displaystyle{ A_1 }[/math] and use this to deduce values of [math]\displaystyle{ A_1 }[/math] and so on. If we ever run out of values before we have finished we will have to make additional guesses. If we ever encounter that a situation where we deduce a value of [math]\displaystyle{ A_1 }[/math] or [math]\displaystyle{ A_2 }[/math], but we have already set them to be something else, we must backtrack to the last guess.
Here is the psudocode:
sage: from sage.crypto.boolean_function import BooleanFunction
sage: B.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: f = x0*x1*x2*x3 + x0*x2*x3 + x1*x2*x3 + x0*x1 + x0*x3 + x1*x2 + x3 + 1
sage: F = BooleanFunction(f)
sage: F.algebraic_degree()
4
- ↑ Biryukov, Alex, et al. "A toolbox for cryptanalysis: Linear and affine equivalence algorithms." Advances in Cryptology—EUROCRYPT 2003: International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4–8, 2003 Proceedings 22. Springer Berlin Heidelberg, 2003.