-
题名一种适用于高维格基约化的综合算法
- 1
-
-
作者
曹金政
程庆丰
李兴华
-
机构
战略支援部队信息工程大学
数学工程与先进计算国家重点实验室
西安电子科技大学网络与信息安全学院
-
出处
《计算机学报》
EI
CAS
CSCD
北大核心
2021年第5期937-947,共11页
-
基金
国家自然科学基金项目(61872449,U1708262,U1736203)资助.
-
文摘
格基约化算法是求解格上最短向量问题(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%.
-
关键词
格基约化
最短向量问题
bkz算法
筛法
-
Keywords
lattice basis reduction
shortest vector problem
bkz lattice reduction algorithm
sieving
-
分类号
TP309
[自动化与计算机技术—计算机系统结构]
-
