International Association
for Cryptologic Research

The power of a statistical attack is inversely proportional to the number of plaintexts

necessary to recover information on the encryption key. By

analyzing the distribution of the random variables involved in the attack,

cryptographers aim to provide a good estimate of the data

complexity of such an attack. In this paper, we analyze the

hypotheses made in simple, multiple, and multidimensional

linear attacks that use either non-zero or zero correlations, and provide more accurate estimates of the data complexity of

these attacks. This is achieved by taking, for the first time, into consideration the key variance of the statistic for both

the right and wrong keys.

For the family of linear attacks we differentiate between the attacks which are performed in the known-plaintext

and those in the distinct-known-plaintext model. By this differentiation, we improve the

data complexity of some attacks by applying the distinct-known-plaintext model.

From the analysis provided in this paper, it follows that

the number of attacked

rounds in the multidimensional linear context is impacted by the fact that the expected capacity of a multidimensional linear

approximation for a random permutation is not equal to

zero as previously assumed. The impact of the result is relatively important, since it weakens most existing multidimensional linear attacks.

From the link between

differential and linear cryptanalysis we also derive a new estimate of the

data complexity of a truncated differential attack. The theory developed

in this paper is backed up by different experiments.