> 原文：https://nigelsmart.github.io/LWE.html > > 作者：Nigel Smart > > 译者：Kurt Pan 2024 年 4 月 10 日，陈一镭在 ePrint 上发表了题为“[格问题的量子算法](https://eprint.iacr.org/2024/555)”的论文。 他针对带错误学习（LWE）问题的某些参数集提出了一种“多项式时间”的量子算法。这很重要，因为 LWE 构成了 NIST 选择的大多数后量子算法的基础，而且还构成了许多提供高级功能（如全同态加密 (FHE)）的密码构造的基础。这篇文章中，我会试图弄清楚这项工作的可能影响是什么。 #### 注意点 阅读以下内容时有一些注意点。其中最值得注意的是： 1. 我不是量子算法专家。 2. 陈的论文尚未经过同行评议，因此可能存在一些错误。 3. 量子计算机可能永远不会被建造出来。事实上，量子计算机总是存在于未来十年后，这已经是一个流传已久的笑话！ ## LWE 问题 好，在此共识基础上，我们开始定义 LWE 问题本身。这是带噪声版本的线性代数。（以其最基础的形式）由四个值 $n, m, q \in \mathbb{N} 、 \alpha \in[0,1]$ 参数化。 值 $q$ 用于定义模约减中的模数。接下来，我们假设将 $\mathbb{Z}_q$ 表示为 $(-q / 2, \ldots, q / 2]$ 范围内的整数值，即在所有模运算中进行中心约减。 值 $\alpha$ 用于定义分布 $D$ 。通常$D$选择为 $\mathbb{Z}$ 上具有标准差 $\alpha \cdot q / \sqrt{2 \cdot \pi}$ 的类高斯分布, 尽管也可以使用其他分布（例如具有大致相同标准差的均匀分布）。在任何情况下，分布 $D$ 都会以极大概率对某个小常数 $c$ 生成 $[-c \cdot \alpha \cdot q, \ldots, c \cdot \alpha \cdot q]$ 范围内的整数值。下面可以将这个 $c$ 想象为比如说10。 LWE 问题由秘密向量 $\mathbf{s} \in \mathbb{Z}_{\mathbf{q}}^n$ 和秘密向量 $\mathbf{e} \in D^m$ 定义，即从$D$分布的$m$个副本的乘积中选择 $\mathbf{e}$ 。因此 $\mathbf{e}$ 包含 $m$个“小”值。 然后, 选择维度 $m \times n$ 的公开矩阵 $A$, 其中每项在$\mathbb{Z}_{\mathbf{q}}$ 中选择, 并计算值 $ \mathbf{y}=A \cdot \mathbf{s}+\mathbf{e} \quad(\bmod q) $ 从复杂性的角度看，需要注意的关键点如下。复杂性理论中，通常将复杂度视为问题输入大小的函数。LWE 中输入问题的大小为 $ n \cdot(m+1) \cdot \log _2 q \approx n \cdot m \cdot \log _2 q . $ 因此大小不依赖于 $\alpha$ 。当谈论求解 LWE 的多项式时间算法（在通常的复杂性理论意义上）时，我们应只考虑复杂度为 $n \cdot m \cdot \log _2 q$ 的多项式函数的算法。 值 $n$ 称为LWE维度, 值 $m$ 表示 “LWE样本” 的数量。和在普通线性代数中一样为了固定解, 需要至少与变量一样多的方程数, 为了固定 $\mathbf{s}$, 这里也需要 $m \geq n$ 。这意味着要求样本数量 $m \geq \Omega(n \cdot \log q)$ 。 但 $\alpha$ 对于LWE的难度至关重要: - 如果 $\alpha=0$ 则可以解释为不存在错误向量 $\mathbf{e}$ 。因此在这种情况下，LWE 问题只是普通的线性代数，平凡的算法可以（本质上）以二次方的时间复杂度解决它。（Kurt Pan注：高斯消元法的复杂度为$O(n^3)$。） - 如果 $\alpha \approx 1$ 则方程基本上是随机的, 没有算法能够恢复 $\mathbf{s}$, 因为方程本质上不包含用来帮助恢复 $\mathbf{s}$ 的信息。 $\alpha$ 的值在应用中很重要: 1. 对于传统公钥加密（如在 Kyber 中）等应用，分布 $D$ 的标准差被选择为固定值 $\sqrt{(3+1) / 2}=2$ （Kurt Pan注：原文如此，似应为$\sqrt{2}$。）（因为该分布是 NewHope 的分布, 其中参数 $B=3$ )。因此我们有 $\alpha \cdot q=2 \cdot \sqrt{2 \cdot \pi}=\sqrt{8 \cdot \pi}$, 即 $\alpha \cdot q$ 是常数。但是, 如果将 $q$ 固定为 $q=3329$ , 则 $\alpha=0.0015 \approx q^{-0.801}$ 。所以 $\alpha \cdot q \approx q^{0.1987}$ 。在 Kyber 中, $n \approx q$ 。 2. 对于公钥签名（如在 Dilithium 中），分布 $D$ (在 Dilithium 密钥中）是 $[-\eta, \ldots, \eta]$ 范围内的均匀分布，其中 $\eta$ 是 2 或 4 。然而, Dilithium 中的模数 $q$ 比 Kyber 中的大得多，为 $q=8380417$ 。因此, $D$ 的标准差最多为 $\sqrt{(2 \cdot \eta)^2 / 12}=4 / \sqrt{3}$, 因此 $\alpha \cdot q=\sqrt{64 \cdot \pi / 3} \approx q^{0.1318}$ 。在 Dilthium 中, 对第3级参数，设置 $n=5 \cdot 256$。 3. 对于诸如分级全同态加密(以 BGV 和 BFV 全同态加密方案为代表) 之类的应用, 支持的同态运算的深度由值 $q$ 和 $\alpha \cdot q$ 之间的间距决定, 即需要非常非常小的 $\alpha$ 值。对于这样的方案, 我们可以将 $\alpha \cdot q$ 视为一个小常数。事实上, 可以认为 $\alpha \cdot q$ 与 Kyber 中的值相同, 即 $\sqrt{8 \cdot \pi}$ 。但随后会选择 $n, m$ 和 $q$ 来获得安全性和同态深度。这确实会导致 $q$ 的值非常大, 例如可能有 $q \approx 2^{1024}$, 在这种情况下 $\alpha \cdot q \approx q^{0.0227}$ 。对于 $q \approx 2^{1024}$ 的 BGV 典型$n$ 值来说, 其数量级为 $2^{15}$ 或 $2^{16}$ 。 (有关支持Bootstrapping的 BGV 参数的讨论, 请参考 Bootstrapping for HElib)。 4. 对于诸如支持高效bootstrapping的 FHE 方案 (以 TFHE 和 FHEW 为代表) 的应用来说, 不需要 $q$ 和 $\alpha \cdot q$ 之间存在巨大间距。事实上对于这些, 可以将 $\alpha$ (本文考虑 $q=2^{64}$的TFHE ） 视为量级为$1 / \sqrt{q}$ , 所以 $\alpha \cdot q \approx \sqrt{q}$ 。对于此类 TFHE 参数, 维度 $n$ 不超过 $2^{11}$ 。 $\alpha \cdot q$ 值的重要性早已为人所知。Regev 的 LWE 原始难度的结果就仅在 $\alpha \cdot q>2 \sqrt{n}$ 时成立。有趣的是, 这个不等式仅适用于上述 TFHE 式的参数, 不适用于 Kyber、Dilithium 或 BGV 的参数集。 确定 LWE 问题参数的经典方法是使用lattice-estimator（https://lattice-estimator.readthedocs.io）。对给定的参数集运行所有已知的格算法, 并尝试确定解决 LWE 问题所需的经典操作的数量。如果得出的值大于 $2^{128}$, 那么通常会认为这些参数是安全的。 但也有反直觉的。例如，如果保持 $m, n$ 和 $\alpha \cdot q$ 不变, 但只增加 $q$, 那么 LWE 问题就会变得更容易！这与（比如说）RSA 或 DLP 不同, 对它们只是增加模数只会变得更安全。 当观察量子复杂度时, 也有点反直觉。例如, Grover 的算法应该蕴含 AES-128 在后量子世界中不被认为是安全的, 因为通过 Grover 的算法对 AES-128 进行攻击将需要 $2^{64}$ 量子“操作”。然而, 大多数人认为 AES-128 在后量子世界中仍将保持安全, 因为适用于 AES-128 的Grover 算法的整体复杂度将远远超出任何可行的量子计算机。 ### LWE问题总结 关键要点: 1. 多项式时间应根据输入问题的大小来衡量。 2. $\alpha$ 值对于安全性和应用都很重要。 3. 在LWE的不同实际应用中, $\alpha$ 值存在显著差异。 4. 即使构建了量子计算机，一个“低”复杂度的量子攻击实际上也可能不会转化为一个实用的量子攻击（如 AES-128）。 ## 提出的算法 陈的算法使用一个量子子程序, 调用 $O(n)$ 次，以生成线性方程组，然后可以通过经典方法求解。为获得满秩线性方程组，该量子子程序会按照需要被调用多次。 算法仅在 $D$ 是类高斯分布时给出，但我们假设可以删除此限制（因此我们可以将其应用于基于 LWE 的实际方案中使用的分布)。 正如前面所说，我不是量子算法方面的专家，所以这里不会讨论量子子程序，但可以讨论陈给出的定理的陈述： > **定理**：令$n, m, q \in \mathbf{N} 、 \alpha \in(0,1)$ ，使得 - $m \geq \Omega(n \cdot \log q)$ >- $q \in \tilde{\Omega}\left((\alpha \cdot q)^4 \cdot m^2\right)$. 则有一种量子算法可以在 $\operatorname{poly}(m, \log q, \alpha \cdot q)$ 时间内求解 LWE。 现在我们更详细地来考虑这个陈述。 ### 条件 首先需要考虑的是条件部分。 我们已经讨论过, 秘密中需要的样本 $m$ 需要多于变量 $n$, 因此第一个条件应该不足为奇。 现在看第二个条件, 即 $q \in \tilde{\Omega}\left((\alpha \cdot q)^4 \cdot m^2\right)$ 。关键点是 $q$ 对 $\alpha \cdot q$ 的依赖。我们将这些分别映射到上面考虑的四种情况中。 1. **Kyber**：这里，回想一下, $\alpha \cdot q \approx q^{0.1987}$ 所以条件变为 $ q \in \tilde{\Omega}\left(q^{0.7948} \cdot m^2\right) . $ 但是, 对 Kyber 也有 $m>n \approx q$ 。因此, 并没有 $ q \in \tilde{\Omega}\left(n^{2.7948}\right) . $ 当然, 所提出的攻击 (如果是正确的) 可能会得到改进, 但似乎不太可能按原样应用于 Kyber。 2. **Dilithium**: 这里, 回想一下, $\alpha \cdot q \approx q^{0.1318}$ 。但现在维度 $n=5 \cdot 256$ (对于第3级参数）和 $q=8380417$, 因此 $q \approx n^{2.22}$ 。这意味着 $\alpha \cdot q \approx n^{0.2925}$, 第二个条件变为 $ q \in \tilde{\Omega}\left(n^{3.170}\right) \text {. } $ 因此，在攻击方面只需进行较少的改进即可将其应用于 Dilithium。 3. **BGV** : 回想一下， $\alpha \cdot q \approx q^{0.00227}$ ， $n$ 在 $2^{15}$ 或 $2^{16}$ 附近，以及 $q \approx 2^{1024}$ 。因此有 $\alpha \cdot q \approx n^{.1550}$ 。第二个条件变为 $ q \in \tilde{\Omega}\left(n^{2.620}\right) . $ 但对于 BGV 有 $q \approx n^{68.266}$ 。因此看来该攻击应该适用于 BGV。 4. **TFHE**：在这种情况下，回想一下， $\alpha \cdot q \approx \sqrt{q}$ 。还有 $q=2^{64}$ 和 $n \leq 2048$ 以及 $q \approx n^{5.818}$, 所以 $\alpha \cdot q$ 可以近似为 $n^{2.909}$。定理第二个条件变为 $ q \in \tilde{\Omega}\left(n^{13.636}\right) . $ 但 $q \approx n^{5.818}$ ! 因此, 该攻击需要进行相当多的改进才能应用于 TFHE。 ### 复杂度 讨论了该定理适用的条件之后, 现在转向定理的结论部分。这里我们需要考虑算法的复杂度, 即 $ \operatorname{poly}(m, \log q, \alpha \cdot q) \text {. } $ 哎呀, 定理并没有给出任何所蕴含的常数或多项式次数。 Shor 的算法对 RSA 和 ECDLP 来说是毁灭性的, 因为量子复杂度实际上并没有那么大。因此, 如果量子计算机建成, 那么 RSA 和 ECDLP 很可能会被破解。另一方面, Grover 针对 AES-128 的算法的量子复杂度非常高, 因此需要一台巨大的量子计算机才能削弱 AES-128 的安全性。从这两个例子我们可以得出结论：常数很重要。（Kurt Pan注：似乎从这两个例子得不到这个结论……） 然而, 我们注意到复杂度取决于 $\alpha \cdot q$, 即取决于一个输入问题大小未指定的参数。因此, 我们必须依次查看其中给出不同的 $\alpha \cdot q$ 值的每个方案。 以下是一个非常粗略的检查, 但它说明了为什么常数在这里很重要。我们可以了解该复杂度对用一台早期的量子计算机发起攻击是否可行。 我所做的是将复杂度估计中的项 $m$ 、 $\log q$ 和 $\alpha \cdot q$ 替换为正在讨论的四个方案中2的幂的这些值（用$n \cdot \log q$ 近似 $m$ ）。然后大家可以对蕴含的常数进行自己的猜测, 并决定需要担心哪种方案。 1. Kyber: $\operatorname{poly}\left(2^{13.87}, 2^{3.55}, 2^{2.32}\right)$. 2. Dilithium: $\operatorname{poly}\left(2^{14.84}, 2^{4.52}, 2^{3.03}\right)$. 3. BGV: $\operatorname{poly}\left(2^{25.00}, 2^{10.00}, 2^{2.32}\right)$. 4. TFHE: $\operatorname{poly} \left(2^{17.00}, 2^{6.00}, 2^{32.00}\right)$. 对于 Kyber 和 Dilithium，我们看到，假设蕴含的常数和次数相对较小，如果可以改进定理的条件部分，则攻击可能是可行的。 对于 BGV，我们已经注意到定理的条件是满足的，因此攻击是否实用（在未来的量子计算机上）取决于攻击对 $m$ 值的依赖。 我怀疑对$m$的依赖性相当弱，因为它可能与量子子程序的重复次数有关，而不是与子程序本身的复杂性有关。但这纯粹是我的猜测。 对于 TFHE，我们看到，假设可以改进定理条件以便将 TFHE 纳入范围，复杂性也不需要依赖于 $\alpha \cdot q$ 的过高次的多项式，因为对于标准 TFHE 参数，这已经是 $2^{32}$ 了。 ## 结论 人们对于这篇新论文应当去芜存菁。除了我之前的关于尚未经过同行评审，尚未建造出量子计算机的注意点外，还有一些额外的注意点。 1. 当前定理的前提条件不适用于Kyber、Dilithium 或 TFHE；但确实适用于 BGV。 2. 即使前提条件有所改进, 对于任何攻击的可行性, 噪声项 $\alpha \cdot q$ 的复杂度估计的重要性都需要被考虑。 4. 对于 $30 \leq x \leq 100$ 来说, 即使 $2^x$ 次量子运算形式的低量子复杂度值也可能不会产生可行的量子算法（类似应用于 AES-128 的 Grover)。 5. 攻击只会击败量子敌手, 如果还没有建造出大规模量子计算机，我们仍然可以愉快地使用（任何形式的）FHE。 6. 很多公司很乐意部署基于配对密码学技术的 SNARK，尽管基于配对的密码学技术都将会早于 LWE 对任何量子计算机垮掉; 只是会由于不同量子算法的复杂性有所不同。