1. 论文基本信息 (Bibliographic Information)

• 标题 (Title): 明文-密文矩阵乘法与全同态加密自举：快速与融合 (Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused)
• 作者 (Authors): Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, and Damien Stehlé.
  • 作者分别来自韩国的 CryptoLab Inc.、首尔国立大学以及法国的 CryptoLab Inc.，这些都是在密码学，特别是格密码和全同态加密领域非常知名的研究机构和团队。
• 发表期刊/会议 (Journal/Conference): IACR ePrint Archive
  • 这是一个国际密码学研究学会 (IACR) 运营的预印本服务器，是密码学领域最新、最前沿研究成果的首发平台。在此发布的论文通常意味着其具有较高的时效性和关注度。
• 发表年份 (Publication Year): 2024
• 摘要 (Abstract): 对一个明文矩阵和一个密文矩阵进行同态乘法，即明文-密文矩阵乘法 (PC-MM)，是隐私保护 Transformer 模型（常用于大语言模型）评估中的核心任务。本文提供了多种基于环学习带误差问题 (RLWE) 的 PC-MM 算法，这些算法将复杂的 PC-MM 分解为明文-明文矩阵乘法 (PP-MM) 以及一些开销相对较小的预处理和后处理步骤。论文针对矩阵维度与 RLWE 环维度的大小关系，以及是否使用预计算，分别给出了不同的算法。特别地，对于带预计算的算法，本文展示了如何仅通过一次与原矩阵维度相同的浮点 PP-MM 来完成 PC-MM，这在实践中极具意义，因为浮点 PP-MM 可以通过高性能的 BLAS 库高效实现。 这些算法依赖于 RLWE 的多密钥变体，该变体能更紧凑地表示多个密文。论文给出了在常规的共享密钥 RLWE 密文和多密钥密文之间相互转换的算法，并证明了这种新格式与同态加法、明文-密文乘法和密钥切换等操作兼容。利用这一点，论文加速了 CKKS 自举过程中的 slots-to-coeffs 和 coeffs-to-slots 步骤（当多个密文被同时自举时）。通过将批量自举与高效的 PC-MM 相结合，论文最终提出了 MaMBo (Matrix Multiplication Bootstrapping)，一种能够在有限的额外开销下执行 PC-MM 的自举算法。
• 原文链接 (Source Link): https://eprint.iacr.org/2024/1284.pdf (预印本)

2. 整体概括 (Executive Summary)

• 研究背景与动机 (Background & Motivation - Why):

  • 核心问题： 在隐私保护机器学习，特别是大语言模型（LLM）的推理场景中，需要对加密的用户数据（矩阵形式）和公开的模型权重（矩阵形式）进行大量的矩阵乘法。这种明文-密文矩阵乘法 (PC-MM) 在现有的全同态加密（FHE）方案中计算开销巨大，是性能瓶颈。
  • 重要性与挑战： 随着 LLM 的模型维度 (dim) 和上下文长度 (ntok) 不断增大（例如达到数千甚至上万），PC-MM 的效率直接决定了隐私计算方案的实用性。现有的 PC-MM 算法要么因为需要在密文内部移动数据而效率低下，要么对矩阵的维度有苛刻的限制（例如要求维度大于 FHE 的环维度 $N$），缺乏灵活性。
  • 创新切入点： 本文的核心思路是将昂贵的 FHE 运算 PC-MM 巧妙地“降维”或转化为廉价的常规运算 PP-MM。通过对 FHE 密文结构的深刻理解，作者将复杂的同态运算转化为对密文底层系数矩阵的明文运算，从而可以利用高度优化的线性代数库（如 BLAS）进行极致加速。

