一文读懂同态加密之CKKS

全同态加密（FHE）被誉为“密码学的圣杯”。不同于 BGV 或 BFV 方案死磕精确整数计算，CKKS 方案另辟蹊径，完美支持了近似浮点数运算。这一特性让它在隐私保护机器学习（PPML）领域大放异彩。本文将带你扒开公式的外衣，从数学基础到算法全流程，彻底搞懂 CKKS 的底层逻辑。

1. 引言

在隐私计算领域，全同态加密（Fully Homomorphic Encryption, FHE）允许我们在不解密的情况下，直接对密文进行计算。通俗地说，就是“数据可用不可见”，计算结果解密后与对明文直接计算的结果完全一致。

2009 年，Craig Gentry 构造了第一个全同态加密方案，开创了这一领域。此后，第二代方案如 BGV 和 BFV 显著提升了效率，但它们主要面向精确整数运算。

2017 年，Cheon、Kim、Kim 和 Song 提出了 CKKS 方案。它的核心创新在于支持近似浮点数运算——这意味着我们可以对加密的实数进行计算，并容忍微小的近似误差。这一妥协不仅极大地提升了计算效率，更使得 CKKS 成为目前隐私保护机器学习中最受欢迎的同态加密方案。

2. 数学预备知识

在深入 CKKS 之前，我们需要简单了解它所依赖的数学土壤。

2.1 多项式环

CKKS 并不直接在普通的数字上计算，而是工作在多项式环上。设 $M = 2N$ 是 2 的幂次，定义分圆多项式：

$$ \Phi_M(X) = X^N + 1 $$

其中 $N = M/2$。我们使用的多项式环为：

$$ \mathcal{R} = \mathbb{Z}[X] / (X^N + 1) $$

这意味着环中所有多项式的次数最高不超过 $N-1$，且满足 $X^N \equiv -1$。类似地，定义商环 $\mathcal{R}_q = \mathbb{Z}_q[X] / (X^N + 1)$，即系数在模 $q$ 意义下进行运算。

2.2 典范嵌入 (Canonical Embedding)

这是 CKKS 的核心数学工具。考虑本原 $M$ 次单位根 $\zeta = e^{2\pi i / M}$，典范嵌入 $\sigma$ 将多项式 $m(X) \in \mathcal{R}$ 映射到复数向量：

$$ \sigma(m) = \left(m(\zeta), m(\zeta^3), \ldots, m(\zeta^{2N-1})\right) \in \mathbb{C}^N $$

简单来说，就是求多项式在 $M$ 次本原单位根的奇数幂处的取值。这个映射是一个完美的环同态：多项式的加法和乘法，完美对应复数向量逐元素的加法和乘法。

关键性质：对于实数多项式（系数为实数），$\sigma$ 的像具有共轭对称性：$m(\zeta^{2N - j}) = \overline{m(\zeta^j)}$。因此，我们只需要存储 $N/2$ 个复数，即可完整表示一个实数多项式。

2.3 RLWE 困难问题

CKKS 的安全性基石是环上带错误学习（Ring Learning With Errors, RLWE）问题。 RLWE 假设表明，给定 $(a, a \cdot s + e)$（其中 $a$ 均匀随机、$s$ 是私钥、$e$ 是极小的噪声多项式），在多项式时间内，攻击者无法将其与真正的均匀随机分布区分开来。

3. CKKS 方案详解

3.1 编码与解码：连接复数与多项式的桥梁

CKKS 的编码步骤将复数消息向量转换为明文多项式，这是区分 CKKS 与其他方案最关键的一步。

编码 (Encoding)

给定消息向量 $\mathbf{z} = (z_1, z_2, \ldots, z_{N/2}) \in \mathbb{C}^{N/2}$，目标是找到一个多项式 $m(X) \in \mathcal{R}$ 使得 $m(\zeta^{2j-1}) \approx z_j$。由于共轭对称性，另一半值自动满足。

