Multiple (Truncated) Differential Cryptanalysis: Explicit Upper Bounds on Data Complexity

Statistical analyzes of multiple (truncated) differential attacks are considered in this paper. Following the work of Blondeau and Gerard, the most general situation of multiple differential attack where there are no restrictions on the set of differentials is studied. We obtain closed form upper bounds on the data complexity in terms of the success probability and the advantage of an attack. This is done under two scenarios – one, where an independence assumption used by Blondeau and Gerard is assumed to hold and second, where no such assumption is made. The first case employs the Chernoff bounds while the second case uses the Hoeffding bounds from the theory of concentration inequalities. In both cases, we do not make use of any approximations in our analysis. Moreover, the results are more generally applicable compared to previous works. The analysis without the independence assumption is the first of its kind in the literature. We believe that the current work places the statistical analysis of multiple (truncated) differential attack on a more rigorous foundation than what was previously known.