#no-go-theorem

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Aparna Gupte, Seyoon Ragavan, Mark Zhandry

本文针对二面体陪集问题(DCP, Dihedral Coset Problem)建立了一条“不可行性”(no-go)定理,属于量子算法与后量子密码学的交叉理论研究。DCP 是 Regev 于 2004 年提出并用于将格上学习带误差问题(LWE)归约到量子求解框架的核心问题之一,其若被高效求解,将对基于格的密码体制构成威胁,因此围绕 DCP 的量子算法设计长期受到关注。作者聚焦于 Regev 提出的“傅里叶采样 + 子集和测量”这一类模板:算法先构造子集和态、测量其低 n-1 位,然后利用剩余的“傅里叶标签”(Fourier labels)继续提取信息。本文证明:只要算法在子集和测量之后,从每个傅里叶标签中丢弃任意 ω(log n) 位信息,那么该算法必然无法成功求解 DCP。换言之,任何沿用该模板的算法都必须高强度、近乎完整地保留并使用傅里叶标签,否则注定失败。这一结论既给出了模板内部的硬性设计约束,也为后续算法设计者提供了明确的“有效方向”指南。作为主要应用,作者分析了 Simon 近期提出的算法(IACR ePrint:2026/1591,2026 年 8 月 11 日):他们证明该算法在子集和测量之后,可以用“最高有效三分之一”的傅里叶标签以指数级小误差实现,因此落入上述通用 no-go 定理的适用范围,从而不能求解 DCP。为便于可验证性,作者还公开发布了用 Lean 4 形式化验证相关结论的代码。整篇工作的方法论特征在于:不是构造更快的攻击算法,而是用信息损失的角度划定一类算法的能力上界,并用机器可检验的形式化方法增强结论的可信度。适合量子算法、格密码与后量子迁移方向的研究者与评估人员阅读。

💡 推荐理由: 网络上常出现“某量子算法攻破格密码”的宣称。本文给出可形式化验证的否定结论,说明 Regev 模板下丢弃傅里叶标签信息即不可行,并明确指出 Simon 的 ePrint:2026/1591 方案并不能求解 DCP。对评估后量子迁移风险、甄别夸大宣称具有直接参考价值。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)