该论文研究 F_3^n 上的向量子集和问题:给定 m 个取自 F_3^n 的随机向量,要求找出一个非空子集使其向量和为零;m 越小,问题越难。该问题与后量子密码(尤其是基于 LWE 的构造)以及组合优化密切相关,也是量子优势研究中的经典试验场。此前 Chen、Liu、Zhandry(EUROCRYPT'22)提出高效量子算法,在 m≈n²/2 时可多项式时间求解,而朴素经典算法在该参数区间需要指数时间,因此被视为指数级量子加速的候选。随后 Kothari、O'Donnell、Wu(STOC 2026)给出高效经典算法,仅需 m≈n²/3 个向量即可求解,从而在这一参数区间内抹消了量子优势的希望。本文沿用 CLZ 的框架,提出一种所需输入向量远少的量子算法,重新点燃指数级量子加速的可能性:对任意固定 ε>0,其量子算法在仅 m=ε·n² 个向量时即可多项式时间求解 F_3-子集和。作者进一步建立完整的“样本量—运行时间”权衡曲线,在指数时间与多项式时间之间连续插值,而不再只是单点结果。核心技术成分是一个针对二进制误差 LWE(Binary-Error LWE)的确定性经典算法,具有独立的密码学意义:作者严格证明了此前仅由代数启发式所预测的样本—时间权衡关系,为该类问题的算法能力提供了严谨刻画。此外,对于更大有限域上的向量子集和问题,本文也显著改进了 KOW 的经典算法。总体而言,论文同时推进了量子算法的上界研究与格密码分析两条主线,属于理论层面的重要进展,讨论的是渐近复杂度和参数权衡,并不涉及对现实密码系统的实用攻击。
💡 推荐理由: 该工作重新划定了 F_3-子集和问题中量子与经典算法的样本—时间边界,并给出二进制误差 LWE 的严格确定性经典算法及样本—时间权衡,直接影响基于 LWE 的后量子密码参数选取与安全裕度评估的理论依据,值得密码与安全评估方向跟进。
🎯 建议动作: 研究跟进:纳入密码算法与参数评估的内部技术跟踪清单,由理论密码方向同事解读后判断是否影响现有 LWE 类方案的安全裕度。