关于陈算法的背景以及更新

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

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

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

1. 密码学家喜欢在被认为“困难”的数学问题之上构建现代公钥加密方案。实践中，我们需要具有特定结构的问题：我们可以为那些持有秘密密钥或“陷门”的人构建高效的解法，同时认为对于不持有秘密密钥的人没有高效的解法。虽然已经考虑了许多问题（并且经常被弃用），但我们今天使用的大多数方案都基于三个问题：因子分解（RSA 密码系统）、离散对数（Diffie-Hellman、DSA）和椭圆曲线离散对数问题（EC-Diffie-Hellman、ECDSA 等）。

2. 虽然我们愿意相信我们喜欢的那些问题从根本上来说是“难的”，但我们知道事实并非如此。研究者已经设计出算法（Kurt Pan注：原文链接到Shor算法。）可以非常高效地（即在多项式时间内）解决所有上述问题——前提是有人知道如何构建一台足够强大的量子计算机来运行攻击算法。幸运的是，这样的计算机还没有被制造出来！

3. 尽管量子计算机还没有强大到足以破解我们的公钥密码，但仅仅是未来的量子攻击的威胁已经激励工业界、政府和学术界联手以“护戒使者”式的方式（Kurt Pan 注：原文链接为NIST PQC竞赛，用《魔戒》中人类、精灵、矮人、巫师、霍比特人联合组成的护戒分队进行比喻。）现在就开始进行应对。这不仅仅是为了让我们的系统面向未来：即使量子计算机需要几十年的时间来建造，未来的量子计算机也可能破解我们今天发送的加密消息！

4. 这个联盟的一个显著成果是 NIST 的后量子密码学 (PQC) 竞赛：这是一项旨在标准化 “后量子”密码方案的公开竞赛。至关重要的是，这些方案必须基于不同的数学问题——尤其显著的是，这些问题要似乎不允许有高效的量子解法。

5. 在这组新方案中，最流行的一类方案是基于与称为格的数学对象相关的问题。 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维度被称为 $\ell$ 而不是 $n$ ，并且作者设置 $\beta=\alpha \cdot q$ 以便于分析）与选择自错误分布的密钥，但是选择为攻击者所选择的 $\kappa$ 个值的问题相对应。

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

$$ \mathrm{LWE}_{\ell-(\kappa-1), m+\ell-(\kappa-1), q, U\left(\mathbb{Z}_q\right), \chi} $$

与问题

$$ \mathrm{LWE}_{\ell, m, q, \chi, \chi}^{\kappa-1 \text { chosen secret }} . $$

之间存在映射关系。

第3.2节

然后选择奇互素值 $p1, \ldots, p\kappa$ , 使得

$$ p2, \ldots, p\kappa \leq \frac{\log n}{p_1}, $$

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

秘密密钥的 $\kappa-1$ 个部分被选择为 $p2, \ldots, p\kappa$ 。现在的关键是求解方程

$$ A \cdot \mathbf{b}=0 \quad(\bmod q) $$

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

$$ \mathbf{b}=\left[-1,2 p_1 p_2, \ldots, 2 p2 p\kappa, 2 p1 \mathbf{s}{[\kappa, \ldots, \ell]}, 2 p_1 \mathbf{e}\right] . $$

该算法的工作原理是猜测 $b_2=|\mathbf{b}|^2$ 。引理 3.6 告诉我们, 对于 $|\mathbf{b}|^2$ 至少有 $\beta^2$ 个这样的选择。事实上, 有很高概率有

$$ b_2 \in 1+4 p_1^2\left(p2^2+\ldots+p\kappa^2\right)+[0.04,0.27] \cdot 4 p_1^2 \beta^2(n-\kappa) . $$

要点一：这意味着此时的复杂度似乎至少为 $\beta^2$ , 因为需要从大约 $p_1^2 \beta^2(n-\kappa)$ 大小的范围中猜测 $b_2$ 。

第3.3节

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

约束 C. 3 似乎是一个问题。对于 $b_2$ 的猜测值, 我们需要找到一个值 $c \in 4 \mathbb{Z}$ 使得

$$ (c+1) b_2=p_1 p2 \cdots p\kappa, $$