• 核心贡献/主要发现 (Main Contribution/Findings - What):

  1. 提出了一系列灵活高效的 PC-MM 算法： 无论矩阵维度 $d$ 是大于还是小于 RLWE 环维度 $N$，无论是否允许预计算，本文都给出了相应的 PC-MM 算法。这些算法的核心是将一次 PC-MM 归约到一到两次 PP-MM。
  2. 引入 shared-a 密文格式用于计算加速： 论文首次将一种常用于密码学安全证明的 shared-a 密文格式应用于实际计算。该格式允许多个密文共享相同的 $a$ 部分，从而将存储和计算成本降低了近一半。论文还提供了格式转换算法，并证明了其与多种 FHE 核心操作兼容。
  3. 实现了批量自举 (Batch Bootstrapping) 的加速： 利用 shared-a 格式的兼容性，论文展示了如何对一批密文同时进行自举操作中的 S2C 和 C2S 步骤，从而分摊计算成本，显著提升了批量处理的效率。
  4. 提出 MaMBo——融合矩阵乘法的自举算法： 这是本文最大的亮点。作者将 PC-MM 操作巧妙地“嵌入”到自举流程中，提出 MaMBo 算法。其效果是，在对密文进行必需的刷新（自举）的同时，“免费”或以极小的额外代价完成了一次矩阵乘法。实验表明，当处理维度大于 $2^9$ 的矩阵时，MaMBo 比标准的 CKKS 自举（不含矩阵乘法）还要快 40% 以上。

3. 预备知识与相关工作 (Prerequisite Knowledge & Related Work)

• 基础概念 (Foundational Concepts):

  • 全同态加密 (Fully Homomorphic Encryption, FHE): 一种允许在密文上直接进行计算的密码技术。对密文进行加法和乘法运算，解密后得到的结果与在明文上进行相应运算的结果相同。这使得我们可以在不获取原始数据的情况下处理敏感数据。
  • 环学习带误差 (Ring Learning With Errors, RLWE): FHE 方案（如 CKKS、BGV、BFV）背后最主流的数学困难问题。一个 RLWE 密文通常是一个多项式对 (a, b)，满足 $a \cdot \mathsf{sk} + b \approx m \pmod Q$，其中 $\mathsf{sk}$ 是密钥多项式，$m$ 是消息多项式，$Q$ 是模数。$a$ 和 $b$ 都在一个特定的多项式环 $\mathcal{R}_{Q,N} = \mathbb{Z}_Q[X]/(X^N+1)$ 中。
  • CKKS 方案: 一种基于 RLWE 的 FHE 方案，专门用于对浮点数或复数进行近似计算。它通过特定的编码方式（slot 编码和 coefficient 编码）将向量数据映射为多项式。
  • 自举 (Bootstrapping): FHE 中的一个关键操作。每次乘法都会使密文中的“噪声”增长，当噪声增长到一定程度后，密文就无法被正确解密。自举过程可以“刷新”密文，将其噪声降低到初始水平，从而允许进行更多的后续计算。这个过程非常昂贵，通常是 FHE 计算的主要开销来源。
  • 明文-密文矩阵乘法 (PC-MM): 计算 $\mathbf{U} \cdot \mathbf{M}$，其中 $\mathbf{U}$ 是公开的明文矩阵，$\mathbf{M}$ 是加密的密文矩阵。
  • 明文-明文矩阵乘法 (PP-MM): 常规的矩阵乘法，两个输入矩阵都是公开的。
  • 槽 (Slots) 与系数 (Coefficients): CKKS 方案中两种不同的数据表示方式。slot 编码通过类似离散傅里叶变换的方式将一个向量编码到多项式在特定单位根上的取值，便于进行向量的逐元素运算。coefficient 编码则是直接将向量的元素作为多项式的系数。自举过程通常需要在两种编码之间进行转换 (S2C 和 C2S)。

• 前人工作 (Previous Works):

  • [24] (Halevi et al., 2018): 提出了一种经典的密文-密文矩阵乘法算法，也可以用于 PC-MM。其主要缺点是需要在 RLWE 密文的 slots 之间移动数据，这涉及到大量的旋转 (Rotation) 操作，导致计算成本非常高。
  • [26] (Lee et al., 2022, LZ算法): 提出了一种更高效的 PC-MM 算法，它避免了密文内部的数据移动。其核心思想是将 PC-MM 归约为两次 PP-MM。然而，该算法的局限性在于只适用于矩阵维度 $d$ 大于等于 RLWE 环维度 $N$ 的情况，缺乏灵活性。

