Paper 2010/325

Effect of the Dependent Paths in Linear Hull

Zhenli Dai, Meiqin Wang, and Yue Sun


Linear Hull is a phenomenon that there are a lot of linear paths with the same data mask but different key masks for a block cipher. In 1994, K. Nyberg presented the effect on the key-recovery attack such as Algorithm 2 with linear hull, in which the required number of the known plaintexts can be decreased compared with that in the attack using an individual linear path. In 2009, S. Murphy proved that K. Nyberg's results can only be used to give a lower bound on the data complexity and will be no use on the real linear cryptanalysis. In fact, the linear hull produces such positive effect in linear cryptanalysis only for some keys instead of the whole key space. So the linear hull can be used to improve the classic linear cryptanalysis for some weak keys. In the same year, K. Ohkuma gave the linear hull analysis on reduced-round PRESENT block cipher, and showed that there are $32\%$ weak keys of PRESENT which make the bias of a given linear hull with multiple paths more than a lower bound. However, K. Ohkuma has not considered the dependency of the multi-path, and his results are based on the assumption that the linear paths are independent. Actually, most of the linear paths are dependent in the linear hull. In this paper, we will analyze the dependency of the linear paths in a linear hull and the real effect of linear hull with the dependent linear paths. Firstly, we give the relation between the bias of a linear hull and its linear paths in linear cryptanalysis. Secondly, we present the formula to compute the rate of weak keys corresponding to the expected bias of the dependent paths. Based on the formula, we show that the dependency of linear paths reduces the number of weak keys corresponding to higher biases of the linear hull compared with that in the independent case. It means that the dependency of linear paths reduces the effect of linear hull. At last, we verify our conclusion by analyzing reduced-round of PRESENT.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Linear HullDependency of Linear PathsWeak KeyPRESENTBlock Cipher
Contact author(s)
mqwang @ sdu edu cn
2010-11-07: revised
2010-06-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenli Dai and Meiqin Wang and Yue Sun},
      title = {Effect of the Dependent Paths in Linear Hull},
      howpublished = {Cryptology ePrint Archive, Paper 2010/325},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.