Statistical Model of Correlation Difference and Related-Key Linear Cryptanalysis

Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Degree programme
IACR Transactions on Symmetric Cryptology, Volume 2021, issue 4
The goal of this work is to propose a related-key model for linear cryptanalysis. We start by giving the mean and variance of the difference of sampled correlations of two Boolean functions when using the same sample of inputs to compute both correlations. This result is further extended to determine the mean and variance of the difference of correlations of a pair of Boolean functions taken over a random data sample of fixed size and over a random pair of Boolean functions. We use the properties of the multinomial distribution to achieve these results without independence assumptions. Using multivariate normal approximation of the multinomial distribution we obtain that the distribution of the difference of related-key correlations is approximately normal. This result is then applied to existing related-key cryptanalyses. We obtain more accurate right-key and wrong-key distributions and remove artificial assumptions about independence of sampled correlations. We extend this study to using multiple linear approximations and propose a $\chi^2$-type statistic, which is proven to be $\chi^2$ distributed if the linear approximations are independent. We further examine this statistic for multidimensional linear approximation and discuss why removing the assumption about independence of linear approximations does not work in the related-key setting the same way as in the single-key setting.
block cipher, linear cryptanalysis, related-key attack
Nyberg , K 2021 , ' Statistical Model of Correlation Difference and Related-Key Linear Cryptanalysis ' , IACR Transactions on Symmetric Cryptology , vol. 2021 , no. 4 , pp. 124-137 .