Z2n上点集整系数线性不等式完全刻画

分类： 数学 >> 应用数学 提交时间： 2022-11-09

冯秀涛 田宇 王永兴 徐圣源 张安鹏

摘要： 近年来，混合整数线性规划(MILP)被广泛用到对称密码的自动化分析中，并逐渐成为一个强有力的工具。在MILP方法中，一个核心的数学问题就是：对给定的Z2n上的高维离散点集S，如何利用尽可能少的不等式刻画它，简称整系数线性不等式完全刻画问题(FLIIIC problem)。该问题是NP-hard的。在这个工作中，我们是首次针对该问题给出了完整的求解理论。我们的方法从Plain集合出发，即由单个线性不等式确定的解集，揭示了其一系列内在属性，包括型、稀疏度、第一类退化、第二类退化，序、极小元、极大元、范数和界。在此基础上我们进一步给出了刻画Plain集合的一个充分必要条件，即集合S是Plain集合的充分必要条件是S集合是good集合。基于上述知识，对任意给定的子集S，我们提出了一个求解S的全部极小闭包和最优线性不等式完全刻画的算法。我们的算法非常高效且实用，可以应用到密码学中各种常见的S盒的刻画。据我们所知，这是首次给出了各种常见S盒的全部极小闭包，且我们得到的所有刻画结果都是目前最好的结果，尤其时在高维S盒刻画方面，我们的结果远优于国内外同行的结果。

同行评议状态:待评议

 点击量 2506  下载量 502  评论