如果你是一个普通人——也就是说，一个不痴迷于关注最新密码学新闻的人——你可能错过了上周的密码学重磅炸弹。这一消息以陈一镭（Yilei Chen）撰写的e-print论文《格问题的量子算法》的形式发布，引起了密码学学术界的轰动。现在，格和量子算法设计方面的专家正在评估这个结果（需要明确的是，我不是其中之一！），但如果结论成立，对于应用密码学社区来说，这将是非常糟糕的一天/一周/一个月/一年。

这里没有详细阐述，而是快速通过五个要点给出背景。

密码学家喜欢在被认为“困难”的数学问题之上构建现代公钥加密方案。实践中，我们需要具有特定结构的问题：我们可以为那些持有秘密密钥或“陷门”的人构建高效的解法，同时认为对于不持有秘密密钥的人没有高效的解法。虽然已经考虑了许多问题（并且经常被弃用），但我们今天使用的大多数方案都基于三个问题：因子分解（RSA 密码系统）、离散对数（Diffie-Hellman、DSA）和椭圆曲线离散对数问题（EC-Diffie-Hellman、ECDSA 等）。
虽然我们愿意相信我们喜欢的那些问题从根本上来说是“难的”，但我们知道事实并非如此。研究者已经设计出算法（Kurt Pan注：原文链接到Shor算法。）可以非常高效地（即在多项式时间内）解决所有上述问题——前提是有人知道如何构建一台足够强大的量子计算机来运行攻击算法。幸运的是，这样的计算机还没有被制造出来！
尽管量子计算机还没有强大到足以破解我们的公钥密码，但仅仅是未来的量子攻击的威胁已经激励工业界、政府和学术界联手以“护戒使者”式的方式（Kurt Pan 注：原文链接为NIST PQC竞赛，用《魔戒》中人类、精灵、矮人、巫师、霍比特人联合组成的护戒分队进行比喻。）现在就开始进行应对。这不仅仅是为了让我们的系统面向未来：即使量子计算机需要几十年的时间来建造，未来的量子计算机也可能破解我们今天发送的加密消息！
这个联盟的一个显著成果是 NIST 的后量子密码学（PQC）竞赛：这是一项旨在标准化 “后量子”密码方案的公开竞赛。至关重要的是，这些方案必须基于不同的数学问题——尤其显著的是，这些问题要似乎不允许有高效的量子解法。
在这组新方案中，最流行的一类方案是基于与称为格的数学对象相关的问题。 NIST 批准的基于格问题的方案包括 Kyber 和 Dilithium。格问题也是几种高效全同态加密（FHE）方案的基础。
这些是新结果的背景。

陈的（尚未经过同行评议的）预印本提出一种新的量子算法，可以高效解决具有特定参数的格中的“最短独立向量问题”（SIVP 以及 GapSVP）。如果成立，该结果可能（使得未来的量子计算机（带有许多重要需要注意点地）可以攻破依赖于这些问题的特定实例的难度的方案。好消息是，即使结果正确，易受攻击的参数也非常具体：陈的算法并不立即适用于最近标准化的 NIST 算法，比如 Kyber 或 Dilithium。此外，该算法确切的具体复杂度尚不清楚：即使量子计算机变得可用，该算法也可能无法实际运行。

但我们领域有一句话，攻击只会变得更好。如果陈的结果可以得到改进，那么量子算法可能会淘汰一整代基于格的所谓“后量子”方案，迫使密码学家和业界（https://security.apple.com/blog/imessage-pq3/ ，https://signal.org/blog/pqxdh/ ，https://bughunters.google.com/blog/5108747984306176/google-s-threat-model-for-post-quantum-cryptography）重新开始。

换句话说，这既是一项伟大的技术成果，也可能是一场微型灾难。（Kurt Pan注：对于相关方向诸多PhD和项目工程师，可能就是沉重的打击。）

如前所述：我既不是基于格的密码学也不是量子计算方面的专家。这些人正忙于验证这篇文章：之前历史上不少重大的结果经过详细检查后都分崩离析了。对于那些寻找最新进展的人来说，这里是 Nigel Smart 写的一篇不错的文章，没有解决这个问题量子算法的正确性（也请参阅下述更新），但确实讨论了对 FHE 和 PQC 方案的可能影响（简而言之：对某些 FHE 方案不利，但实际上取决于算法运行时间的具体细节。） [[近期量子攻击对 LWE 的影响]]

https://eprint.iacr.org/2024/583.pdf 这是关于发现论文中“错误”的另一个简短笔记，作者陈一镭似乎很快就解决了这个问题。

直到本周，我还打算写另一篇关于复杂性理论、格及其对应用密码学意味着什么的长篇文章。但基于现状，我希望你能原谅我，如果再延迟些发布的话。

Nigel Smart 4月16日更新
https://nigelsmart.github.io/LWE.html

阅读论文的更新
今天我更详细地查看了论文的第 3 节, 其中更详细地给出了攻击参数。