Fast MILP Modelings for Sboxes
Hao Tan, Dong Xu Miao, Bin Shen, Zheng Wen Zhang · 2021
Converting the process of finding a differential characteristic into an automatic solution to the MILP problem can greatly improve the efficiency of cryptographic algorithm evaluation and analysis. S-box is a key component of confusion in block ciphers. When the number of inequalities for modeling S-box difference characteristic is significantly reduced, the solution rate tends to be higher. This article proposes two new algorithms(aggregation algorithm and filter algorithm) for fast modeling of S-boxes. Both algorithms have low time complexity and are easy to implement. The combination of the two algorithms only takes about 10 minutes to describe the 8-bit S-box. In actual engineering applications, the two algorithms can greatly improve the efficiency of users.