Paper 2016/096
Provable Security Evaluation of Structures against Impossible Differential and Zero Correlation Linear Cryptanalysis
Bing Sun, Meicheng Liu, Jian Guo, Vincent Rijmen, and Ruilin Li
Abstract
Impossible differential and zero correlation linear cryptanalysis are two of the most important cryptanalytic vectors. To characterize the impossible differentials and zero correlation linear hulls which are independent of the choices of the nonlinear components, Sun et al. proposed the structure deduced by a block cipher at CRYPTO 2015. Based on that, we concentrate in this paper on the security of the SPN structure and Feistel structure with SPtype round functions. Firstly, we prove that for an SPN structure, if \alpha_1\rightarrow\beta_1 and \alpha_2\rightarrow\beta_ are possible differentials, \alpha_1\alpha_2\rightarrow\beta_1\beta_2 is also a possible differential, i.e., the OR "" operation preserves differentials. Secondly, we show that for an SPN structure, there exists an rround impossible differential if and only if there exists an rround impossible differential \alpha\not\rightarrow\beta where the Hamming weights of both \alpha and \beta are 1. Thus for an SPN structure operating on m bytes, the computation complexity for deciding whether there exists an impossible differential can be reduced from O(2^{2m}) to O(m^2). Thirdly, we associate a primitive index with the linear layers of SPN structures. Based on the matrices theory over integer rings, we prove that the length of impossible differentials of an SPN structure is upper bounded by the primitive index of the linear layers. As a result we show that, unless the details of the Sboxes are considered, there do not exist 5round impossible differentials for the AES and ARIA. Lastly, based on the links between impossible differential and zero correlation linear hull, we projected these results on impossible differentials to zero correlation linear hulls. It is interesting to note some of our results also apply to the Feistel structures with SPtype round functions.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published by the IACR in EUROCRYPT 2016
 Keywords
 Impossible differentialZero correlation linearSPN structureFeistel structureAESCamelliaARIA
 Contact author(s)
 happy_come @ 163 com
 History
 20160205: received
 Short URL
 https://ia.cr/2016/096
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/096, author = {Bing Sun and Meicheng Liu and Jian Guo and Vincent Rijmen and Ruilin Li}, title = {Provable Security Evaluation of Structures against Impossible Differential and Zero Correlation Linear Cryptanalysis}, howpublished = {Cryptology ePrint Archive, Paper 2016/096}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/096}}, url = {https://eprint.iacr.org/2016/096} }