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

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

作　　者：胡建勇 张文政[1,2] 董新锋[1,2] 周宇[1,2] 苗旭东 HU Jianyong;ZHANG Wenzheng;DONG Xinfeng;ZHOU Yu;MIAO Xudong(No.30 Institute of CETC,Chengdu Sichuan 610041,China;Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041,China)

机构地区：[1]中国电子科技集团公司第三十研究所,四川成都610041 [2]保密通信重点实验室,四川成都610041

出　　处：《通信技术》2022年第4期480-485,共6页Communications Technology

基　　金：国家重点研发计划(2020YFC1522900);四川省科技计划(2020JDJQ0076)。

摘　　要：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.

关 键 词：S盒 积分分析 可分性质 线性不等式 凸包 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]