一文读懂同态加密之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$。由于共轭对称性，另一半值自动满足。
具体流程如下：
- 扩展向量：构造 $\mathbf{w} = (z_1, z_2, \ldots, z_{N/2}, \overline{z_{N/2}}, \ldots, \overline{z_1}) \in \mathbb{C}^N$。
- 缩放精度：乘以缩放因子 $\Delta > 0$（通常是 2 的幂次），得到 $\Delta \cdot \mathbf{w}$。
- 逆典范嵌入：通过 $\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} $$
- 四舍五入：由于计算存在浮点误差，将系数四舍五入到最近的整数： $$ 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 中最硬核、也最耗时的操作，分为三步：
- 张量积：计算多项式交叉乘积，得到三元组 $(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} $$
- 重线性化：利用预先生成的密钥 $\mathsf{evk}$ 消去 $d_2$ 项，将密文恢复为二维向量 $(c_0’’, c_1’’)$。 此时，噪声发生相乘爆炸，更关键的是，缩放因子从 $\Delta$ 变成了 $\Delta^2$！
- 重缩放 (Rescaling)：这是 CKKS 的神来之笔。其作用类似于浮点数乘法后的“截断多余小数位”。 $$ \mathsf{RS}(\mathsf{ct}) = \left\lfloor \Delta^{-1} \cdot \mathsf{ct} \right\rceil \pmod{q_{\ell-1}} $$
🎯 重缩放的双重功效：
- 将缩放因子从 $\Delta^2$ 强行降回 $\Delta$，防止数据溢出。
- 将模数从 $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 时代的钥匙。
参考文献
- Cheon, J. H., et al. (2017). Homomorphic encryption for arithmetic of approximate numbers. ASIACRYPT.
- Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. STOC.
- Lyubashevsky, V., et al. (2010). On ideal lattices and learning with errors over rings. EUROCRYPT.
- Li, B., & Micciancio, D. (2021). On the security of homomorphic encryption on approximate numbers. EUROCRYPT.
- Kim, A., et al. (2022). General bootstrapping approach for RLWE-based homomorphic encryption. IEEE TIFS.