1. 论文基本信息

1.1. 标题

Low-Complexity Deep Convolutional Neural Networks on Fully Homomorphic Encryption Using Multiplexed Parallel Convolutions

1.2. 作者

Eunsang Lee, Joon-Woo Lee, Junghyun Lee, Young-Sik Kim, Yongjune Kim, Jong-Seon No, Woosuk Choi。 作者主要来自韩国的研究机构，如三星高级技术研究院 (Samsung Advanced Institute of Technology) 等。

1.3. 发表期刊/会议

机器学习研究进展 (Proceedings of Machine Learning Research, PMLR)，发表于 2022 年。MLR 是机器学习领域知名的开放获取出版平台，收录了许多高质量的会议论文，如国际机器学习大会 (ICML) 等。

1.4. 发表年份

2022 年

1.5. 摘要

最近，标准 ResNet-20 网络首次成功地在全同态加密 (Fully Homomorphic Encryption, FHE) 方案，即剩余数系统变体 Cheon-Kim-Kim-Song (RNS-CKKS) 方案上通过自举/引导 (bootstrapping) 实现，但该实现因高推理延迟 (latency) 和低安全级别而缺乏实用性。为了改善性能，本文首先通过多路复用并行卷积 (multiplexed parallel convolution) 最小化总自举运行时 (bootstrapping runtime)，该方法能够紧凑地收集多个通道的稀疏输出数据。此外，本文提出了去虚部引导 (imaginary-removing bootstrapping) 以防止深度神经网络在近似 ReLU (APR) 操作期间发生灾难性发散 (catastrophic divergence)。同时，本文优化了层级消耗 (level consumptions) 并使用了更轻量级和更严格的参数。仿真结果显示，与现有最先进的工作相比，本文的 ResNet-20 实现的推理延迟降低了 4.67 倍，摊销运行时 (amortized runtime，即每张图像的运行时) 减少了 134 倍，并达到了标准的 128 位安全级别。此外，本文首次在 RNS-CKKS 方案上成功以高准确率实现了 ResNet-110。

1.6. 原文链接

https://proceedings.mlr.press/v162/lee22e/lee22e.pdf

2. 整体概括

2.1. 研究背景与动机

论文试图解决的核心问题： 在保护数据隐私的前提下，在加密数据上高效、准确地执行深度卷积神经网络 (Convolutional Neural Networks, CNNs) 的推理任务，特别是非常深的标准 CNNs (Very Deep Standard CNNs, VDSCNNs)，如 ResNet-110。

为什么这个问题在当前领域是重要的： 随着人工智能应用的普及，客户端越来越不愿将敏感的私有数据（如医疗信息）直接发送给服务器进行推理。隐私保护机器学习 (Privacy-Preserving Machine Learning, PPML) 成为了解决这一问题的关键技术。在 PPML 中，全同态加密 (Fully Homomorphic Encryption, FHE) 允许在加密数据上直接进行计算，而无需解密，从而从根本上保护了数据隐私。然而，FHE 的计算开销非常高，特别是在处理复杂的深度神经网络时，性能和实用性成为主要瓶颈。

现有研究存在的具体挑战或空白 (Gap)：

• 非标准 CNNs 的局限性： 大多数先前的 PPML 工作采用非标准 CNNs，例如减少层数或用低度多项式替换激活函数。这种方法通常需要重新训练 (retraining) 模型，但训练过程本身成本高昂，且访问训练数据集常受数据隐私限制。此外，为大型数据集设计非标准 CNNs 也很困难。因此，直接使用预训练好的标准 CNNs (Standard CNNs, SCNNs) 具有更强的实用价值。
• 交互式 PPML 的通信瓶颈： 结合同态加密 (HE) 和安全多方计算 (Secure Multi-Party Computation, MPC) 的交互式 PPML 需要服务器和客户端之间进行大量数据通信，例如一个 ReLU 函数可能需要 19KB 的通信量，导致处理一张 CIFAR-10 图像的 ResNet-20 或 ResNet-32 可能需要几 GB 的通信。
• 非交互式 PPML 的深度限制和性能问题： 仅使用 FHE 的非交互式 PPML 受限于可用层级消耗 (level consumption)，这使得大多数方法只能支持少量层。虽然自举/引导 (bootstrapping) 操作可以任意增加可用层级，但其计算开销巨大。Lee et al., 2022b 首次实现了带自举的标准 ResNet-20，但其实现存在以下严重问题：

  • 高推理延迟： 即使使用 64 个 CPU 线程，ResNet-20 的推理也需要 10,602 秒，远不能满足实际应用需求。

  • 低安全级别： 其安全级别低于标准的 128 位。

  • 深度限制： 尚未能实现比 ResNet-20 更深的 CNNs。

  • 低效率数据打包： 只将单个通道数据打包到密文中，导致自举次数过多，且参数和层级消耗未优化，进一步加剧了问题。

  • 近似 ReLU 的稳定性问题： 深度网络中 近似 ReLU (APR) 操作可能导致数值发散。

    这篇论文的切入点或创新思路： 本文的目标是解决 Lee et al., 2022b 存在的这些问题，实现实用化的、可用于 VDSCNNs 的 PPML。其核心思路在于：

1. 优化数据打包和卷积算法： 引入多路复用打包和多路复用并行卷积，显著减少自举操作的次数和密钥切换操作 (Key-Switching Operation, KSO) 的数量。
2. 解决数值稳定性问题： 提出去虚部引导，防止 APR 在深度网络中因累积的虚部噪声而发散。
3. 精细化参数和层级管理： 优化 FHE 参数和计算流程，减少层级消耗，并达到标准的安全级别。

2.2. 核心贡献/主要发现

论文最主要的贡献可以总结为以下几点：

• 显著降低自举运行时： 通过使用一种紧凑的多路复用打包 (multiplexed packing) 方法，并提出高效的多路复用并行卷积 (multiplexed parallel convolution) 算法，极大地减少了自举操作的总运行时。多路复用并行卷积通过充分利用密文槽位，将所需的旋转次数减少了 62%。
• 解决深度网络中的灾难性发散问题： 首次发现并解决了 VDSCNNs 在 RNS-CKKS 方案上使用 APR 时因虚部累积噪声导致的灾难性发散现象。通过引入去虚部引导 (imaginary-removing bootstrapping) 解决了这一问题，确保了深度网络推理的准确性。
• 优化 FHE 参数和层级消耗： 精心优化了 FHE 参数设置，包括多项式度、模数大小和密钥汉明权重，以实现更快的推理速度和标准的 128 位安全级别。同时，通过巧妙地整合卷积、批归一化和缩放操作，减少了层级消耗。
• 性能大幅提升：
  • 对于 ResNet-20，实现了比 Lee et al., 2022b 低 4.67 倍的推理延迟（2,271秒 对比 10,602秒，且本文仅使用 1 个 CPU 线程，而先前工作使用了 64 个 CPU 线程）。
  • 摊销运行时（每张图像的运行时）减少了 134 倍（79秒 对比 10,602秒），这对于处理大量图像的服务器场景尤为关键。
• 首次实现超深 ResNet 模型： 首次在 RNS-CKKS 方案上成功以高准确率实现了 ResNet-32/44/56/110 等更深的网络模型，并且这些模型的准确率非常接近于其明文骨干 (backbone) CNNs 的准确率。
• 开源代码： 提供了其实现的源代码，促进了社区的进一步研究和应用。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 全同态加密 (Fully Homomorphic Encryption, FHE)

概念定义： 全同态加密 (FHE) 是一种加密技术，它允许用户在加密数据上直接执行任意计算（包括加法和乘法），而无需先解密数据。计算结果仍然是加密的，并且在解密后与在明文数据上执行相同计算得到的结果一致。FHE 是实现隐私保护机器学习 (PPML) 的核心技术之一，因为它使得数据可以在云端或其他不受信任的环境中进行处理，同时确保原始数据的机密性。

3.1.2. RNS-CKKS 方案 (Residue Number System variant Cheon-Kim-Kim-Song scheme)

概念定义： RNS-CKKS 方案是 FHE 领域中一种流行的近似同态加密方案，由 Cheon、Kim、Kim 和 Song 在 2018 年提出，是 CKKS 方案的一个变体，使用了剩余数系统 (Residue Number System, RNS) 来优化性能。它专门设计用于处理实数或复数的定点算术运算，非常适合机器学习中的浮点数计算。

• 密文 (Ciphertext)： 在 RNS-CKKS 方案中，一个密文通常表示为 $(b, a) \in R_Q^2$，其中 $R_Q = \mathbb{Z}_Q[X] / \langle X^N + 1 \rangle$ 是一个多项式环， $Q$ 是一个大整数，通常是多个素数的乘积。
• 槽 (Slots)： RNS-CKKS 方案支持 SIMD (Single Instruction, Multiple Data) 操作，即一个密文可以同时加密多个数据。通常，$N/2$ 个实数（或复数）可以被加密到单个密文的 $N/2$ 个槽中。我们将 $N/2$ 记为 $n_t$。
• 同态操作： RNS-CKKS 方案支持基本的同态操作：
  • 同态加法 ($\oplus$)： [u]\oplus$[v] = [u + v]$，对加密向量进行逐元素加法。
  • 同态标量乘法/逐元素乘法 ($\odot$)： [u]\odot$v = [u$\cdotv]，对加密向量和明文向量进行逐元素乘法。[u]\odot$[v] = [u$\cdotv]，对两个加密向量进行逐元素乘法。
  • 同态旋转 (Rot)： $Rot([u]; r) = [<u_r>]$，将加密向量的元素循环左移 $r$ 位。
