Equivalence Algorithms: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
= The hierarchy of equivalences = | = The hierarchy of equivalences = | ||
Given two vectorial boolean functions <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>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> | 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 12: | Line 12: | ||
This algorithm is 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. | This algorithm is 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 | 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>. | ||
Revision as of 14:27, 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 is 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].
- ↑ 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.