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>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> | 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 = | |||
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== | |||
This algorithm is from <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> | |||
Revision as of 14:00, 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 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 } 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 is from [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.
