S盒可分特征的线性不等式刻画研究

The Characterization of Division Trails of S-box by Using Linear Inequalities

S盒可分特征的刻画是自动化积分分析的关键。为实现通用性,支持动态S盒和大状态S盒的刻画,给出了3种线性不等式刻画方法及其一般刻画形式,其中,凸包的H表示方法不会引入临时变量,其一般刻画形式使用的线性不等式数量最少,但属于非等价刻画;大M方法在引入一个二进制临时变量的情况下实现等价刻画,但线性不等式数量最多;维数扩充法同样引入一个二进制临时变量,在实现等价刻画的同时线性不等式数量与凸包的H表示方法相当,刻画效果最优。

The characterization of division trails of S-box is very important for automatic integral cryptanalysis. In order to realize universality and support dynamic S-box and large S-box, three methods to characterize division trails by using linear inequalities and their general forms are studied. Among them, the H-representation-of-convex-hull method does not introduce temporary variables, and the corresponding general form uses the least number of linear inequalities, but it belongs to non-equivalent characterization.The big-M method realizes equivalent characterization by introducing a binary temporary variable, but uses the maximum number of linear inequalities. The dimension-extend method also introduces a binary temporary variable and realizes equivalent characterization. At the same time, it almost uses the same number of linear inequalities as the H-representation-of-convex-hull method. It is the best method to characterize division trails of S-box by using linear inequalities.