• 层级 (Level)： 每个密文都有一个非负整数层级 $\ell$，代表它可以承受的同态乘法运算的次数。每次同态乘法后，密文的层级会减一，并且需要进行重缩放 (rescaling) 操作来控制噪声增长。
• 重缩放 (Rescaling)： 同态乘法后，为了防止噪声增长过快，需要进行重缩放操作。这个操作会降低密文的模数，从而降低噪声，但同时也会降低密文的层级。
• 自举/引导 (Bootstrapping)： 当密文的层级降到零，无法再进行乘法运算时，自举操作可以将这个“零层级”的密文转换成一个具有更高层级的新密文，从而允许继续进行同态计算。自举是 FHE 能够支持任意深度计算的关键技术，但也是目前 FHE 中最耗时的操作之一。
• 重复槽打包 (Repetitive Slot, RS packing)： 一种特殊的密文打包方法。如果一个消息向量 $\mathbf{v}$ 的大小 $n$ 小于总槽数 $n_t$，可以通过将 $\mathbf{v}$ 重复拼接成 $$(\mathbf{v} | \mathbf{v} | \dots | \mathbf{v})$$ 这种形式，并加密到密文的所有槽中。使用 RS packing 的密文进行自举，通常比其他打包方式的自举运行时更短。
• 密钥切换操作 (Key-Switching Operation, KSO)： KSO 是一种将密文关联的密钥从一个公钥切换到另一个公钥的操作，而不会改变加密的消息。在 RNS-CKKS 方案中，旋转操作和自举操作都需要进行 KSO，并且 KSO 是非常耗时的操作，因此减少 KSO 的次数是优化性能的关键。

3.1.3. 卷积神经网络 (Convolutional Neural Networks, CNNs)

概念定义： 卷积神经网络 (CNNs) 是一种特殊类型的深度神经网络，广泛应用于图像识别、计算机视觉等领域。其核心特点是使用卷积层 (convolutional layers) 来自动提取特征，并通过池化层 (pooling layers) 减少特征图的维度，以及激活函数 (activation functions) 引入非线性。

• 标准 CNNs (Standard CNNs, SCNNs)： 指那些在明文数据上广泛使用和验证的传统 CNN 架构，例如 ResNet、VGG 等，它们通常具有良好的性能和泛化能力。
• 非常深的标准 CNNs (Very Deep Standard CNNs, VDSCNNs)： 指那些具有很多层（例如数十到数百层）的 SCNNs，它们能够学习更复杂、更抽象的特征，从而在更困难的数据集上取得更高的准确率。例如 ResNet-110 就是一个 VDSCNN。

3.1.4. ResNet (Residual Network)

概念定义： ResNet (Residual Network) 是一种在 2015 年由 Kaiming He 等人提出的深度卷积神经网络架构。它引入了残差连接 (Residual Connection) 或跳跃连接 (Skip Connection)，允许信息跳过一个或多个层直接传递到网络的更深层。

• 残差连接： 核心思想是让网络学习残差函数 $F(x) = H(x) - x$，而不是直接学习目标函数 H(x)。通过一个跳跃连接，将输入 $x$ 直接加到几层网络的输出 F(x) 上，最终输出为 $H(x) = F(x) + x$。这种设计有效地解决了训练深度网络时出现的梯度消失和梯度爆炸问题，使得训练数百甚至数千层的深度网络成为可能，从而显著提升了模型的性能。ResNet-20、ResNet-32、ResNet-110 等是不同深度的 ResNet 模型。

3.1.5. 近似 ReLU (Approximate ReLU, APR)

概念定义： ReLU (Rectified Linear Unit) 是深度学习中最常用的激活函数之一，其定义为 $f(x) = \max(0, x)$。然而，在 FHE 方案中直接实现 max 操作非常困难，因为它是一个非线性的比较操作，不直接支持同态乘法。因此，在 FHE 环境中，ReLU 通常需要通过多项式近似 (Polynomial Approximation) 来实现，即将 ReLU 函数近似为一个低次多项式。这种近似的 ReLU 被称为近似 ReLU (Approximate ReLU, APR)。

• 挑战： APR 的精度会影响模型的最终准确率。此外，在 RNS-CKKS 方案中，由于处理的是复数，APR 操作在深度网络中可能会遇到数值稳定性问题，即累积的虚部噪声可能导致近似结果发散，从而使模型失效。

3.2. 前人工作

• 早期隐私保护机器学习 (PPML) 工作：
  • Gilad-Bachrach et al., 2016 (CryptoNets) 等开创性工作提出了在 FHE 上进行神经网络推理的方法。
  • Dathathri et al., 2019 (CHET)、Boemer et al., 2019 (nGraph-HE)、Chou et al., 2018 等专注于优化 FHE 神经网络的编译器或架构。
  • 这些早期工作通常采用非标准 CNNs，即对网络结构进行修改以适应 FHE 的限制，例如减少网络层数，或者用低度多项式替换 ReLU 等激活函数。这种方法虽然在一定程度上实现了隐私保护推理，但需要重新训练这些修改后的网络，且其性能可能不如标准网络，也难以扩展到大型复杂数据集。
• 交互式 PPML (HE + MPC)：
  • Juvekar et al., 2018 (GAZELLE)、Mishra et al., 2020 (DELPHI)、Park et al., 2022 (AESPA) 等工作结合了同态加密 (HE) 和安全多方计算 (MPC) 来实现 PPML。这种方法通过在客户端和服务器之间进行多次交互来完成计算，可以降低单个加密方案的负担。
  • 局限性： 交互式方法的主要缺点是通信开销巨大。例如，Mishra et al., 2020 指出，一个 ReLU 函数的计算就需要 19KB 的数据通信。对于深层网络，这会导致数 GB 甚至更大的通信量，不适用于带宽受限或延迟敏感的应用。
• 基于 FHE 的 SCNN 实现 (Lee et al., 2022b)：
  • Lee et al., 2022b 的工作是本文的直接前身。他们首次成功地在 RNS-CKKS 方案上实现了带有自举操作的标准 ResNet-20，用于加密的 CIFAR-10 图像分类，并取得了高准确率。
  • 局限性： 尽管是重要一步，但该实现面临严重的实用性问题：
    • 高推理延迟： ResNet-20 推理需要 10,602 秒，即使使用了 64 个 CPU 线程。
    • 低安全级别： 安全性低于标准的 128 位。
    • 低效数据打包： 数据打包方式效率低下，一个密文只打包一个通道的数据，导致需要进行大量的自举操作。
    • 未能实现更深网络： ResNet-20 以上的深层网络无法通过其方法实现。
• HEAR (Kim et al., 2021a)：
  • HEAR 提出了一种新的数据打包方法，称为多路复用打包 (multiplexed packing)，以及一种多路复用卷积算法。该方法最初是为了处理 HE 友好型 CNNs 的池化操作和加速卷积而设计的。
  • 本文的重新利用： 本文重新利用了 HEAR 的多路复用打包概念，但将其重新设计和扩展，以解决带步长卷积的 SCNNs 在 FHE 上的自举运行时问题，这与 HEAR 的原始目标有所不同。

3.3. 技术演进

FHE 在深度学习领域的应用，经历了从“实现少量、浅层、非标准模型”到“尝试实现标准、深层模型”的演进。早期工作为了适应 FHE 的高计算开销，不得不牺牲模型复杂度和性能，使用简化网络或替换激活函数。随着 FHE 方案本身的进步（如 CKKS 和 RNS-CKKS 方案在处理实数和近似计算方面的优化，以及自举算法效率的提升），研究者开始尝试在 FHE 上部署更接近实际应用的标准深度学习模型。Lee et al., 2022b 是一个重要的里程碑，它证明了带自举的 SCNN 在 FHE 上的可行性。本文则在此基础上，专注于解决实际部署中的核心瓶颈——性能和安全性，并成功将可支持的网络深度推进到 ResNet-110，代表了这一方向的又一个重大进展。

3.4. 差异化分析

本文的方法与 Lee et al., 2022b 相比，核心区别和创新点在于：

1. 数据打包与卷积效率： Lee et al., 2022b 使用 gap packing 且每个密文只包含一个通道的数据，导致自举次数过多。本文引入并改进了多路复用打包，将多个通道的数据紧凑地打包到一个密文中，并设计了高效的多路复用并行卷积算法，极大地减少了卷积所需的旋转操作（从而减少了 KSO 和自举次数），这是性能提升的关键。
2. 数值稳定性： Lee et al., 2022b 未能解决深度网络中 APR 可能因虚部噪声发散的问题，限制了网络深度。本文提出了去虚部引导，通过主动移除 APR 输入的虚部，确保了深度网络推理的数值稳定性，从而首次成功实现了 ResNet-110。
3. 参数与层级优化： 本文不仅优化了 FHE 参数以达到 128 位安全级别，还通过巧妙地整合卷积和批归一化操作，减少了层级消耗，进一步提升了性能，并减少了自举的需求。
4. 实际性能： 综合上述改进，本文在推理延迟和摊销运行时上都取得了数量级的提升，使得 SCNN 在 FHE 上的推理更具实用性。

4. 方法论

4.1. 方法原理

本文方法的核心思想是，通过对全同态加密 (FHE) 中深度卷积神经网络 (CNNs) 推理过程中的关键瓶颈进行多方面优化，包括数据打包、同态卷积算法、自举 (bootstrapping) 机制以及层级消耗管理，从而显著提高性能和鲁棒性，并首次实现超深 ResNet 模型。

其背后的理论基础和直觉体现在以下几个方面：

• FHE 效率瓶颈： RNS-CKKS 方案中，同态乘法会增加噪声并消耗层级，当层级耗尽时需要昂贵的自举操作。旋转操作需要密钥切换操作 (KSO)，也是主要开销。因此，减少乘法次数、旋转次数和自举次数是提升效率的关键。

• 数据填充密度： 在 FHE 中，密文的槽位是固定且有限的。数据打包越紧凑，每个密文包含的有效信息越多，摊销到每个数据点的计算开销就越低。尤其是在处理带步长 (strided) 的卷积时，稀疏填充会导致大量无效计算和不必要的自举。

• 数值稳定性： RNS-CKKS 方案是基于复数的，而通常的机器学习数据是实数。在长时间的同态计算中，即使原始数据为实数，噪声也会在复数域中累积，特别是虚部噪声，这可能导致近似函数（如 APR）在处理具有虚部噪声的输入时出现错误或发散。

