Paper 2023/911

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$ 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 {\em 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$ 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$) 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$ to arbitrary finite Abelian groups ($\mathbb{F}_p^n$).