**Capacity and Data Complexity in Multidimensional Linear Attack**

*Jialin Huang and Serge Vaudenay and Xuejia Lai and Kaisa Nyberg*

**Abstract: **Multidimensional linear attacks are one of the most powerful variants of linear cryptanalytic techniques now.
However, there is no knowledge on the key-dependent capacity and data complexity so far.
Their values were assumed to be close to the average value for a vast majority of keys.
This assumption is not accurate. In this paper, under a reasonable condition, we explicitly formulate the capacity as a Gamma distribution and the data complexity as an Inverse Gamma distribution, in terms of the average linear potential and the dimension. The capacity distribution is experimentally verified on the 5-round PRESENT.

Regarding complexity, we solve the problem of estimating the average data complexity, which was difficult to estimate because of the existence of zero correlations. We solve the problem of using the median complexity in multidimensional linear attacks, which is an open problem since proposed in Eurocrypt 2011. We also evaluate the difference among the median complexity, the average complexity and a lower bound of the average complexity -- the reciprocal of average capacity. In addition, we estimate more accurately the key equivalent hypothesis, and reveal the fact that the average complexity only provides an accurate estimate for less than half of the keys no matter how many linear approximations are involved.

Finally, we revisit the so far best attack on PRESENT based on our theoretical result.

**Category / Keywords: **secret-key cryptography / multidimensional linear attack, capacity, data complexity, linear hull effect, linear potential

**Original Publication**** (with minor differences): **IACR-CRYPTO-2015

**Date: **received 20 Jan 2016

**Contact author: **jlhuang cn at gmail com

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

**Version: **20160122:085622 (All versions of this report)

**Short URL: **ia.cr/2016/051

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]