使用NTT友好环的LaBRADOR实现存在可靠性缺陷

量子算法的最新进展将后量子密码学推至聚光灯下。在日益增长的担忧中，密码学工程师现在必须应对这一转变，以近年来的标准化工作为指导。虽然公钥加密领域（有充分理由）一直是这类工作的主要焦点，但其他领域，例如后量子证明系统，仍然是活跃但有待探索的研究领域。

基于格（Lattice）的证明系统属于这一类。在研究方面，近年来提出了许多新协议。然而，目前实现这些协议的生产级库仍然很少（如果有的话），并且还没有大规模的现实世界部署。虽然论文中总是提到参数选择，但最微小的歧义也可能误导实现者，导致灾难性的后果。

在上一篇文章中，我们了解了 LaBRADOR 证明系统。在这篇文章中，我们将看到 LaBRADOR 的三个实现被破解了。有趣的是，我们会发现，出于效率考虑而在基于格的密码学中广泛推荐使用的 NTT 友好环（NTT-friendly rings），破坏了协议的可靠性。

下表列出了在 GitHub 上找到的各种 LaBRADOR 实现。一些受影响的库尚未达到生产就绪状态，因此“可靠性比特”仅指我们在本文中探讨的不安全环选择所造成的影响。

环的陷阱

多项式环在基于格的密码学中无处不在，主要是由于 NTT 变换支持的高效乘法。LaBRADOR 使用的环形式为：

[ R_q: \mathbb{Z}_q[X]/(X^d+1) ]

我们可以将环元素视为度数最多为 $d-1$ 的多项式，系数在 $\mathbb{Z}_q$ 中。

研究人员很自然地将“经典”证明系统文献（通常在有限域上操作）中的技术移植到基于格的证明系统（在多项式环上操作）中。确实，LaBRADOR 使用了这样一种技术：随机线性组合，将证明者的声明聚合为单个声明。

第一个随机线性组合（在标量上）

协议中第一次出现这种情况是在常数项约束的聚合中（ePrint, p.12）。在简化的协议中：

• 验证者采样随机的标量向量：$\vec{\psi} \xleftarrow{$} \mathbb{Z}_q^L$, $\vec{\omega} \xleftarrow{$} \mathbb{Z}_q^{256}$。
• 证明者使用它们作为随机系数来计算声明的线性组合。
• 如果结果等于零，那么约束条件被满足的概率为 1-p。

在这里，作弊证明者通过检查的概率 $p$ 究竟是多少？为了得到上界，我们假设一个最大程度作弊的证明者。因此，会有一个声明 $(v_{\text{cheating}} - v_{\text{expected}}) \neq 0 \in \mathbb{Z}q$，但要通过检查：$\omega'(u{\text{cheating}} - u_{\text{expected}}) = 0$1。由于 $\omega'$ 在 $\mathbb{Z}_q$ 中是均匀随机的，对任何证明者来说，这种情况发生的概率为 $1/q$，假设 $q$ 是素数。至关重要的是，ePrint 上的 LaBRADOR 论文没有明确说明 $q$ 需要是素数，但隐含地假设了这一点。

基于这个隐含假设，论文指定 $q \approx 2^{32}$。32 比特的可靠性被认为是不安全的，因此它通过执行多轮聚合来进行可靠性放大，以达到 128 比特。以 128 比特为目标的轮数计算如下：

[ k = \lceil 128 / \log q \rceil ]

注意，这里假设 $q$ 提供 $\log q$ 比特的可靠性，这再次隐含地将 $q$ 视为素数。如果 $q$ 是合数，$\mathbb{Z}_q$ 将是一个环，而不是域，因此它包含零因子。在这种情况下，概率并非简单的 $1/q$，我们必须考虑具体的模数 $q$。

第二个随机线性组合（在环上）

第二个利用随机线性组合进行批量检查约束的关键步骤是在最终约束聚合步骤中（ePrint, p.12-13）。在这种情况下，随机采样的系数是环元素。同样，我们简化协议：

• 验证者采样 $\alpha_k, \beta_k \xleftarrow{$} R_q$。
• 证明者使用它们作为随机系数来计算所有约束的线性组合，并将它们合并为一个最终检查。
• 如果结果等于零，那么约束条件被满足的概率为 1-p。

