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

• 标题 (Title): DaCapo: Automatic Bootstrapping Management for Efficient Fully Homomorphic Encryption (DaCapo：用于高效全同态加密的自动自举管理)
• 作者 (Authors): Seonyoung Cheon, Yongwoo Lee, Dongkwan Kim, Ju Min Lee, Hanjun Kim (Yonsei University); Sunchul Jung, Taekyung Kim (CryptoLab. Inc); Dongyoon Lee (Stony Brook University)
• 发表期刊/会议 (Journal/Conference): USENIX Security Symposium 2024 (SEC '24)。该会议是计算机安全领域的四大顶级学术会议之一，享有极高的声誉和影响力。
• 发表年份 (Publication Year): 2024
• 摘要 (Abstract): 全同态加密 (FHE) 支持对加密数据进行计算，为隐私保护计算外包提供了可能。然而，由于每个FHE乘法都会消耗密文有限的“尺度容量”，其应用被限制在小程序上。通过重置累积的尺度，自举 (Bootstrapping) 操作可以支持更长的FHE乘法链。然而，手动放置自举操作带来了巨大的编程负担：放置不足会导致尺度溢出，放置过多则会引入巨大的计算开销。此外，自举的放置还会影响其他FHE操作的成本，使整个管理过程更加复杂。本文提出了 DaCapo，这是第一个自动进行自举管理的编译器。为了减少自举次数，DaCapo 分析程序中每个点的“存活”密文 (live-out ciphertexts)，并识别出插入自举操作的候选点。DaCapo 会估算在不同尺度管理方案下每个自举放置计划的FHE操作延迟，并选择延迟最小的方案。本文使用现有FHE编译器因缺乏自举支持而无法编译的深度学习模型对 DaCapo 进行了评估，与手动实现的FHE程序相比，平均实现了 1.21 倍的加速。
• 原文链接 (Source Link): https://www.usenix.org/system/files/sec24summer-prepub-336-cheon.pdf (预印本 Pre-published)

2. 整体概括 (Executive Summary)

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

  • 核心问题： 在全同态加密 (FHE) 中，尤其是 RNS-CKKS 方案中，乘法运算会持续消耗密文的“尺度容量” (scale capacity)。当程序包含大量乘法（即“乘法深度”很高）时，尺度会溢出，导致计算结果不可恢复。bootstrapping 操作可以“刷新”密文，重置其尺度，从而支持任意深度的计算。然而，决定在何处以及何时插入 bootstrapping 操作是一个极其困难且繁琐的手动过程。
  • 重要性与挑战：
    1. 正确性保证： 程序员必须手动追踪每个密文的尺度增长，在溢出前插入 bootstrapping，这非常容易出错。
    2. 性能开销： bootstrapping 是FHE中最昂贵的操作之一，其延迟远高于其他运算。插入过多会严重拖慢程序性能。
    3. 复杂依赖： bootstrapping 的位置会改变密文的尺度和级别 (level)，这反过来会影响后续其他FHE操作（如加法、乘法）的延迟，因为这些操作在不同级别下的成本不同。这种复杂的“连锁反应”使得手动优化几乎不可能。
  • 切入点： 现有的FHE编译器（如 EVA、Hecate）能够自动管理除 bootstrapping 之外的尺度操作，但无法处理需要 bootstrapping 的大型程序（如深度神经网络）。本文的切入点是将 bootstrapping 的放置问题转化为一个编译器自动优化的任务，从而彻底解决手动管理的难题。

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

  • 提出了 DaCapo： 这是学术界第一个能够自动管理和放置 bootstrapping 操作的FHE编译器。
  • 提出了存活感知分析 (Liveness-Aware Analysis)： 通过分析程序中每个点的“存活”密文数量，优先选择存活密文最少的点作为 bootstrapping 的候选位置，从而自然地减少了需要执行 bootstrapping 的次数。
  • 提出了成本感知优化 (Cost-Aware Optimization)： DaCapo 不仅考虑 bootstrapping 本身的开销，还估算不同放置方案对后续所有FHE操作延迟的“连锁影响”，最终选择一个全局延迟最低的方案。
  • 关键发现： 实验证明，DaCapo 编译的程序比专家手动优化的版本平均快 1.21倍，并且能够成功编译和运行现有工具无法处理的复杂深度学习模型（如 ResNet、VGG16）。一个反直觉的发现是，有时插入更多的 bootstrapping 操作反而能获得更低的总体延迟，因为这可以将程序划分为多个“浅”计算块，使得大部分其他操作能在更低、更快的级别上执行。

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

• 基础概念 (Foundational Concepts):

  • 全同态加密 (Fully Homomorphic Encryption, FHE): 一种革命性的加密技术，允许在加密数据（密文）上直接进行计算，而无需先解密。计算结果解密后与在明文上进行相同计算的结果一致。这使得我们能将敏感数据的计算任务外包给不受信任的云服务商，而不用担心数据泄露。

  • RNS-CKKS 方案: 一种流行的FHE方案，特别适合于机器学习等需要对实数（浮点数）进行近似计算的场景。它通过将多个数打包成一个向量进行计算，实现了单指令多数据 (SIMD) 的并行处理。

  • 密文的属性 (Ciphertext Properties): 在 RNS-CKKS 中，一个密文主要有以下几个关键属性，如下图所示：

    该图像是论文中的示意图，展示了全同态加密（FHE）中尺度因子及其运算操作，包括加法、乘法、模切换（Modswitch）、重标定（Rescale）和自举（Bootstrapping）。图中定义了尺度容量$S_f^L$、尺度$m$和尺度因子$S_f$的关系，并通过图示说明了各运算对尺度的影响。

    • 尺度 (Scale): 为了用整数表示实数，FHE会对明文数据乘以一个大的缩放因子，这个因子就是“尺度”。例如，实数 1.1 可以用整数 11 和尺度 $10^1$ 来表示。两个密文相乘时，它们的尺度也会相乘，导致尺度快速增长。
    • 系数模数 (Coefficient Modulus) $Q$: 这是密文能够容纳的数值范围的上限，也定义了尺度容量 (Scale Capacity)。如果累积的尺度超过了这个容量，就会发生“尺度溢出” (scale overflow)，计算结果将出错且无法恢复。
    • 级别 (Level) $l$: 尺度容量 $Q$ 通常由一系列素数模数相乘得到。级别 $l$ 代表当前密文还剩下多少个这样的素数模数可供使用。每次执行 rescale 或 modswitch 操作，级别会减 1。级别越高，计算开销越大。初始级别为 $L$。

  • FHE 核心操作:

    • 算术运算 (Add/Mul): 对密文进行加法或乘法。乘法会使结果的尺度变为两个操作数尺度的乘积。
    • 重标定 (Rescale): 一个关键的尺度管理操作。在乘法后，rescale 操作会将密文的尺度除以一个固定的“尺度因子” $S_f$，同时级别 $l$ 减 1。这可以控制尺度的增长，但会消耗级别。
    • 自举 (Bootstrapping): 当级别即将耗尽，无法再进行 rescale 时，就需要 bootstrapping。这个操作像一个“刷新”按钮，它将一个低级别、高尺度的密文转换成一个高级别、低尺度的全新密文，使其可以继续参与后续的乘法运算。在本文中，bootstrapping 将密文的级别重置为初始级别 $L$。bootstrapping 是FHE中最昂贵的操作。

• 前人工作 (Previous Works):

  • FHE 库: 许多底层库被开发出来以实现FHE方案，如 HEaaN、SEAL、PALISADE 等。这些库提供了FHE操作的API，但需要程序员手动管理所有细节。
  • FHE 编译器: 为了简化编程，出现了一些FHE编译器，如 EVA [18] 和 Hecate [41]。它们可以自动插入 rescale、modswitch 等操作来管理尺度。但它们的共同局限性是都不支持 bootstrapping。因此，它们只能编译乘法深度较浅的小型程序（如 LeNet-5），无法处理像 ResNet 这样需要 bootstrapping 的复杂模型。
  • 手动自举放置: 对于大型FHE程序，目前唯一的解决方案是专家程序员手动在代码中插入 bootstrapping 调用 [36, 38]。这不仅耗时耗力、极易出错，而且很难找到性能最优的放置策略。

• 差异化分析 (Differentiation): 本文提出的 DaCapo 与之前工作的核心区别在于，它是第一个自动化 bootstrapping 管理的编译器。它填补了现有FHE编译器无法处理深层计算的空白，将程序员从复杂、易错的手动 bootstrapping 放置工作中解放出来，并能找到比手动放置更优的性能方案。

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

DaCapo 的核心思想是，将 bootstrapping 的放置问题建模为一个编译器优化问题，通过两阶段流水线——候选点选择器 (Candidate Selector) 和 自举规划器 (Bootstrapping Planner)——来找到全局最优解。

该图像是一张示意图，展示了DaCapo自动靴磨机制的流程和不同靴磨插入点的代价估算。图中包含了输入程序、候选点选择、代价估算及最终靴磨插入的步骤，用箭头和数值标识了计算成本和流程。该图为理解自动靴磨管理策略提供直观支持。

• 方法原理 (Methodology Principles):

  • 洞察 1: 减少 bootstrapping 次数比简单地延迟 bootstrapping 更重要。 bootstrapping 开销巨大，其目标应是最小化执行次数。
    • 存活分析 (Liveness Analysis): 一个 bootstrapping 操作需要作用于所有在当前点之后还会被用到的“存活” (live-out) 密文上。因此，在数据流汇合（存活密文少）的点进行 bootstrapping，比在数据流发散（存活密文多）的点进行更划算。
    • 旁路边分析 (Bypass Edge Analysis): 有些存活密文虽然“活着”，但在很长一段计算中都不会被使用（例如，ResNet中的跳跃连接）。这种“长寿但未使用”的密文（称为 bypass edge）在短期内不需要 bootstrapping。DaCapo 会识别并暂时忽略它们，从而更精确地计算所需 bootstrapping 的数量，找到更多优质的候选点。
  • 洞察 2: bootstrapping 的位置会影响全局性能，有时多做反而更快。 bootstrapping 会重置密文的级别。在一个恰当的位置插入 bootstrapping，可以将程序划分为两个子部分。如果其中一个子部分的乘法深度较浅，那么这部分的所有计算都可以在更低的级别上执行，从而节省大量时间。这种节省可能超过额外 bootstrapping 操作带来的开销。因此，必须进行成本感知 (Cost-aware)的分析。

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

  第一阶段：自举候选点选择器 (Bootstrapping Candidate Selector) 该阶段的目标是生成一个合理的 bootstrapping 插入点候选集合，为后续的成本规划做准备。

  • 步骤1：存活与旁路边分析 (Liveness and Bypass Edge Analysis)
    • DaCapo 遍历程序中的每个计算点，使用标准的编译器技术——存活变量分析 (live variable analysis)——来计算在每个点之后仍然会被使用的密文数量。
    • 同时，它识别出 bypass edges。如果一个密文在被定义后，要经过一段很长的计算（其累积尺度超过某个阈值 $S_{th}$）才会被再次使用，那么它就被标记为 bypass edge。
    • 在计算每个点的“有效存活密文数”时，bypass edges 会被排除。这使得 DaCapo 能够找到那些真正需要 bootstrapping 的密文汇聚点。
  • 步骤2：候选点过滤 (Candidates Filtering)
    • DaCapo 首先只考虑“有效存活密文数”为 1 的点作为候选点，因为这些点进行 bootstrapping 的成本最低。
    • 然后，它会检查仅在这些点插入 bootstrapping 是否足以防止整个程序出现尺度溢出。
    • 如果不足以防止溢出，它会逐步放宽标准，例如，将“有效存活密文数”为 2 的点也加入候选集，直到找到一个能够保证程序正确运行的最小候选集。

  第二阶段：成本感知的自举规划器 (Cost-aware Bootstrapping Planner) 该阶段的目标是从候选集中选出一个 bootstrapping 放置组合，使得整个程序的总延迟最小。

  • 步骤1：成本估算 (Cost Estimation)
    • DaCapo 采用一种类似动态规划的方法。它将整个程序看作一个有向无环图 (DAG)，节点是FHE操作。
    • 它从程序的起点开始，依次计算到达每个候选点 $C_i$ 的最小累计延迟。
    • 要计算到达 $C_i$ 的最小延迟，它会考虑所有在 $C_i$ 之前的候选点 $C_j$。对于每个 $C_j$，它会计算两种情况的延迟：
      1. 在 $C_j$ 不进行 bootstrapping，从上一个 bootstrapping 点直接计算到 $C_i$ 的延迟。
      2. 在 $C_j$ 进行 bootstrapping，其延迟为：(到达 $C_j$ 的最小延迟) + (bootstrapping 的开销) + (从 $C_j$ 到 $C_i$ 的计算延迟)。
    • DaCapo 会记录到达每个候选点的最小延迟及其对应的 bootstrapping 路径。
  • 步骤2：自举插入点选择 (Bootstrapping Insertion Point Selection)
    • 这个过程一直持续到程序的终点。最终，规划器会得到到达程序终点的最小总延迟，并回溯找出实现这个最小延迟的最佳 bootstrasempre 放置方案。

• 数学公式与关键细节 (Mathematical Formulas & Key Details): 虽然论文主要通过算法伪代码描述流程，但其背后的关键数学概念是 RNS-CKKS 的尺度和级别管理。

  • 累积尺度 (Accumulated Scale): 乘法操作 $C_{out} = C_1 \times C_2$ 会导致尺度累积：$scale(C_{out}) = scale(C_1) \times scale(C_2)$。DaCapo 必须追踪这个值的增长。
  • 尺度溢出条件: 必须始终满足 AccumulatedScale $< S_f^L$。DaCapo 的一个核心任务就是防止违反此条件。
  • 重标定条件: rescale 操作要求 $m / S_f \ge S_w$，其中 $m$ 是当前尺度，$S_w$ 是预定义的最小尺度“水位线” (waterline)，用于控制计算噪声。DaCapo 的成本估算必须遵循这个约束。
  • 成本函数: 延迟估算基于预先分析好的FHE操作延迟表（如论文中的 Table 2）。总成本 $Cost_{total}$ 可以表示为： $$Cost_{total} = \sum_{i \in \text{Ops}} \text{Latency}(op_i, \text{level}_i) + N_{boot} \times \text{Latency}_{boot}$$ 其中，$\text{Latency}(op_i, \text{level}_i)$ 是第 $i$ 个操作在其所在级别 level``_i 的延迟，$N_{boot}$ 是 bootstrapping 的总次数，$\text{Latency}_{boot}$ 是单次 bootstrapping 的延迟。DaCapo 的目标是最小化这个 $Cost_{total}$。

5. 实验设置 (Experimental Setup)

• 数据集 (Datasets):

  • 实验使用了 CIFAR-10 数据集。这是一个广泛应用于计算机视觉领域的图像分类标准数据集，包含10个类别的60000张32x32彩色图像。
  • 选择此数据集是因为它可以有效地评估 DaCapo 在处理具有代表性的深度学习模型（如ResNet）时的性能和准确性。

• 评估指标 (Evaluation Metrics):

  • 加速比 (Speedup):

    1. 概念定义: 加速比是衡量性能提升的核心指标。它通过比较基线方法（手动放置）的运行时间与 DaCapo 生成程序的运行时间来计算。加速比大于1表示 DaCapo 的性能更优。
    2. 数学公式: $$\text{Speedup} = \frac{\text{Latency}_{\text{Manual}}}{\text{Latency}_{\text{DaCapo}}}$$
    3. 符号解释: $\text{Latency}_{\text{Manual}}$ 是手动实现版本的程序总延迟时间。$\text{Latency}_{\text{DaCapo}}$ 是由 DaCapo 编译器自动生成版本的程序总延迟时间。

  • 分类准确率 (Classification Accuracy):

    1. 概念定义: 该指标用于验证 DaCapo 生成的FHE程序在进行近似计算后，是否保持了与原始模型相当的预测能力。
    2. 数学公式: $$\text{Accuracy} = \frac{\text{Number of Correct Predictions}}{\text{Total Number of Predictions}}$$
    3. 符号解释: “Number of Correct Predictions”是模型正确分类的样本数量，“Total Number of Predictions”是测试集中的总样本数量。

  • 延迟 (Latency):

    1. 概念定义: 指完成一次推理任务（例如，对一张图片进行分类）所花费的总时间，单位通常为秒。这是评估性能的直接度量。
    2. 数学公式: 无标准化公式，为直接测量的时间值 $T$。

• 对比基线 (Baselines):

  • Manual: 这是主要的基线。它代表了当前最先进的实践，即由专家根据 [36] 中提出的策略手动放置 bootstrapping 操作。这是一个非常强力的基线，因为它体现了人类专家的优化水平。
  • Liveness: DaCapo 的一个变体，只使用存活分析来选择候选点，但不进行旁路边分析和成本感知规划。
  • Bypass: DaCapo 的另一个变体，使用了存活分析和旁路边分析来选择候选点，但仍然不进行成本感知规划。
  • 这两个变体主要用于消融实验 (Ablation Studies)，以证明 DaCapo 的每个组件（旁路边分析、成本感知规划）都是有效且必要的。

6. 实验结果与分析

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

  该图像是一个条形图，展示了不同FHE编译器和优化策略在多个深度学习模型上的加速比对比。图中包括手动方式、Liveness、Bypass和DaCapo四种方案，DaCapo在大多数模型中实现了最高加速比，平均加速比达1.21倍。

  • DaCapo 的性能优势： 从上图可以看出，深蓝色的条形图（DaCapo）在绝大多数模型上都超过了基线1.0，表明其性能优于手动实现。在所有12个基准测试中，DaCapo 取得了平均 1.21倍 的几何平均加速比。
  • 组件的有效性：
    • Liveness（浅蓝色）在某些情况下性能甚至不如 Manual，说明仅靠存活分析是不够的。
    • Bypass（橙色）相比 Liveness 有所提升，尤其是在 ResNet 模型中，证明了旁路边分析对于找到更好的候选点至关重要。
    • DaCapo（深蓝色）全面超越 Liveness 和 Bypass，凸显了成本感知规划是实现最终性能飞跃的关键。它能在众多候选方案中，精确找到那个平衡了 bootstrapping 开销和算术运算开销的最佳点。

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

  该图像是一个柱状图，展示了不同深度学习模型在多种FHE编译策略下的延迟时间对比，涵盖Bootstrap time、Manual、Liveness、Bypass和DaCapo五种方法，其结果表明DaCapo在大多数模型中实现了延迟下降。

  • bootstrapping 数量与总延迟的关系： 以下是转录自原文的 Table 4，展示了 Manual 和 DaCapo 生成的 bootstrapping 操作数量。

    模型	ResNet-20 (ReLU)	ResNet-20 (SiLU)	ResNet-44 (ReLU)	ResNet-44 (SiLU)	AlexNet (ReLU)	AlexNet (SiLU)	VGG16 (ReLU)	VGG16 (SiLU)	SqueezeNet (ReLU)	SqueezeNet (SiLU)	MobileNet (ReLU)	MobileNet (SiLU)
    Manual	37	19	85	43	66	12	54	20	58	18	53	27
    DaCapo	37	19	85	43	67	12	53	20	57	19	61	27

    一个非常有趣的发现出现在 MobileNet (ReLU) 模型上。DaCapo 插入了 61 次 bootstrapping，而手动实现只有 53 次。尽管 bootstrapping 次数更多，但从上图（图5）可以看出，DaCapo 的总延迟（深蓝色条）反而更低。这强有力地证明了论文的核心洞察：通过更频繁地 bootstrapping，DaCapo 将计算保持在较低的级别，从而大幅降低了大量算术运算的成本，这种节省超过了额外 bootstrapping 的开销。

  • 成本估算的准确性：

    该图像是图表，展示了图6中DACAPO基于剖析数据的估计结果与实际延迟的关系。横坐标为估计开销（秒），纵坐标为实际延迟（秒）。图中包含回归直线方程 y=1.034x 及拟合优度 $R^2=0.9986$，显示估计高度准确。

    此图展示了 DaCapo 的成本估算模型非常准确。横轴是 DaCapo 预测的延迟，纵轴是实际运行的延迟。所有数据点紧密分布在 y = 1.034x 这条直线上，且 $R^2$值高达 0.9986，说明预测与现实高度一致。这是 DaCapo 能够做出正确决策的基础。

  • 准确率验证： 以下是转录自原文的 Table 3，对比了 PyTorch（明文计算）和 DaCapo（FHE计算）的分类准确率。

    模型	ResNet-20	ResNet-44	AlexNet	VGG16	SqueezeNet	MobileNet
    	ReLU / SiLU	ReLU / SiLU	ReLU / SiLU	ReLU / SiLU	ReLU / SiLU	ReLU / SiLU
    Pytorch	90.6% / 92.6%	91.2% / 92.7%	89.0% / 86.6%	93.8% / 93.0%	89.4% / 88.0%	91.4% / 91.4%
    DACAPO	90.7% / 92.6%	91.3% / 92.7%	89.0% / 86.6%	93.8% / 92.9%	89.2% / 87.9%	91.2% / 91.4%

    结果显示，DaCapo 编译的FHE程序的准确率与明文计算的 PyTorch 模型几乎完全相同，差异在0.2%以内，证明了其在实现高性能的同时保证了计算的正确性。

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

• 结论总结 (Conclusion Summary):

  • 本文成功设计并实现了 DaCapo，这是第一个用于FHE的自动 bootstrapping 管理编译器。
  • DaCapo 通过创新的存活感知和成本感知分析，能够自动为复杂的FHE程序（如深度神经网络）找到近乎最优的 bootstrapping 放置策略。
  • 实验结果表明，DaCapo 不仅能够编译现有工具无法处理的大型模型，而且其性能比专家手动优化的版本平均高出 21%。它还揭示了 bootstrapping 优化中一个反直觉但重要的原则：最优解并不总是 bootstrapping 次数最少的解。

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

  • 启发式阈值： 文中提到的 bypass edge 分析依赖一个启发式设定的阈值 $S_{th}$（本文设为最大尺度容量的一半）。这个值的选择可能会影响性能，一个更自适应或自动确定的方法可能是未来的改进方向。
  • 搜索空间的剪枝： DaCapo 的规划过程是基于候选点进行的启发式搜索，而非穷举搜索。虽然在实践中效果很好，但理论上可能无法保证找到绝对的全局最优解。
  • 硬件依赖性： 成本模型依赖于在特定硬件（NVIDIA RTX 3090）上分析得到的延迟数据。如果更换硬件，需要重新进行性能分析，这降低了通用性。未来的工作可以探索更具移植性的成本模型。
  • 适用范围： 当前的工作主要集中在 RNS-CKKS 方案和无数据依赖控制流的程序（如神经网络推理）。将其扩展到其他FHE方案或支持更复杂的程序结构（如循环、分支）将是重要的下一步。

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

  • 重大实践意义： DaCapo 最重要的贡献在于它极大地降低了开发复杂隐私保护应用的门槛。FHE虽然理论强大，但其极高的编程复杂性（尤其是 bootstrapping 管理）是阻碍其广泛应用的最大障碍。DaCapo 这样的自动化工具是推动FHE从理论走向实用的关键一步。
  • 系统性思维的胜利： DaCapo 的成功体现了编译器和系统优化思想在密码学工程中的强大威力。它没有发明新的密码学原语，而是通过对现有操作的智能调度和规划，实现了显著的性能提升。这启发我们，在很多领域，对现有组件的“编排”与发明新组件同样重要。
  • 反直觉的优化结论： “更多 bootstrapping 可能更快”这一发现非常有价值。它打破了人们倾向于“尽可能减少昂贵操作”的思维定势，揭示了在FHE这种具有复杂成本依赖的系统中，需要进行全局和动态的权衡。这对于其他资源受限的计算领域（如内存管理、功耗优化）也可能具有借鉴意义。
  • 批判性思考： 论文的评估主要集中在深度学习推理任务上，这类任务的数据流是静态且可预测的。DaCapo 的静态分析方法在面对具有数据依赖控制流（例如，循环次数取决于输入数据）的通用程序时可能会遇到挑战。此外，编译时间（虽然论文提到为4小时，但没有详细分析其扩展性）也是一个需要考虑的实际问题，特别是对于更大规模的模型。