Paper 2016/405

Multiple Differential Cryptanalysis: A Rigorous Analysis

Subhabrata Samajder and Palash Sarkar

Abstract

Statistical analyses of multiple differential attacks are considered in this paper. Following the work of Blondeau and Gérard, the most general situation of multiple differential attack where there are no restrictions on the set of differentials is studied. We obtain closed form 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 Gérard 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. As a consequence, 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 differential attack on a more rigorous foundation than what was previously known.