这里，概率 $p$ 并非显而易见。作弊者通过检查的条件是 $\alpha_k'(u_{\text{cheating}} - u_{\text{expected}}) = 0 \in R_q$，其中 $(u_{\text{cheating}} - u_{\text{expected}}) \neq 0$。2 在这种情况下，我们需要详细分析多项式环及其零因子。

LaBRADOR 对多项式环有明确说明：选择 $q, d$ 使得 $X^d+1$ 模 $q$ 恰好分裂为两个不可约因子。因此，我们得到同构：

[ \mathbb{Z}_q[X]/(X^d+1) \cong \mathbb{Z}_q[X]/P_1(x) \times \mathbb{Z}_q[X]/P_2(x) ]

其中 $q$ 和 $d$ 的选择使得 $P_1, P_2$ 模 $q$ 都是次数为 $d/2$ 的不可约多项式。

简单来说，我们可以将环元素 $\alpha \in R_q$ 视为一个元组 $(\alpha_1, \alpha_2) \in (R_1 \times R_2)$。现在，$R_q$ 上的乘法可以看作是元组形式下的逐分量乘法。

这种情况下，作弊证明者可以构造 $(u_{\text{cheating}} - u_{\text{expected}}) = (0, u') \in R_1 \times R_2$。由于 $q$ 是素数 且 $P_1, P_2$ 模 $q$ 不可约，这两个环中都没有零因子3。因此，检查仅当随机采样的 $\alpha_k = (\alpha_1, 0) \in R_1 \times R_2$ 时才会通过。也就是说，我们只关心第二个“槽”（slot），它需要为 $0$ 才能“抵消” $u'$，结果得到乘积：$(0 \cdot \alpha_1, u' \cdot 0) = (0, 0)$。

这等于在 $R_2$ 中随机抽到零环元素的概率，零环元素是一个次数为 $d/2$ 的多项式，其在 $\mathbb{Z}_q$ 中的所有系数都等于零。因此，$p = 1/q^{d/2}$，这是可忽略的。4

NTT 陷阱

回顾一下，数论变换（Number Theoretic Transform）可以看作多项式系数形式与其在 $2d$ 次单位根 $\zeta^i$ 上的求值之间的同构：

[ \mathbb{Z}q[X]/(X^d+1) \cong \prod{i=0}^{d-1} \mathbb{Z}_q[X]/(X - \zeta^{2i+1}) \cong \mathbb{Z}_q^d ]

多项式环是否支持此变换取决于模数 $q$ 和次数 $d$：对于这个特定的环，假设 $q$ 是素数，需要 $2d$ 整除 $q-1$。当支持 NTT 时，环完全分裂成尽可能小的环，即商多项式次数为 1 的多项式环。

注意，正如我们之前所见，随机线性组合的安全性取决于最小环因子的阶。在 NTT 友好的情况下，这个阶将是 $q$，而不是 LaBRADOR 论文所需的 $q^{d/2}$。

陷入陷阱

2 的幂次模数 - Lazarus 的致命原罪

Lazarus 使用的环是：

[ R: \mathbb{Z}_{2^{32}}[X]/(X^{64}+1) ]

错误的聚合步骤数

回顾一下，常数项约束聚合的聚合步骤数计算如下：

[ k = \lceil 128 / \log q \rceil ]

隐含假设 $q$ 是素数。然而，在这种情况下，$q = 2^{32}$。

对于第一个随机线性组合，随机系数从 $\mathbb{Z}{2^{32}}$ 中采样。因此，作弊证明者可以构造 $(u{\text{cheating}} - u_{\text{expected}}) = 2^{31}$。现在，检查通过的条件是：

[ \omega' \cdot (u_{\text{cheating}} - u_{\text{expected}}) = 0 \pmod{q} \implies \omega' \cdot 2^{31} = 0 \pmod{2^{32}} ]

因此，任何偶数的 $\omega'$ 都会导致：$2\ell \cdot 2^{31} = 2^{32} \cdot \ell = 0 \mod 2^{32}$。作弊者通过检查的概率为 $1/2$！

可靠性放大不会考虑这一点；聚合步骤仍然按之前定义的方式计算，使用 $\log q$ 作为分母。将有 $k=4$ 轮聚合，每轮仅获得 1 比特的可靠性，因此总可靠性仅为 4 比特，而非目标的 128 比特。

环上的不安全线性组合

第二个随机线性组合（环上的）的可靠性以类似的方式崩溃。简化的检查是 $u \cdot \alpha = 0$，其中 $u \neq 0$ 由证明者控制，$\alpha$ 是由验证者采样的随机挑战。

对于 Lazarus 选择的环，恶意证明者可以构造所有系数都是 $2^{31}$ 的多项式。让 $\vec{u}$ 是系数向量：

[ \vec{u} = (2^{31}, 2^{31}, \ldots, 2^{31}) \in (\mathbb{Z}_{2^{32}})^{64} ]

环乘法本质上是模 $(X^{64}+1)$ 的多项式乘法。乘积 $c = u \cdot \alpha$ 的系数可以通过对系数向量使用负循环Rollup来计算。每个系数 $c_k$ 将是：

[ c_k = \left( \sum_{i=0}^{k} u_i \cdot a_{k-i} \right) - \left( \sum_{i=k+1}^{63} u_i \cdot a_{64+k-i} \right) ]

由于 $\vec{u} = (2^{31}, \ldots, 2^{31})$：

[ c_k = \left( \sum_{i=0}^{k} 2^{31} \cdot a_{k-i} \right) - \left( \sum_{i=k+1}^{63} 2^{31} \cdot a_{64+k-i} \right) = 2^{31} \cdot \left( \sum_{i=0}^{k} a_{k-i} - \sum_{i=k+1}^{63} a_{64+k-i} \right) ]

令 $P = \sum_{i=0}^{k} a_{k-i}$ 且 $N = \sum_{i=k+1}^{63} a_{64+k-i}$。则：

[ c_k = 2^{31}(P - N) = 2^{31}(P + N - 2N) = 2^{31}(P + N) - 2^{32}N ]

但 $P + N$ 是 $\alpha$ 所有系数的和：

[ P + N = \sum_{i=0}^{k} a_{k-i} + \sum_{i=k+1}^{63} a_{64+k-i} = \sum_{i=0}^{63} a_i ]

最终，乘积系数将是：

[ c_k = 2^{31} \cdot \sum_{i=0}^{63} a_i ]

注意与上一节作弊证明者的相似性：再次使用 $2^{31}$ 来利用模数为 $2^{32}$ 的事实。现在，由于 $\alpha$ 是均匀随机的，其系数之和为偶数的概率是 $1/2$。也就是说，对于某个整数 $\ell$：

[ c_k = 2^{31} \cdot 2 \cdot \ell = 2^{32} \cdot \ell = 0 \pmod{2^{32}} ]

由于所有系数都为零，$c = 0 \in R$。因此，作弊证明者将再次以 $1/2$ 的概率通过检查。这是一个毁灭性的结果，因为这里没有可靠性放大轮。完整协议的可靠性将只有 1 比特！

Lazarus - 总结

• 2 的幂次模数 $q$ 导致 $\mathbb{Z}_q$ 中一半的元素是零因子。
• 这损害了两个聚合步骤（常数项聚合中只有 4 比特可靠性，最终聚合中只有 1 比特可靠性）。

在其余三个受影响的库（icicle-labrador, condor-rs, lattirust/labrador 仅在一个示例中）中，选择的环不安全，因为它分裂成了更小的环，要么是通过有意支持 NTT 而完全分裂，要么是通过中国剩余定理（CRT）和环因子上的 NTT 部分分裂。

CRT+NTT - icicle-labrador, condor-rs 和 lattirust/labrador（几乎）的致命原罪

icicle-labrador

icicle-labrador 选择 $d=64$，模数 $q$ 是合数，是 KoalaBear 素数与 BabyBear 素数的乘积：

[ q = p_{kb} \cdot p_{bb} ]

其中：

[ p_{kb} = 2^{31} - 2^{24} + 1, \quad p_{bb} = 2^{31} - 2^{27} + 1 ]

错误的聚合步骤数

再次，合数 $q$ 损害了常数项聚合。步骤数 $k$ 在代码中计算时使用了 $\log q \approx 62$，所以 $k=3$。但是，由于 $q$ 是合数，每一步提供的可靠性约为 $\approx 31$ 比特。因此，聚合的最终可靠性将是 93 比特，而非目标的 128 比特。

环上的不安全线性组合

对环上线性组合可靠性损害最大的是支持 NTT 的两个环因子。icicle-labrador 有意选择了这样的环，以实现高效的多项式乘法。但是，通过结合中国剩余定理和 NTT，我们得到该环的如下同构：

[ \mathbb{Z}q[X]/(X^{64}+1) \cong \mathbb{Z}{p_{kb}}[X]/(X^{64}+1) \times \mathbb{Z}{p{bb}}[X]/(X^{64}+1) \cong \mathbb{Z}{p{kb}}^{64} \times \mathbb{Z}{p{bb}}^{64} \cong \mathbb{Z}_q^{64} ]

环完全分裂，现在最小的因子将是 $\mathbb{Z}{p{bb}}$。恶意证明者现在可以构造：

[ \vec{u} = (\kappa \cdot p_{kb}, 0, \ldots, 0) \in \mathbb{Z}_q^{64} ]

这也可以看作在 CRT 表示中只有一个非零槽。现在，如果随机抽取的 $\alpha$ 在该槽中的系数是 $p_{bb}$ 的倍数，则检查通过：

[ u \cdot \alpha = (\kappa \cdot p_{kb} \cdot l \cdot p_{bb}, 0, \ldots, 0) = (\kappa \cdot l \cdot q, 0, \ldots, 0) = (0, \ldots, 0) \in \mathbb{Z}_q^{64} ]

在 $\mathbb{Z}q$ 中有 $p{kb}$ 个 $p_{bb}$ 的倍数，因此检查通过的概率为：

[ \frac{p_{kb}}{p_{bb} \cdot p_{kb}} = \frac{1}{p_{bb}} ]

因此，该随机线性组合的可靠性仅为 $\approx 31$ 比特。

icicle-labrador - 总结

• 为效率选择合数模数 $q$ 和 NTT 友好环因子，使得环完全分裂，基础环的阶不够大。
• 两个聚合步骤都受到影响，最终聚合步骤损害了协议，仅提供31 比特的可靠性。

condor-rs

condor-rs 选择的模数有类似的缺陷。具体：

[ q = 2^{32} - 1 = 3 \cdot 5 \cdot 17 \cdot 257 \cdot 65537 ]

错误的聚合步骤数

再次，$q$ 不是素数。$\mathbb{Z}_q$ 的最小环因子是 $\mathbb{Z}_3$，因此单轮可靠性仅为 $1/3$，约 $\approx 1.58$ 比特。但在计算 $k$ 时，使用了 $\log q$。因此：

[ k = \lceil 128 / \log q \rceil = 4 ]

所有轮次的结果可靠性将仅为 $\approx 6$ 比特，而非目标的 128 比特。

环上的不安全线性组合

与 icicle-labrador 类似，我们可以首先使用 CRT 同构：

[ \mathbb{Z}q[X]/(X^{64}+1) \cong \mathbb{Z}3[X]/(X^{64}+1) \times \mathbb{Z}5[X]/(X^{64}+1) \times \mathbb{Z}{17}[X]/(X^{64}+1) \times \mathbb{Z}{257}[X]/(X^{64}+1) \times \mathbb{Z}{65537}[X]/(X^{64}+1) ]

注意 $\mathbb{Z}_{257}[X]/(X^{64}+1)$ 支持 NTT。因此：

[ \mathbb{Z}{257}[X]/(X^{64}+1) \cong \mathbb{Z}{257}^{64} ]

这导致原始环分裂：

[ \mathbb{Z}q[X]/(X^{64}+1) \cong \mathbb{Z}3[X]/(X^{64}+1) \times \mathbb{Z}5[X]/(X^{64}+1) \times \mathbb{Z}{17}[X]/(X^{64}+1) \times \mathbb{Z}{257}^{64} \times \mathbb{Z}{65537}[X]/(X^{64}+1) ]

我们现在可以看到最小的环因子是 $\mathbb{Z}{257}$。作弊证明者可以通过仅在 $\mathbb{Z}{257}$ 中有一个非零槽来构造 $u$，方式类似于上一节。然后，检查通过的概率为 $1/257$。这仅为 $\approx 8$ 比特的可靠性。

condor-rs - 总结

• 合数模数 $q$ 有许多小因子，其中包括 $257$。由 CRT 产生的以 $\mathbb{Z}_{257}$ 为基础环的多项式环因子对 NTT 友好。
• 两个聚合步骤都受到影响（由于第一步的小因子，仅 6 比特可靠性；由于 CRT + NTT 友好环因子，仅 8 比特可靠性）。

lattirust/labrador

lattirust/labrador 核心没有这个问题，因为 LaBRADOR 的实现与实际参数选择是解耦的。然而，上述陷阱仍然存在，因为实现允许类似的不安全参数。对于聚合步骤数，$k$ 再次使用 $\log q$ 作为分母计算，隐含假设 $q$ 是素数。

仓库中包含的测试确实有不安全的参数，类似于 icicle-labrador。具体：

[ q = q_1 \cdot q_2 ]

其中：

[ q_1 = 274177, \quad q_2 = 67280421310721 ]

对于常数项聚合，经过 2 轮（每轮约 18 比特）后，可靠性约为 36 比特。

至于环上的随机线性组合，两个结果环 $\mathbb{Z}{q_1}[X]/(X^{64}+1)$ 和 $\mathbb{Z}{q_2}[X]/(X^{64}+1)$ 都支持 NTT。最小的环因子将是 $\mathbb{Z}_{q_1}$，与之前类似，作弊证明者通过检查的概率为 $1/q_1$，结果仅为 $\approx 18$ 比特的可靠性。

lattirust/labrador - 总结

• 合数模数 $q$ 和 NTT 友好环，类似于 icicle-labrador。
• 两个聚合步骤都受到影响（第一步仅 36 比特可靠性，由于 CRT + NTT 友好环，仅 18 比特可靠性）。

关于在实践中利用陷阱的简要说明

环元素的槽视角有助于理解为什么当环分裂时，环上随机线性组合的可靠性分析会失效。在实践中，这并不简单。在求值域（即槽视角）中操纵单个槽会导致系数形式膨胀，而 LaBRADOR 只允许“短”的见证。因此，即使聚合检查通过，伪造的证明也会因为短度检查而失败。

要了解理论攻击如何转化为概念验证攻击，我们可以转而关注一类声明。在 LaBRADOR 中，简化的 $u$ 实际上是：

[ \sum_{i,j=1}^r a_{ij}^{(k)} \langle \vec{x}_i, \vec{x}j \rangle + \sum{i=1}^r \langle \vec{\phi}_i, \vec{x} \rangle - b^{(k)} ]

这个方程编码了一个约束。我们可以关注那些没有交叉项约束（$a_{ij}=0$）的声明族，并且恶意证明者的“陷阱”（例如，icicle-labrador 部分中 $p_{kb}$ 的倍数）是声明 $\vec{\phi}$ 的一部分。直观地说，通过选择一个略有不同的作弊见证，作弊值与期望值之间的差异在槽视角下将具有所需的性质（它们被“编码”在声明中），而作弊见证仍然很短。短度检查和随机线性组合检查都将通过，从而产生伪造的证明。

结语

在这篇文章中，我们看到了多项式环上的协议在安全实现方面可能面临的挑战。为高效环乘法选择的参数可能会意外地导致可靠性问题，最微小的歧义也可能误导实现者做出错误的选择，这再次凸显了标准化的价值。

对于一种在保持协议安全保证的同时利用 NTT 优化的方法，我们强烈推荐阅读 Chung 等人的这篇论文。

1. $\omega$ 的选择不失一般性；$\psi$ 的分析类似。 ↩
2. $\alpha_k'$ 的选择不失一般性；$\beta_k'$ 的分析类似。 ↩
3. 它们是扩域 $\mathbb{F}_{q^{d/2}}$。 ↩
4. 当然，在这种情况下，作弊证明者可以选择两个环中的任何一个。然而，在一般情况下，他们会选择阶最大的环作为 0 槽，以最大化他们的优势。 ↩

• 原文链接： blog.zksecurity.xyz/post...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～