• 差异化分析 (Differentiation):

  • 灵活性: 本文的算法覆盖了 $d \ge N$ 和 $d < N$ 两种情况，解决了 [26] 的局限性。
  • 效率: 通过引入 shared-a 格式和预计算，本文将在线计算成本从 [26] 的两次模 PP-MM 进一步降低到一次模 PP-MM，甚至一次浮点 PP-MM。这使得 PC-MM 的性能可以逼近常规矩阵乘法。
  • 功能融合: 本文最大的创新在于提出了 MaMBo，将 PC-MM 和自举这两个昂贵的操作融合在一起，实现了“一箭双雕”的效果，极大地提升了 FHE 在复杂应用中的整体性能。

4. 方法论 (Methodology - Core Technology & Implementation Details)

本论文的核心方法论是将 PC-MM 的数学结构映射到对底层明文系数矩阵的运算，并通过 shared-a 密文格式和与自举的融合来最大化效率。

• 方法原理 (Methodology Principles): 基本思想源于对 RLWE 解密过程的矩阵化表示。一个 RLWE 密文 (a, b) 满足 $a \cdot \mathsf{sk} + b \approx m$。当我们将一个矩阵 $\mathbf{M}$ 的每一行 $m_{i,*}$ 用一个 RLWE 密文 $(a_i, b_i)$ 加密时，整个加密矩阵可以被表示为一个大的矩阵方程。之后，对密文矩阵 $\mathbf{M}$ 的左乘操作，就可以转化为对构成密文的系数矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 的左乘。

