摘要
格基约化算法是求解格上最短向量问题(SVP)的一类算法,在格理论中有重要地位,尤其在格理论构造的公钥密码中发挥重要作用.目前公认效率最高的主流算法是Blockwise-Korkine-Zolotarev(BKZ)及其改进形式BKZ 2.0,主要思想是分块约化,调用多项式次的局部格上SVP算法.但是BKZ类算法仍然存在约化程度不够充分、在高维度格中约化效率不高的问题,也存在多种改进的算法.本文在已有算法的基础上,对BKZ结构进行优化,并应用筛法的最新研究成果,设计了一种新的综合算法——Blockwise-Sieving-Reduction(BSR).在预处理阶段,将格矩阵划分后分别进行BKZ预处理,该过程可直接进行并行化.在格基约化阶段,该算法结合BKZ算法与筛法的优点,使用分块逐次增大的多轮BKZ算法进行预处理,并在BKZ结构中使用改进的筛法替代原有的枚举子过程,通过插入向量改进局部格的性质,提高了BKZ算法的效率,使之能在更大的分块下求解SVP.针对更高维度的格矩阵,设计了递归调用的算法变种,称为i-BSR算法,该算法使用了渐进约化等实现技术,可以进行更大维度格的约化.从理论角度进行分析,论证了该算法可以进行格基约化并求格上短向量.实验结果表明,该算法在较大分块下,能够以可接受的时间代价完成SVP求解,且得到的向量优于已有算法的实验结果,新算法得到的首向量长度可以缩短至BKZ 2.0的90%.
The lattice reduction theory is key to the lattice theory and specifically lattice cryptology.It is recognized that lattice reduction algorithm is the most practical method to solve the shortest vector problem in the lattice and therefore plays an increasingly important role in cryptography.Today the most efficient and most welcome algorithm is Blockwise-Korkine-Zolotarev(BKZ)and its improved form BKZ 2.0,which will give a short lattice vector after calling SVP oracle on projected sublattices for polynomial times,yet these algorithms still cannot reduce the lattice to our expectations,and there have been several proposals for improved or modified algorithms using the basic idea and structure of BKZ.Based on the existing algorithms,we optimize the block wise reduction structure and apply the latest research results of the sieving method to design a new comprehensive algorithm in large lattices,Blockwise-Sieving-Reduction(BSR).We explain that our algorithm can serve as a lattice reduction algorithm and give a short vector in the lattice not worse than BKZ.It has been found that certain versions of sieving are more efficient in solving SVP of large dimension than enumeration that is embedded in BKZ-like algorithms.We show that our algorithm combines the block wise reduction structure of BKZ algorithm and the efficiency of sieve method.Furthermore,we try a new way to preprocess the lattice before the main reduction process.We divide the entire lattice matrix into several small lattice matrices while maintain the lattice vectors,then we apply multiple rounds of BKZ algorithm with different small block sizes to increase the speed of pre-processing.In this part,we can run parallel threads,each for the reduction of a sub-lattice.This is a plain application of parallel computing and requires no modifications on the algorithm.In the main reduction phase,our algorithm replaces the original enumeration sub-process in the BKZ structure with the improved version of sieve method to get a short vector in projected lattices.We expect that this modification will give us shorter sublattice vectors and therefore improve the properties of the local projected lattices,so as to improve the efficiency of the lattice reduction algorithm to make it capable of solving the SVP under a larger block.For the reduction of larger lattice matrices,we implement a recursive variant of BSR,named i-BSR.Our algorithm run the BSR process recursively,and uses more specific techniques such as progressive reduction.We design i-BSR as a optimized version of BSR algorithm to make it suitable for larger lattices of bigger dimension.In theory,we demonstrate that the algorithm can solve approximate SVP.We make experiments on lattices of different dimensions,from 35 to 888,and ranks from 9 to 111.The experiment results show that the algorithm can complete the SVP solution with an acceptable time cost with larger block than BKZ,and the obtained vector is better than the experimental results of the existing algorithm.By comparation,the length of the first vector obtained by the new algorithm can be shortened to 90%of BKZ 2.0.
作者
曹金政
程庆丰
李兴华
CAO Jin-Zheng;CHENG Qing-Feng;LI Xing-Hua(Strategic Support Force Information Engineering University,Zhengzhou 450001;State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001;School of Cyber Engineering,Xidian University,Xi’an 710071)
出处
《计算机学报》
EI
CAS
CSCD
北大核心
2021年第5期937-947,共11页
Chinese Journal of Computers
基金
国家自然科学基金项目(61872449,U1708262,U1736203)资助.
关键词
格基约化
最短向量问题
BKZ算法
筛法
lattice basis reduction
shortest vector problem
BKZ lattice reduction algorithm
sieving
