CKKS 同态加密数学基础推导

Cheon-Kim-Kim-Song (CKKS) Scheme - 首个支持近似算术的高效同态加密方案

阅读本文需要一定的代数学基础

本文将介绍CKKS构造同态，密钥生成，加解密，加乘法同构，旋转，自举的数学原理

目录

1. 引言
2. 数学基础
3. CKKS 方案概览
4. 核心构造
5. 同态运算
6. 重缩放与模数切换

引言

同态加密的发展

同态加密（Homomorphic Encryption, HE）允许在密文上直接进行计算，而无需解密。这一特性使得云计算场景下的数据隐私保护成为可能。

CKKS 的核心创新

CKKS（Cheon-Kim-Kim-Song） 方案于 2017 年提出，其核心创新在于：

1. 支持近似算术：可以加密实数/复数向量，计算结果与明文计算存在可控误差
2. SIMD 风格批处理：单次加密可处理 N 个数据，支持向量化的并行计算
3. 高效的旋转操作：支持密文向量的循环移位
4. 重缩放（Rescaling）技术：管理噪声增长，支持任意深度的计算

应用场景

CKKS 特别适合以下场景：

• 机器学习推理（加密神经网络）
• 隐私保护的统计分析
• 基因组数据分析
• 金融数据的安全计算

数学基础

2.1 环与多项式

2.1.1 分圆多项式

设 N = 2^d 为 2 的幂次，m = 2N。第 m 个分圆多项式为：

\Phi_m(X) = X^N + 1

分圆域 \mathbb{Q}(\zeta_m) 是有理数域添加本原 m 次单位根 \zeta_m = e^{2\pi i/m} 得到的扩张。

2.1.2 多项式环

定义两个重要的多项式环：

原始多项式环：
R = \mathbb{Z}[X]/(X^N + 1)

这个符号表示商环（Quotient Ring），下面分步拆解：

\begin{array}{c|c} \text{符号} & \text{含义} \\ \hline \mathbb{Z}[X] & \text{整数系数多项式环：所有形如 } a_0 + a_1 X + \cdots + a_d X^d \text{ 的多项式，系数 } a_i \in \mathbb{Z} \\ (X^N + 1) & \text{由多项式 } X^N + 1 \text{ 生成的理想（ideal）} \\ / & \text{商运算：将环中相差一个理想元素的元素视为等价} \end{array}

R 中的元素是次数小于 N 的整数系数多项式：
a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-1} X^{N-1}, \quad a_i \in \mathbb{Z}

且满足约束关系 X^N \equiv -1 \pmod{X^N + 1}，即所有 X^N 都可以用 -1 替换。

运算示例（设 N=4，即在 R = \mathbb{Z}[X]/(X^4+1) 中）：

• 加法：(1 + 2X) + (3 - X) = 4 + X
• 乘法降次：X^2 \cdot X^3 = X^5 = X \cdot X^4 \equiv -X
• 幂运算：X^6 = X^2 \cdot X^4 \equiv -X^2

可以将商群理解为将正规子群 N“压缩”为单位元”，即在 G 中把 N 内的元素视作同一个单位元。这样，商群将原群划分为若干等价类，每个等价类对应一个陪集。

模 q 多项式环：
R_q = \mathbb{Z}_q[X]/(X^N + 1) = \mathbb{Z}[X]/(q, X^N + 1)

这是原始多项式环 R 的模 q 版本，其中 q 为整数模数（通常是若干素数的乘积）。两种写法等价：

\begin{array}{c|c} \text{写法} & \text{含义} \\ \hline \mathbb{Z}_q[X]/(X^N + 1) & \mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z} \text{ 是模 } q \text{ 整数环（元素为 } \{0, 1, ..., q-1\}\text{），先对系数取模 } q\text{，再对多项式取模 } (X^N+1) \\ \mathbb{Z}[X]/(q, X^N + 1) & \text{同时模去两个理想：系数模 } q\text{，且满足 } X^N \equiv -1 \end{array}

R_q 中的元素是次数小于 N、系数在 [0, q-1] 范围内的多项式：
a_0 + a_1 X + \cdots + a_{N-1} X^{N-1}, \quad a_i \in \{0, 1, ..., q-1\}

双重取模：

1. 系数层面：所有系数运算都在模 q 下进行（即结果对 q 取余）
2. 多项式层面：满足 X^N \equiv -1，高次项需降次

运算示例（设 N=4, q=17）：

• 系数模 q：15X + 7X = 22X \equiv 5X \pmod{17}
• 乘法：3X^2 \cdot 5X^3 = 15X^5 = 15X \cdot X^4 \equiv -15X \equiv 2X \pmod{(17, X^4+1)}

在 CKKS 中的作用：密文多项式的系数都存储为模 q 的整数，这是实现同态运算的基础。

其中 q 为整数模数，N 为 2 的幂次。

2.1.3 中国剩余定理与环同构

引理 2.1（环同构）：设 N = 2^k 为 2 的幂次，考虑多项式在复数域上的求值，存在以下环同构：

\mathbb{C}[X]/(X^N + 1) \cong \mathbb{C}^N

即系数为复数的分圆多项式环同构于 N 个复数域的直积。同构映射由中国剩余定理（CRT）给出：

\text{CRT}: a(X) \mapsto (a(\zeta), a(\zeta^3), \ldots, a(\zeta^{2N-1})) \in \mathbb{C}^N

这里 \zeta = e^{\pi i/N} 是 2N 次本原单位根。

注：N = 2^k 的条件至关重要。此时：

1. X^N + 1 恰好是第 2N 个分圆多项式 \Phi_{2N}(X)
2. 模 2N 的乘法群 \mathbb{Z}_{2N}^* = \{1, 3, 5, \ldots, 2N-1\} 恰好包含所有奇数
3. 因此 X^N + 1 的根为 \zeta^j（j 取所有奇数）

CRT 证明：下面我们从整数环出发，逐步推广到主理想整环（PID），最后应用到多项式环，完整证明上述同构关系。

第一步：整数环上的 CRT

定理（整数 CRT）：设 n_1, n_2, \ldots, n_k 是两两互素的正整数，令 n = n_1 n_2 \cdots n_k。则：

\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}

证明：

1. 构造同态：定义映射
   \phi: \mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}, \quad a \mapsto (a \bmod n_1, \ldots, a \bmod n_k)

2. 确定核（Kernel）：
   \ker(\phi) = \{a \in \mathbb{Z} : n_i \mid a \text{ 对所有 } i\} = \{a \in \mathbb{Z} : n \mid a\} = n\mathbb{Z}

   （若 n_i 两两互素，则 \text{lcm}(n_1,\ldots,n_k) = n_1\cdots n_k = n）

3. 证明满射（Surjective）：需证：对任意 (a_1, \ldots, a_k)，存在 a 使得 a \equiv a_i \pmod{n_i} 对所有 i。

   令 m_i = n / n_i = \prod_{j \neq i} n_j。由两两互素，\gcd(m_i, n_i) = 1。

   因此存在 m_i^{-1} \bmod n_i（乘法逆元）。构造：
   a = \sum_{i=1}^k a_i \cdot m_i \cdot (m_i^{-1} \bmod n_i)

   验证：当 j \neq i 时，n_j \mid m_i，故 a \equiv a_i \cdot m_i \cdot m_i^{-1} \equiv a_i \pmod{n_i}。

