Commutative cryptanalysis as a generalization of differential cryptanalysis

Abstract Recently, Baudrin et al. analyzed a special case of Wagner’s commutative diagram cryptanalysis, referred to as commutative cryptanalysis . For a family $$(E_k)_k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>E</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> </mml:msub> </mml:math> of permutations on a finite vector space G , commutative cryptanalysis exploits the existence of affine permutations $$A,B :G \rightarrow G$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo>:</mml:mo> <mml:mi>G</mml:mi> <mml:mo>→</mml:mo> <mml:mi>G</mml:mi> </mml:mrow> </mml:math> , $$I \notin \{A,B\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>I</mml:mi> <mml:mo>∉</mml:mo> <mml:mo>{</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> such that $$E_k \circ A (x) = B \circ E_k(x)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>E</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>∘</mml:mo> <mml:mi>A</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>B</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>E</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> holds with high probability, taken over inputs x , for a significantly large set of weak keys k . Several attacks against symmetric cryptographic primitives can be formulated within the framework of commutative cryptanalysis, most importantly differential attacks, as well as rotational and rotational-differential attacks. Besides, the notion of c -differentials on S-boxes can be analyzed as a special case within this framework. We discuss the relations between a general notion of commutative cryptanalysis, with A and B being arbitrary functions over a finite Abelian group, and differential cryptanalysis, both from the view of conducting an attack on a symmetric cryptographic primitive, as well as from the view of a theoretical study of cryptographic S-boxes.