具体流程如下：

  1. 扩展向量：构造 $\mathbf{w} = (z_1, z_2, \ldots, z_{N/2}, \overline{z_{N/2}}, \ldots, \overline{z_1}) \in \mathbb{C}^N$。
  2. 缩放精度：乘以缩放因子 $\Delta > 0$（通常是 2 的幂次），得到 $\Delta \cdot \mathbf{w}$。
  3. 逆典范嵌入：通过 $\sigma^{-1}$ 映射回多项式： $$ m(X) = \sigma^{-1}(\Delta \cdot \mathbf{w}) = \frac{1}{N}\sum_{j=0}^{N-1} (\Delta \cdot w_j) \cdot \left(\sum_{k=0}^{N-1} \zeta^{-j(2k+1)} X^k\right) \pmod{X^N + 1} $$
  4. 四舍五入：由于计算存在浮点误差，将系数四舍五入到最近的整数： $$ m(X) = \lfloor \sigma^{-1}(\Delta \cdot \mathbf{w}) \rceil \in \mathcal{R} $$

💡 直观理解： 缩放因子 $\Delta$ 的作用类似于定点数表示中的“小数点位置”。$\Delta$ 越大，保留的精度越高，但同时也会消耗更多的“噪声预算”（Noise Budget）。

解码 (Decoding)

给定明文多项式 $m(X) \in \mathcal{R}$，解码就是编码的逆过程：先做典范嵌入，再除以缩放因子 $\Delta$。

$$ \mathbf{z} = \frac{1}{\Delta} \cdot (m(\zeta), m(\zeta^3), \ldots, m(\zeta^{2N-1})) $$

3.2 核心参数设置

CKKS 方案运行依赖以下关键参数：

参数 物理含义
$N$ 多项式环的维度，必须为 2 的幂次。
$\Delta$ 缩放因子，通常取 $2^{p}$，决定计算精度。
$q_L$ 最大模数，由多层模数链组成。
$h$ 私钥分布中非零系数的数量（汉明权重）。

模数链（Modulus Chain）是 CKKS 的灵魂设计。定义 $q_\ell = q_0 \cdot p^\ell$（$\ell = 0, 1, \ldots, L$），其中 $q_0$ 是基础模数，$p$ 与缩放因子相关。每一层 $\ell$ 都对应着当前的计算深度与精度状态。

3.3 密钥生成

  • 私钥 (Secret Key)：从汉明权重三元分布（HWT）中采样私钥 $s \in \mathcal{R}$，系数取自 ${-1, 0, 1}$，且非零系数恰好为 $h$ 个。
  • 公钥 (Public Key)：$(b, a) \in \mathcal{R}_{q_L}^2$，其中 $a$ 随机采样，$e$ 为离散高斯噪声，计算 $b = -a \cdot s + e \pmod{q_L}$。
  • 重线性化密钥 (Evaluation Key)：同态乘法会使密文膨胀（从 2 个多项式变成 3 个）。重线性化密钥 $\mathsf{evk} = (b’, a’)$ 用于将密文“压缩”回正常大小，其生成方式为 $b’ = -a’ \cdot s + e’ + p \cdot s^2 \pmod{q_L \cdot p}$。

3.4 加密与解密

加密：将编码后的多项式 $m$ 混入公钥和噪声。采样极小多项式 $v, e_0, e_1$，计算密文 $\mathsf{ct} = (c_0, c_1)$：

$$ \begin{aligned} c_0 &= v \cdot b + m + e_0 \pmod{q_L} \ c_1 &= v \cdot a + e_1 \pmod{q_L} \end{aligned} $$

解密：使用私钥 $s$ 消除掩码：

$$ m \approx c_0 + c_1 \cdot s \pmod{q_\ell} $$

展开验证可知，结果包含原始消息 $m$ 和少量噪声（$v \cdot e + e_0 + e_1 \cdot s$）。这部分噪声在解码除以 $\Delta$ 时会被作为舍入误差抹去。

4. 同态运算：如何在密文上跳舞？

4.1 同态加法

给定密文 $\mathsf{ct} = (c_0, c_1)$ 和 $\mathsf{ct}’ = (c_0’, c_1’)$，直接对应项相加：

$$ \mathsf{ct}_{\mathsf{add}} = (c_0 + c_0’ \pmod{q_\ell}, \quad c_1 + c_1’ \pmod{q_\ell}) $$

噪声变化：加法导致噪声近似相加（新噪声 $\approx e + e’$），增长极其缓慢，几乎没有计算深度的限制。

4.2 同态乘法与重缩放 (Rescaling)