4. 应用同态基本定理：
   \mathbb{Z}/n\mathbb{Z} = \mathbb{Z}/\ker(\phi) \cong \text{Im}(\phi) = \prod_{i=1}^k \mathbb{Z}/n_i\mathbb{Z}

\square

显式同构：

• 正向：a \bmod n \mapsto (a \bmod n_1, \ldots, a \bmod n_k)
• 逆向（CRT重构）：给定 (a_1, \ldots, a_k)，计算
  a = \sum_{i=1}^k a_i \cdot m_i \cdot (m_i^{-1} \bmod n_i) \bmod n

第二步：推广到主理想整环（PID）

在将CRT从整数环推广到多项式环之前，我们需要理解**主理想整环（Principal Ideal Domain, PID）**这一重要代数结构。

定义（主理想整环）：一个整环 R 称为主理想整环，如果 R 的每个理想都是主理想，即对 R 的任意理想 I，存在元素 a \in R 使得：

I = (a) = \{r \cdot a : r \in R\}

PID中的"理想"都可以由单个元素生成，就像整数环中所有偶数构成理想 (2)，由2生成。

为什么整数环 \mathbb{Z} 和多项式环 \mathbb{C}[X] 都是PID？

在PID中，任意两个元素 a, b 都存在最大公因式 \gcd(a,b)，且满足Bézout恒等式：存在 u, v \in R 使得：

u \cdot a + v \cdot b = \gcd(a,b)

这正是CRT证明中构造逆元的关键工具！

定理（PID 上的 CRT）：设 R 是PID，f_1, \ldots, f_k \in R 两两互素（即 \gcd(f_i, f_j) = 1 对 i \neq j），令 f = f_1 f_2 \cdots f_k。则：

R/(f) \cong R/(f_1) \times \cdots \times R/(f_k)

证明：

1. 构造同态：
   \phi: R \to R/(f_1) \times \cdots \times R/(f_k), \quad a \mapsto (a \bmod f_1, \ldots, a \bmod f_k)

2. 确定核：
   \ker(\phi) = \{a \in R : f_i \mid a \text{ 对所有 } i\} = (f)

   因为 f_i 两两互素，所以 \text{lcm}(f_1,\ldots,f_k) = f_1 \cdots f_k = f。

3. 证明满射（关键步骤）：需找到 e_i \in R 使得：

   • e_i \equiv 1 \pmod{f_i}
   • e_i \equiv 0 \pmod{f_j} 对 j \neq i

   令 g_i = f / f_i = \prod_{j \neq i} f_j。因 \gcd(f_i, f_j) = 1，有 \gcd(g_i, f_i) = 1。

   在PID中，由Bézout恒等式，存在 u_i, v_i \in R 使得：
   u_i \cdot g_i + v_i \cdot f_i = 1

   取 e_i = u_i \cdot g_i，则：

   • e_i \equiv 1 \pmod{f_i}（因 e_i = 1 - v_i f_i）
   • e_i \equiv 0 \pmod{f_j} 对 j \neq i（因 f_j \mid g_i）

   对任意 (a_1, \ldots, a_k)，构造 a = \sum_{i=1}^k a_i \cdot e_i，则 a \equiv a_i \pmod{f_i}。

4. 由同态基本定理得证：
   R/(f) \cong \prod_{i=1}^k R/(f_i)

\square

第三步：应用到多项式环 \mathbb{C}[X]

设定：

• R = \mathbb{C}[X] 是PID（因 \mathbb{C} 是域，\mathbb{C}[X] 是Euclidean整环，从而是PID）
• f(X) = X^N + 1
• 在 \mathbb{C} 上完全分解：f(X) = \prod_{j=0}^{N-1} (X - \zeta^{2j+1})，其中 \zeta = e^{2\pi i / 2N} 是 2N 次本原单位根

验证互素条件：对 i \neq j，一次多项式 (X - \zeta^{2i+1}) 和 (X - \zeta^{2j+1})：

• 都是首一的
• 根不同
• \gcd = 1（两两互素）

应用CRT：

\mathbb{C}[X]/(X^N+1) \cong \prod_{j=0}^{N-1} \mathbb{C}[X]/(X - \zeta^{2j+1})

第四步：简化每个分量

定理：\mathbb{C}[X]/(X - \alpha) \cong \mathbb{C}

证明：定义求值映射：
\text{ev}_\alpha: \mathbb{C}[X] \to \mathbb{C}, \quad f(X) \mapsto f(\alpha)

• 满射：对任意 c \in \mathbb{C}，常数多项式 f(X) = c 满足 f(\alpha) = c
• 核：\ker(\text{ev}_\alpha) = \{f \in \mathbb{C}[X] : f(\alpha) = 0\} = (X - \alpha)（因 X-\alpha 不可约）

由同态基本定理：\mathbb{C}[X]/(X-\alpha) \cong \mathbb{C}

\square

在模 (X - \alpha) 下，X \equiv \alpha，所以任何多项式 f(X) 都等价于常数 f(\alpha)。

第五步：综合结果

显式同构：

• 正向（NTT）：f(X) \mapsto (f(\zeta), f(\zeta^3), \ldots, f(\zeta^{2N-1}))
• 逆向（INTT）：(z_0, \ldots, z_{N-1}) \mapsto \sum_{j=0}^{N-1} z_j \cdot e_j(X)，其中 e_j 是Lagrange基多项式(逆向本质上是在做多项式插值)

总结表：

符号说明：

• R = \mathbb{Z}[X]/(X^N + 1) 是前面定义的原始多项式环（次数 < N 的整系数多项式）
• \mathbb{C}[X]/(X^N + 1)：系数为复数的多项式环，模 (X^N + 1)。从代数角度，这与 R \otimes_{\mathbb{Z}} \mathbb{C}（R 与复数域在 \mathbb{Z} 上的张量积）同构
• \mathbb{Z}_{2N}^*：模 2N 的乘法群（与 2N 互素的剩余类），由于 N=2^d，互素的数即为奇数

环同态的性质：映射 \sigma: a(X) \mapsto (a(\zeta), a(\zeta^3), \ldots, a(\zeta^{2N-1})) 保持环运算：

• 加法：\sigma(a + b) = \sigma(a) + \sigma(b)（分量相加）
• 乘法：\sigma(a \cdot b) = \sigma(a) \odot \sigma(b)（分量相乘，Hadamard积）

实例（设 N=4）：

• \zeta = e^{\pi i/4} = \frac{1+i}{\sqrt{2}}（8次本原单位根）
• 根为 \zeta^1, \zeta^3, \zeta^5, \zeta^7（即 \zeta, i\zeta, -\zeta, -i\zeta）
• 多项式 a(X) = 1 + 2X + 3X^2 + 4X^3 映射为向量：

\sigma(a) = (a(\zeta), a(\zeta^3), a(\zeta^5), a(\zeta^7)) \in \mathbb{C}^4

2.2 格密码学基础

2.2.1 格的定义

定义 2.1（格）：设 \mathbf{b}_1, \ldots, \mathbf{b}_n \in \mathbb{R}^m 是 n 个线性无关的向量，由它们生成的格定义为：

\mathcal{L} = \left\{ \sum_{i=1}^n z_i \mathbf{b}_i : z_i \in \mathbb{Z} \right\}

在 CKKS 中，我们使用的是一种特殊的格——理想格（Ideal Lattice），它具有额外的代数结构。

