Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

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