• 计算整合： FHE 运算的层级消耗是有限的。通过将多个线性运算（如缩放、卷积、批归一化）巧妙地整合到一个 FHE 操作中，可以减少所需的层级，从而降低自举频率，或允许网络达到更深的深度。

  本文的直觉是，不是简单地将明文世界的运算映射到密文世界，而是要根据 FHE 的特性进行“FHE-Native”的设计和优化，从底层的数据表示到高层的算法流程，全面考虑 FHE 的效率和鲁棒性约束。

4.2. 核心方法详解

4.2.1. 数据打包方法比较与多路复用打包 (Multiplexed Packing)

在 FHE 中，数据如何打包到密文的槽中对性能至关重要。本文比较了几种数据打包方法，并提出了改进的多路复用打包。

首先，我们回顾论文中 Vec 函数的定义，它是将三维张量映射到一维向量以适应 FHE 密文槽的方法。 一个三维张量 $\overline{A} \in \mathbb{R}^{\overline{h}_i \times \overline{w}_i \times \overline{c}_i}$ 被映射到 $\mathbb{R}^{n_t}$ 中的一维向量 $\mathbf{y} = (y_0, \dots, y_{n_t-1})$，其中 $y_i$ 定义为： $$y_i = \left\{ \begin{array}{ll} \overline{A}_{\lfloor (i \bmod \overline{h}_i \overline{w}_i) / \overline{w}_i \rfloor, i \bmod \overline{w}_i, \lfloor i / \overline{h}_i \overline{w}_i \rfloor}, & 0 \leq i < \overline{h}_i \overline{w}_i \overline{c}_i \\ 0, & \mathrm{otherwise} \end{array} \right.$$ 这里，$\overline{h}_i$, $\overline{w}_i$, $\overline{c}_i$ 分别是输入张量的高度、宽度和通道数。$n_t$ 是密文的总槽数。这个 Vec 函数本质上是将三维张量通过“栅格扫描 (raster scan)”的方式展平为一维向量。 以下是 Vec 函数的示意图 (Figure 2 / 图像 4)。

该图像是一个图表，展示了论文中图4比较的几种数据打包方法，包括(a) 间隙打包，(b) 多通道间隙打包，以及(c) 复用打包，帮助提升同态加密卷积的效率。

Figure 2. Vec function that maps a given tensor in $\mathbb{R}^{\overline{h}_i \times \overline{w}_i \times \overline{c}_i}$ to a vector in $\mathbb{R}^{n_t}$.

论文中，$n_t = 2^{15}$，确保所有张量可以打包到一个密文中。

传统的 Gap packing：

• Lee et al., 2022b 采用了 gap packing (间隙打包) 方法，其特点是在每个密文中只打包一个通道的数据。
• 如图 Figure 1(c) 所示，步长卷积会导致密文槽位中出现间隙，有效数据变得稀疏。例如，对于步长为 $s$ 的卷积，输出数据会以 $k_o h_o \times k_o w_o$ 的形式稀疏打包，其中 $k_o$ 是输出间隙因子。
• 问题： 这种方法要求进行与通道数一样多的自举操作，并且稀疏的打包方式导致大量槽位被零填充，降低了密文利用率，增加了不必要的计算开销。

Gap packing with multiple channels：

• 这是一种对 gap packing 的改进，尝试将多个通道的数据打包到一个密文中。
• 问题： 尽管能减少自举次数，但由于间隙的存在，密文槽位中仍有大量虚拟数据 (dummy slots)，填充密度仍然很低，特别是对于多次步长卷积后，间隙因子会指数级增长，导致自举运行时随网络深度指数级增加。

Multiplexed packing (多路复用打包)：

• 本文借鉴了 HEAR (Kim et al., 2021a) 提出的 multiplexed packing 方法，并对其进行了重新利用。

• 原理： multiplexed packing 的核心思想是将多个通道的明文张量 $h_i \times w_i$ 紧凑地映射到一个更大的多路复用张量 $k_i h_i \times k_i w_i$ 中，然后将多个这样的多路复用张量加密到一个密文中。这通过巧妙地安排数据在二维平面上的位置来实现，使得不同通道的数据紧密相邻。

• 优势： 这种方法显著提高了密文的填充密度，减少了虚拟槽位。从而，每个密文可以承载更多的有效数据，大幅减少所需的自举操作次数和 KSO 数量。

  以下是 Multiplexed packing 的示意图 (Figure 3 / 图像 5)，展示了 $h_i = w_i = 4$ 且 $k_i = 2$ 时的多路复用打包。

  该图像是论文中图5的示意图，展示了参数为 $s=2$，$k_i=2$，$h_i=w_i=4$ 的多路复用输入张量上的多路复用卷积算法，细致地展示了卷积系数乘法和所有输入通道求和的过程。

Figure 3. Multiplexed packing MultPack when `h _ { i } = w _ { i } = 4` and $k _ { i } = 2$ .

正式定义：对于 $$t_i = \lceil c_i / k_i^2 \rceil$$，MultPack 函数将张量 $A \in \mathbb{R}^{h_i \times w_i \times c_i}$ 映射到密文 $\mathsf{Enc}(\mathsf{Vec}(A')) \in \mathbb{R}^{n_t}$，其中 $A'$ 是一个多路复用张量 $A' = (A'_{i_3, i_4, i_5})_{0 \le i_3 < k_i h_i, 0 \le i_4 < k_i w_i, 0 \le i_5 < t_i} \in \mathbb{R}^{k_i h_i \times k_i w_i \times t_i}$，其定义为： $$A'_{i_3, i_4, i_5} = \left\{ \begin{array}{ll} A_{\lfloor i_3 / k_i \rfloor, \lfloor i_4 / k_i \rfloor, k_i^2 i_5 + k_i (i_3 \bmod k_i) + i_4 \bmod k_i}, & \mathrm{if~} k_i^2 i_5 + k_i (i_3 \bmod k_i) + i_4 \bmod k_i < c_i \\ 0, & \mathrm{otherwise} \end{array} \right.$$ 其中 $$0 \le i_3 < k_i h_i, 0 \le i_4 < k_i w_i, \text{and } 0 \le i_5 < t_i$$。 当 $k_i = 1$ 时，MultPack 恢复为普通的栅格扫描打包。

以下是几种打包方法的比较 (Figure 4 / 图像 6)。

该图像是图6，展示了在 $k_i=2$ 且 $c_o=c_n=32$ 条件下的多路复用并行卷积算法的示意图，详细描绘了数据的单输入单输出卷积（SISO convolution）、旋转与求和及零值与旋转的处理流程。

Figure 4. Comparison of several data packing methods.

以下是原文 Table 2，展示了不同打包方法对 ResNet-20 实现所需自举次数的比较。

以下是原文 Table 2 的结果：

Table 2. The number of bootstrappings for implementation of ResNet-20 according to various data packing methods. (a), (b), and (c) imply gap packing, gap packing with multiple channels, and multiplexed packing, respectively. Str_conv1 and Str_conv2 denote the first and the second strided convolutions $s = 2$ in ResNet-20, respectively.

从 Table 2 可以看出，多路复用打包 ((c)) 显著减少了自举次数，并且总 KSO 数量从 42,336 (a) 和 2,238 (b) 降低到 1,512 (c)。

4.2.2. 多路复用并行卷积 (Multiplexed Parallel Convolution)

本文提出了两种多路复用卷积算法：MuLTCoNV 和 MULTPARCoNV，后者是前者的改进版本，旨在进一步减少旋转次数。

传统 SISO 卷积 (Single-Input Single-Output Convolution) 简介： Gazelle (Juvekar et al., 2018) 提出了一种在 HE 上执行单输入单输出 (SISO) 卷积 ($c_i = c_o = 1$) 的方法。

• 输入：包含输入张量的密文。

• 过程：将输入密文旋转 $f_h f_w$ 次（其中 $f_h$ 和 $f_w$ 是滤波器的高度和宽度），每次旋转后乘以包含相应滤波器系数的明文向量，最后将所有乘法结果相加。

• 步长卷积的挑战： 对于步长 ($s$) 大于 1 的卷积，需要在输出密文中引入间隙 (gap)。

  以下是 SISO 卷积在 HE 上的示意图 (Figure 1(b) / 图像 1)。

  该图像是论文中的示意图，展示了SISO卷积操作在明文数据和同态加密（HE）中的实现过程，包含步长s=1和s=2的零填充及加权求和公式 $c_{x,y} = \sum_{max(1,x-2) \le i \le min(3,x)}\sum_{max(1,y-2) \le j \le min(3,y)} a_{x+1-2,y+1-2} \cdot f_{i,j}$。

Figure 1. SISO Convolution on HE (Juvekar et al., 2018; Lee et al., 2022b).

a. MuLTCoNV (Multiplexed Convolution) 算法 MuLTCoNV 算法是 HEAR 中卷积算法的推广，以支持步长卷积 ($s >= 2$)。

• 输入： 包含多路复用输入张量的密文。

• 目标： 输出包含多路复用输出张量的密文。

• 方法： 它同时对多个输入通道执行同态卷积，对所有输入通道的 SISO 卷积输出进行求和，并通过选择并收集输出间隙 $k_o = s k_i$ 的有效值，而不是输入间隙 $k_i$，从而处理步长卷积。

  以下是 MuLTCoNV 算法的示意图 (Figure 5 / 图像 7)。

  该图像是图表，展示了ResNet-110推理过程中使用普通引导和提出的去虚部引导方法时，每层虚部绝对值均值的变化。图中较大虚部对应近似ReLU失败。

Figure 5. Multiplexed convolution algorithm for multiplexed input tensor for $s = 2$ , $k _ { i } = 2$ , and `h _ { i } = w _ { i } = 4`

为了描述 MuLTCoNV 算法，我们首先需要定义 MultWgt 函数和 SUMSLOTS 子例程。

MultWgt 函数： 该函数将权重张量 $U \in \mathbb{R}^{f_h \times f_w \times c_i \times c_o}$ 映射到 $\mathbb{R}^{n_t}$ 中的一个元素。 首先，定义三维多路复用权重张量 $\overline{U}'^{(i_1, i_2, i)} = (\overline{U}'^{(i_1, i_2, i)}_{i_3, i_4, i_5})_{0 \le i_3 < k_i h_i, 0 \le i_4 < k_i w_i, 0 \le i_5 < t_i} \in \mathbb{R}^{k_i h_i \times k_i w_i \times t_i}$，对于给定的 $i_1, i_2, i$（其中 $0 \le i_1 < f_h, 0 \le i_2 < f_w, \text{and } 0 \le i < c_o$），定义如下： $$\overline{U}'^{(i_1, i_2, i)}_{i_3, i_4, i_5} = \left\{ \begin{array}{ll} 0, & \mathrm{if~} k_i^2 i_5 + k_i (i_3 \bmod k_i) + i_4 \bmod k_i \ge c_i \\ & \mathrm{or~} \lfloor i_3 / k_i \rfloor - (f_h - 1) / 2 + i_1 \notin [0, h_i - 1] \\ & \mathrm{or~} \lfloor i_4 / k_i \rfloor - (f_w - 1) / 2 + i_2 \notin [0, w_i - 1], \\ U_{i_1, i_2, k_i^2 i_5 + k_i (i_3 \bmod k_i) + i_4 \bmod k_i, i}, & \mathrm{otherwise}, \end{array} \right.$$ 其中 $$0 \le i_3 < k_i h_i, 0 \le i_4 < k_i w_i, \text{and } 0 \le i_5 < t_i$$。 然后，MultWgt 函数定义为 MultWgt(U;i_1, i_2, i$) = Vec($\overline{U}'^{(i_1, i_2, i)})。