• 方法步骤与流程 (Steps & Procedures):

  1. LZ 算法回顾 ($d=N$):

     • 假设矩阵 $\mathbf{M}$ 的维度为 $d \times d$ (这里 $d=N$)，其第 $i$ 行 $m_{i,*}$ 被加密为密文 $(a_i, b_i)$。
     • 解密关系为 $a_i \cdot \mathsf{sk} + b_i \approx \sum_j m_{i,j}X^j$。
     • 将所有 $d$ 个密文写成矩阵形式，得到： $$\mathbf{A} \cdot \mathrm{Toep}(\mathsf{sk}) + \mathbf{B} \approx \mathbf{M} \pmod q$$
       • 符号解释:
         • $\mathbf{A}$: 一个 $d \times N$ 矩阵，其第 $i$ 行是多项式 $a_i$ 的系数向量。
         • $\mathbf{B}$: 一个 $d \times N$ 矩阵，其第 $i$ 行是多项式 $b_i$ 的系数向量。
         • $\mathrm{Toep}(\mathsf{sk})$: 一个 $N \times N$ 的托普利茨矩阵 (Toeplitz Matrix)，由密钥 $\mathsf{sk}$ 生成，它代表了多项式乘法 $\cdot \mathsf{sk}$ 这个线性操作。
         • $\mathbf{M}$: $d \times N$ 的明文矩阵。
     • 用明文矩阵 $\mathbf{U}$ 左乘上式两边： $$(\mathbf{U} \cdot \mathbf{A}) \cdot \mathrm{Toep}(\mathsf{sk}) + (\mathbf{U} \cdot \mathbf{B}) \approx \mathbf{U} \cdot \mathbf{M} \pmod q$$
     • 令 $\mathbf{A}' = \mathbf{U} \cdot \mathbf{A}$ 和 $\mathbf{B}' = \mathbf{U} \cdot \mathbf{B}$。可以发现，新矩阵 $\mathbf{A}'$ 和 $\mathbf{B}'$ 的每一行构成的新密文对 (a'_i, b'_i) 正是 $\mathbf{U} \cdot \mathbf{M}$ 对应行的加密。
     • 结论: 一次 PC-MM 被转化为两次 PP-MM ($\mathbf{U} \cdot \mathbf{A}$ 和 $\mathbf{U} \cdot \mathbf{B}$)。

  2. 本文的扩展与优化:

     • 大维度情况 ($d \ge N$): 使用 shared-a 密文格式。此时，一个 $d \times d$ 的矩阵 $\mathbf{M}$ 被加密。假设 $d=kN$。加密 $\mathbf{M}$ 的第 $i$ 行需要 $k$ 个密文，但这些密文可以共享同一个 $a_i$ 部分，而使用 $k$ 个不同的密钥 $\mathsf{sk}_0, \dots, \mathsf{sk}_{k-1}$。

     • 矩阵方程变为： $$\mathbf{A} \cdot [\mathrm{Toep}(\mathsf{sk}_0) | \dots | \mathrm{Toep}(\mathsf{sk}_{k-1})] + \mathbf{B} \approx \mathbf{M} \pmod q$$

       • 符号解释:
         • $\mathbf{A}$: 维度为 $d \times N$，其第 $i$ 行是共享的多项式 $a_i$ 的系数。
         • $\mathbf{B}$: 维度为 $d \times d$ ($d \times kN$)，是所有 $b_{i,j}$ 的系数矩阵。
       • 优势: $\mathbf{A}$ 的列数从 $d$ 降为了 $N$，计算 $\mathbf{U} \cdot \mathbf{A}$ 的开销显著降低。总计算量从两次 $d \times d \times d$ 的 PP-MM 降低为一次 $d \times d \times N$ 和一次 $d \times d \times d$ 的 PP-MM。

     • 小维度情况 ($d < N$): 使用 MLWE 密文格式。此时，一个 RLWE 密文可以容纳矩阵的多行。通过 MLWE 格式，作者构造了类似的矩阵方程，同样将 PC-MM 归约到 PP-MM。

     • 带预计算的优化: 如果明文矩阵 $\mathbf{U}$ 是提前已知的，可以进行预计算。此时，作者使用了另一种矩阵方程形式，将密钥矩阵 $\mathbf{S}$ 放在了左边。 $$\mathbf{S} \cdot \mathrm{Toep}(a) + \mathbf{B} \approx \mathbf{M} \pmod q$$

       • 符号解释:
         • $\mathbf{S}$: 密钥矩阵，其第 $i$ 行是密钥 $\mathsf{sk}_i$ 的系数。
         • $\mathrm{Toep}(a)$: 由共享的 $a$ 部分生成。
       • 左乘 $\mathbf{U}$ 后变为 $(\mathbf{U} \cdot \mathbf{S}) \cdot \mathrm{Toep}(a) + (\mathbf{U} \cdot \mathbf{B}) \approx \mathbf{U} \cdot \mathbf{M}$。
       • 优势: 在线阶段，Toep(a) 和 $\mathbf{B}$ 是已知的，而 $\mathbf{U}$ 和 $\mathbf{S}$ 是未知的。然而，论文通过巧妙的转换，将计算变为对 $\mathbf{B}$ 的乘法。如果允许对密钥进行操作，可以预计算 $\mathbf{S}' = \mathbf{U} \cdot \mathbf{S}$，从而将在线计算量减少到仅有一次 PP-MM ($\mathbf{U} \cdot \mathbf{B}$)。

     • 浮点 PP-MM 优化:

       • 在 CKKS 等近似加密方案中，密文 $b$ 部分的低位比特充满了噪声，没有信息价值。

       • 因此，在计算 $\mathbf{U} \cdot \mathbf{B}$ 时，无需进行昂贵的模 $q$ 整数乘法。可以只提取 $\mathbf{B}$ 中系数的高位有效比特，将其转换为浮点数，然后执行标准的浮点 PP-MM，最后再对结果进行舍入和模约简。

       • 这使得 PC-MM 的核心计算可以完全由高度优化的 BLAS 浮点运算库完成，性能大幅提升。

         该图像是论文中关于浮点数PP-MM的示意图，展示了处理流程中的数据提取、浮点乘法和模约简步骤。绿色代表密文基础数据，粉色表示模$q_0 q_1$溢出。

       上图（图像1）展示了这一过程：绿色区域代表密文中包含有效数据的部分，在与明文 $u$ 相乘后，结果可能会超出原有的模数范围（粉色区域），但通过浮点计算和后续处理，可以得到正确的结果。

  3. MaMBo: 融合 PC-MM 和批量自举:

     • 批量自举: 利用 shared-a 格式，多个密文的 S2C (slot-to-coeffs) 和 C2S (coeffs-to-slots) 转换可以批量处理。因为这些操作主要是线性变换（加法、与明文相乘、旋转），涉及 $a$ 部分的计算可以被所有密文共享，从而分摊成本。
     • 融合流程:
       1. 输入一批共享密钥的 RLWE 密文。
       2. 格式转换: 将它们转换为 shared-a 格式。
       3. 批量 S2C: 对这批 shared-a 密文执行 S2C，将它们从 slot 编码转换为 coefficient 编码。
       4. 执行 PC-MM: 在 coefficient 编码的密文上，执行前述的高效 PC-MM 算法之一。这个阶段的密文模数较低，计算开销也较小。
       5. ModRaise: 提升密文模数，为后续自举步骤做准备。
       6. 批量 C2S: 执行 C2S 将密文转换回 slot 编码。
       7. EvalMod: 执行自举的最后一步，移除噪声项。
       8. 格式转换 (可选): 将 shared-a 密文转换回标准的 RLWE 密文。
     • 核心优势: PC-MM 被巧妙地插入到自举流程的中间。自举本身就需要 S2C，而本文的 PC-MM 算法正好在 coefficient 编码（S2C 的输出）上操作。这使得两个昂贵的操作实现了“流水线”处理，PC-MM 的额外开销被大幅降低。

