基于混合整数线性规划模型的SPONGENTS盒紧凑约束分析  

Compact constraint analysis of SPONGENT S-box based on mixed integer linear programming model

作　　者：石一鹏 刘杰[1] 祖锦源 张涛[1] 张国群 SHI Yipeng;LIU Jie;ZU Jinyuan;ZHANG Tao;ZHANG Guoqun(School of Software,Northwestern Polytechnical University,Xi􀆳an Shaanxi 710129,China;Shanghai Institute of Mechanical and Electrical Engineering,Shanghai 201109,China)

机构地区：[1]西北工业大学软件学院,西安710129 [2]上海机电工程研究所,上海201109

出　　处：《计算机应用》2023年第5期1504-1510,共7页journal of Computer Applications

基　　金：上海航天科技创新基金资助项目(SAST2021‑054);太仓市基础研究计划面上项目(TC2021JC32);中央高校基本科研业务费专项资金资助项目(D5000210638)。

摘　　要：应用基于混合整数线性规划(MILP)模型的S盒紧凑约束计算方法,可以较好地解决SPONGENT在差分密码分析过程中差分路径搜索效率低下的问题;为寻找S盒的最优描述,提出一种紧凑性验证算法从约束条件存在必要性的角度验证S盒的不等式约束的紧凑性问题。首先,引入MILP模型分析SPONGENT S盒的不等式约束,得到了由23个不等式组成的约束;然后,提出一种用于评价约束不等式存在必要性的指标,并基于该指标提出了一种验证约束不等式组紧凑程度的紧凑性验证算法;最后,使用所提算法验证所求得的SPONGENT S盒约束的紧凑性。计算分析表明,23个不等式都具有唯一可以排除的不可能差分模式,即每个不等式都有存在的必要性;同时,对于同一案例,与利用贪心算法原理筛选的不等式相比,数量减少了20%。因此,所得到的SPONGENT的S盒不等式约束是紧凑的,且所提紧凑性验证算法的效果要优于对比的贪心算法。Applying the compact constraint calculation method of S-box based on Mixed Integer Linear Programming(MILP)model can solve the low efficiency of differential path search of SPONGENT in differential cryptanalysis.To find the best description of S box,a compactness verification algorithm was proposed to verify the inequality constraints in S-box from the perspective of the necessity of the existence of constraints.Firstly,the MILP model was introduced to analyze the inequality constraints of SPONGENT S-box,and the constraint composed of 23 inequalities was obtained.Then,an index for evaluating the existence necessity of constraint inequality was proposed,and a compactness verification algorithm for verifying the compactness of group of constraint inequalities was proposed based on this index.Finally,the compactness of the obtained SPONGENT S-box constraint was verified by using the proposed algorithm.Calculation analysis show that the 23 inequalities have a unique impossible difference mode that can be excluded,that is,each inequality has the necessity of existence.Furthermore,for the same case,the number of inequalities was reduced by 20%compared to that screened by using the greedy algorithm principle.Therefore,the obtained inequality constraint of S-box in SPONGENT is compact,and the proposed compactness verification algorithm outperforms the greedy algorithm.

关 键 词：差分密码分析 混合整数线性规划 代换‒置换网络 SPONGENT S盒 

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