SUMSLOTS 算法： 该子例程用于将密文中相隔 $p$ 个位置的 $m$ 个槽位值相加。 以下是原文 Algorithm 1 的内容： Algorithm 1 SUMSLOTS(cta; m, p)

1: Input: Tensor ciphertext cta, number of added slots m, and gap p
2: Output: Tensor ciphertext ctc
3: ctb^(0) <- cta
4: for j <- 1 to floor(log2 m) do
5:     ctb^(j) <- ctb^(j-1) $\oplus$ Rot(ctb^(j-1); 2^(j-1) * p)
6: end for
7: ctc <- ctz_ero (initialize with all-zeros ciphertext)
8: for j <- 0 to floor(log2 m) - 1 do
9:     if floor(m / 2^j) mod 2 == 1 then
10:        ctc <- ctc $\oplus$ Rot(ctb^(j); floor(m / 2^(j+1)) * 2^(j+1) * p)
11:    end if
12: end for
13: Return ctc

• 输入： 张量密文 $ct_a$，要相加的槽位数 $m$，以及间隙 $p$。
• 输出： 结果张量密文 $ct_c$。
• 解释： 这个算法通过一系列的旋转 (Rot) 和同态加法 ($\oplus$)，实现了对密文中特定模式槽位的求和。它利用了二进制分解的思想，在 log(m) 次迭代中完成求和，每次迭代都将密文旋转 $2^{j-1} \cdot p$ 个位置，然后与原密文相加。

MuLTCoNV 算法： 以下是原文 Algorithm 2 的内容： Algorithm 2 MuLTCoNV(ct', U )

1: Input: Multiplexed tensor ciphertext ct'a and weight tensor U
2: Output: Multiplexed tensor ciphertext ct'd
3: ct'd <- ctz_ero
4: for i_1 <- 0 to f_h - 1 do
5:     for i_2 <- 0 to f_w - 1 do
6:         ct'^(i_1, i_2) <- Rot(ct'a; k_i^2 w_i (i_1 - (f_h - 1) / 2) + k_i (i_2 - (f_w - 1) / 2))
7:     end for
8: end for
9: for i <- 0 to c_o - 1 do
10:    ct'b <- ctz_ero
11:    for i_1 <- 0 to f_h - 1 do
12:        for i_2 <- 0 to f_w - 1 do
13:            ct'b <- ct'b $\oplus$ ct'^(i_1, i_2) $\odot$ MultWgt(U; i_1, i_2, i)
14:        end for
15:    end for
16:    ct'c <- SUMSLOTS(ct'b; k_i, 1)
17:    ct'c <- SUMSLOTS(ct'c; k_i, k_i w_i)
18:    ct'c <- SUMSLOTS(ct'c; t_i, k_i^2 h_i w_i)
19:    ct'd <- ct'd $\oplus$ Rot(ct'c; -floor(i / k_o^2) k_o^2 h_o w_o - floor((i mod k_o^2) / k_o) k_o w_o - (i mod k_o)) $\odot$ Vec(S'^(i))
20: end for
21: Return ct'd

• 输入： 多路复用张量密文 ct'_a 和权重张量 $U$。
• 输出： 多路复用张量密文 ct'_d。
• 解释：
  • 步骤 4-8： 对输入密文 ct'_a 进行一系列旋转，以模拟卷积核在输入张量上的滑动。每个 $ct'^(i_1, i_2)$ 对应于输入张量在卷积核某个位置上的视图。旋转量根据输入间隙 $k_i$ 和输入宽度 $w_i$ 以及卷积核位置 $i_1, i_2$ 计算。
  • 步骤 9-15： 对于每个输出通道 $i$，计算其 SISO 卷积结果。这通过将旋转后的输入密文 $ct'^(i_1, i_2)$ 与对应的明文权重 $MultWgt(U; i_1, i_2, i)$ 进行逐元素乘法，然后将所有结果同态相加得到 ct'_b。
  • 步骤 16-18： 使用 SUMSLOTS 子例程收集 ct'_b 中的有效数据。这些 SUMSLOTS 调用用于在三个维度上（宽度、高度、通道）对多路复用张量中的相关值进行求和，从而得到每个输出位置的最终卷积结果。
  • 步骤 19： 将处理后的 ct'_c 旋转到其在输出多路复用张量中的正确位置，并与一个选择张量 $Vec(S'^(i))$ 进行逐元素乘法。$S'^(i)$ 是一个特殊的选择张量，用于在输出槽位中选择性地放置有效结果并丢弃无效的虚拟数据。这个步骤将不同输出通道的结果整合到最终的输出密文 ct'_d 中。

b. MULTPARCoNV (Multiplexed Parallel Convolution) 算法 MULTPARCoNV 是 MuLTCoNV 的改进，旨在进一步减少旋转次数，特别是当需要为多个输出通道执行 SISO 卷积时。其核心思想是利用密文中的空闲槽位，并行处理多个输出通道的计算。

• 多路复用并行打包 (MultParPack)：
  • MultParPack 函数将 $p_i$ 个相同的多路复用张量打包到一个密文中。其中 $$p_i = 2^{\lfloor \log_2 (n_t / (k_i^2 h_i w_i t_i)) \rfloor}$$ 表示可以打包的副本数量。
  • 如果 $k_i^2 h_i w_i t_i \nmid n_t$，则在 $p_i$ 副本之间填充零。
  • $MultParPack(A) =$\bigoplus_{j=0}^{p_i-1} \mathsf{Rot}(\mathsf{MultPack}(A); j(n_t / p_i))

，这意味着它通过一系列旋转和加法，将 `MultPack(A)` 的

p_i

个副本放置在密文的不同段中。

        以下是 `MultParPack` 的示意图 (Figure 10 / 图像 2)。

        ![Figure 1. SISO Convolution on HE (Juvekar et al., 2018; Lee et al., 2022b).](/files/papers/690707318fdab0b9b2fe5880/images/2.jpg)
        *该图像是一个示意图，展示了输入三维张量通过 Vec 函数映射到一维向量的过程，涉及维度转换和索引排列，公式表达为 $\mathbb{R}^{\overline{h}_i \times \overline{w}_i \times \overline{c}_i} \to \mathbb{R}^{n_t}$。*

Figure 10. Multiplexed parallel packing method MultParPack when $k _ { i } ^ { 2 } h _ { i } w _ { i } t _ { i } \\mid n _ { t }$ .

*   **`ParMultWgt` 函数：**
    *   该函数类似于 `MultWgt`，但针对并行处理进行了调整。它将权重张量 $U \in \mathbb{R}^{f_h \times f_w \times c_i \times c_o}$ 映射到 $\mathbb{R}^{n_t}$ 中的一个元素，用于多路复用并行卷积。
    *   首先定义 $\overline{U}''^{(i_1, i_2, i_3)} = (\overline{U}''^{(i_1, i_2, i_3)}_{i_5, i_6, i_7})_{0 \le i_5 < k_i h_i, 0 \le i_6 < k_i w_i, 0 \le i_7 < t_i p_i} \in \mathbb{R}^{k_i h_i \times k_i w_i \times t_i p_i}$，对于 $0 \le i_1 < f_h, 0 \le i_2 < f_w, \text{and } 0 \le i_3 < q$：