5. 实验设置 (Experimental Setup)

根据论文摘要和引言部分的描述，实验主要关注算法的性能。

• 数据集 (Datasets): 实验没有使用特定的自然语言或图像数据集，而是直接在不同维度 $d$ 的矩阵上进行测试，这些维度参考了主流大语言模型（如 LLaMA-7B 的 dim=4096，GPT-3.5 的 ntok 高达 16384）的参数设置，以模拟真实应用场景。
• 评估指标 (Evaluation Metrics):
  • 运行时间 (Runtime):
    1. 概念定义: 这是评估算法性能最直接的指标，衡量执行特定任务（如一次 PC-MM 或一次 MaMBo）所花费的墙上时间（wall-clock time），单位通常是秒（s）或毫秒（ms）。时间越短，算法效率越高。
    2. 数学公式: 该指标无特定数学公式，为直接物理测量值。
    3. 符号解释: N/A。
  • 吞吐量 (Throughput):
    1. 概念定义: 在批量处理场景下（如批量自举），该指标衡量单位时间内能够处理的密文数量。对于 MaMBo，它衡量的是在完成自举和 PC-MM 融合操作的前提下，每秒能处理多少个密文。
    2. 数学公式: $$\text{Throughput} = \frac{\text{Number of Ciphertexts in Batch}}{\text{Total Runtime}}$$
    3. 符号解释:
       • Number of Ciphertexts in Batch: 批处理中的密文总数。
       • Total Runtime: 完成该批处理所花费的总时间。
• 对比基线 (Baselines):
  • 标准 CKKS 自举: 与 MaMBo 进行比较，以展示在不执行 PC-MM 的情况下，MaMBo 的速度优势。这可以凸显 MaMBo 中批量处理和算法优化的效果。
  • 串行 PC-MM + 自举: 先执行一个 PC-MM 算法，再对结果逐个进行标准自举。这用来与 MaMBo 的融合方法进行对比，证明融合的优越性。
  • [26] 的算法: 作为 PC-MM 部分的性能对比基线，验证本文提出的新 PC-MM 算法在灵活性和效率上的提升。

6. 实验结果与分析 (Results & Analysis)

