求解子集和问题的采样格归约算法  

Sampling-based Lattice Reduction Algorithm for Subset Sum Problem

作　　者：曹金政 程庆丰[1,2] 史闻博 鲁宁 CAO Jin-Zheng;CHENG Qing-Feng;SHI Wen-Bo;LU Ning(Strategic Support Force Information Engineering University,Zhengzhou 450001,China;State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China;School of Computer and Communication Engineering,Northeastern University at Qinhuangdao,Qinhuangdao 066004,China;School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China;School of Computer Science and Technology,Xidian University,Xi’an 710126,China)

机构地区：[1]战略支援部队信息工程大学,河南郑州450001 [2]数学工程与先进计算国家重点实验室,河南郑州450001 [3]东北大学秦皇岛分校计算机与通信工程学院,河北秦皇岛066004 [4]东北大学计算机科学与工程学院,辽宁沈阳110169 [5]西安电子科技大学计算机科学与技术学院,陕西西安710126

出　　处：《软件学报》2022年第11期3917-3929,共13页Journal of Software

基　　金：国家自然科学基金(61872449,62072092,62072093)。

摘　　要：子集和问题是计算机科学中的重要问题,也是构建多种公钥密码体制的基础.提出了采样归约算法,使用随机采样方法降低问题维度,将原问题分解并归约为多个更小规模的格上最短向量,降低了构造格的半径,从而提高求解的效率,得到原问题的精确解或提高近似解的逼近程度.给出了理论上采样归约算法最差情况的成功率.更进一步地,在目标解重量较低的情况下,可以进行分段采样,对问题增加限定条件,提高解题效率.实验结果表明,对于高维度的子集和问题,与CJLOSS等已有的格归约子集和问题方法相比,该算法可以更高效地求解出问题的精确解,而且可以提高近似解的逼近程度,输出近似解的平均长度达到了CJLOSS算法的0.55倍、DR算法的0.64倍.The subset sum problem is an important problem in computer science and the basis for constructing many public key cryptosystems.A random sampling method is proposed,so the dimension of the problem can be reduced by decomposing the original problem into multiple smaller subsets sum problems,reducing the radius of the constructed lattice,thereby improving the efficiency of solving SVP,and then reaching the solution.The theoretically worst-case success rate of the algorithm is given,and a possible method to improve the success rate of the algorithm is given based on the 0-1 distribution of the solution vector,when the weight of target solution is low,the solution vector is divided into sectors,thus applying restrictive conditions to the problem to improve the efficiency of problem-solving.Experimental results show that for high-dimensional subsets and problems,compared with the existing lattice reduction subsets and problem methods such as CJLOSS,the proposed algorithm can solve the exact solution of the problem more efficiently,and can improve the approximation degree of the approximate solution,the average length of the output approximate solution is 0.55 times that of the CJLOSS algorithm and 0.64 times that of the DR algorithm.

关 键 词：子集和问题 格归约方法 降维算法 近似解 

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