同态加密方案BFV/BGV中密文乘法的重线性化技术

密文乘法后的问题：噪声膨胀与维度增长

BFV 和 BGV 都是基于环学习误差假设（Ring-LWE）的层级全同态加密方案。它们支持对密文进行加法和乘法操作，但每次乘法会带来两个棘手的问题：噪声急剧增长 和 密文规模膨胀。

• 噪声增长：每个密文都携带一个小的噪声，初始噪声在 $B$ 量级。加法噪声增长约 $2B$，而乘法噪声增长约 $B^2$，甚至更高（取决于参数）。若不控制，几次乘法后噪声就会超过解密阈值，导致解密失败。
• 密文规模膨胀：一个 BFV/BGV 密文通常由两个多项式组成 $(c_0, c_1)$。当两个这样的密文相乘时，结果会变成三个多项式 $(c_0', c_1', c_2')$，即维度从 2 增加到了 3。继续乘法，维度会指数增长，无法管理。

为了解决密文规模膨胀问题，重线性化 技术被引入。它将三维密文重新压缩回二维，同时控制噪声的增长。

重线性化的核心思想

重线性化的目标是：将三个多项式 $(c_0', c_1', c_2')$ 转化为两个多项式 $(c_0'', c_1'')$，使得解密后得到与原始乘法相同的结果，但密文维度恢复为 2。

这个转化的本质是利用一组重线性化密钥（relin keys）来表示高次项 $c_2'$。具体来说，对于 BGV 方案（BFV 类似），重线性化密钥是一组经过加密的“幂次”辅助向量，用于将 $c_2' s^2$ 项（其中 $s$ 是私钥）重新表达为关于 $s$ 的一阶项，从而消除 $s^2$ 项。

用公式说明

设两个密文分别为 $\mathsf{ct}_1 = (c_{1,0}, c_{1,1})$ 和 $\mathsf{ct}_2 = (c_{2,0}, c_{2,1})$，并假设私钥为 $s$。解密时计算：$m \approx (c_0 + c_1 s) \bmod q$。

乘法后的原始结果是一个三元组 $(d_0, d_1, d_2)$，满足：

$$ d_0 + d_1 s + d_2 s^2 \approx \text{乘法结果} \pmod{q} $$

重线性化利用公开的密钥 $\mathsf{rlk} = (rlk_0, rlk_1)$，其中 $rlk_0 + rlk_1 s \approx s^2 \pmod{q}$。该密钥由私钥持有者提前生成并发布。

通过计算：

$$ \begin{aligned} c_0'' &= d_0 + \text{PowersOf2}(d_2) \cdot \mathsf{rlk}_0 \\ c_1'' &= d_1 + \text{PowersOf2}(d_2) \cdot \mathsf{rlk}_1 \end{aligned} $$

其中 $\text{PowersOf2}(d_2)$ 是一个向量化操作，将 $d_2$ 分解为基 2 的倍乘表示。最终得到的 $(c_0'', c_1'')$ 是二维密文，解密时满足 $c_0'' + c_1'' s \approx d_0 + d_1 s + d_2 s^2$，从而正确恢复乘法结果。

重线性化的具体步骤（以 BGV 为例）

阶段 1：准备工作——生成重线性化密钥

1. 生成私钥：选择一个秘密多项式 $s \in R_q$（通常为小系数，如二进制或三元）。
2. 生成第一个辅助项：随机选取 $a \leftarrow R_q$，并计算 $b = a \cdot s + e + s^2$，其中 $e$ 是小噪声。实际中还需分母基分解，但核心是 $b - a s \approx s^2$。
3. 发布密钥：将 $(b, -a)$ 作为重线性化密钥 $\mathsf{rlk}$ 公开。注意，不直接暴露 $s$。

阶段 2：执行密文乘法

4. 计算乘积三元组：给定两个密文 $\mathsf{ct}_1 = (c_{1,0}, c_{1,1})$ 和 $\mathsf{ct}_2 = (c_{2,0}, c_{2,1})$，计算：
   $$ \begin{aligned} d_0 &= c_{1,0} \cdot c_{2,0} \\ d_1 &= c_{1,0} \cdot c_{2,1} + c_{1,1} \cdot c_{2,0} \\ d_2 &= c_{1,1} \cdot c_{2,1} \end{aligned} $$
   所有运算在多项式环 $R_q$ 上进行。

5. 分解高次项系数：将多项式 $d_2$ 的每个系数分解为数字基 $T$（通常取 2 或大基数）下的表示。设 $T = 2^r$，则分解后得到 $\ell$ 个低比特多项式 $d_2^{(0)}, \dots, d_2^{(\ell-1)}$，使得 $d_2 = \sum_{i=0}^{\ell-1} T^i \cdot d_2^{(i)}$。这种分解是为了将大标量乘法转化为小标量乘法，控制噪声。

阶段 3：合并重线性化

6. 加权组合：对每个分解后的多项式 $d_2^{(i)}$，用重线性化密钥的对应部分做点积：
   $$ \begin{aligned} c_0'' &= d_0 + \sum_{i=0}^{\ell-1} d_2^{(i)} \cdot \mathsf{rlk}_{0,i} \\ c_1'' &= d_1 + \sum_{i=0}^{\ell-1} d_2^{(i)} \cdot \mathsf{rlk}_{1,i} \end{aligned} $$
   其中 $(\mathsf{rlk}_{0,i}, \mathsf{rlk}_{1,i})$ 是预计算好的密钥分量。

7. 输出结果：得到二维密文 $\mathsf{ct}_{\text{new}} = (c_0'', c_1'')$，其维度与初始密文相同。后续可继续参与加法和乘法运算。

重线性化对噪声的影响

重线性化不会消除乘法的内在噪声增长，但会引入额外的小噪声（来自分解和密钥的误差）。设计良好的参数（如 $T$ 与模数 $q$ 匹配）可以使得这部分额外噪声远小于乘法本身带来的噪声。通常，重线性化后的噪声约为 $O(B^2 + B \cdot \ell \cdot \text{分解误差})$，仍保持可接受范围。

如果跳过重线性化，后续每轮乘法都会使密文维度增加，很快导致无法计算。因此，在实际方案中（如 Microsoft SEAL、HElib 等库），每次乘法后自动执行重线性化，以保证密文结构稳定。

常见实现细节与优化

• 基分解的基数 $T$：增大 $T$ 可减少分解项数 $\ell$，但会增加重线性化误差。典型选择为 $T = 2^{16}$ 或 $T = 2^{32}$，在噪声与效率间平衡。
• 密钥切换思想的扩展：重线性化实际上是密钥切换（key switching）的一个特例——将 $s^2$ 密钥下的密文切换到 $s$ 密钥下。因此广义的密钥切换可用于任意多项式函数 $f(s)$ 的切换。
• 模数链的配合：在层级方案中，每个乘法后还会执行模数切换（modulus switching）来压缩噪声，与重线性化协同工作。