定义 2.2（理想格）：设 R = \mathbb{Z}[X]/(X^N + 1) 为分圆多项式环，I \subseteq R 是 R 的一个理想。通过系数嵌入（coefficient embedding），将多项式 a(X) = a_0 + a_1 X + \cdots + a_{N-1} X^{N-1} \in R 映射为整数向量 (a_0, a_1, \ldots, a_{N-1}) \in \mathbb{Z}^N。

理想格是指由理想 I 的系数嵌入生成的格：

\mathcal{L}(I) = \left\{ (a_0, a_1, \ldots, a_{N-1}) \in \mathbb{Z}^N : a(X) = \sum_{i=0}^{N-1} a_i X^i \in I \right\}

理想格具有以下性质：代数结构（不仅是加法群，还保持多项式乘法结构）、循环性（由于 X^N \equiv -1，格具有特定的对称性）、效率优势（基于理想格的运算可用 NTT 加速，比普通格快 O(N) 倍）。

一般格中的向量是任意的，而理想格中的向量必须对应某个理想中的多项式。例如，若 f(X) \in I，则 X \cdot f(X) \in I 也必须在格中，这给格带来了额外的约束和结构。

2.2.2 环面学习问题（RLWE）

CKKS 的安全性基于 Ring Learning With Errors (RLWE) 问题。

定义 2.3（RLWE 分布）：设安全参数为 N（2 的幂次）和模数 q。定义：

• 多项式环：R = \mathbb{Z}[X]/(X^N + 1)，R_q = \mathbb{Z}_q[X]/(X^N + 1)
• 误差分布：\chi 是 R 上的概率分布（通常为离散高斯分布 D_{R, \sigma}，标准差 \sigma 较小）

多项式环 R 中的元素是 N-1 次整系数多项式 a(X) = a_0 + a_1 X + \cdots + a_{N-1} X^{N-1}。

"\chi 是 R 上的概率分布"意味着：从 R 中按某种规则随机选取多项式。具体采样方式为：

1. 对每个系数位置 i = 0, 1, \ldots, N-1，独立地从一维离散高斯分布 D_{\mathbb{Z}, \sigma} 采样整数 e_i
2. 组合成多项式：e(X) = e_0 + e_1 X + \cdots + e_{N-1} X^{N-1}

RLWE 分布 D_{\text{RLWE}} 由以下方式生成：

• 均匀随机选取 a \leftarrow R_q
• 均匀随机选取密钥 s \leftarrow R
• 从误差分布采样 e \leftarrow \chi
• 输出样本 (a, b) \in R_q^2，其中 b = a \cdot s + e \mod q

定义 2.4（决策性 RLWE 问题）：给定 (a, b) \in R_q^2，区分以下两种情况：

• 情况 1（RLWE 样本）：(a, b) 按 RLWE 分布生成，即 a \leftarrow R_q 均匀随机，b = a \cdot s + e \mod q
• 情况 2（均匀随机）：a, b 均独立均匀随机从 R_q 中选取

攻击者的目标是判断给定的 (a, b) 属于哪种情况。

定义 2.5（最短向量问题）：设 \mathcal{L} 是一个格，定义：

• 最短向量问题（SVP）：找到格中长度最短的非零向量，即找到 \mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\} 使得 \|\mathbf{v}\| 最小
• 近似最短向量问题（Approximate SVP，\gamma-SVP）：找到非零向量 \mathbf{v} \in \mathcal{L}，使得 \|\mathbf{v}\| \leq \gamma \cdot \lambda_1(\mathcal{L})，其中 \lambda_1(\mathcal{L}) 是最短向量的长度，\gamma \geq 1 是近似因子

对于理想格，相应地定义 Ideal-SVP 和 \gamma-Ideal-SVP。

定理 2.1（安全性归约）：对于适当选择的参数，如果存在一个算法能在多项式时间内解决 RLWE 问题，那么存在一个算法能在多项式时间内解决 \gamma-Ideal-SVP（对于某个近似因子 \gamma）。即：

\text{RLWE} \leq_P \gamma\text{-Ideal-SVP}

这意味着 RLWE 问题的困难性至少与 Ideal-SVP 相当。

证明：此归约证明涉及复杂的格归约技术，超出本文范围，详见相关密码学文献。

\square

2.3 复数编码理论

CKKS 的核心是将复数向量编码为多项式，这是实现 SIMD 风格并行计算的关键。

2.3.1 规范嵌入

定义 2.6（规范嵌入）：定义映射 \sigma: R \to \mathbb{C}^N 为：

\sigma: a(X) \mapsto (a(\zeta), a(\zeta^3), \ldots, a(\zeta^{2N-1}))

其中 \zeta^j（j 为奇数）是 X^N + 1 的所有根。

注意：规范嵌入 vs. CKKS 编码

规范嵌入 \sigma: R \to \mathbb{C}^N 的方向是多项式 → 复数向量。

但 CKKS 的编码（Encode）使用的是 \sigma^{-1}，方向是复数向量 → 多项式：
\text{Encode}: \mathbf{z} \in \mathbb{C}^{N/2} \xrightarrow{\text{扩展+缩放}} \mathbf{z}_{\text{full}} \in \mathbb{C}^N \xrightarrow{\sigma^{-1}} m(X) \in R

因此：

• 规范嵌入 \sigma：用于理论分析和解码（Decode）
• CKKS 编码 \sigma^{-1}：用于加密前的数据准备

性质 2.1：

• \sigma 是环同态（保持加法和乘法）
• 对于 a, b \in R：\sigma(a \cdot b) = \sigma(a) \odot \sigma(b)（分量乘法）

2.3.2 解码空间

定义 明文空间 为：

\mathcal{S} = \mathbb{C}^{N/2}

注意：由于 a(X) \in \mathbb{R}[X]/(X^N+1) 时 a(\zeta^{2N-j}) = \overline{a(\zeta^j)}，所以我们只有 N/2 个复数槽位。

CKKS 方案概览

3.1 核心思想

CKKS 方案的核心思想可以用以下图示表示：

复数向量 z ∈ ℂ^(N/2)      【待加密数据】
        ↓ 编码 (σ⁻¹)
多项式 m(X) ∈ R           【SIMD: N/2个槽位打包到一个多项式】
        ↓ 加密
密文 ct = (c₀, c₁) ∈ R_q² 【含噪声的加密容器】
        ↓ 同态运算 (⊕, ⊗)
结果密文 ct'               【密文上完成批量计算】
        ↓ 解密
近似多项式 m̃(X)            【含误差，可控】
        ↓ 解码 (σ)
结果向量 z' ∈ ℂ^(N/2)     【z'_j ≈ f(z_j)】

1. 编码 ≠ 加密：编码是确定性的插值转换（无密钥）；加密才是带噪声的同态加密
2. 为什么编码？ CKKS 只能加密多项式，不能直接加密复数向量
3. SIMD 优势：一次加密处理 N/2 个复数，同态运算自动并行作用于所有槽位
4. 近似性：解密后是近似值，误差可通过增大缩放因子 \Delta 控制

3.2 参数设置

CKKS 方案由以下参数完全确定：

3.2.1 安全性级别

根据同态加密标准（Homomorphic Encryption Standard）：

3.2.2 误差分布

通常使用离散高斯分布 D_{\mathbb{Z}^N, \sigma}：

• 标准差 \sigma \approx 3.2
• 密钥分布：稀疏分布（HWHM = Hamming Weight Half Minimum）

3.2.3 参数选择原则

安全性约束：