同态乘法是 CKKS 中最硬核、也最耗时的操作，分为三步：

  1. 张量积：计算多项式交叉乘积，得到三元组 $(d_0, d_1, d_2)$： $$ d_0 = c_0 \cdot c_0’, \quad d_1 = c_0 \cdot c_1’ + c_1 \cdot c_0’, \quad d_2 = c_1 \cdot c_1’ \pmod{q_\ell} $$
  2. 重线性化：利用预先生成的密钥 $\mathsf{evk}$ 消去 $d_2$ 项，将密文恢复为二维向量 $(c_0’’, c_1’’)$。 此时，噪声发生相乘爆炸，更关键的是，缩放因子从 $\Delta$ 变成了 $\Delta^2$！
  3. 重缩放 (Rescaling)：这是 CKKS 的神来之笔。其作用类似于浮点数乘法后的“截断多余小数位”。 $$ \mathsf{RS}(\mathsf{ct}) = \left\lfloor \Delta^{-1} \cdot \mathsf{ct} \right\rceil \pmod{q_{\ell-1}} $$

🎯 重缩放的双重功效：

  1. 将缩放因子从 $\Delta^2$ 强行降回 $\Delta$，防止数据溢出。
  2. 将模数从 $q_\ell$ 降到 $q_{\ell-1}$，直接消除掉一部分乘法带来的低位噪声！ 代价就是：每次乘法都会消耗一层模数，模数链的深度 $L$ 决定了你能连续做多少次乘法。

4.3 旋转 (Rotation)

CKKS 支持对密文槽中的数据进行循环移位。借助多项式环的 Galois 自同构 $\kappa_{2r+1}: m(X) \mapsto m(X^{2r+1})$，可以在极小代价下实现诸如矩阵乘法、卷积计算中的数据重排。

5. 安全性与性能评估

安全性边界： 在标准的 RLWE 假设下，CKKS 是 IND-CPA 安全的。但在解密结果对不可信方可见的场景下，由于 CKKS 的解密包含近似误差，攻击者可通过反复发空请求推断出私钥（Li & Micciancio, 2021 攻击）。因此，CKKS 最佳实践是将最终结果直接输出给可信方，或在解密前人为注入高斯噪声（Noise Flooding）来防御。

性能特性： 在 $N = 2^{15}$（即 32768）的典型配置下，底层多项式乘法通过 NTT（数论变换）加速，时间复杂度为 $O(N \log N)$。单次同态乘法耗时仅需数十毫秒级。

操作 时间复杂度 噪声增长 模数消耗
加法 $O(N)$ 极小（相加） 0 层
乘法 $O(N \log N)$ 极大（相乘） 1 层
旋转 $O(N \log N)$ 小 0 层

6. 方案对比与应用场景

没有万能的方案，只有最合适的场景。相比于其他 FHE 方案，CKKS 的定位非常明确：

特性 CKKS BGV / BFV TFHE
数据类型 浮点数 / 复数 整数 布尔值 / 短整数
计算精度 近似（存在误差） 精确计算 精确计算
打包容量 $N/2$ 个数据槽 $N$ 个数据槽 极小（常为 1 bit）
核心应用 机器学习、联邦学习 传统统计、整数运算 复杂逻辑电路计算

典型落地场景：

  • 隐私保护机器学习 (PPML)：加密神经网络的训练与推理（如 HE-Transformer）。
  • 医疗数据分析：在加密基因数据上执行 GWAS（全基因组关联分析）。
  • 金融风控：多方联合进行加密信用评分。

7. 总结

CKKS 巧妙地利用了典范嵌入，将现实世界中的浮点数向量无缝过渡到密码学的多项式环中。它的核心脉络可以用三个公式概括：

  • 编码映射：$\mathsf{Encode}(\mathbf{z}) = \lfloor \sigma^{-1}(\Delta \cdot \mathbf{w}) \rceil$
  • 掩码解密：$m \approx c_0 + c_1 \cdot s$
  • 乘法自愈：$\mathsf{RS}(\mathsf{Relin}((c_0, c_1) \otimes (c_0’, c_1’)))$

理解了这三步，你就握住了通往现代隐私保护 AI 时代的钥匙。

参考文献

  1. Cheon, J. H., et al. (2017). Homomorphic encryption for arithmetic of approximate numbers. ASIACRYPT.
  2. Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. STOC.
  3. Lyubashevsky, V., et al. (2010). On ideal lattices and learning with errors over rings. EUROCRYPT.
  4. Li, B., & Micciancio, D. (2021). On the security of homomorphic encryption on approximate numbers. EUROCRYPT.
  5. Kim, A., et al. (2022). General bootstrapping approach for RLWE-based homomorphic encryption. IEEE TIFS.