子格筛法的两种优化方法  

Two Optimization Methods of SubSieve Algorithm

作　　者：张维 孙明豪 屈龙江[1,2] ZHANG Wei;SUN Ming-Hao;QU Long-Jiang(College of Science,National University of Defense Technology,Changsha 410073,China;Hunan Engineering Research Center of Commercial Cryptography Theory and Technology Innovation,Changsha 410073,China)

机构地区：[1]国防科技大学理学院,长沙410073 [2]商用密码理论与技术创新湖南省工程研究中心,长沙410073

出　　处：《密码学报》2023年第3期476-490,共15页Journal of Cryptologic Research

基　　金：国家自然科学基金(62032009)。

摘　　要：子格筛法是求解格上最短向量问题(shortest vector problem,SVP)的一个高效算法,通过在(n-d)维投影子格上调用高斯筛法以求解n维格上的SVP问题,其中d是自由维数.子格筛法的降维思想有效降低了筛法的时间复杂度,缩小了与枚举算法运行效率的差距.本文在简要回顾高斯筛法和子格筛法的算法思想及运行机理的基础上,提出子格筛法的两种优化方法.通过调整高斯筛法的算法参数,改变算法输出包含的信息,增大了子格筛法的自由维数d,从而降低了算法的时间复杂度;在子格筛法最重要的子程序高斯筛法中加入过滤器,在更新列表向量的同时可以更快地完成筛选,从而将高斯筛法的二次搜索过程降低为亚二次搜索过程,节约了算法的运行时间;综合应用上述两种方法优化子格筛法,提出Filteredα-子格筛法.实验数据表明两种优化方法都能有效提升子格筛法的运行效率.在70–86维的随机格上,Filteredα-子格筛法的运行效率相比于初始子格筛法最高提升了约58.8%,平均提高了约41.7%.The SubSieve algorithm is an efficient algorithm for solving the shortest vector problem(SVP)on lattices which uses a few calls to the GaussSieve algorithm on the(n-d)-dimensional projected sublattice to solve the SVP on an n-dimensional lattice,where d is the free dimension.The idea of dimensional reduction of the SubSieve algorithm effectively reduces the time complexity of the sieve and narrows the gap in the running efficiency with the enumeration algorithm.This paper briefly reviews the main idea and the mechanisms of the GaussSieve algorithm and the SubSieve algorithm.Subsequently,two methods are proposed to improve the SubSieve algorithm.First,by adjusting the algorithm parameters of the GaussSieve algorithm to change its output,the free dimension d of the SubSieve algorithm can be increased,and the time complexity is reduced.Second,by adding filters to the GaussSieve algorithm which is the most important subroutine of the SubSieve algorithm,the vectors can be sieved more quickly when the list is updated.By this way,the quadratic search can be reduced in the GaussSieve algorithm to a sub-quadratic search process and the runtime is reduced.Finally,the above two methods are applied to optimize the SubSieve algorithm,forming the Filteredα-SubSieve algorithm.According to the experimental results,the above two methods do improve the efficiency of the initial SubSieve algorithm.On random lattices in dimension 70–86,compared with that of the initial SubSieve algorithm,the efficiency of the Filteredα-SubSieve algorithm can be improved by up to 58.8%and 41.7%on average.

关 键 词：格 子格筛法 最短向量问题 自由维数 过滤器 

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