International Association
for Cryptologic Research

All statistical analysis of symmetric key attacks use the central limit theorem to approximate the distribution

of a sum of random variables using the normal distribution. Expressions for data complexity using such an approach are

{\\em inherently approximate}. In contrast, this paper takes a rigorous approach to analysing attacks on block ciphers.

In particular, no approximations are used. Expressions for upper bounds on the data complexities of several basic and advanced

attacks are obtained. The analysis is based on the hypothesis testing framework. Probabilities of Type-I and Type-II errors

are upper bounded using standard tail inequalities. In the cases of single linear and differetial cryptanalysis, the Chernoff bound

is used. For the cases of multiple linear and multiple differential cryptanalysis, the theory of martingales is required. A

Doob martingale satisfying the Lipschitz condition is set up so that the Azuma-Hoeffding inequality can be applied. This allows

bounding the error probabilities and obtaining expressions for data complexities. We believe that our method provides important

results for the attacks considered here and more generally, the techniques that we develop have much wider applicability.