SuperBall: A New Approach for MILP Modelings of Boolean Functions
SuperBall: A New Approach for MILP Modelings of Boolean Functions
复制标题
DOI：
10.46586/tosc.v2022.i3.341-367
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Ting Li;Yao Sun
中科院分区：
文献类型：
--
作者：
Ting Li;Yao Sun
混合整数线性规划(MILP)解算器已经成为搜索密码特征的最强大的工具之一。研究影响MILP模型效率的因素具有重要意义。为此，应构建不同类型的MILP模型，并对其进行仔细研究。由于布尔函数是密码学的基本组成部分，本文研究了布尔函数的描述模型。这里，布尔函数的描述性模型指的是一组整数线性不等式，其中这些不等式的二元解的集合正好是该布尔函数的支持。以前，很难构造各种类型的描述性模型进行研究，一个重要的原因是只能产生几种类型的不等式。在看到这一点后，一种名为SuperBall的新方法被提出，以产生不平等。SuperBall方法以待定系数法为基础，通过添加适当的约束条件，可以产生几乎所有类型的不等式。此外，本文还对Sasaki-Todo算法进行了改进，从一组候选不等式构造描述模型，同时考虑了它们的大小和优点，而以往的工作没有考虑到描述模型的优点。作为应用，我们为Liliput、Skinny-128和AES的Sbox构建了几种类型的描述模型。实验结果首先证明了SuperBall方法产生的不等式的多样性是好的。更重要的是，实验结果表明，描述性模型的强弱确实会影响描述模型的效率，虽然在所有的实验中并不存在一个效率最高的描述模型，但我们确实找到了一个尺寸最小、强度相对较大的特定类型的描述性模型，并且这种类型的描述性模型在我们的大多数实验中都有较好的效率。
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.