• N 和 Q 的选择必须满足安全性要求（见上表）
• 更大的 Q 允许更深的计算，但需要更大的 N 来保持安全性

精度与效率权衡：

性能基准（N = 2^{14} = 16384，128-bit 安全性）：

3.3 关键特性

近似算术

CKKS 是一种 近似同态加密（Approximate Homomorphic Encryption）方案。解密结果包含小误差：

\text{Decrypt}(\text{Encrypt}(m)) \approx m

误差满足：
\|m - \tilde{m}\|_\infty \leq \epsilon

其中 \epsilon 可通过参数选择控制在可接受范围内。

SIMD 批处理

单次加密可处理 N/2 个复数，支持：

• 分量加法：(a_1, \ldots, a_n) + (b_1, \ldots, b_n) = (a_1+b_1, \ldots, a_n+b_n)
• 分量乘法：(a_1, \ldots, a_n) \odot (b_1, \ldots, b_n) = (a_1 b_1, \ldots, a_n b_n)

核心构造

4.1 密钥生成

4.1.1 密钥生成算法

符号说明：

• \lambda：安全参数（如 128-bit、256-bit 安全级别）
• \chi_{\text{key}}：密钥分布，通常采用 HWHM（Hamming Weight Half Minimum）分布，即从 \{0, \pm 1\}^N 中选取固定汉明重量（非零元数量）的稀疏多项式
• Q = q_L \cdot q_{L-1} \cdots q_0：顶层模数（所有层级模数的乘积）

CKKS.KeyGen(1^\lambda):

1. 私钥（Secret Key）：
   sk = s \leftarrow \chi_{\text{key}}

   s 是小系数多项式（稀疏且系数在 \{-1, 0, 1\}），只有持有 s 才能正确解密。

2. 公共密钥（Public Key）：
   a \leftarrow R_Q \text{ (均匀随机)}
   e \leftarrow \chi_{\text{err}} \text{ (误差分布，小系数)}
   b = -a \cdot s + e \in R_Q, \quad pk = (b, a) \in R_Q^2

   设计原理：这实际上是 RLWE 样本 (a, b)，其中 b = -a \cdot s + e。这种构造使得：
   b + a \cdot s = e
   右侧是小误差（不是精确为 0，但很小），这是解密的关键等式。

4.1.2 密钥性质

4.2 编码（Encoding）

编码是将复数向量转换为多项式的过程。

4.2.1 编码算法

输入：复数向量 \mathbf{z} = (z_0, z_1, \ldots, z_{N/2-1}) \in \mathbb{C}^{N/2}

输出：多项式 m(X) \in R

算法步骤：

1. 扩展为完整向量：由于共轭对称性，构造
   \mathbf{z}_{\text{full}} = (z_0, z_1, \ldots, z_{N/2-1}, \overline{z_{N/2-1}}, \ldots, \overline{z_1}, \overline{z_0}) \in \mathbb{C}^N

2. 缩放：乘以缩放因子 \Delta（通常为 2^p，如 \Delta = 2^{30}）
   \mathbf{v} = \Delta \cdot \mathbf{z}_{\text{full}}

   为什么需要缩放？ 后续要进行舍入，缩放可以减小舍入带来的精度损失。\Delta 越大，精度越高，但可计算的乘法深度越小。

3. 逆规范嵌入（插值）：求解多项式 m'(X) \in \mathbb{C}[X] 使得
   m'(\zeta^{2j+1}) = v_j, \quad j = 0, 1, \ldots, N-1

   这等价于计算 m'(X) = \sigma^{-1}(\mathbf{v})，其中 \sigma^{-1} 是规范嵌入的逆映射（可通过 Lagrange 插值实现）。

4. 舍入到整数系数：由于明文空间是 R = \mathbb{Z}[X]/(X^N+1)（整数系数多项式），需要将 m'(X) 的系数舍入到最近整数：
   m(X) = \left\lfloor m'(X) \right\rceil = \left\lfloor \sigma^{-1}(\Delta \cdot \mathbf{z}_{\text{full}}) \right\rceil \in R

4.2.2 编码的数学表示

定理 4.1（编码的正确性）：设 \mathbf{z} \in \mathbb{C}^{N/2}，m = \text{Encode}(\mathbf{z}) 是编码得到的多项式。对 m 进行解码（规范嵌入并除以 \Delta）得到：

\frac{\sigma(m)}{\Delta} = \mathbf{z}_{\text{full}} + \frac{\mathbf{\epsilon}_{\text{round}}}{\Delta}

其中舍入误差满足 \|\mathbf{\epsilon}_{\text{round}}\|_\infty \leq \frac{1}{2}。因此解码后的相对误差不超过 \frac{1}{2\Delta}。

证明：由编码算法，m(X) = \lfloor \sigma^{-1}(\Delta \cdot \mathbf{z}_{\text{full}}) \rceil。设 m'(X) = \sigma^{-1}(\Delta \cdot \mathbf{z}_{\text{full}})，则 m = m' + \epsilon_{\text{round}}，其中 \|\epsilon_{\text{round}}\|_\infty \leq \frac{1}{2}。因此 \sigma(m) = \Delta \cdot \mathbf{z}_{\text{full}} + \sigma(\epsilon_{\text{round}})，除以 \Delta 即得结论。

\square

4.2.3 编码示例

设 N = 4（即 2 个复数槽），要编码 \mathbf{z} = (1+2i, 3-4i)：

1. 计算单位根：\zeta = e^{\pi i/4}
2. 扩展向量：\mathbf{z}_{\text{full}} = (1+2i, 3-4i, 3+4i, 1-2i)
3. 求解插值多项式（设 \Delta = 100）
4. 得到 m(X) \approx 100 \cdot \sigma^{-1}(\mathbf{z}_{\text{full}})

4.3 解码（Decoding）

解码是编码的逆过程，从多项式还原为复数向量。

算法：

1. 规范嵌入（求值）：计算多项式 m(X) 在所有 N 个根处的取值
   \mathbf{w} = \sigma(m) = (m(\zeta), m(\zeta^3), \ldots, m(\zeta^{2N-1})) \in \mathbb{C}^N

2. 去除缩放：除以缩放因子 \Delta
   \mathbf{w}' = \mathbf{w} / \Delta

   此时 \mathbf{w}' \approx \mathbf{z}_{\text{full}}，即编码时构造的完整向量（含共轭对称部分）。

