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