• 核心结果分析 (Core Results Analysis):

  • PC-MM 算法性能: 论文提出的 PC-MM 算法，特别是利用 shared-a 格式和浮点 PP-MM 的版本，性能远超以往方法。由于核心计算可以由 OpenBLAS 等库执行，其实际运行时间与明文矩阵乘法非常接近，开销主要在于预处理和后处理。

  • MaMBo 性能: 摘要中提到，当用于自举对应于维度 $d \ge 2^9$ 矩阵的密文时，MaMBo（包含了一次 PC-MM）比不含 PC-MM 的标准 CKKS 自举还要快 40% 以上。这个结果极其惊人，它表明 MaMBo 不仅没有因为增加 PC-MM 功能而变慢，反而由于批量处理带来的优化而变得更快。

  • 算法总结表: 论文在 Table 1 中系统性地总结了其提出的各种 PC-MM 算法及其适用场景。以下是该表格的转录与整理：

    矩阵维度 d	密文格式	归约形式	参考文献
    $d \le N$	MLWE	Mod-PP-MMd,d,d + Mod-PP-MMd,d,N	Alg. 2
    	sh.-a MLWE	Precomp. + Mod-PP-MMd,d,d	Alg. 4
    	sh.-a MLWE	Precomp. + FP-PP-MMd,d,d	Alg. 4 + Sec. 5
    $d \ge N$	RLWE	2× Mod-PP-MMd,d,d	[26]
    	sh.-a RLWE	Mod-PP-MMd,d,d + Mod-PP-MMd,d,N	Alg. 1
    	sh.-a RLWE	Precomp. + Mod-PP-MMd,d,d	Alg. 3
    	sh.-a RLWE	Precomp. + FP-PP-MMd,d,d	Alg. 3 + Sec. 5

    • 表格解读: 该表格清晰地展示了本文的贡献。对于任意维度 $d$，都提供了相应的高效算法。sh.-a (shared-a) 格式的使用，以及预计算 (Precomp.) 和浮点 PP-MM (FP-PP-MM) 的引入，是实现极致性能的关键路径。

• 消融实验/参数分析 (Ablation Studies / Parameter Analysis):

  • Table 1 本身就是一种变体分析。它比较了不同密文格式（MLWE vs sh.-a MLWE）、有无预计算、使用模 PP-MM 还是浮点 PP-MM 等情况下的算法构成，清晰地展示了每一种优化技术带来的好处（例如，预计算可以将两次 PP-MM 减少为一次）。
  • 通过比较 MaMBo 和标准自举的性能，也验证了批量处理 shared-a 格式密文的有效性。

7. 总结与思考 (Conclusion & Personal Thoughts)

• 结论总结 (Conclusion Summary): 该论文在全同态加密的应用实践上取得了重大突破。它不仅提供了一套完整、灵活且高效的 PC-MM 算法工具箱，将昂贵的同态运算转化为可由硬件加速的常规运算，更通过 MaMBo 算法，创造性地将 PC-MM 与自举过程融合，实现了“1+1<1”的惊人效果——在刷新密文的同时，以负成本（比单独自举还快）完成了一次矩阵乘法。这极大地降低了在隐私保护场景下部署大语言模型等复杂应用的门槛。

• 局限性与未来工作 (Limitations & Future Work):

  • 格式转换开销: 从标准 RLWE 密文转换到 shared-a 格式需要一个 $O(n^2)$（$n$ 为批处理大小）的矩阵乘法操作。当批处理的密文数量 $n$ 非常大时，这个转换本身可能成为新的瓶颈。
  • 预计算的依赖: 性能最高的算法依赖于预计算，这意味着明文矩阵 $\mathbf{U}$ 必须提前已知。这在 LLM 推理（权重矩阵固定）等场景下是可行的，但在某些 $\mathbf{U}$ 动态变化的场景下则不适用。
  • 多密钥管理: shared-a 格式和一些高级操作需要管理多个密钥，这增加了密钥管理的复杂性。

• 个人启发与批判 (Personal Insights & Critique):

  • 范式转移的启发: 这篇论文最精彩的地方在于其思想的转变。它没有在 FHE 的框架内“硬磕” PC-MM，而是跳出框架，通过对密文结构的矩阵化分解，将问题转化到另一个更容易解决的领域（高性能计算）。这种“降维打击”的思路对解决其他 FHE 性能瓶颈问题极具启发性。
  • 理论与实践的完美结合: 论文将一个在安全证明中使用的理论工具 (shared-a 格式) 成功地应用到了计算优化上，是理论指导实践的典范。同时，通过拥抱 BLAS 这类成熟的工业级计算库，使得 FHE 研究成果能够真正落地并获得实实在在的性能收益。
  • 对可编程自举的推动: MaMBo 可以看作是一种特殊形式的可编程自举 (Programmable Bootstrapping)，即在自举过程中嵌入一个特定的函数（这里是 PC-MM）。这篇论文的成功为未来研究在自举中嵌入更多、更复杂的函数提供了宝贵的经验和可能性，有望使 FHE 摆脱“只能做简单加乘”的刻板印象，向通用计算平台更近一步。