3. 提取有效分量：由于共轭对称性 w'_{N-1-j} = \overline{w'_j}，只需取前 N/2 个分量：
   \mathbf{z} = (w'_0, w'_1, \ldots, w'_{N/2-1}) \in \mathbb{C}^{N/2}

误差分析：

解码结果包含两部分误差：

• 舍入误差 \mathbf{\epsilon}_{\text{round}}：编码时系数舍入引入（与 \Delta 成反比）
• 加密噪声 \mathbf{\epsilon}_{\text{noise}}：同态加密和解密过程中的噪声累积

\mathbf{z}_{\text{decoded}} = \mathbf{z}_{\text{original}} + \underbrace{\frac{\mathbf{\epsilon}_{\text{round}}}{\Delta}}_{\text{编码误差}} + \underbrace{\frac{\mathbf{\epsilon}_{\text{noise}}}{\Delta}}_{\text{加密噪声}}

选择足够大的 \Delta 可使两项误差都任意小。

4.4 加密

4.4.1 加密算法

设计目标：构造密文 (c_0, c_1) 使得 c_0 + c_1 \cdot s \approx m \pmod{Q}，即解密时能得到明文加上小噪声。

CKKS.Encrypt(pk = (b, a), m \in R):

1. 采样随机掩码：

   • v \leftarrow \chi_{\text{enc}}：加密随机数（类似一次性密钥）
   • e_0, e_1 \leftarrow \chi_{\text{err}}：加密噪声（小系数多项式）

2. 构造密文：利用公钥 "包装" 明文
   c_0 = b \cdot v + e_0 + m \pmod{Q}
   c_1 = a \cdot v + e_1 \pmod{Q}

3. 输出：ct = (c_0, c_1) \in R_Q^2

密文本质上是 RLWE 样本的"变形"。v 是"盲化因子"，确保同一明文每次加密结果不同（语义安全）；e_0, e_1 是新加入的加密噪声。

4.4.2 安全性基础

加密的安全性基于 RLWE 假设（定义 2.3）：区分 (a, a \cdot s + e) 与 (a, u)（u 均匀随机）是困难的。

密文的安全性分析：

密文 (c_0, c_1) 的第二分量 c_1 = a \cdot v + e_1 具有 RLWE 样本的形式（其中 v 作为"临时密钥"）。由 RLWE 假设，c_1 与均匀随机不可区分。

第一分量 c_0 = b \cdot v + e_0 + m = (-a \cdot s + e) \cdot v + e_0 + m。在 v 的随机性掩盖下，c_0 也与随机元素不可区分（即使给定 c_1）。

因此密文 (c_0, c_1) 与均匀随机对不可区分，满足 IND-CPA 安全。

4.5 解密

4.5.1 解密算法

CKKS.Decrypt(sk = s, ct = (c_0, c_1)):

\tilde{m} = c_0 + c_1 \cdot s \pmod{q}

其中 q 是当前层级的模数（初始时 q = Q，经过重缩放后 q 会减小）。

为什么是近似？
c_0 + c_1 \cdot s = m + e_{\text{total}}
结果不是精确的 m，而是 m 加上噪声。CKKS 是近似加密，解密结果是近似的。

4.5.2 解密原理

核心等式：对于合法生成的公钥 (b, a) 和私钥 s，密钥生成保证了：
b + a \cdot s = e \pmod{Q}
其中 e 是小噪声（系数绝对值通常 < 6\sigma）。这个等式是解密的基础。

为什么加密构造能解密？ 对密文 ct = (c_0, c_1) 计算 c_0 + c_1 \cdot s：

解密误差：
e_{\text{enc}} = e \cdot v + e_0 + e_1 \cdot s

虽然看起来复杂，但 e, v, e_0, e_1, s 都是小系数多项式，乘积和求和后仍保持较小（相对于模数 Q）。

4.5.3 解密分析与误差来源

定理 4.2（解密近似性）：设 ct 加密明文 m 且当前层级模数为 q，则：

\text{Decrypt}(sk, ct) = m + e_{\text{total}} \pmod{q}

总误差 e_{\text{total}} 包含三部分：

只要 \|e_{\text{total}}\|_\infty < q/(2\Delta)，解码后就能得到正确的明文（因为 \sigma^{-1} 涉及除以 \Delta）。这就是 CKKS 需要重缩放的原因：控制噪声增长，保持噪声在可接受范围内。

同态运算

5.1 同态加法

5.1.1 加法算法

CKKS.Add(ct_1, ct_2) —— 同态加法算法

给定加密 m_1 的密文 ct_1 = (c_0^{(1)}, c_1^{(1)}) 和加密 m_2 的密文 ct_2 = (c_0^{(2)}, c_1^{(2)})，计算加密 m_1 + m_2 的新密文。

输出：ct_{\text{add}} = (c_0^{\text{add}}, c_1^{\text{add}})

运算：对应分量相加
c_0^{\text{add}} = c_0^{(1)} + c_0^{(2)} \pmod{q}
c_1^{\text{add}} = c_1^{(1)} + c_1^{(2)} \pmod{q}

5.1.2 正确性

定理 5.1（加法正确性）：若 ct_1 加密 m_1，ct_2 加密 m_2，则 ct_{\text{add}} 加密 m_1 + m_2。

证明：设 ct_i 解密得到 \tilde{m}_i = c_0^{(i)} + c_1^{(i)} \cdot s = m_i + e_i（i=1,2），其中 m_i 是明文多项式，e_i 是噪声。

计算 ct_{\text{add}} 的解密：

因此 ct_{\text{add}} 解密后得到 (m_1 + m_2) + (e_1 + e_2)，即明文和 m_1 + m_2 加上累积噪声。

\square

5.1.3 误差增长

\|e_{\text{add}}\| \leq \|e_1\| + \|e_2\|

加法使误差线性增长。

5.2 同态乘法

5.2.1 朴素乘法

对于密文 ct_1 = (c_0^{(1)}, c_1^{(1)}) 和 ct_2 = (c_0^{(2)}, c_1^{(2)})，计算：

d_0 = c_0^{(1)} \cdot c_0^{(2)}
d_1 = c_0^{(1)} \cdot c_1^{(2)} + c_1^{(1)} \cdot c_0^{(2)}
d_2 = c_1^{(1)} \cdot c_1^{(2)}

则有：

(c_0^{(1)} + c_1^{(1)} s)(c_0^{(2)} + c_1^{(2)} s) = d_0 + d_1 s + d_2 s^2

5.2.2 重线性化（Relinearization）

问题：乘法后密文变为三元组 (d_0, d_1, d_2)，解密需要 s^2：
d_0 + d_1 \cdot s + d_2 \cdot s^2
这会导致密文维度持续增长，需要转换回标准形式 (c_0', c_1')。

核心思想：

乘法后解密需要 s^2，但我们希望保持只用 s 就能解密（否则密钥会越来越大）。

evk 的作用就是**"代替" s^2 的工作**——它里面偷偷包含了 s^2 的信息，通过数学技巧可以把 d_2 \cdot s^2 转换成只需要 s 的形式。

评估密钥 evk 的组成：

evk = (b', a') 是在密钥生成阶段生成的辅助密钥，其中：

• a' \leftarrow R_{Q^2}：均匀随机选取的多项式
• e' \leftarrow \chi_{\text{err}}：小噪声
• b' = -a' \cdot s + e' + Q \cdot s^2 \in R_{Q^2}

计算 b' + a' \cdot s：

b' + a' \cdot s = e' + Q \cdot s^2 \approx Q \cdot s^2

右边约等于 Q \cdot s^2（e' 很小可忽略）。这意味着 evk 把 s^2 "放大"了 Q 倍存储，后续可以通过除以 Q 把 s^2 提取出来。

CKKS.Relinearize((d_0, d_1, d_2), evk = (b', a')):

1. 将 d_2 从模 q 提升到模 Q^2（零填充或适当扩展）
2. 计算（在模 Q^2 下进行，然后舍入回模 q）：
   c_0' = d_0 + \left\lfloor \frac{d_2 \cdot b'}{Q} \right\rceil \pmod{q}
   c_1' = d_1 + \left\lfloor \frac{d_2 \cdot a'}{Q} \right\rceil \pmod{q}

正确性验证：

完美！新的 (c_0', c_1') 解密后得到与原三元组相同的结果，但只需要 s（不需要 s^2）。

为什么需要 Q \cdot s^2 和模 Q^2？

这种构造叫做 "密钥切换"（Key Switching） 技术。

