Efficient Algorithms for Modeling SBoxes Using MILP

Mixed Integer Linear Programming (MILP) is a well-known approach for the cryptanalysis of a symmetric cipher. A number of MILP-based security analyses have been reported for non-linear (SBoxes) and linear layers. Researchers proposed word- and bit-wise SBox modeling techniques using a set of inequalities which helps in searching differential trails for a cipher. In this paper, we propose two new techniques to reduce the number of inequalities to represent the valid differential transitions for SBoxes. Our first technique chooses the best greedy solution with a random tiebreaker and achieves improved results for the 4-bit SBoxes of MIBS, LBlock, and Serpent over the existing results of Sun et al. [25]. Subset addition, our second approach, is an improvement over the algorithm proposed by Boura and Coggia. Subset addition technique is faster than Boura and Coggia [10] and also improves the count of inequalities. Our algorithm emulates the existing results for the 4-bit SBoxes of Minalpher, LBlock, Serpent, Prince, and Rectangle. The subset addition method also works for 5-bit and 6-bit SBoxes. We improve the boundary of minimum number inequalities from the existing results for 5-bit SBoxes of ASCON and SC2000. Application of subset addition technique for 6-bit SBoxes of APN, FIDES, and SC2000 enhances the existing results. By applying multithreading, we reduced the execution time needed to find the minimum inequality set over the existing techniques.