密码学报（中英文）2024，Vol.11Issue(5)：1090-1107,18.DOI:10.13868/j.cnki.jcr.000636
平均情况下BKZ算法的启发式分析
A Heuristic Average-Case Analysis of BKZ Algorithm
摘要
Abstract
The most widely used lattice basis reduction algorithm-BKZ algorithm,is one of the most important tools to attack lattice-based cryptosystems or estimate their security.However,how to predict the practical performance of BKZ algorithm is a well-known challenging problem.Based on dynamical systems,Hanrot et al.firstly proposed an analysis on BKZ in 2011 and gave a polynomial bound on the number of SVP oracle calls while preserving the quality of its outputs.Recently,Li and Nguyen improved this analysis and gave better bounds for both the output quality and the running time.However,there are some remaining problems:(1)the effect of LLL reduction procedures after SVP oracle calls cannot be explained reasonably in the dynamic analysis;(2)the previous results are both worst-case analyses which have a gap with the practical performance of BKZ.In this paper,a heuristic average-case analysis on BKZ algorithm is proposed based on Gaussian Heuristic by using the dynamical system method,where the effect of LLL reduction procedures after SVP oracle calls can be analyzed based on Geometric Series Assumption.The analysis results in this paper are better and can give more accurate theoretical estimations of the output quality for BKZ algorithm in practice which can be verified by the experiments.关键词
格基约化算法/动力系统/平均情况下分析/高斯启发式/几何级数假设Key words
lattice basis reduction algorithm/dynamical systems/average-case analysis/Gaussian heuristic/geometric series assumption分类
信息技术与安全科学引用本文复制引用
孙明豪,王世雄,屈龙江..平均情况下BKZ算法的启发式分析[J].密码学报（中英文）,2024,11(5):1090-1107,18.基金项目
国家自然科学基金(62032009,62102440)National Natural Science Foundation of China(62032009,62102440) （62032009,62102440）