重线性化的误差分析：

上述推导中使用了近似 b' + a' \cdot s \approx Q \cdot s^2，实际等式为 b' + a' \cdot s = Q \cdot s^2 + e'（其中 e' 是 evk 的生成噪声）。

详细推导：

计算重线性化后的第一分量 c_0' 对解密的贡献：

类似地，第二分量 c_1' 对解密的贡献（乘以 s 后）：

\frac{d_2 \cdot a'}{Q} \cdot s = \frac{d_2 \cdot a' \cdot s}{Q}

两者相加时，\frac{-d_2 \cdot a' \cdot s}{Q} 和 \frac{d_2 \cdot a' \cdot s}{Q} 相互抵消，剩下：

d_2 \cdot s^2 + \frac{d_2 \cdot e'}{Q}

因此重线性化引入的误差为：
e_{\text{rk}} = \left\lfloor \frac{d_2 \cdot e'}{Q} \right\rceil

（加上舍入符号表示实际计算中的整数舍入）。由于除以了 Q，e_{\text{rk}} 通常比 e' 小得多，但会贡献到总误差中。

5.2.3 乘法算法

CKKS.Mult(ct_1, ct_2, evk):

1. 计算 (d_0, d_1, d_2) 如上
2. ct_{\text{mult}} = \text{Relinearize}((d_0, d_1, d_2), evk)
3. 返回 ct_{\text{mult}}

5.2.4 正确性与误差分析

定理 5.2（乘法正确性）：若 ct_1 解密为 \tilde{m}_1 = m_1 + e_1，ct_2 解密为 \tilde{m}_2 = m_2 + e_2，则 ct_{\text{mult}} 解密为 m_1 \cdot m_2 + e_{\text{mult}}。

证明：由解密定义，c_0^{(i)} + c_1^{(i)} \cdot s = \tilde{m}_i = m_i + e_i（i=1,2）。朴素乘法后的三元组满足：
d_0 + d_1 s + d_2 s^2 = (c_0^{(1)} + c_1^{(1)} s)(c_0^{(2)} + c_1^{(2)} s) = \tilde{m}_1 \cdot \tilde{m}_2 = (m_1 + e_1)(m_2 + e_2)

展开得：
m_1 m_2 + \underbrace{m_1 e_2 + m_2 e_1 + e_1 e_2}_{\text{乘法噪声}}

重线性化将三元组转换为二元组 (c_0', c_1')，保持解密值近似不变（引入额外小的重线性化误差 e_{\text{rk}}）。因此：
c_0' + c_1' \cdot s \approx m_1 m_2 + e_{\text{mult}}

其中 e_{\text{mult}} = m_1 e_2 + m_2 e_1 + e_1 e_2 + e_{\text{rk}}。

\square

误差增长：
\|e_{\text{mult}}\| \approx N \cdot \|e_1\| \cdot \|e_2\|

（系数 N 来自多项式乘法的范数增长）。误差呈平方级增长，这是限制乘法深度的主要原因。

5.3 明文-密文运算

当其中一个操作数是明文（未加密的多项式）时，运算更高效：

明文-密文乘法：
\text{Mult}_{\text{plain}}(ct, m) = (c_0 \cdot m, c_1 \cdot m)

正确性验证：
(c_0 \cdot m) + (c_1 \cdot m) \cdot s = (c_0 + c_1 \cdot s) \cdot m = \tilde{m}_{\text{ct}} \cdot m

解密后得到明文乘积，且噪声只被乘了 m（线性增长，而非密文乘法的平方增长）。

明文-密文加法：
\text{Add}_{\text{plain}}(ct, m) = (c_0 + m, c_1)

正确性验证：
(c_0 + m) + c_1 \cdot s = (c_0 + c_1 \cdot s) + m = \tilde{m}_{\text{ct}} + m

解密后得到明文和，噪声不增加（仍是原密文的噪声）。

5.4 旋转（Rotation）

注意：旋转是可选的高级操作，不在基础加解密流程中。它用于在 SIMD 槽位之间移动数据，实现如向量内积、矩阵运算等复杂操作。

5.4.1 动机与基本概念

CKKS 使用 SIMD 技术，单次加密可处理 N/2 个复数。考虑计算两个加密向量的内积 \langle \mathbf{a}, \mathbf{b} \rangle = \sum_{i=0}^{n-1} a_i b_i：分量乘法可计算 (a_0 b_0, a_1 b_1, \ldots, a_{n-1} b_{n-1})，但如何将所有分量求和？

解决方案：通过旋转实现"循环累加"。设 ct_{ab} 加密分量乘积 (a_0 b_0, a_1 b_1, a_2 b_2, a_3 b_3)：

第0步: ct_ab = (a0b0, a1b1, a2b2, a3b3)
第1步: 旋转后相加 → (a0b0+a1b1, a1b1+a2b2, a2b2+a3b3, a3b3+a0b0)
第2步: 再旋转后相加 → (a0b0+a1b1+a2b2+a3b3, ...) ← 每个槽位都是内积！

旋转的核心价值在于：在密文上实现数据重排，从而完成复杂的向量运算。

5.4.2 自同构映射与旋转密钥

自同构映射

定义 5.1（自同构映射）：对于奇数 k \in \mathbb{Z}_{2N}^*（即 k 与 2N 互素），定义映射：

\tau_k: R \to R, \quad a(X) \mapsto a(X^k) \pmod{X^N + 1}

引理 5.1（自同构的性质）：\tau_k 是环自同构，即对任意 a, b \in R：

• \tau_k(a + b) = \tau_k(a) + \tau_k(b)
• \tau_k(a \cdot b) = \tau_k(a) \cdot \tau_k(b)

证明：由多项式运算的线性性和乘法对 X^k 替换的保持性直接得出。

\square

命题 5.1（自同构实现槽位置换）：设 m(X) 是明文多项式，定义槽位索引 i \in \{0, 1, \ldots, N-1\} 对应根 \zeta^{2i+1}，即第 i 个槽位存储 m(\zeta^{2i+1})。则自同构 \tau_k 作用后，槽位 i 的值移动到槽位 j，其中 j 满足：

(2i+1)k \equiv 2j+1 \pmod{2N}

证明：计算 \tau_k(m)(\zeta^{2i+1}) = m(\zeta^{(2i+1)k \mod 2N})。由于 k 是奇数，(2i+1)k 仍是奇数，故存在 j 使得 (2i+1)k \equiv 2j+1 \pmod{2N}。

\square

为什么 k 必须满足特定条件？

例 5.1：设 N=4，取 k=3。计算 (2i+1) \cdot 3 \mod 8：

• i=0: 1 \times 3 = 3 \to j=1
• i=1: 3 \times 3 = 9 \equiv 1 \to j=0
• i=2: 5 \times 3 = 15 \equiv 7 \to j=3
• i=3: 7 \times 3 = 21 \equiv 5 \to j=2

因此 \tau_3 实现置换：槽位 (z_0, z_1, z_2, z_3) \to (z_1, z_0, z_3, z_2)。

旋转密钥与算法

问题：直接对密文应用 \tau_k 得到 (\tau_k(c_0), \tau_k(c_1))，但解密需要 \tau_k(s) 而非 s：

\tau_k(c_0) + \tau_k(c_1) \cdot s \neq \tau_k(c_0 + c_1 \cdot s) = \tau_k(m + e)

解决方案：通过旋转密钥实现密钥切换。

定义 5.2（旋转密钥）：对于自同构参数 k，旋转密钥 rk_k = (b_k, a_k) 定义为：

b_k = -a_k \cdot s + e_k + P \cdot \tau_k(s) \in R_{PQ}

其中 a_k \leftarrow R_{PQ} 均匀随机，e_k \leftarrow \chi_{\text{err}}，P 是特殊模数。

性质：b_k + a_k \cdot s = e_k + P \cdot \tau_k(s) \approx P \cdot \tau_k(s)。即 rk_k 将 \tau_k(s) "放大" P 倍存储。

安全性：旋转密钥可公开，安全性基于 RLWE 假设。(b_k, a_k) 与均匀随机对不可区分。

算法 5.1（旋转）：

输入：密文 ct = (c_0, c_1) \in R_q^2，自同构参数 k，旋转密钥 rk_k = (b_k, a_k)

输出：旋转后的密文 ct' = (c_0', c_1')

1. 计算自同构：\tilde{c}_0 = \tau_k(c_0)，\tilde{c}_1 = \tau_k(c_1)
2. 模数提升：将 \tilde{c}_1 从模 q 零扩展到模 PQ
3. 密钥切换：
   c_0' = \tilde{c}_0 + \left\lfloor \frac{\tilde{c}_1 \cdot b_k}{P} \right\rceil \pmod{q}, \quad c_1' = \left\lfloor \frac{\tilde{c}_1 \cdot a_k}{P} \right\rceil \pmod{q}
4. 返回 (c_0', c_1')

定理 5.3（旋转正确性）：设 ct 加密明文 m（带噪声 e），则旋转后的密文 ct' 解密得到 \tau_k(m) + \tau_k(e) + e_{\text{rot}}，其中旋转噪声 e_{\text{rot}} = \lfloor \tilde{c}_1 \cdot e_k / P \rceil。

证明：

其中 e_{\text{round}} 是舍入误差，可忽略。

\square

旋转步长与自同构参数的映射

定义 5.3（旋转步长）：旋转步长 r 指槽位向右移动的位数，即 r=1 表示 (z_0, z_1, \ldots) \to (z_{n-1}, z_0, \ldots)。

命题 5.2（旋转步长与自同构参数）：旋转步长 r 对应的自同构参数 k 满足：

k \equiv 5^r \pmod{2N}

映射表（N=16，n=8）：

注：由于循环性质，只需 n-1 个不同的旋转密钥。

5.4.3 旋转算法与应用

向量内积算法

算法 5.2（向量内积 - 对数算法）：

输入：加密向量 ct_a，ct_b

输出：加密 \langle \mathbf{a}, \mathbf{b} \rangle 的密文（每个槽位都包含结果）

1. ct \leftarrow ct_a \cdot ct_b
2. 对于 j = 0, 1, \ldots, \log_2(n) - 1：
   • ct_{\text{rot}} \leftarrow \text{Rotate}(ct, 2^j)
   • ct \leftarrow ct + ct_{\text{rot}}
3. 返回 ct

原理：二分归约思想。每轮将相邻的 2^j 个元素配对相加，经过 \log_2(n) 轮后每个槽位都包含总和。

例 5.2（n=8）：

初始:     (p0, p1, p2, p3, p4, p5, p6, p7)
旋转1步:  (p7, p0, p1, p2, p3, p4, p5, p6)
相加:     (p0+p7, p1+p0, p2+p1, p3+p2, p4+p3, p5+p4, p6+p5, p7+p6)
旋转2步:  (p6+p5, p7+p6, p0+p7, p1+p0, ...)
相加:     (p0+p1+p6+p7, ...)
旋转4步:  (p4+p5+p6+p7, ...)
相加:     (p0+p1+...+p7, ...) ← 每个槽位都是总和

复杂度：朴素算法需 n-1 次旋转，对数算法仅需 \log_2(n) 次。对于 n=1024，从 1023 次降至 10 次。

复杂度分析与优化

复杂度：

优化技巧：

1. Baby-Step Giant-Step：用 O(\sqrt{n}) 个密钥支持所有旋转。设 m = \lceil \sqrt{n} \rceil，预生成 m 个小步密钥（旋转 1, 2, 4, \ldots 步）和 m 个大步密钥（旋转 m, 2m, \ldots 步），任意旋转 r = q \cdot m + rem 可分解为小步+大步。

2. 惰性旋转：连续旋转 r_1 步和 r_2 步可合并为一次旋转 (r_1 + r_2) \mod n 步，减少噪声累积。

与重线性化的统一视角

两者都是密钥切换技术的应用：通过预先生成的辅助密钥，把需要"新密钥"的项转换为只需要"原密钥"的形式。

重缩放与模数切换

6.1 重缩放（Rescaling）

6.1.1 问题背景

回顾 4.2 编码 中引入的缩放因子 \Delta：编码时将明文乘以 \Delta 以控制精度。因此，加密的明文实际上是 \Delta \cdot m。

乘法后，缩放因子平方：

\text{Mult}(\Delta \cdot m_1, \Delta \cdot m_2) \approx \Delta^2 \cdot m_1 m_2

6.1.2 重缩放操作

CKKS.Rescale(ct, \ell):

输入：层级 \ell 的密文 ct \in R_{q_\ell}^2
输出：层级 \ell-1 的密文 ct' \in R_{q_{\ell-1}}^2

1. 计算 ct' = \left\lfloor \frac{q_{\ell-1}}{q_\ell} \cdot ct \right\rceil \pmod{q_{\ell-1}}
2. 输出 ct'

6.1.3 重缩放的数学原理

设 q_\ell = q_{\ell-1} \cdot q^*，则：

\text{Rescale}(ct) = \frac{1}{q^*} ct + \epsilon

若 ct 加密 \Delta^2 \cdot m，重缩放后：

\approx \frac{\Delta^2}{q^*} \cdot m = \Delta \cdot m \quad \text{(当 } q^* \approx \Delta\text{)}

定理 6.1（重缩放正确性）：若 q^* \approx \Delta，重缩放恢复正确的缩放因子。

证明：设 ct 加密 \Delta^2 \cdot m，即 c_0 + c_1 \cdot s = \Delta^2 \cdot m + e。重缩放操作计算 ct' = \lfloor ct / q^* \rceil，因此：

c_0' + c_1' \cdot s \approx \frac{\Delta^2}{q^*} \cdot m + \frac{e}{q^*} \approx \Delta \cdot m + e'

其中 e' = e / q^* 是新的噪声。由于 q^* \approx \Delta，缩放因子恢复为 \Delta。

\square

6.2 模数链设计

6.2.1 层级结构

设总共有 L+1 个层级，模数链为：

Q_L \to Q_{L-1} \to \cdots \to Q_0

其中：
Q_\ell = q_\ell \cdot q_{\ell-1} \cdots q_0 = \prod_{i=0}^{\ell} q_i

通常选择 q_i \approx \Delta（如 \Delta = 2^{30}，q_i = 2^{30}）。

6.2.2 层级变化

6.2.3 模数消耗与乘法深度

定义 6.1（乘法深度）：设 f 是一个算术电路。f 的乘法深度定义为从输入到输出的任意有向路径上乘法门的最大数量，记为 \text{depth}(f)。

例 6.1（乘法深度）：

• f(x,y) = x \cdot y：\text{depth}(f) = 1
• f(x,y,z) = x \cdot y \cdot z：分解为 t = x \cdot y，f = t \cdot z，故 \text{depth}(f) = 2
• f(x) = a_0 + a_1 x + a_2 x^2（Horner 形式 a_0 + x(a_1 + a_2 x)）：\text{depth}(f) = 2

引理 6.1（模数消耗）：设密文初始层级为 \ell，乘法深度为 d。若 d > \ell，则计算无法完成。

证明：设密文 ct 在层级 \ell，缩放因子为 \Delta。

乘法操作：ct_1 \cdot ct_2 \to ct_{\text{new}}，缩放因子变为 \Delta^2。

重缩放操作：\text{Rescale}(ct_{\text{new}}) = \lfloor ct_{\text{new}} / q_\ell \rceil，缩放因子恢复为 \Delta，层级降为 \ell - 1。

因此，每次乘法+重缩放消耗一个模数因子。d 次乘法需要 d 个模数因子。若 d > \ell，模数耗尽，计算失败。

\square

推论 6.1（模数链长度要求）：计算乘法深度为 d 的电路，需要模数链长度 L \geq d。

6.3 自举（Bootstrapping）

6.3.1 自举原理

问题陈述

设定：设模数链为 Q_L > Q_{L-1} > \cdots > Q_0，其中 Q_\ell = \prod_{i=0}^{\ell} q_i。

问题：给定层级 0 的密文 ct \in R_{Q_0}^2，如何恢复到更高层级以继续计算？

定义 6.2（自举）：自举的作用是把层级 0 的密文"刷新"成顶层 L 的密文，明文内容不变，但噪声被重置，模数链恢复，可以继续计算。

6.3.2 CKKS 自举构造

输入：ct = (c_0, c_1) \in R_{Q_0}^2，满足 c_0 + c_1 \cdot s = m + e \pmod{Q_0}

输出：ct' = (c_0', c_1') \in R_{Q_L}^2，满足 c_0' + c_1' \cdot s' = m + e' \pmod{Q_L}

第一步：模数提升

将密文从模 Q_0 提升到模 Q_L。系数不变，只是模数扩大：

ct^{(1)} = (c_0 \bmod Q_L,\; c_1 \bmod Q_L) \in R_{Q_L}^2

此时 ct^{(1)} 满足：

c_0 + c_1 \cdot s = m + e \pmod{Q_0}

但模数已变为 Q_L，为后续计算提供了空间。

第二步：同态解密

模数提升后，密文 ct^{(1)} = (c_0, c_1) 满足：

c_0 + c_1 \cdot s = m + e \pmod{Q_0}

目标是计算 m + e 然后用新公钥重新加密。但服务器没有私钥 s，无法直接计算 c_0 + c_1 \cdot s。

解决方法：客户端生成新的密钥对 (s', pk')，其中 s' 是新私钥，pk' 是新公钥。然后构造自举密钥 bsk = \text{Enc}_{pk'}(s)，即用新公钥加密原私钥。服务器利用CKKS的同态性质，在密文上"模拟"解密过程。

解密函数 \text{Dec}_s(ct) = c_0 + c_1 \cdot s 是关于 s 的一次多项式。服务器有：

• 密文分量 c_0, c_1（这些是模 Q_L 下的多项式系数，可视为明文）
• 加密的私钥 bsk = \text{Enc}_{pk'}(s)

利用同态数乘（明文乘密文）和同态加法：
\text{Enc}_{pk'}(c_0) + c_1 \cdot bsk = \text{Enc}_{pk'}(c_0) + \text{Enc}_{pk'}(c_1 \cdot s) = \text{Enc}_{pk'}(c_0 + c_1 \cdot s)

这里 c_0, c_1 作为明文系数与密文进行运算。

第三步：多项式近似

上述计算得到 \text{Enc}_{pk'}(c_0 + c_1 \cdot s)，但 c_0 + c_1 \cdot s 可能很大（因为模数提升到了 Q_L），我们需要的是 (c_0 + c_1 \cdot s) \bmod Q_0 = m + e。

模约简函数 f(x) = x \bmod Q_0 包含取整操作，不是多项式，无法直接同态计算。因此需要找一个多项式 P(x) 来近似 f(x)。

多项式近似方法：
模约简函数 f(x) = x - Q_0 \cdot \lfloor x/Q_0 \rceil 是周期为 Q_0 的锯齿波。可以用以下方法近似：

1. 正弦函数近似：f(x) \approx \frac{Q_0}{2\pi} \sin(\frac{2\pi x}{Q_0})，然后用 Taylor 展开得到多项式
2. Chebyshev 多项式：在区间 [-Q_L/2, Q_L/2] 上最小化最大误差

设 P(x) = \sum_{i=0}^{d} a_i x^i 是 d 次近似多项式，满足 |P(x) - (x \bmod Q_0)| \leq \epsilon_P。

同态求值：由于 P 是多项式，可以用同态加法和同态乘法计算：
P(\text{Enc}_{pk'}(c_0 + c_1 \cdot s)) = \sum_{i=0}^{d} a_i \cdot (\text{Enc}_{pk'}(c_0 + c_1 \cdot s))^i = \text{Enc}_{pk'}(P(c_0 + c_1 \cdot s))

其中 (\cdot)^i 通过 i 次同态乘法实现。最终：
ct' = \text{Enc}_{pk'}((m + e) + \epsilon)

近似误差 |\epsilon| \leq \epsilon_P。结果 ct' 是新公钥 pk' 下的密文，对应私钥 s'，模数链恢复到顶层 L。

自举正确性

定理 6.3（CKKS 自举正确性）：设输入密文 ct 满足 c_0 + c_1 \cdot s = m + e \pmod{Q_0}，多项式近似误差为 \epsilon_P。则自举输出密文 ct' 满足：

\text{Dec}_{s'}(ct') = m + e'

其中噪声 e' 满足 \|e'\|_\infty \leq \|e\|_\infty + \epsilon_P + e_{\text{eval}}，e_{\text{eval}} 是同态求值引入的噪声。

证明：设 x = c_0 + c_1 \cdot s。模数提升后，c_0, c_1 在模 Q_L 下，s 是小系数私钥，因此 x 的系数大小约为 O(Q_L)。多项式 P 在区间 [-Q_L, Q_L] 上近似模约简函数 t \mapsto t \bmod Q_0。同态计算 P(x) 得到：

P(x) = (x \bmod Q_0) + \epsilon = m + e + \epsilon

其中 \epsilon 是近似误差，\|\epsilon\|_\infty \leq \epsilon_P。加上同态求值噪声 e_{\text{eval}}，最终得到 m + e'。\square

6.3.3 复杂度与优化

自举复杂度

定理 6.4（自举复杂度）：设多项式 P 的次数为 d，则 CKKS 自举需要：

证明：多项式 P(x) = \sum_{i=0}^{d} a_i x^i 的同态求值需要计算 x^i（i=0,1,\ldots,d）。使用平方-乘法算法，计算 x^d 需要 O(\log d) 次乘法。所有单项式 x^i 可在 O(d) 次乘法内完成。每次乘法的时间复杂度为 O(N \log N)（使用 NTT），总时间为 O(d \cdot N \log N)。

多项式求值需要 O(\log d) 的乘法深度。这意味着模数链必须有足够的层级来支持这些乘法。CKKS自举要求 L \geq O(\log d)，即顶层模数 Q_L 必须足够大以容纳自举过程中的所有乘法运算。

\square

附录：数学符号速查表

模数符号

误差符号

其他符号