Welcome to the resource topic for 2022/626
Title:
The Simplest SAT Model of Combining Matsui’s Bounding Conditions with Sequential Encoding Method
Authors: Senpeng Wang, Dengguo Feng, Bin Hu, Jie Guan, Tairong Shi, Kai Zhang
Abstract:As the first generic method for finding the optimal differential and linear characteristics, Matsui’s branch and bound search algorithm has played an important role in evaluating the security of symmetric ciphers. By combining the Matsui’s bounding conditions with automatic search models, the search efficiency can be improved. All the previous methods realize the bounding conditions by adding a set of constraints. This may increase the searching complexity of models. In this paper, by using Information Theory to quantify the effect of bounding conditions, we give the general form of bounding conditions that can use all the information provided by Matsui’s bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. Different from all the previous methods, our new method can realize the bounding conditions by removing the variables and clauses from Satisfiability Problem (SAT) models based on the original sequential encoding method. With the help of some small size Mixed Integer Linear Programming (MILP) models, we build the simplest SAT model of combining Matsui’s bounding conditions with sequential encoding method. Then, we apply our new method to search the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables, clauses and the solving time of the SAT models are decreased significantly. And we find some new differential and linear characteristics covering more rounds. For example, the optimal differential probability of the full rounds GIFT128 is obtained for the first time.
ePrint: https://eprint.iacr.org/2022/626
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .