Paper 2016/051

Capacity and Data Complexity in Multidimensional Linear Attack

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


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.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
multidimensional linear attackcapacitydata complexitylinear hull effectlinear potential
Contact author(s)
jlhuang cn @ gmail com
2016-01-22: received
Short URL
Creative Commons Attribution


      author = {Jialin Huang and Serge Vaudenay and Xuejia Lai and Kaisa Nyberg},
      title = {Capacity and Data Complexity in Multidimensional Linear Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2016/051},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.