**Separable Statistics and Multidimensional Linear Cryptanalysis**

*S. Fauskanger and I. Semaev*

**Abstract: **Multidimensional linear cryptanalysis of block ciphers is improved in this work by introducing
a number of new ideas. Firstly, formulae is given to compute approximate multidimensional distributions of encryption internal bits. Conventional statistics like LLR(Logarithmic Likelihood Ratio) do not fit to work in Matsui's Algorithm 2 for large dimension data, as the observation depend on too many cipher key bits. So, secondly, a new statistic which reflects the structure of the cipher round is constructed instead. Thirdly, computing the statistic values which fall into a critical region is presented as an optimisation problem for which an efficient algorithm is suggested. The algorithm works much faster than brute forcing all relevant key bits to compute the statistic. An attack for 16-round DES was implemented. We got an improvement over Matsui's attack on DES in data and time complexity keeping success probability the same.

**Category / Keywords: **secret-key cryptography / block ciphers, multidimensional linear cryptanalysis, separable statistics, DES

**Date: **received 9 Oct 2017

**Contact author: **igor at ii uib no

**Available format(s): **PDF | BibTeX Citation

**Version: **20171011:153951 (All versions of this report)

**Short URL: **ia.cr/2017/994

[ Cryptology ePrint archive ]