并且我们需要选择 $p_i$ 使得

$$ p2 \cdots p\kappa=-1 \quad\left(\bmod p_1\right) . $$

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

1. 为 $c \in 4 \mathbb{Z}$ 选择一个值。

2. 设置 $p_1=c+1$ 。

3. 使用引理 $3.6 \sqrt{b_2} \leq 3 p_1 \beta \sqrt{n}$ 中的界来猜测 $b_2$ 的值, 即 $0 \leq b_2 \leq 9 p_1^2 \beta^2 n$ 。我们有约束 $b_2=1\left(\bmod 4 p_1^2\right)$ , 因此只需要考虑 $b_2$ 的粗略估计值 $2 \beta^2 n$ 。

4. 现在将 $b_2$ 分解为互素的 $p2, \ldots, p\kappa$ 以获得某个 $\kappa$ 值。

5. 设置 $A=b_2-1-4 p_1^2\left(p2^2+\ldots+p\kappa^2\right)$ 。

6. 如果 $A \notin[0.04,0.27] \cdot 4 p_1^2 \beta^2(n-\kappa)$ 则拒绝。也许我们甚至不用拒绝这些值？

尽管使用此方法, 我仍无法使 $p2 \cdots p\kappa=-1\left(\bmod p_1\right)$ 条件成立。注意作者在论文中的示例是 $p2 \cdots p\kappa=1\left(\bmod p_1\right)$ 而不是 $-1\left(\bmod p_1\right)$ 。所以也许这是一个拼写错误!

假设我们猜测的 $b_2$ 是素数, 并且是一个正确的值。然后我们必须有 $\kappa=2$ 和 $p_2=b_2$ 。此时似乎没有理由应该有 $p_2=-1\left(\bmod p_1\right)$ 。还会有

$$ p_2=1+p_1^2 p_2^2+[0.04,0.27] \cdot 4 p_1^2 \beta^2(n-\kappa) . $$

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

与 相关的更新

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

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

例如, 假设我们输入的 LWE 样本是对 $n \times n$ 方阵 $A$ 的

$$ \mathbf{y}=A \cdot \mathbf{s}+\mathbf{e}(\bmod q) $$

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

$$ \mathbf{z}=R \cdot \mathbf{y}=(R \cdot A) \cdot \mathbf{s}+R \cdot \mathbf{e}(\bmod q) . $$

但现在噪声值已从 $|\mathbf{e}|{\infty}$ 上升到 $|R \cdot \mathbf{e}|{\infty}$ 。这会增加 $\alpha$ 的值, 从而增加上面的 $\beta$ 值, 从而增加攻击的复杂度。

Nigel Smart 4月17日更新

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

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

• 第一个是 $p2 \cdots p\kappa=-1\left(\bmod p_1\right)$ 的问题。其实这样做只是为了避免带上另一个变量 $c^{\prime}=p2 \cdots p\kappa\left(\bmod p_1\right)$ 。所以我们可以忽略这一点。

• 第二个问题是关于对 $i>2$ 时的界 $p_i \leq(\log n) / p_1$ 。如果加入这个条件, 那么根本没有足够的奇互素的 $p_i$ 来使算法工作, 除非 $n$ 非常大, 比如 $2^{10^x}$ ，对于一些相当大的 $x$ 。因此, 如果保持这个条件, 那么该算法在任何意义上肯定是不可行的。一镭向我指出, 这个条件也不是必需的（除了去获得一个较好的近似因子）, 可以用 $p_i=O(\log n)$ 甚至 $p_i \leq 10 \log n$ 代替它。在另一个方向上, 可以采用 $\kappa=O(1)$ , 也许还可以采用 $\kappa=10$ 。

重新审视条件 C.3

了解这些后, 考虑假设 $p_i \leq 10 \log n$ 或假设 $\kappa$ 已固定的这两个修复后，让我们重新审视 C. 3 并提出一种算法,

选项 A：设置 $p_i \leq 10 \log n$

1. 为 $\kappa$ 选择一个值 (待定)。

2. 为 $c \in 4 \mathbb{Z}$ 选择一个值, 例如 $c=4$ 。