\overline{U}''^{(i_1, i_2, i_3)}_{i_5, i_6, i_7} = \left\{ \begin{array}{ll} 0, & \mathrm{if~} k_i^2 (i_7 \bmod t_i) + k_i (i_5 \bmod k_i) + i_6 \bmod k_i \ge c_i \\ & \mathrm{or~} \lfloor i_7 / t_i \rfloor + p_i i_3 \ge c_o \\ & \mathrm{or~} \lfloor i_5 / k_i \rfloor - (f_h - 1) / 2 + i_1 \notin [0, h_i - 1] \\ & \mathrm{or~} \lfloor i_6 / k_i \rfloor - (f_w - 1) / 2 + i_2 \notin [0, w_i - 1], \\ U_{i_1, i_2, k_i^2 (i_7 \bmod t_i) + k_i (i_5 \bmod k_i) + i_6 \bmod k_i, \lfloor i_7 / t_i \rfloor + p_i i_3}, & \mathrm{otherwise}, \end{array} \right.

其中

0 \le i_5 < k_i h_i, 0 \le i_6 < k_i w_i, \text{and } 0 \le i_7 < t_i p_i

。
    然后，`ParMultWgt` 定义为 `ParMultWgt(`U`;`i_1, i_2, i_3$) = Vec($\overline{U}''^{(i_1, i_2, i_3)}`)`。

以下是 `MULTPARCoNV` 算法的示意图 (Figure 6 / 图像 8)。

![Figure 8. Level optimization by integrating computations.](/files/papers/690707318fdab0b9b2fe5880/images/8.jpg)
*该图像是论文中的示意图，展示了通过整合计算实现的层级优化方法。左侧为原始操作流程，右侧为优化后通过参数调整和计算合并减少运算层级的过程。*

Figure 6. Multiplexed parallel convolution algorithm when $k _ { i } = 2$ and `c _ { o } = c _ { n } = 3 2` .

**`MULTPARCoNV` 算法：**
以下是原文 Algorithm 3 的内容：
**Algorithm 3 MULTPARCoNV(ct , U )**

1: Input: Parallly multiplexed tensor ciphertext ct''a and weight tensor U 2: Output: Parallelly multiplexed tensor ciphertext ct''d 3: ct''d <- ctz_ero 4: for i_1 <- 0 to f_h - 1 do 5: for i_2 <- 0 to f_w - 1 do 6: ct''^(i_1, i_2) <- Rot(ct''a; k_i^2 w_i (i_1 - (f_h - 1) / 2) + k_i (i_2 - (f_w - 1) / 2)) 7: end for 8: end for 9: for i_3 <- 0 to q - 1 do 10: ct''b <- ctz_ero 11: for i_1 <- 0 to f_h - 1 do 12: for i_2 <- 0 to f_w - 1 do 13: ct''b <- ct''b $\oplus$ ct''^(i_1, i_2) $\odot$ ParMultWgt(U; i_1, i_2, i_3) 14: end for 15: end for 16: ct''c <- SUMSLOTS(ct''b; k_i, 1) 17: ct''c <- SUMSLOTS(ct''c; k_i, k_i w_i) 18: ct''c <- SUMSLOTS(ct''c; t_i, k_i^2 h_i w_i) 19: for i_4 <- 0 to min(p_i - 1, c_o - 1 - p_i i_3) do 20: i <- p_i i_3 + i_4 21: ct''d <- ct''d $\oplus$ Rot(ct''c; -floor(i / k_o^2) k_o^2 h_o w_o + floor(n_t / p_i) (i mod p_i) - floor((i mod k_o^2) / k_o) k_o w_o - (i mod k_o)) $\odot$ Vec(S'^(i)) 22: end for 23: end for 24: for j <- 0 to log2 p_o - 1 do 25: ct''d <- ct''d $\oplus$ Rot(ct''d; -2^j (n_t / p_o)) 26: end for 27: Return ct''d

*   **输入：** 并行多路复用张量密文 `ct''_a` 和权重张量 $U$。
*   **输出：** 并行多路复用张量密文 `ct''_d`。
*   **解释：**
    *   **步骤 4-8：** 与 `MuLTCoNV` 类似，对输入密文进行旋转以模拟卷积核滑动。
    *   **步骤 9-15：** 核心优化在于这一部分。`MULTPARCoNV` 并不像 `MuLTCoNV` 那样对每个输出通道进行独立的乘法求和，而是利用 `ParMultWgt` 同时处理多个输出通道的权重，从而在一个乘法步骤中并行计算多个输出通道的结果。$q =$\lceil c_o / p_i \rceil

代表了需要进行多少次这样的并行组计算。 * 步骤 16-18： 同样使用 SUMSLOTS 收集有效数据。 * 步骤 19-22： 这一步将并行计算的输出通道结果进行整理和放置。它通过旋转 ct''_c 并与选择张量 $Vec(S'^(i))$ 进行逐元素乘法，将 $p_i$ 个并行计算的通道结果放置到正确的位置。$floor(n_t / p_i) (i mod p_i)$ 这部分旋转量确保了不同的并行通道结果被放置到密文中不同的 $p_i$ 副本段中。 * 步骤 24-26： 对 ct''_d 进行额外的旋转和加法，以聚合 $p_o$ 个并行输出副本，确保最终输出的紧凑性和正确性。

• 旋转次数比较： MuLTCoNV 和 MULTPARCoNV 在 ResNet-20 推理中所需的旋转次数分别为 4,360 和 1,657，这意味着 MULTPARCoNV 将旋转次数（即 KSO 数量）减少了 62%，这是其高效性的主要来源。

4.2.3. 去虚部引导 (Imaginary-Removing Bootstrapping)

问题： RNS-CKKS 方案在底层处理复数。虽然通常会将实数数据加密到复数槽的实部，并假设虚部为零，但在深度神经网络推理过程中，由于噪声的累积，密文的虚部会逐渐不再为零。这对于依赖于多项式近似的函数，特别是近似 ReLU (APR)，可能导致灾难性发散 (catastrophic divergence)。

• APR 的发散机制： APR 通常由一系列的极小极大近似多项式 (minimax approximate polynomials) 组成。如果一个多项式的输入值超出了其设计好的近似范围，其输出可能会剧烈发散。论文中举例，如果一个多项式 $p_1(x)$ 的输出 $p_1(x_0)$ 接近其局部最大值 $1+b$，当输入 $x$ 包含纯虚部噪声时，泰勒展开式 $T_{p_1, 2}(x) = p_1(x_0) - a(x-x_0)^2

会导致 `Re(`p_1(x)`)` 超过

1+b

，从而使后续的 `APR` 步骤完全发散。

    **解决方案：** 提出**去虚部引导 (Imaginary-Removing Bootstrapping)**。
*   **原理：** 在每次 `APR` 操作之前，引入一个同态操作来显式地去除密文中的虚部。这通过计算 $Re(x) = x/2 +$\overline{x/2}

实现。其中 $\overline{x/2}$ 是 $x/2$ 的同态共轭 (homomorphic conjugation)。

• 实现： 通过在自举过程中，将 SLOTToCoEFF 操作中所有系数减半，并同态计算 $v + \bar{v}$ 来实现。

• 成本： 额外成本非常低，只需一个 KSO 用于同态共轭，且不消耗额外的层级。

• 效果： 显著抑制了虚部噪声的累积，防止了 APR 在深度网络中的灾难性发散，从而保持了模型的准确率。

  以下是 去虚部引导 的效果对比图 (Figure 7 / 图像 9)。

  该图像是论文中图9所示的示意图，展示了基于RNS-CKKS方案的ResNet-20/32/44/56/110网络结构。输入图像张量表示为 $A \in \mathbb{R}^{32\times32\times3}$，经过多层卷积、批归一化、Bootstrapping及近似ReLU处理，最终通过平均池化和全连接层输出。

Figure 7. Mean of absolute values of imaginary parts after each layer when performing ResNet-110 inference using the normal bootstrapping and the proposed imaginary-removing bootstrapping.

从 Figure 7 可以看出，使用普通引导时，虚部绝对值均值在第 69 层之后开始发散，而使用去虚部引导时，虚部噪声始终保持在很低的水平。

4.2.4. 层级消耗优化 (Optimization of Level Consumption)

在 RNS-CKKS 方案中，层级消耗是限制网络深度的关键因素。本文通过整合计算来优化层级消耗。

• 操作顺序： 在本文的实现中，一个典型的层操作顺序是：卷积 (Convolution) -> 批归一化 (Batch Normalization) -> 自举 (Bootstrapping) -> 近似 ReLU (APR)。
• 缩放操作： 由于自举和 APR 通常只适用于 $[-1, 1]$ 范围内的输入值，因此在自举前需要进行 $1/B$ 的缩放，在 APR 后进行 $B$ 的缩放，以保持数值范围。
• 整合计算：

  • 本文提出将批归一化操作中的常数（即缩放因子 $a$）与卷积的选择过程进行整合。

  • 同时，在批归一化过程中，将考虑缩放因子 $B$ 的修改后的常数向量进行加法。

  • 通过这种巧妙的整合，可以在不增加层级消耗的情况下完成多个操作，从而节省了三个层级。

    以下是层级优化的示意图 (Figure 8 / 图像 10)。

    该图像是图10，展示了当 $k_{i}^2 h_{i} w_{i} t_{i} \mid n_{t}$ 时的多路复用并行打包方法 MultParPack，图中示意多个数据块的复制及并行排列过程。

Figure 8. Level optimization by integrating computations.

MULTPARCoNVBN (Convolution/Batch Normalization Integration) 算法： 批归一化 (Batch Normalization) 通常表示为 $C_j \cdot (A_{i_1, i_2, j} - M_j) + I_j$，其中 C, M, I 是批归一化的常数向量。这个操作可以重写为 $\mathsf{Vec}(\overline{C}) \cdot \mathsf{Vec}(A) + (\mathsf{Vec}(\overline{I}) - \mathsf{Vec}(\overline{C}) \cdot \mathsf{Vec}(\overline{M}))$。 通过将缩放操作、卷积和批归一化整合，可以得到等效的计算公式： $$\begin{array}{c} \left( \mathbf{c}'' \odot \mathsf{MULTPARCONV}(\mathsf{ct}_\times, BU) \oplus \left( \mathbf{i}'' - \mathbf{c}'' \cdot \mathbf{m}'' \right) \right) \odot \left( \frac{1}{B} \cdot \mathbf{1} \right) \\ = \mathbf{c}'' \odot \mathsf{MULTPARCONV}(\mathsf{ct}_\times, U) \oplus \frac{1}{B} \left( \mathbf{i}'' - \mathbf{c}'' \cdot \mathbf{m}'' \right) \end{array}$$ 其中 $$\mathbf{c}''`,`\mathbf{m}''`,`\mathbf{i}''$$ 是经过 ParBNConst 转换的批归一化常数向量。 这个整合可以在没有额外层级消耗的情况下完成。

以下是原文 Algorithm 7 的内容： Algorithm 7 MULTPARCoNVBN(ct''a , U , $\overline{C, M, I}$)

1: Input: Parallelly multiplexed tensor ciphertext ct''a, weight tensor U, and batch normalization constant vectors $\overline{C, M, I}$
2: Output: Parallelly multiplexed tensor ciphertext ct''d
3: ct''d <- ctz_ero
4: for i_1 <- 0 to f_h - 1 do
5:     for i_2 <- 0 to f_w - 1 do
6:         ct''^(i_1, i_2) <- Rot(ct''a; k_i^2 w_i (i_1 - (f_h - 1) / 2) + k_i (i_2 - (f_w - 1) / 2))
7:     end for
8: end for
9: for i_3 <- 0 to q - 1 do
10:    ct''b <- ctz_ero
11:    for i_1 <- 0 to f_h - 1 do
12:        for i_2 <- 0 to f_w - 1 do
13:            ct''b <- ct''b $\oplus$ ct''^(i_1, i_2) $\odot$ ParMultWgt(U; i_1, i_2, i_3)
14:        end for
15:    end for
16:    ct''c <- SUMSLOTS(ct''b; k_i, 1)
17:    ct''c <- SUMSLOTS(ct''c; k_i, k_i w_i)
18:    ct''c <- SUMSLOTS(ct''c; t_i, k_i^2 h_i w_i)
19:    for i_4 <- 0 to min(p_i - 1, c_o - 1 - p_i i_3) do
20:        i <- p_i i_3 + i_4
21:        ct''d <- ct''d $\oplus$ Rot(ct''c; -floor(i / k_o^2) k_o^2 h_o w_o + floor(n_t / p_i) (i mod p_i) - floor((i mod k_o^2) / k_o) k_o w_o - (i mod k_o)) $\odot$ (ParBNConst(C) $\cdot$ Vec(S'^(i)))
22:    end for
23: end for
24: for j <- 0 to log2 p_o - 1 do
25:    ct''d <- ct''d $\oplus$ Rot(ct''d; -2^j (n_t / p_o))
26: end for
27: ct''d <- ct''d $\ominus$ (1/B) (ParBNConst(C) $\cdot$ ParBNConst(M) - ParBNConst(I))
28: Return ct''d

• 输入： 并行多路复用张量密文 ct''_a、权重张量 $U$、以及批归一化常数向量 $\overline{C, M, I}$。
• 输出： 并行多路复用张量密文 ct''_d。
• 解释： 这个算法是 MULTPARCoNV 的扩展，它在步骤 21 的乘法中，不再仅仅与选择张量 $Vec(S'^(i))$ 相乘，而是与 (ParBNConst(C)\cdot$Vec(S'^(i)))$ 相乘，将批归一化中的缩放因子 $C$ 整合到卷积的选择过程中。最后，在步骤 27，它减去一个常数项 (1/B) (ParBNConst(C)\cdotParBNConst(M) - ParBNConst(I))，这包含了批归一化中的偏移和缩放因子 $B$。这个整合使得批归一化操作的线性部分不消耗额外的层级，从而实现了层级优化。

4.2.5. RNS-CKKS 方案上的 ResNet 架构 (The Proposed Architecture for ResNet on the RNS-CKKS Scheme)

本文在 RNS-CKKS 方案上实现了 ResNet-20/32/44/56/110，并集成了上述优化技术。

a. 参数设置 (Parameter Setting)

• 多项式度 (Polynomial Degree) N： $N = 2^{16}$。
• 槽数 (Number of Slots) $n_t$： $n_t = 2^{15}$。
• 安全级别： 达到标准的 128 位安全。
  • 密钥汉明权重： 从 Lee et al., 2022b 的 64 增加到 192，这增加了可用模数位数。
  • 模数大小： base modulus、special modulus 和 bootstrapping modulus 设置为 51 位素数（原为 60 位），default modulus 设置为 46 位素数（原为 50 位）。尽管模数长度减少，但通过高精度自举技术和参数优化仍能保持准确性。
  • 总模数位长： 1553 位，符合 128 位安全要求 (基于稀疏秘密密钥 LWE 问题的混合双重攻击分析)。
• 自举 (Bootstrapping)：
  • 使用 RS bootstrapping，消息大小 $n = 2^{14}, 2^{13}, 2^{12}$。
  • 采用 improved multi-interval Remez algorithm (Lee et al., 2021c) 的高精度自举技术。
  • CoEFFToSLOT 和 SLOTToCoEFF 过程使用三层级 level collapsing technique。
  • 近似多项式度：余弦函数 59，反正弦函数 1，双角公式数量为 2。
  • 总层级消耗：自举消耗 14 层，总模数消耗 644。
  • 定义了不同消息大小的去虚部自举：BOOT14 ($n=2^{14}$)，BOOT13 ($n=2^{13}$)，BOOT12 ($n=2^{12}$)。
• 近似 ReLU (APR)：
  • 使用 APPRELU(\mathsf{ct_x})，由复合极小极大近似多项式组成。
  • 精度参数 $\alpha = 13$，多项式度集合 $\{15, 15, 27\}$。
  • $\ell_1$ 范数近似误差小于 $2^{-13}$，这使得可以直接使用标准 ResNet 模型的预训练参数，无需再训练。

b. 网络结构 (The Proposed Structure) 本文实现了 ResNet-20/32/44/56/110，其基本构建块由 MULTPARCoNVBN (这里简称为 CoNvBN)、APPRELU、BOOT、AvGPooL、DowNsAMP 和全连接层组成。

以下是 RNS-CKKS 方案上的 ResNet 结构 (Figure 9 / 图像 11)。

该图像是示意图，展示了AvGPoOL算法中选择并顺序排列$k_i^2 t_i$个有效值的重排过程，图中用箭头标示了数据如何从多维块映射到一维序列。

Figure 9. Structure of the proposed ResNet-20/32/44/56/110 on the RNS-CKKS scheme. The input image is packed in `c t _ { A }` in a raster scan fashion and using RS packing.

* **输入：** `CIFAR-10` 或 `CIFAR-100` 图像，打包到 $ct_A$ 中。 * **层级流程：** * 每个残差块通常包含两个 `CoNvBN` 层，一个 `APPRELU` 激活层，以及一个 `BOOT` (自举) 操作。 * `DowNsAMP` 和 `AvGPooL` 操作在需要时用于下采样和平均池化。 * 与 `Lee et al., 2022b` 相比，本文的实现在一个层中只需一次自举，而不是两次，这得益于层级消耗的显著降低。 * **全连接层：** 使用 `Halevi & Shoup, 2014` 的对角线方法实现。

c. 附录中其他算法 为了支持多路复用并行张量，论文还提出了 PARMULTBN、DOWNSAMP 和 AvGPOOL 算法。

PARMULTBN (Multiplexed Parallel Batch Normalization) 算法： 该算法在并行多路复用张量上执行批归一化。 首先定义 ParBNConst 函数，它将批归一化常数向量 $H \in \mathbb{R}^{c_i}$ 映射到 $\mathbb{R}^{n_t}$ 中的一个向量 $\mathbf{h}'' = (h_0'', h_1'', \dots, h_{n_t-1}'')$： $$h''_j = \left\{ \begin{array}{ll} 0, & \mathrm{if~} j \bmod (n_t / p_i) \ge k_i^2 h_i w_i t_i \mathrm{~or~} k_i^2 i_3 + k_i (i_1 \bmod k_i) + i_2 \bmod k_i \ge c_i \\ H_{k_i^2 i_3 + k_i (i_1 \bmod k_i) + i_2 \bmod k_i}, & \mathrm{otherwise}, \end{array} \right.$$ 其中 $0 \le j < n_t$，$$i_1 = \lfloor ((j \bmod (n_t/p_i)) \bmod k_i^2 h_i w_i) / k_i w_i \rfloor$$，$$i_2 = ((j \bmod (n_t/p_i)) \bmod k_i w_i)$$，$$i_3 = \lfloor (j \bmod (n_t/p_i)) / k_i^2 h_i w_i \rfloor$$。

以下是原文 Algorithm 4 的内容： Algorithm 4 PARMULTBN(ct''a , C , M , I )

1: Input: Parallelly multiplexed tensor ciphertext ct''a and batch normalization constant vectors C , M , I $\in \mathbb{R}^{c_i}$
2: Output: Parallelly multiplexed tensor ciphertext ct''b
3: c'' <- ParBNConst(C), m'' <- ParBNConst(M), i'' <- ParBNConst(I)
4: ct''b <- c'' $\odot$ ct''a $\oplus$ (i'' - c'' $\cdot$ m'')
5: Return ct''b

• 输入： 并行多路复用张量密文 ct''_a 和批归一化常数向量 C, M, I。
• 输出： 并行多路复用张量密文 ct''_b。
• 解释： 该算法通过将批归一化常数向量 C, M, I 转换为并行多路复用形式的明文向量 c'', m'', i''，然后通过一次同态逐元素乘法 ($\odot$) 和一次同态加法 ($\oplus$) 完成批归一化，与明文世界的批归一化公式完全对应。

DOWNSAMP (Multiplexed Parallel Downsampling) 算法： 用于在并行多路复用张量上执行下采样操作。 该算法使用一个选择张量 $S''$ 来实现下采样。选择张量 $S''^(i_1, i_2)$ 定义为： $$S''^{(i_1, i_2)}_{i_3, i_4, i_5} = \left\{ \begin{array}{ll} 1, & \mathrm{if~} (\lfloor i_3 / k_i \rfloor) \bmod 2 = 0 \\ & \mathrm{and~} (\lfloor i_4 / k_i \rfloor) \bmod 2 = 0 \\ & \mathrm{and~} i_3 \bmod k_i = i_1 \\ & \mathrm{and~} i_5 = i_2 \\ 0, & \mathrm{otherwise}, \end{array} \right.$$ 其中 $$0 \le i_3 < k_i h_i, 0 \le i_4 < k_i w_i, \text{and } 0 \le i_5 < t_i$$。

以下是原文 Algorithm 5 的内容： Algorithm 5 DOWNSAMP(ct)

1: Input: Parallelly multiplexed tensor ciphertext ct''a
2: Output: Parallelly multiplexed tensor ciphertext ct''c
3: ct''c <- ctz_ero
4: for i_1 <- 0 to k_i - 1 do
5:     for i_2 <- 0 to t_i - 1 do
6:         i_3 <- floor(((k_i i_2 + i_1) mod (2 k_o)) / 2)
7:         i_4 <- (k_i i_2 + i_1) mod 2
8:         i_5 <- floor((k_i i_2 + i_1) / (2 k_o))
9:         ctb <- ct''a $\odot$ Vec(S''^(i_1, i_2))
10:        ctc <- ctb $\oplus$ Rot(ctb; k_i^2 h_i w_i (i_2 - i_5) + k_i w_i (i_1 - i_3) - k_i i_4)
11:    end for
12: end for
13: ct''c <- Rot(ct''c; -k_o^2 h_o w_o t_i / 8)
14: for j <- 0 to log2 p_o - 1 do
15:    ct''c <- ct''c $\oplus$ Rot(ct''c; -2^j (k_o^2 h_o w_o t_o))
16: end for
17: Return ct''c

• 输入： 并行多路复用张量密文 ct''_a。
• 输出： 并行多路复用张量密文 ct''_c。
• 解释： DOWNSAMP 通过与选择张量 $Vec(S''^(i_1, i_2))$ 进行逐元素乘法来选择特定的数据，然后通过旋转 (Rot) 和同态加法 ($\oplus$) 将选中的数据重新排列到新的位置，以实现下采样并更新间隙因子。

AvGPOOL (Average Pooling) 算法： 该算法不仅执行平均池化，还重新排列索引。

• 原理： 平均池化是对输入张量的 $h_i \times w_i$ 区域求平均值。在 FHE 中，这通过同态求和并乘以 $1/(h_i w_i)$ 来实现。
• 选择向量： 使用一个特殊的选择向量 $\bar{\mathbf{s}}'^{(i_3)}$ 来实现。 $$\bar{\mathbf{s}}'^{(i_3)}_j = \left\{ \begin{array}{ll} \frac{1}{h_i w_i}, & \mathrm{if~} j - k_i i_3 \in [0, k_i - 1] \\ 0, & \mathrm{otherwise}, \end{array} \right.$$ 其中 $0 \le j < n_t$ 和 $0 \le i_3 < k_i t_i$。

以下是 AvGPOOL 的重排过程示意图 (Figure 11 / 图像 3)。

该图像是图示，展示了图3中的多路复用打包（Multiplexed packing）方法，其中 (a) 详细表示不同通道的数据排列，(b) 展示了多路复用打包的简化矩阵表示。图中涉及参数 $h_i = w_i = 4$ 和 $k_i = 2$ 。

Figure 11. Rearranging process that selects and places $k _ { i } ^ { 2 } t _ { i }$ valid values sequentially in AvGPoOL algorithm.

以下是原文 Algorithm 6 的内容： Algorithm 6 AvGPOOL($\mathsf{ct''a}$)

1: Input: Parallelly multiplexed tensor ciphertext ct''a
2: Output: One-dimensional array ciphertext ctb
3: ctb <- ctz_ero
4: for j <- 0 to log2 w_i - 1 do
5:     ct''a <- Rot(ct''a; 2^j * k_i)
6: end for
7: for j <- 0 to log2 h_i - 1 do
8:     ct''a <- Rot(ct''a; 2^j * k_i^2 w_i)
9: end for
10: for i_1 <- 0 to k_i - 1 do
11:    for i_2 <- 0 to t_i - 1 do
12:        ctb <- ctb $\oplus$ Rot(ct''a; k_i^2 h_i w_i i_2 + k_i w_i i_1 - k_i(k_i i_2 + i_1)) $\odot$ $\bar{\mathbf{s}}'^{(k_i i_2 + i_1)}$
13:    end for
14: end for
15: Return ctb

• 输入： 并行多路复用张量密文 ct''_a。
• 输出： 一维数组密文 ctb。
• 解释：
  • 步骤 4-9： 通过一系列旋转和加法操作（这里省略了加法，但实际上 Rot 后会与原值相加，或通过 SUMSLOTS 聚合），对输入密文在宽度和高度维度上进行求和，这是平均池化的第一步。
  • 步骤 10-14： 对于每个通道，通过旋转将求和结果移动到正确位置，并与选择向量 $$\bar{\mathbf{s}}'^{(k_i i_2 + i_1)}$$ 进行逐元素乘法，该选择向量包含 $1/(h_i w_i)$ 的值，从而完成平均池化和结果重排。这个过程将 $k_i^2 t_i$ 个有效值顺序放置到一个一维数组密文中。

5. 实验设置

5.1. 数据集

• 名称： CIFAR-10 和 CIFAR-100。
• 来源： 由 Alex Krizhevsky、Vinod Nair 和 Geoffrey Hinton 收集。
• 规模与特点：
  • 两者均包含 50,000 张用于训练的图像和 10,000 张用于测试的图像。
  • 图像尺寸均为 32x32 像素。
  • CIFAR-10 包含 10 个类别（如飞机、汽车、鸟类等）。
  • CIFAR-100 包含 100 个类别，每个类别有 600 张图像（500 张训练，100 张测试）。
• 选择理由： CIFAR-10 和 CIFAR-100 是计算机视觉领域常用的基准数据集，具有适中的复杂度和图像尺寸，适合用于评估深度学习模型。本文使用这些数据集来评估其在加密数据上实现 ResNet 模型的性能和准确率。
• 样本示例： 论文未直接提供数据集中的具体图像样本，但 CIFAR 数据集包含日常生活中的物体图像，例如：
  • CIFAR-10：飞机、汽车、鸟、猫、鹿、狗、青蛙、马、船、卡车。
  • CIFAR-100：更细粒度的 100 个类别，分为 20 个超类别。

5.2. 评估指标

对论文中出现的每一个评估指标，我们提供完整的说明。

5.2.1. 推理延迟 (Inference Latency)

• 概念定义 (Conceptual Definition): 推理延迟是指一个加密的深度学习模型在接收到加密输入数据后，完成所有必要的计算（包括同态卷积、激活、池化、自举等）并生成加密输出结果所需的时间。它衡量的是模型执行单次推理任务的速度。在隐私保护机器学习中，低推理延迟对于实现实时或近实时应用至关重要。
• 数学公式 (Mathematical Formula): 推理延迟通常以时间单位（如秒）直接测量。它没有一个统一的数学公式，而是通过计时器测量从输入加密到输出加密的整个过程所消耗的时间。 $\text{Latency} = T_{\text{end}} - T_{\text{start}}$
• 符号解释 (Symbol Explanation):
  • $T_{\text{start}}$：推理过程开始的时间点。
  • $T_{\text{end}}$：推理过程结束的时间点。
  • $\text{Latency}$：推理的总耗时。

5.2.2. 摊销运行时 (Amortized Runtime / Runtime per Image)

• 概念定义 (Conceptual Definition): 摊销运行时是指在处理多个（例如一批）加密图像时，平均每张图像所需的推理时间。这对于服务器端需要同时处理大量客户端请求的场景非常重要。通过并行化处理多个图像，总运行时可能会增加，但摊销到每张图像的平均时间可以显著降低，从而提高系统的吞吐量。
• 数学公式 (Mathematical Formula): $$\text{Amortized Runtime} = \frac{\text{Total Runtime for Multiple Images}}{\text{Number of Images}}$$
• 符号解释 (Symbol Explanation):
  • $\text{Total Runtime for Multiple Images}$：处理所有图像的总时间。
  • $\text{Number of Images}$：处理的图像总数量。
  • $\text{Amortized Runtime}$：平均每张图像的推理时间。

5.2.3. 分类准确率 (Classification Accuracy)

• 概念定义 (Conceptual Definition): 分类准确率是衡量一个分类模型性能的最基本指标之一，它表示模型正确预测的样本数量占总样本数量的比例。在隐私保护机器学习中，确保加密推理的准确率与明文推理的准确率相当或接近，是评估方法有效性的关键。如果准确率显著下降，即使隐私得到了保护，模型的实用价值也会大打折扣。
• 数学公式 (Mathematical Formula): $$\text{Accuracy} = \frac{\text{Number of Correct Predictions}}{\text{Total Number of Predictions}} \times 100\%$$
• 符号解释 (Symbol Explanation):
  • $\text{Number of Correct Predictions}$：模型正确分类的样本数量。
  • $\text{Total Number of Predictions}$：模型进行预测的总样本数量。

5.3. 对比基线

本文将自己的方法与以下基线模型进行了比较：

• Lee et al., 2022b 的 ResNet-20 实现： 这是本文主要的对比对象，因为它是第一个在 RNS-CKKS 方案上使用自举技术实现标准 ResNet-20 的工作。本文旨在解决其高延迟和低安全级别的问题。

6. 实验结果与分析

实验在 AMD Ryzen Threadripper PRO 3995WX (2.096 GHz, 64 核) 和 512 GB RAM 的 Ubuntu 20.04 系统上，使用 Microsoft SEAL 库 (SEAL) 进行。评估数据集为 CIFAR-10 和 CIFAR-100。

为了提供上下文，以下是原文 Table 1，展示了 Bootstrapping 在不同槽数下的 KSO 数量和运行时：

以下是原文 Table 1 的结果：

Table 1. The number of KSOs and bootstrapping runtime according to various number of slots for bootstrapping

Table 1 显示，随着槽位数量的增加，Bootstrapping 所需的 `KSO` 数量和运行时也相应增加。这强调了优化数据打包以减少 Bootstrapping 需求的必要性。

6.1. 核心结果分析

6.1.1. 推理延迟 (Latency)

本文对 ResNet-20/32/44/56/110 模型在 RNS-CKKS 方案上进行了推理，并与 Lee et al., 2022b 的结果进行了比较。

以下是原文 Table 3 的结果：

Table 3. Classification runtime for one CIFAR-10/CIFAR-100 image using ResNet on the RNS-CKKS scheme

**分析：** * **ResNet-20 性能对比：** 针对 `ResNet-20`，`Lee et al., 2022b` 的实现需要 10,602 秒 (使用 64 个 CPU 线程)。本文的实现仅需 2,271 秒 (使用单个 CPU 线程)，推理延迟降低了 `4.67` 倍。这一显著提升主要归因于密钥切换操作 (KSO) 数量的大幅减少（本文需要 3,306 个 KSO，而 `Lee et al., 2022b` 需要 384,160 个 KSO，减少了 116 倍）。 * **单线程优势与未来潜力：** 论文强调其实现仅使用一个 CPU 线程。如果未来 `RNS-CKKS` 库能支持多线程操作，或者结合 GPU/硬件加速器，推理延迟有望进一步降低 100 倍甚至 1000 倍。 * **首次实现深层 ResNet：** 本文首次成功在 `RNS-CKKS` 方案上实现了 `ResNet-32/44/56/110`。 * **运行时与层数的关系：** 实验结果显示，随着层数的增加，运行时呈现线性增长，这在分层 HE 方案中是很难实现的，证明了本文方法的效率和可扩展性。 * **自举仍是主要开销：** 从 Table 3 可以看出，`BOOT` (自举) 操作仍然是总运行时间中占比最大的部分，通常占 `72%` 到 `74%`。这表明尽管本文对自举进行了优化，但它依然是 FHE 计算的性能瓶颈。

6.1.2. 摊销运行时 (Amortized Runtime)

对于服务器需要处理多个图像的场景，摊销运行时是一个更重要的指标。

以下是原文 Table 4 的结果：

Table 4. Classification (amortized) runtime for multiple CIFAR10/CIFAR-100 images using ResNet models on the RNS-CKKS scheme

**分析：** * **ResNet-20 摊销运行时对比：** `Lee et al., 2022b` 的 `ResNet-20` 摊销运行时为 10,602 秒。本文的实现，通过使用 50 个线程并行分类 50 张图像，总运行时为 3,973 秒，摊销运行时为 79 秒。这使得摊销运行时比先前工作快了 `134` 倍。 * **多线程利用：** 由于本文的优化实现每层仅需一个自举和卷积，这使得可以利用多线程同时处理多个图像，从而显著降低了每张图像的平均处理时间。这对于实际的隐私保护服务场景具有重要意义。

6.1.3. 准确率 (Accuracy)

准确率是衡量模型性能的关键指标。

以下是原文 Table 5 的结果：

Table 5. Classification accuracies for CIFAR-10/CIFAR-100 images using ResNet models on the RNS-CKKS scheme

**分析：** * **高准确率：** 本文实现的 `ResNet-20/32/44/56/110` 在 `CIFAR-10` 和 `CIFAR-100` 上的分类准确率非常接近其明文骨干 (backbone) CNNs 的准确率。例如，`ResNet-20` 在 `CIFAR-10` 上的骨干准确率为 91.52%，而本文实现的准确率为 91.31%，差异非常小。 * **去虚部引导的重要性：** 这种高准确率得益于本文提出的去虚部引导，它成功解决了深度网络中 `APR` 操作可能导致的灾难性发散问题。这意味着本文的方法能够有效地利用预训练好的标准 `VDSCNNs` 的高准确率，而无需进行耗时的再训练。

6.2. 数据呈现 (表格)

所有核心表格已在 6.1 核心结果分析 中转录并分析。

为了提供更全面的参数信息，以下是附录 H 中原文 Table 6 的内容，展示了 CoNvBN 或 DowNsAMP 过程中使用的各种参数：

以下是原文 Table 6 的结果：

Table 6. Parameters that are used in each CoNvBN or DowNsAMP process

**符号解释：** * `fh, fw`: 滤波器 (filter) 的高度和宽度。 * $s$: 卷积步长 (stride)。 * `hi, ho`: 输入和输出张量的高度。 * `Wi, Wo`: 输入和输出张量的宽度。 * `Ci, co`: 输入和输出通道数。 * `ki, ko`: 输入和输出间隙因子。 * `ti, to`: 输入和输出多路复用张量的通道维度（根据 $k_i$ 或 $k_o$ 计算）。 * `pi, po`: 输入和输出张量的并行副本数量。 * $q$: 并行卷积中处理输出通道组的数量。

6.3. 消融实验/参数分析

论文没有明确进行“消融实验”来独立评估每个组件的贡献。然而，其工作本身可以看作是对 Lee et al., 2022b 的全面改进和优化，其效果通过最终性能提升得到了验证。

• 多路复用打包和并行卷积的贡献： 从 Table 2 可以明显看出，multiplexed packing 相比 gap packing 和 gap packing with multiple channels，显著减少了 ResNet-20 的总自举次数和 KSO 数量。这直接导致了 ResNet-20 推理延迟的 4.67 倍降低。

• 去虚部引导的贡献： Figure 7 直观展示了去虚部引导在控制虚部噪声累积方面的关键作用，从而确保了深层网络（如 ResNet-110）的数值稳定性，进而保证了高准确率。

• 层级消耗优化的贡献： 论文提到通过整合卷积和批归一化，节省了三个层级，这使得在每层只需一次自举成为可能，进一步减少了自举的总体开销。

• FHE 参数的选择： 论文详细介绍了对多项式度、槽数、密钥汉明权重和模数大小的优化选择，以在性能和 128 位安全级别之间取得平衡。这些参数的精细调整对于实现高效和安全的 VDSCNN 至关重要。

  总的来说，论文的实验结果通过对比现有最先进工作，并展示了在更深网络上的首次成功实现，有力地证明了其各项优化策略的有效性。

7. 总结与思考

7.1. 结论总结

本文成功构建了一个高效的、隐私保护的非常深的标准卷积神经网络 (VDSCNN) 模型，可在 RNS-CKKS 全同态加密方案上运行。其主要成就包括：

• 自举运行时最小化： 通过引入多路复用打包方法，并提出创新的多路复用并行卷积算法（MULTPARCoNV），显著减少了所需的密钥切换操作 (KSO) 数量，从而大幅降低了自举操作的总运行时。
• 解决数值发散问题： 首次发现并成功解决了 VDSCNNs 在 RNS-CKKS 方案上执行近似 ReLU (APR) 操作时因虚部噪声累积导致的灾难性发散现象。通过提出去虚部引导 (Imaginary-Removing Bootstrapping)，确保了深度网络推理的数值稳定性和高准确率。
• 层级与参数优化： 优化了同态计算的层级消耗，并采用了更轻量级和更严格的 FHE 参数，不仅提升了推理速度，还达到了标准的 128 位安全级别。
• 显著的性能提升： 相较于现有最先进的工作 (Lee et al., 2022b)，本文的 ResNet-20 实现了 4.67 倍的推理延迟降低和 134 倍的摊销运行时减少。
• 突破网络深度限制： 首次成功在 RNS-CKKS 方案上实现了 ResNet-32/44/56/110 等深层网络模型，且保持了与明文骨干 (backbone) CNNs 相近的准确率。

7.2. 局限性与未来工作

论文本身并未明确列出其局限性，但从其讨论和现有 FHE 技术的通用挑战来看，可以推断：

• 绝对延迟仍然较高： 尽管实现了显著的相对性能提升，但即使是优化后的 ResNet-20 单次推理仍需 2,271 秒，ResNet-110 更是高达 13,282 秒。这对于需要实时响应的许多实际应用场景而言，延迟仍然过高。
• 硬件加速的依赖性： 论文提到未来的潜在改进依赖于多线程 RNS-CKKS 操作的实现以及 GPU 或硬件加速器的使用。这意味着当前纯 CPU 上的性能提升仍有其极限，更广泛的实用性可能需要专用硬件的支持。
• 训练阶段的复杂性： 本文主要关注加密推理，而深度神经网络的训练阶段在 FHE 上仍是巨大的挑战，其计算开销远超推理。
• 近似函数的固有误差： APR 本质上是对 ReLU 的近似。虽然论文通过精细设计将近似误差控制在很低水平，但在某些极端情况下，或对于对数值精度极其敏感的任务，近似误差的累积仍可能是一个潜在问题。

未来工作方面，论文指出了以下方向：

• 实现支持多线程的 RNS-CKKS 操作，以进一步降低整体延迟。
• 利用 GPU 或专用硬件加速器（如 Jung et al., 2021 和 Kim et al., 2021b 所示）来大幅提升 FHE 运算速度。

7.3. 个人启发与批判

个人启发： 这篇论文在全同态加密领域取得了令人印象深刻的进展，为实现隐私保护的深度学习推理带来了重要突破。它最主要的启发在于：

1. FHE-Native 优化思维： 面对 FHE 的高计算开销，不能简单地将明文算法“翻译”到加密域，而必须深入理解 FHE 的底层特性（如噪声管理、层级消耗、KSO 开销、SIMD 槽位利用），并基于这些特性设计和优化算法。多路复用打包和并行卷积正是这种思维的典范。
2. 数值稳定性在 FHE 中的重要性： 论文首次发现并解决了深度 APR 在 RNS-CKKS 中可能发生的灾难性发散问题，这揭示了在复数域进行 FHE 计算时，虚部噪声管理的关键性。这一发现及其解决方案对于未来 FHE 复杂计算的鲁棒性研究具有指导意义。
3. 实用性与理论结合： 论文不仅有理论上的创新，更通过显著的性能提升和首次实现深层 ResNet，展示了其在实际隐私保护机器学习场景中的巨大潜力。

批判： 尽管论文贡献巨大，但仍有一些方面值得批判性思考：

1. “低复杂度”的相对性： 论文标题中的“Low-Complexity”是相对于 FHE 领域的现有工作而言的。从绝对意义上讲，即使优化后的推理延迟（数千秒）对于许多实时或交互式应用来说仍然是非常高的，这使得 FHE 在大规模商业部署上仍面临巨大挑战。
2. 模型通用性与适应性： 论文专注于 ResNet 架构在图像分类任务上的实现。对于其他类型的深度学习模型（如目标检测、语义分割、自然语言处理中的 Transformer 模型），或者更复杂的网络结构，如何有效应用这些优化技术仍需进一步探索。
3. 安全性与性能的权衡： 论文实现了 128 位安全级别，这很好。但在实际应用中，用户对安全级别的需求可能不同。如何在更高的安全级别下（例如 256 位）保持性能，或者在可接受的略低安全级别下进一步提升性能，将是值得研究的方向。
4. 硬件加速的潜在瓶颈： 论文寄希望于 GPU 或专用硬件加速器来进一步提升性能。虽然这很有前景，但 FHE 的计算模式与现有通用计算硬件（如 GPU）的匹配度仍需深入研究和定制化设计，以实现真正的“即插即用”式加速。
5. 缺乏对模型鲁棒性的讨论： APR 虽然精度高，但仍是近似。在加密域中，模型对对抗性攻击或输入噪声的鲁棒性是否会受到影响，以及如何量化这种影响，是值得关注的问题。