安全与密码学2024eprint.iacr.org编辑精选
格问题的量子算法
Quantum Algorithms for Lattice Problems
专业 · 约 90 分钟读完前置知识：格密码与 LWE 基础、量子计算基础、后量子密码标准化背景
导读
这篇论文提出了求解格上问题（与 LWE 相关）的量子算法，声称能在多项式时间内完成一定参数范围内的求解。不过作者自己在文中指出，该算法达到的模数-噪声比仍然过大，还不足以攻破实际部署的（Ring）LWE 加密方案，例如 CRYSTALS-Kyber；作者把改进近似因子留作未来工作。
HN 关注点：这类结果是否会动摇 NIST 后量子密码标准的基础，而讨论焦点恰恰在于论文自身的参数限制使其暂时无法威胁实际方案。
HN 评论精选
这几条评论里：质疑 2 补充 2
补充论文作者自己承认参数范围不够，尚无法威胁 Kyber 等实际部署方案。
引自论文原文：需要指出，我们的量子算法所达到的模数-噪声比仍然过大，尚不足以攻破实践中使用的基于 (Ring)LWE 的公钥加密方案。特别是我们还没有攻破 NIST PQC 标准化候选方案。例如 CRYSTALS-Kyber 的误差项取自一个小常数范围，模数 q = 3329，维数 n = 256·k（k ∈ {3,4,5}），所以可以认为 q 相对 n 几乎是线性的。而我们的算法在取 αq ∈ O(1) 时，只适用于 q ∈ Ω~(n^2) 的情形，因此目前还无法攻破 CRYSTALS-Kyber。提升算法近似因子的工作留待未来完成。
ghostway查看英文原文
From the paper: > Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. For example, for CRYSTALS-Kyber [BDK+18], the error term is chosen from a small constant range, the modulus is q = 3329, the dimension is n = 256 · k where k ∈ {3, 4, 5}, so we can think of q as being almost linear in n. For our algorithm, if we set αq ∈ O(1), then our algorithm applies when q ∈ Ω^~(n^2), so we are not able to break CRYSTALS-Kyber yet. We leave the task of improving the approximation factor of our quantum algorithm to future work.
质疑追问结果对 LWE 与 Ring-LWE 的适用范围，以及对 FrodoKEM 等方案的影响。
这个结果适用于所有 LWE 问题吗？该方法是否区分 LWE 与 Ring-LWE？如果都适用，那对 FrodoKEM 这类押注非结构化格能提供更高安全性的系统是个重大打击。
axblount查看英文原文
Does this result apply to all LWE problems? Does this approach care about LWE vs Ring-LWE at all? If so, it's a big blow to systems like FrodoKEM that banked on unstructured lattices providing higher security.
补充指出若结果成立，将动摇维基百科中关于格密码抗量子安全性的通行表述。
这会如何影响维基百科上的这些说法？其一：某些基于格的构造似乎能抵抗经典计算机和量子计算机的攻击；此外，许多基于格的构造在“某些被充分研究的格计算问题无法被高效求解”这一假设下被认为是安全的。其二：一类抗量子密码算法基于 Oded Regev 于 2005 年提出的“带误差学习”（learning with errors）概念。
tromp查看英文原文
How does this affect these statements on Wikipedia [1] > some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently. and [2] ? > One class of quantum resistant cryptographic algorithms is based on a concept called "learning with errors" introduced by Oded Regev in 2005. [1] https://en.wikipedia.org/wiki/Lattice-based_cryptography [2] https://en.wikipedia.org/wiki/Ring_learning_with_errors_key_exchange
质疑认为结果若成立将冲击 NIST 近十年后量子密码标准化工作。
如果这篇论文的结论站得住脚，我认为它几乎可以抹掉 NIST 在后量子密码上近十年的努力，这将是密码学界的一次地震级转变。
deyiao查看英文原文
If the findings of this paper hold up, I believe it could pretty much undo a decade of NIST's efforts in post-quantum cryptography. a seismic shift in the world of cryptography.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2024Hacker News 讨论帖13 分 · 1 评
- 2024Hacker News 讨论帖233 分 · 124 评
同领域还值得读
如何入侵一台已关机的电脑：在 Intel ME 中运行未签名代码
How to hack a turned-off computer, or running unsigned code in Intel ME
这篇 Black Hat 2017 白皮书讨论 Intel Management Engine（ME）的安全问题：如何在 ME 中运行未签名代码，以及攻破处于关机状态的电脑的相关…
安全与密码学2017 · 543 分 · 107 评专业 · 约 40 分钟编辑精选比特币：一种点对点的电子现金系统（2008）
Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
中本聪 2008 年发表的比特币白皮书，提出了无需可信第三方的点对点电子现金系统。
安全与密码学2017 · 536 分 · 394 评入门 · 约 45 分钟编辑精选GPRS 加密算法 GEA-1 的密码分析表明存在故意弱点
Cryptanalysis of GPRS Encryption Algorithms GEA-1 suggest intentional weakness
首次公开了对 GPRS 加密算法 GEA-1 和 GEA-2 的密码分析攻击。
安全与密码学2021 · 487 分 · 107 评专业 · 约 90 分钟编辑精选Signal 消息协议的形式化安全分析
A Formal Security Analysis of the Signal Messaging Protocol
用形式化方法分析 Signal 消息协议（TextSecure）的安全性：作者在多阶段密钥交换模型下，借助自动化证明工具对协议的密钥协商与 Double Ratchet 密钥更新…
安全与密码学2016 · 353 分 · 230 评专业 · 约 120 分钟编辑精选A2：模拟恶意硬件
A2: Analog Malicious Hardware
论文研究如何在芯片设计阶段植入模拟电路形式的恶意硬件后门，使其难以被常规检测发现。
安全与密码学2016 · 315 分 · 94 评专业 · 约 75 分钟编辑精选