Automatic Search for A Variant of Division Property Using Three Subsets (Full Version)
Automatic Search for A Variant of Division Property Using Three Subsets (Full Version)
复制标题
DOI：
10.1007/978-3-030-12612-4_21
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Kai Hu;Meiqin Wang
中科院分区：
文献类型：
--
作者：
Kai Hu;Meiqin Wang
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 theXORoperation for(The definition ofandis 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 fromshould be appended towhenKey-XORoperation 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 intofromin 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.
