金年会·(中国)金字招牌,信誉至上

原文：https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/
作者：Matthew Green
译者：Kurt Pan

如果你是一个普通人——也就是说，一个不痴迷于关注最新密码学新闻的人——你可能错过了上周的密码学重磅炸弹。这一消息以陈一镭 (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 节, 其中更详细地给出了攻击参数。

第3.1节

这部分将输入的LWE问题（现在LWE维度被称为而不是，并且作者设置以便于分析）与选择自错误分布的密钥，但是选择为攻击者所选择的个值的问题相对应。

基本上为, 带有参数的错误分布的输入问题

与问题

之间存在映射关系。

第3.2节

然后选择奇互素值 , 使得

其中。对于较小的值，可以预期会等于1或2，除非选择（从而）为很大的值。因此，的选择也会影响需要从多少个LWE样本（即）开始（请参见下面关于增加对具体LWE问题实例意味着什么的评论）。

秘密密钥的个部分被选择为。现在的关键是求解方程

，其中向量 b 具有特殊形式

该算法的工作原理是猜测。引理 3.6 告诉我们, 对于至少有个这样的选择。事实上, 有很高概率有

要点一：这意味着此时的复杂度似乎至少为，因为需要从大约大小的范围中猜测。

第3.3节

之后，3.3 节定义了一系列常量和约束，使主量子子程序能够工作，并成功解决底层的LWE 问题。

约束 C. 3 似乎是一个问题。对于的猜测值, 我们需要找到一个值使得

并且我们需要选择使得

我能让事情按顺序解决的唯一方法如下（这几乎就是作者所建议的）：

为选择一个值。
设置。
使用引理中的界来猜测的值, 即。我们有约束 , 因此只需要考虑的粗略估计值。
现在将分解为互素的以获得某个值。
设置。
如果则拒绝。也许我们甚至不用拒绝这些值？

尽管使用此方法, 我仍无法使条件成立。注意作者在论文中的示例是而不是。所以也许这是一个拼写错误!

假设我们猜测的是素数, 并且是一个正确的值。然后我们必须有和。此时似乎没有理由应该有。还会有

这显然不能成立。因此, 为了使分解为有意义, 我们确实需要为特殊值。所以有些事情看起来很奇怪!

与相关的更新

正如 Vadim Lyubasevksy 向我指出的那样, 论文中考虑的问题实际上是针对通用 LWE的, 即针对可能无限的或大量的样本。在现实世界的密码系统中, 有固定数量的基本样本, 特别是通常我们只给定这样的样本。

如果攻击需要更多样本, 那么我们需要根据给定的样本生成这些样本。这是通过组合现有样本的小线性组合来完成的。但我们不能在线性组合中使用太小的值, 否则会将已知的小向量引入到得到的之后算法将对其进行求解的格中；也就是说，它最终会求解你已经知道的向量。因此，我们需要选择乘数较小但又不能太小的组合。但这本身就会放大噪声（即值)。这使得攻击不太实用。

例如, 假设我们输入的 LWE 样本是对方阵的

然后, 为了生成新样本, 可以将右侧的方程乘以一个矩阵, 该矩阵包含小值, 不是太稀疏, 但小值也不是太小。即将形成系统

但现在噪声值已从上升到。这会增加的值, 从而增加上面的值, 从而增加攻击的复杂度。

Nigel Smart 4月17日更新

https://nigelsmart.github.io/LWE.html

所以昨天我遇到了条件 C. 3 的两个问题。这些都通过和一镭的沟通得到了一定的解决。

第一个是的问题。其实这样做只是为了避免带上另一个变量。所以我们可以忽略这一点。
第二个问题是关于对时的界。如果加入这个条件, 那么根本没有足够的奇互素的来使算法工作, 除非非常大, 比如，对于一些相当大的。因此, 如果保持这个条件, 那么该算法在任何意义上肯定是不可行的。一镭向我指出, 这个条件也不是必需的（除了去获得一个较好的近似因子）, 可以用甚至代替它。在另一个方向上, 可以采用, 也许还可以采用。