标题：Automatic Search for a Variant of Division Property Using Three Subsets
作者：Hu, Kai ;Wang, Meiqin
作者机构：[Hu, K] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, 250100, China;[ Wang, M] 更多
会议名称：Cryptographers Track at the RSA Conference 2019, CT-RSA 2019
会议日期：4 March 2019 through 8 March 2019
来源：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
关键词：Automatic research; Division property; STP; Three-subset
摘要：The division property proposed at Eurocrypt’15 is a novel technique to find integral distinguishers, which has been applied to most kinds of symmetric ciphers such as block ciphers, stream ciphers, and authenticated encryption,Â etc. The original division property is word-oriented, and later the bit-based one was proposed at FSE’16 to get better integral property, which is composed of conventional bit-based division property (two-subset division property) and bit-based division property using three subsets (three-subset division property). Three-subset division property has more potential to achieve better integral distinguishers compared with the two-subset division property. The bit-based division property could not be to apply to ciphers with large block sizes due to its unpractical complexity. At Asiacrypt’16, the two-subset division property was modeled using Mixed Integral Linear Programming (MILP) technique, and the limits of block sizes were eliminated. However, there is still no efficient method searching for three-subset division property. The propagation rule of the XOR operation for L (The definition of L and K is introduced in Sect.Â 2.), which is a set used in the three-subset division property but not in two-subset one, requires to remove some specific vectors, and new vectors generated from L should be appended to K when Key-XOR operation is applied, both of which are difficult for common automatic tools such as MILP, SMT or CP. In this paper, we overcome one of the two challenges, concretely, we address the problem to add new vectors into K from L in an automatic search model. Moreover, we present a new model automatically searching for a variant three-subset division property (VTDP) with STP solver. The variant is weaker than the original three-subset division property (OTDP) but it is still powerful in some ciphers. Most importantly, this model has no constraints on the block size of target ciphers, which can also be applied to ARX and S-box based ciphers. As illustrations, some improved integral distinguishers have been achieved for SIMON32, SIMON32/48/64(102), SPECK32 and KATAN/KTANTAN32/48/64 according to the number of rounds or number of even/odd-parity bits. © 2019, Springer Nature Switzerland AG.