原始发布日期:2026-10-11,arXiv:2610.15265v1。Thijs Laarhoven 研究的是行列式为一、按 Haar 测度抽取的随机格,在最短向量半径附近进行不剪枝枚举时,树的规模如何随维数增长。论文把规模写成 n 的 cn+o(n) 次方,核心问题是换用怎样的基,才能减小其中的常数 c。
论文先分析准 HKZ 基的几何形状,将此前的启发式预测推进为随机格模型下的高概率结论:完整枚举树的主导常数为 1/(2e),约 0.1839。这个结果描述特定模型和搜索方式的渐近规模,并没有声称枚举在现实维数上已经超过筛法,也不是任何格密码实例的直接攻击时间。
随后作者利用稠密的本原子格,把格拆为子格及其正交商格,对两部分分别使用反向对偶 HKZ 和 HKZ 基。单次近似对半分块将常数降到约 0.1516;递归分块可进一步降到 0.1474 以下。证明不仅需要候选子格数量的期望,还要控制交叠候选的相关性,以建立所需子格高概率存在。
下界分析则从嵌套本原子格链的平均值公式出发,限制基的前缀行列式轮廓,得到约 0.1464 的通用下界。额外采用论文明确列出的第一矩充分性假设,分块构造才可逼近这个下界。作者将无须该假设的上下界,与依赖假设的更强结论分开,不能把二者合并成已经完全解决的最优性证明。
算法应用仍有一道重要门槛:找到这些稠密子格本身可能非常昂贵。论文给出的随机格 CVPP 查询算法,在不计算预处理成本时,查询时间约为 n 的 0.08913n+o(n) 次方且使用多项式空间;这不直接给出更快的完整 SVP 算法。原文采用 CC BY-SA 4.0,本文编译部分标明改写,并按同一许可提供。
量仔观察
本站认为,这项工作值得纳入算法安全评估,因为它同时研究攻击子程序的几何收益和理论边界,而非只报告一次实现提速。对参数评估者而言,最有用的区分是树节点数、搜索算法成本和获得输入基的成本。若忽略第三项,便会把一个有价值的存在性结果错误地写成低成本密钥恢复。
目前不宜据此修改某个标准参数集的安全位数。要走到这一步,还需要解释结构化密码格与 Haar 随机格模型之间的联系、有限维数及低阶项的影响,以及预处理在攻击总预算中的占比。本站未独立复核全部证明,以上数学结论均按作者论文陈述报道。
