【Hacker News搬运】陈算法速帖

[hackernews]

Title: A quick post on Chen's algorithm

陈算法速帖

Text:

hn link

Url: https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/

文章标题为“关于陈氏算法的快速帖子”，作者讨论了最近由Yilei Chen发表的一篇名为“量子算法与格问题”的预印本，该预印本在密码学研究社区引起了巨大震动。作者首先介绍了现代公钥加密方案基于的数学难题，然后指出量子计算机虽然目前还不足以破解我们的公钥加密，但未来量子计算机可能会破解我们今天发送的加密消息。因此，业界、政府和学术界已经开始合作，以解决这一问题。

NIST举办了一场名为“后量子密码学竞赛”的开放竞赛，旨在标准化“后量子”加密方案。这些方案必须基于不同的数学问题，特别是那些似乎不适用于高效量子解决方案的问题。在这些新方案中，最受欢迎的方案是基于与数学对象“格”相关的问题。

陈氏的预印本声称找到了一种新的量子算法，能够高效解决格问题中的“最短独立向量问题”（SIVP，以及GapSVP），如果这一结果成立，那么未来量子计算机可能会破解依赖于这些问题难度的方案。然而，即使是正确的，易受攻击的参数也非常具体：陈氏算法并不立即适用于最近标准化的NIST算法，如Kyber或Dilithium。此外，算法的确切具体复杂性也不立即清楚：即使量子计算机可用，也可能无法实际运行。

作者最后提到，攻击只会变得更好。如果陈氏的结果能够得到改进，那么量子算法可能会使一整代基于格的“后量子”方案过时，迫使密码学家和行业重新开始。

Post by: feross

Comments:

keepamovin: There'll probably be discovered a class of problems which is hard and Q hard, provably and we'll be set. Something basically new to cryptography, that was tried once in the past but failed until seen through a new light of more recent maths or research fashion.<p>But until then it seems to me like something based on the difficulty of attacking hash functions would be a good bet for Q resistant. Totally unsure how to make a PK scheme from that, but it has a few nice properties:<p>- hashes are often tuneable, you can add more state and increase the keyspace/security<p>- good hashes don't have any weaknesses that Q can exploit<p>- hashes are often pretty fast<p>- hashes are well studied<p>- hashes seem to be hard in C and hard in Q

keepamovin: 有；可能会发现一类可证明的困难和Q困难的问题；将被设置。密码学的一些基本上是新的东西，过去曾尝试过一次，但失败了，直到最近的数学或研究方式出现了新的曙光<p> 但在那之前，在我看来，基于攻击哈希函数的难度的东西对Q抵抗来说是一个不错的选择。完全不确定如何从中生成PK方案，但它有一些不错的属性：＜p＞-哈希通常是可调谐的，您可以添加更多的状态并增加密钥空间；安全性＜p＞-好的散列don&#7；Q没有任何可以利用的弱点<p>-哈希通常很快<p>-对哈希进行了充分的研究<p>-在C中哈希似乎很难，在Q中也很难

faitswulff: It seems like the post-quantum algorithm that Signal selected [0] involves lattices [1] somehow:<p>> Kyber is an IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices.<p>Curious to see if Chen's work will eventually lead to Signal selecting a different algorithm.<p>[0]: <a href="https://signal.org/blog/pqxdh/" rel="nofollow">https://signal.org/blog/pqxdh/</a><p>[1]: <a href="https://pq-crystals.org/kyber/" rel="nofollow">https://pq-crystals.org/kyber/</a>

faitswulff: Signal选择[0]的后量子算法似乎以某种方式涉及晶格[1]：<p>&gt；Kyber是一种IND-CCA2-安全密钥封装机制（KEM），其安全性基于解决模块格上的带误差学习（LWE）问题的难度<p> 好奇地想看看陈；的工作最终将导致Signal选择不同的算法<p> [0]：<a href=“https://；&#x2F；signal.org/x2F；blog#xx2F；pqxdh#xx2F”rel=“nofollow”>https://&#x2F；signal.org；博客&#x2F；pqxdh</a> <p>[1]：<a href=“https://；&#x2F；pq crystals.org&#x2F：kyber&#x2F”rel=“nofollow”>https://&#x2F；pq-crystals.org；kyber</一

jonahx: I appreciate short, accessible writeups on subjects like these.

jonahx: 我很欣赏关于这些主题的短小精悍的文章。

glitchc: Let's wait for the dust to settle to see if Chen has indeed broken the Shortest Vector Problem for lattices. Bold claims require strong evidence.

glitchc: 设；让我们等尘埃落定，看看陈是否真的打破了格的最短向量问题。大胆的主张需要强有力的证据。

anonymous-panda: I find the panic over potential threat of quantum quite amusing when the machine is still extremely theoretical - all existing machines are slower than classical and it’s not even clear they can scale to the required number of qubits.<p>There’s nowhere near the same urgency and significantly more denial over global warming. A bit apples and oranges but climate models have a better track record, are wildly conservative (ie our present is much worse than the past climate models predicted) and it’s a real problem we know exists and is a bullet train headed our way.

anonymous-panda: 当量子机器仍然非常理论化时，我发现对量子潜在威胁的恐慌非常有趣——所有现有的机器都比经典机器慢，甚至不清楚它们能扩展到所需的量子位数量<p> 在全球变暖问题上，没有同样的紧迫性和明显更多的否认。有点像苹果和桔子，但气候模型有更好的记录，非常保守（即我们现在的情况比过去的气候模型预测的要糟糕得多），这是一个我们知道存在的真正问题，是一列子弹头列车。