3. 设置 $p_1=c+1$ , 即 $p_1=5$ 。

4. 根据 $p_i \approx 10 \log n$ 选择奇互素值 $p2, \ldots, p\kappa$ （也与 $p_1$ 互素 ）。

问题是，我们应该选择多大的 $\kappa$ ?

同样，我们知道 $b_2=p2 \cdots p\kappa$ ，并且也知道（假设 $\kappa>4 ） \quad b_2$ 的大小将由 $p_1^2 \beta^2(n-\kappa)$ 项主导。由于 $\kappa$ 与 $n$ 相比很小，我们基本上会得到类似这样的东西

$$ p_i^{\kappa-1} \approx p_1^2 n \beta^2 \text {. } $$

回想一下, 对 Kyber 和 BGV ， $\beta=\sqrt{8 \pi}$ , 对Dilithium $\beta=\sqrt{64 \pi / 3}$ , 对TFHE $\beta=2^{32}$ 。如上所述，这是假设 $\beta$ 对需要生成更多样本不需要增加,  因此对 $\beta$ 的这些假设是最好的可能情况。

当 $\beta=\sqrt{8 \pi}$ 时，需要

$$ (\kappa-1) \log (10 \log n) \approx 2 \log \left(p_1 \beta\right)+\log n \approx 6.443+\log n $$

即，

$$ \kappa \approx \frac{6.443+\log n}{\log (10 \log n)}+1 $$

注意, 要得到 $\kappa>4$ ，需要 $n$ 比这里的 $2^{29}$ 大。不管怎么想, 这都是非常大量的 LWE 样本数。

当 $\beta=2^{32}$ 时，我们得到

$$ (\kappa-1) \log (10 \log n) \approx 2 \log \left(p_1 \beta\right)+\log n \approx 47.58+\log n . $$

即

$$ \kappa \approx \frac{47.58+\log n}{\log (10 \log n)}+1 . $$

注意, 这里总是会得到 $\kappa>4$ , 无论 $n$ 值如何。

选项 B：设置 $\kappa=10$

1. 选择 $\kappa=10$ 。无论如何选择 $\kappa>4$ 。

2. 为 $c \in 4 \mathbb{Z}$ 选择一个值, 例如 $c=4$ 。

3. 设置 $p_1=c+1$ ，即 $p_1=5$ 。

4. 选择奇互素值 $p2, \ldots, p\kappa$ (也与 $p_1$ 互素)。

现在的问题是，我们应该选择多大的互素值 $p2, \ldots, p\kappa$ ?

同样, 我们知道 $b_2=p2 \cdots p\kappa$ 并且我们也知道（假设 $\kappa>4 ） \quad b_2$ 的大小将由 $p_1^2 \beta^2(n-\kappa)$ 项主导。由于 $\kappa$ 相比 $n$ 很小，我们基本上会得到类似下式的东西

$$ p_i^{\kappa-1} \approx p_1^2 n \beta^2 \text {. } $$

所以

$$ \log p_i \approx \frac{2 \log \left(p_1 \beta\right)+\log n}{\kappa-1} . $$

使用 $\beta=\sqrt{8 \pi}$ ，需要

$$ \log p_i \approx 0.715+\frac{\log n}{9} . $$

即

$$ p_i \approx 2 n^{1 / 9} . $$

但是要获得 $\kappa=10$ 这样的互素值我们需要 $2 n^{1 / 9} \geq 31$ , 即 $n>2^{35}$ 。这又是大量的样本数。

使用 $\beta=2^{32}$ ，需要

$$ \log p_i \approx 5.286+\frac{\log n}{9} . $$

即

$$ p_i \approx 198 n^{1 / 9} . $$

任意 $n$ 值都会导致这样的互素值存在。

C. 3小节的总结

通过削弱近似因子, 我们可以为互素的 $p1, \ldots, p\kappa$ 和值 $\kappa$ 选择实用值。我们看到, 对于 Kyber、Dilthium 和 BGV, 需要的样本数量 $m$ 将非常大才能选择此类互素值, 但是对于 TFHE, $\beta$ 值非常大，这种互素数的存在是直接的, 因为这迫使 $b_2$ 确实非常大。

