New Observation on Division Property

Bing Sun; Xin Hai; Wenyu Zhang; Lei Cheng; Zhichao Yang

Paper 2015/459

New Observation on Division Property

Bing Sun, Xin Hai, Wenyu Zhang, Lei Cheng, and Zhichao Yang

Abstract

Feistel structure is among the most popular choices for designing ciphers. Recently, 3-round/5-round integral distinguishers for Feistel structures with non-bijective/bijective round functions are presented. At EUROCRYPT 2015, Todo proposed the Division Property to effectively construct integral distinguishers for both Feistel and SPN structures. In this paper, firstly, it is proved that if X, which is a subset of F_2^n, has the division property D_k^n, the number of elements in X is at least 2^k, based on which we can conclude that if a multi-set X has the division property D_n^n, it is in some sense equivalent to either F_2^n or the empty set. Secondly, let d be the algebraic degree of the round function of a Feistel structure. If d\le n-1, the corresponding integral distinguishers are improved as follows: there exists a 3-round integral distinguisher with at most 2^n chosen plaintexts and a 4-round integral distinguisher with at most 2^{2n-2} chosen plaintexts. These results can give new insights to both the division property and Feistel structures.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. Science China, Information Science
Keywords: Feistel structure Integral cryptanalysis Division property
Contact author(s): happy_come @ 163 com
History: 2016-08-22: last of 3 revisions; 2015-05-14: received; See all versions
Short URL: https://ia.cr/2015/459
License: CC BY

BibTeX

@misc{cryptoeprint:2015/459,
      author = {Bing Sun and Xin Hai and Wenyu Zhang and Lei Cheng and Zhichao Yang},
      title = {New Observation on Division Property},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/459},
      year = {2015},
      url = {https://eprint.iacr.org/2015/459}
}