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

作者：石一鹏; 刘杰; 祖锦源; 张涛; 张国群

来源：计算机应用, 2022, 1-9.

• 差分密码分析
• 混合整数线性规划
• 代换-置换网络
• SPONGENT
• S盒

为了解决SPONGENT在差分密码分析过程中差分路径搜索效率低下的问题，应用了基于混合整数线性规划模型（MILP）的S盒紧凑约束计算方法；对于S盒的不等式约束缺乏紧凑性验证的问题，提出了一种紧凑性验证算法。首先引入MILP模型针对SPONGENT的S盒进行不等式约束分析，得到了由23个不等式组成的约束，并且提出了一种用于评价约束不等式存在必要性的指标；然后基于该指标提出了一种验证约束不等式组紧凑程度的紧凑性验证算法；最后使用紧凑性算法对所求得的SPONGENTS盒约束进行了紧凑性验证。计算分析表明，所有的23个不等式都具有唯一可以排除的不可能差分模式，即每个不等式都有存在的必要性。同时，针对案例使用紧凑性验证算法，与2014年Sun等提出的贪心算法相比，不等式数量减少了20%。因此，所得到的SPONGENT的S盒不等式约束是紧凑的，所提出的紧凑性验证算法对于Sun等提出的贪心算法具有优化作用。

• 单位
  西北工业大学; 上海机电工程研究所