SuperBall: A New Approach for MILP Modelings of Boolean Functions

Abstract

Mixed Integer Linear Programming (MILP) solver has become one of the most powerful tools of searching for cryptographic characteristics. It has great significance to study the influencing factors of the efficiency of MILP models. For this goal, different types of MILP models should be constructed and carefully studied. As Boolean functions are the fundamental cryptographic components, in this paper, we study the descriptive models of Boolean functions. Here, a descriptive model of a Boolean function refers to a set of integer linear inequalities, where the set of the binary solutions to these inequalities is exactly the support of this Boolean function. Previously, it is hard to construct various types of descriptive models for study, one important reason is that only a few kinds of inequalities can be generated. On seeing this, a new approach, called SuperBall, is proposed to generate inequalities. The SuperBall approach is based on the method of undetermined coefficients, and it could generate almost all kinds of inequalities by appending appropriate constraints. Besides, the Sasaki-Todo Algorithm is also improved to construct the descriptive models from a set of candidate inequalities by considering both their sizes and strengths, while the strengths of descriptive models have not been considered in the previous works. As applications, we constructed several types of descriptive models for the Sboxes of Liliput, SKINNY-128, and AES. The experimental results first prove that the diversity of the inequalities generated by the SuperBall approach is good. More importantly, the results show that the strengths of descriptive model do affect the efficiencies, and although there is not a type of descriptive model having the best efficiency in all experiments, we did find a specific type of descriptive model which has the minimal size and relatively large strength, and the descriptive models of this type have better efficiencies in most of our experiments.