本文研究后量子密码核心困难假设 LWE 的量子归约链条。背景上,Regev 曾建立从 LWE 到二面体陪集问题 (DCP) 的量子归约,其后 Brakerski 等人提出外推二面体陪集问题 (EDCP) 并证明其与 LWE 等价。但与 DCP 不同,EDCP 不再具备陪集结构,因此隐藏子群问题 (HSP) 的成熟技术难以直接套用,这成为量子归约分析中的关键瓶颈。作者提出分圆陪集问题 (CCP),即 DCP 的分圆推广,其核心贡献在于该问题保留了精确的隐藏子群结构。构造方式为:取 ζ_p 为本原 p 次单位根,令 π=ζ_p-1,q=p^t,L=t(p-1),在环 R_q = Z_q[ζ_p] ≅ Z[ζ_p]/(π^L) 上工作,该同构来自完全分歧恒等式 (p)=(π)^{p-1}。基于由此得到的 π-adic 理想链,作者构造了一个量子筛,逐级将相位态按模 π^L, π^{L-1}, …, π 递降约化。理论结果显示:对任意固定素数 p 与模数 q=p^t,算法以时间与样本复杂度 2^{O_p(log n·log q)} 求解 CCP,且仅使用多项式量级的量子空间。该筛方法同时适用于均匀 EDCP 与高斯 S|LWE> 态,在 q=poly(n) 时给出上述问题的准多项式时间算法,从而把 Bai 等人 (CRYPTO 2025) 针对 2 的幂情形设计的 EDCP 筛推广到分圆设定。作者明确强调:该结果本身并不构成对标准 LWE 的准多项式时间算法,因为目前已知的归约只能产生数量有限的近似 CCP 态,这一限制是后续能否威胁实用 PQC 的关键分水岭。
💡 推荐理由: 后量子密码 (ML-KEM/ML-DSA 所依赖的 LWE 与模格假设) 的安全边界高度依赖量子归约研究。本文说明 EDCP 类问题在分圆设定下可被准多项式量子算法求解,但尚未触及标准 LWE,属重要理论进展而非现实威胁,值得密码与 PQC 团队跟踪。
🎯 建议动作: 研究跟进