第二个要点：对于较小的 $\beta$ 值, 使攻击起作用所需的样本数量确实会非常大。

继续第 3.3 节

选择了 $p1, \ldots, p\kappa$ 的值后, 我们就固定了对 $b_2$ 的猜测。但这个猜测可能是错误的。事实上, 其正确的概率约为

$$ \frac{1}{\beta^2 p_1^2(n-k)} \text {. } $$

因此, 我们需要继续执行攻击, 通过随机化输入样本来调整参数（如上所述）。直到攻击起作用。

所以需要重申上述的要点一。要点一（回顾），复杂度至少为 $\beta^2$ 。因此, 如果 $\beta^2$ 很大, 比如在TFHE中, 这已经是不行的了。我们继续假设 $b_2$ 是正确的。因此, 选择互素值后, 需要为 $D$ 选择一个值, 论文称该值应该是奇数以及 $O\left((\log n)^2\right)$ 。目前我们假设它已被选择。

然后设置

$$ \begin{gathered} M=2(c+1) D^2 b_2 \ P=M^2 / 2 \ u^2=D^2 b_2 \end{gathered} $$

现在我们需要确定 $t^2$ 以确保条件C.2满足，定义为

$$ t^2=\frac{M}{2}-u^2 . $$

注意到

$$ \frac{t^2}{u^2}=\frac{M}{2 u^2}-1=\frac{2(c+1) D^2 b_2}{2 u^2}-1=\frac{2(c+1) D^2 b_2}{2 D^2 b_2}-1=(c+1)-1=c . $$

所以条件 C. 1 已经满足。条件 C. 1 中唯一不满足的是 $\sqrt{c} \in\left(64(\log n)^3, 65(\log n)^3\right)$ 。

然后需要从条件 C. 4 中选择 $r$ 的值。相关的不等式是

$$ M \leq r \leq \frac{P}{2 \log n}=\frac{M^2}{4 \log n} $$

和

$$ r \leq \frac{D q}{2(\log n)^3} . $$

注意第二个不等式蕴含下式

$$ \frac{D q}{2(\log n)^3} \geq M=2(c+1) D^2 b_2 $$

即

$$ q \geq 4(c+1) D b_2(\log n)^3 \approx 4(c+1) D(\log n)^3 p_1^2 n \beta^2 . $$

代入我们上面的值, 有

$$ q \geq c^{\prime} n \beta^2, $$

$c^{\prime}$ 值我们可以忽略 。

要点三：注意这意味着该攻击不适用于 TFHE 的标准参数, 因为 $\beta \approx \sqrt{q}$ , 并且TFHE中乘以 $n$ 得到的 $q$ 太小, 无法应用攻击。

要点四：该攻击不适用于 Kyber、Dilithium 或 BGV，因为此处所需的 $n$ 的大值（如上所述）也意味着这些方案中使用的 $q$ 值太小了。

在条件 C. 7 中, $r$ 的值实际上被选择为

$$ r=\frac{u t^3}{4 \log n} . $$

最后要选择的参数是 $s^2$ , 它是通过

$$ s^2=2 u^2 t^2+\epsilon . $$

从条件 C. 5 中选择的。

然后还有一些额外的条件, 即条件 C. 6 和 C.7, 它们定义了各种参数的范围。我的理解是这些会影响算法获得的近似因子。

4月17日总结

1. 该算法肯定需要 $O\left(\beta^2\right)$ 次重复。因此对于大 $\beta^2$ (TFHE) 这是不可行的。（要点一）

2. 对于较小的 $\beta$ 值（Kyber、Dilithium、BGV)，该算法需要大量的 LWE 样本 $m$ 。 (要点二)

3. 该算法需要 $q>c^{\prime} n \beta^2$ , 这要么因为 $\beta$ 很大 (TFHE), 要么因为 $n=\ell+m+1$ 很大（根据上个要点，因为 $\beta$ 很小)而太高。(要点三/四)

4. 从公钥方案中拥有的固定数量的样本中生成大量样本, 会生成比此处考虑的更大的 $\beta$ 值。这使得攻击不太实用。