Equivalence Algorithms: Difference between revisions
From Boolean
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 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 and such that .
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 and are permutations.
The idea of the algorithm is to go use information gathered about to deduce information about and the other way around. To see how this can work let's say we know some value of , lets say . We of course also know the value of at so lets say that . Then we know that . So we now know that must be equal to .
- ↑ 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.
