Link Between the Differential Cryptanalysis and Linear Approximations over Finite Abelian Groups And Its Applications

Abstract In recent years, progress in practical applications of multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZKP) motivates people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over finite Abelian groups or prime fields $${\mathbb {F}}_p$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:math> for large p . In this paper, we establish the links between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups. As the first application, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. More precisely, we consider the linearity , which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. This thereby generalizes the work of Pott in 2004 and completes the generalization of Sidelnikov–Chabaud–Vaudenay’s bound from $${\mathbb {F}}_2^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> to finite Abelian groups. As the second application, we give an exact expression for the correlation of differential-linear approximations over arbitrary finite Abelian groups ( $${\mathbb {F}}_p^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> ) under the sole assumption that the two parts of the cipher are independent of each other. In particular, we completely generalize the differential-linear cryptanalysis from $${\mathbb {F}}_2^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> to arbitrary finite Abelian groups ( $${\mathbb {F}}_p^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>p</mml:mi> <mml:mi>n</mml:mi> </mml:msubsup> </mml:math> ).