F_(2)^(n)中点集的线性不等式刻画  

Linear Inequality Description of Point Set in F_(2)^(n)

作　　者：董军武[1] 张晓磊 Dong Junwu;Zhang Xiaolei(College of Mathematics and Information Science,Guangzhou University,Guangzhou Guangdong 510006,China)

机构地区：[1]广州大学数学与信息科学学院,广东广州510006

出　　处：《信息安全与通信保密》2023年第9期65-78,共14页Information Security and Communications Privacy

摘　　要：在分组密码的差分攻击中,为了利用计算机搜索最佳差分路径,人们将问题转换为其S-盒的差分分布表的最佳线性不等式逼近问题。确切地说,给定向量空间F_(2)^(n)的一个非空点集A,寻找数目尽可能少的一次多项式的集合,使得满足所有多项式的值均大于或等于0的点集恰好为给定的点集A。在文献中能看到的做法通常是利用计算机软件(例如SAGE数学软件)算出很多的多项式,再用线性规划的方法从中挑选出最小个数的多项式。研究一次多项式的产生方法,称F_(2)^(n)中的点集S是相容的,是指存在某个整系数一次多项式f(X),使得S={P∈F_(2)^(n)|f(P)<0}。主要有以下3个方面的结果:一是给定向量空间的维数n,对任意的1≤k≤2n,一定存在k元相容点集S;二是利用多项式加法的技巧,构造出一批k元相容点集;三是对于小参数k=1,2,3,4,给出k元点集S是相容的充分必要条件,同时也给出相应的k元相容点集的计数公式。In differential attacks on block ciphers,in order to search the optimal differential path by computer,people transform the problem into the optimal linear inequality approximation problem of the differential distribution table of its S-box.Precisely,given a nonempty point set A of the vector space F_(2)^(n),and find the set of primary polynomials whose number is as small as possible such that the set of points satisfying the value of all polynomials≥0 is exactly the given point set A.The method in the literature is usually to use computer software such as SAGE Math to generate many polynomials,and then use linear programming method to select the minimum number of polynomials.This paper studies the method of generating a primary polynomial.To call the set S of points in F2 n compatible is to say that there exists some integer coefficient primary polynomial f(X)such that S={P∈F2 n|f(P)<0}.The main results of this paper are as follows:firstly,given the dimension n of a vector space,for any positive integer 1≤k≤2n,there must exist a compatible point set S with k elements;secondly,by using the technique of polynomial addition,many classes of compatible point sets with k elements are constructed;thirdly,for small parameters k=1,2,3,4,a sufficiently and necessary condition for a point set S with k elements to be compatible is given,as well as a counting formula for the corresponding k-element compatible point set.

关 键 词：差分分布表 相容点集 多项式加法 单位向量子空间 单位仿射子空间 

分 类 号：TN918.1[电子电信—通信与信息系统] O236.2[电子电信—信息与通信工程]