💻 computer science

HE-DAP: Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization for Statistical Computation

HE-DAP 是一个跨平台优化框架，它能够自动调节同态加密中多项式求值与自举（bootstrapping）之间的权衡，从而显著加速平方根倒数运算，并提升在不同硬件环境下进行隐私保护统计分析的端到端性能。

原作者： Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

发布于 2026-06-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图给一位朋友发送一条秘密信息，但你只能通过一个非常严格、疑心很重的邮局进行传输。这个邮局（即同态加密系统）允许你在不打开锁定的箱子的情况下对其中的内容进行数学运算。这对于保护隐私非常棒，但有一个代价：邮局的速度极其缓慢。每当你进行一次计算，箱子就会变得越来越重、越脆弱。如果你进行的计算次数过多，箱子就会破裂，你的秘密也会随之丢失。

计算“平方根倒数”（可以理解为“分数的平方根”）是我们在统计学中需要解决的最常见的数学问题之一。它是许多数据分析任务中的关键步骤，比如计算某个特定数据点的异常程度。

问题所在：“一刀切”的错误

此前，研究人员已经有了在这些锁定的箱子里解决平方根倒数问题的“配方”。他们称之为 PP-STAT。

把 PP-STAT 想象成一个固定的蛋糕食谱。这个食谱规定：“使用正好 29 杯面粉，并烘烤正好 6 小时。”

问题在于： 这个食谱只在一种特定的厨房里（一个名为 Lattigo 的库，运行在特定的 CPU 芯片上）经过了测试。在这个厨房里，这个食谱效果还可以。
现实情况是： 但如果你换了一个厨房呢？也许你拥有一个超高速的烤箱（GPU），或者一个不同的炉灶（另一种软件库，称为 HEaaN）。在这些新的厨房里，“29 杯面粉”可能需要极长的时间来搅拌，而“6 小时烘烤时间”可能才是最慢的部分。
结果： 在新的厨房里使用同一个固定的食谱是非常低效的。你可能会在搅拌食材上花费 6 个小时，而原本只需要 1 个小时就能烤好；或者在烘烤时间上浪费大量时间，而原本可以通过更快的搅拌来完成。研究发现，在某些环境下，由于做法不对，旧的食谱比它本应达到的速度慢了近 6 倍。

解决方案：HE-DAP（聪明的厨房助手）

作者创建了一个名为 HE-DAP 的新工具。把 HE-DAP 想象成一个聪明的厨房助手，它不仅仅是遵循食谱，它还会先“品尝一下厨房的味道”。

在开始实际工作之前，HE-DAP 会在您使用的特定计算机和软件上运行一系列快速测试。它会询问：

“在这里，搅拌面粉（数学运算）很慢，还是烘烤时间（重置箱子）很慢？”
“如果我少用一点面粉但延长烘烤时间，会更快吗？”
“如果我多用一点面粉但缩短烘烤时间，会更快吗？”

根据这些测试，HE-DAP 会动态地为您的特定机器编写一份全新的、定制的食谱。它会决定需要多少“面粉”（数学复杂度）以及进行多少次“烘烤”（迭代次数），才能在最短时间内做出完美的蛋糕（准确的结果）。

其工作原理（通俗易懂版）

权衡取舍： 为了防止秘密箱子破裂，你有两个选择：
- 选项 A： 在开始时进行非常复杂的计算（比如使用高阶多项式）以获得一个很好的初始猜测值。如果计算本身很简单，这会很快；但如果计算很难，这就会很慢。
- 选项 B： 进行较简单的计算，但通过“重置”箱子（一个称为 Bootstrapping 的过程）来防止它破裂。这个“重置”过程在某些厨房里非常昂贵，但在其他厨房里则很便宜。
自适应： HE-DAP 会弄清楚哪种选项对您的特定计算机来说更便宜。
- 在 GPU（超快速图形卡）上，“重置”按钮的速度极快。所以，HE-DAP 会说：“让我们做简单的计算，并频繁按下重置按钮！”
- 在 CPU（标准处理器）上，“重置”按钮很慢。所以，HE-DAP 会说：“让我们在开始时做一个复杂的计算，这样我们就不用频繁按下重置按钮了！”

结果：更快、更聪明

论文在三种不同类型的计算机设置上测试了这个新“智能助手”：

Lattigo (标准 CPU)： 它使过程快了 1.96 倍。
HEaaN-CPU： 它使过程快了 2.18 倍。
HEaaN-GPU： 它使过程快了 2.35 倍。

至关重要的是，它不仅提高了速度，还保持了同样高的准确度。事实上，在某些情况下，它甚至比旧的固定食谱更准确，因为它避免了将错误的食谱强加给新机器所带来的误差。

为什么这很重要

这篇论文表明，为了让保护隐私的数据分析在现实世界中发挥作用，我们不能只使用一套静态的规则。我们需要能够适应其运行硬件的系统。HE-DAP 证明了，通过自动调整这些设置，我们可以让保护隐私的统计分析变得实用且高效，将一个缓慢、笨拙的过程转变为运行速度提升近两倍且不牺牲安全性或准确性的高效过程。

简而言之： HE-DAP 是一个能让你不再夏天穿厚羽绒服、冬天穿轻薄 T 恤的工具。它会检查天气（你的计算机环境），并给你最完美的着装（数学参数），让你既能快速完成工作，又能感到舒适。

技术摘要：HE-DAP

问题陈述

同态加密（HE）能够实现对加密数据的隐私保护分析，但面临着高计算开销的问题。在统计和机器学习工作负载中，一个关键的瓶颈是平方反根数（ $1/\sqrt{a}$ ）的计算，这是执行诸如 Z-score 标准化、偏度、峰度和皮尔逊相关系数等函数时所需的基础操作。

现有的最先进方法，例如 PP-STAT [13] 和 HEaaN-STAT [24]，依赖于用于平方反根数计算的固定参数配置。这些配置通常涉及用于初始化牛顿法（Newton's method）的切比雪夫多项式逼近的具体阶数，以及固定的牛顿-拉夫森（Newton-Raphson）迭代次数。作者指出，这种静态方法存在一个根本性的缺陷：两种主要的 HE 操作——切比雪夫多项式求值与自举（bootstrapping，即噪声管理）——之间的相对计算成本在不同的 HE 库（例如 Lattigo 与 HEaaN）和硬件环境（例如 CPU 与 GPU）之间会发生剧烈变化（差异高达 6 倍）。

因此，针对一种环境（例如 Lattigo 在 CPU 上，其中自举较慢且更倾向于使用高阶多项式）优化的配置，在另一种环境（例如 HEaaN-GPU，其中自举很快且多项式求值成为瓶颈）中会变得次优或低效。这种环境依赖性使得现有的框架缺乏通用性，且在异构系统中部署时效率低下。

方法论：HE-DAP

为了解决这一问题，作者提出了 HE-DAP（基于同态加密的动态自适应参数优化），这是一个跨平台框架，能够根据特定的执行环境自动确定平方反根数计算的最佳参数。

核心机制

HE-DAP 在配置阶段（实际数据处理之前）运行，用以剖析目标服务器的性能特征。它动态选择 CryptoInvSqrt 算法中的三个关键参数：

$d$ ：切比雪夫多项式逼近的阶数。
$c$ ：预自举（Pre-Bootstrapping，即在平方反根数计算前对输入密文进行自举）的二元指示器。
$i$ ：牛顿-拉夫森迭代次数。

算法工作流

剖析（Profiling）： HE-DAP 评估所有可能的输入密文层级（ $l$ ），范围从 $l_{BTS} + 1$ 到 $l_{max}$ 。
搜索空间探索： 对于每个层级，它测试多项式阶数（ $d$ $d$ ）、预自举指示器（ $c$ $c$ ）以及迭代次数（ $i$ $i$ ）的组合。
- 如果输入层级不足以支持多项式深度，则考虑预自举（ $c=1$ ）。
- 如果层级足够，则在不进行预自举的情况下进行（ $c=0$ ）。
优化准则： 对于每种组合，系统测量平均相对误差（MRE）和运行时间。它识别出满足目标 MRE 阈值的最佳迭代次数（ $i$ ）。
参数选择： 框架为每个层级记录两个最优元组：
- 精度导向型（Accuracy-Oriented）： 在满足严格 MRE 约束的前提下最小化运行时间。
- 速度导向型（Speed-Oriented）： 不论 MRE 如何，仅最小化运行时间（适用于可以容忍较高误差的应用）。
运行时应用： 在实际的统计分析期间，服务器使用与当前密文层级对应的预计算最优参数，从而消除了手动调优或使用固定且次优默认值的需求。

核心贡献

HE-DAP 框架： 引入了一种新型的自适应优化器，可为不同的 HE 库和硬件自动配置平方反根数操作，摆脱了静态、特定于环境的参数限制。
性能提升： 证明了 HE-DAP 能显著加速核心平方反根数计算。在 HEaaN-GPU 环境中，与 PP-STAT 的固定配置相比，它实现了高达 2.35 $\times$ 的加速，同时保持了极高的数值精度（MRE $\le 3.1 \times 10^{-8}$ ）。
全面评估： 在三种不同设置（Lattigo、HEaaN-CPU 和 HEaaN-GPU）和四种核心统计度量（Z-score、偏度、峰度和皮尔逊相关系数）下进行了严格评估。结果证实，HE-DAP 能够为 CPU 和 GPU 环境持续发现最优配置。
开源： 发布了完整的 HE-DAP 实现以确保可复现性。

实验结果

作者使用 CKKS 方案将 HE-DAP 与 PP-STAT（基于 Lattigo）和 HEaaN-STAT（基于 GPU）进行了对比评估。

平方反根数性能：
- HEaaN-GPU： 在层级 12 时，HE-DAP 比 PP-STAT 的固定配置加速了 2.35 $\times$ ；在层级 7 时（精度导向型）加速了 1.79 $\times$ 。与 HEaaN-STAT 相比，它实现了高达 2.15 $\times$ 的运行时间缩减，且具有更低的 MRE。
- HEaaN-CPU： 在层级 12 时，比 PP-STAT 实现了 2.18 $\times$ 的加速。
- Lattigo： 在层级 11 时，比 PP-STAT 实现了 1.96 $\times$ 的加速，同时将 MRE 降低了 79 $\times$ 。
端到端统计分析：
- 将 HE-DAP 应用于真实数据集（UCI Adult 和 Medical Cost Insurance）的统计度量（ZNorm、Skew、Kurt、PCC）时，表现出一致的加速效果。
- 在 Adult 数据集上，HE-DAP 在保持相似 MRE 的情况下，比 PP-STAT 减少了 42%–44% 的运行时间。
- 在 Insurance 数据集上，运行时间缩减达到了 44.6%。
权衡分析： “速度导向”模式允许获得更大的加速（在 GPU 上比 HEaaN-STAT 快达 6.34 $\times$ ），但代价是增加了 MRE，这展示了该框架针对不同应用需求的灵活性。

重要性与主张

本文声称，HE-DAP 证明了原则性的参数优化可以使隐私保护统计分析在大规模应用中变得切实可行。通过自动适配异构执行环境，HE-DAP 解决了现有框架因固定参数而导致的低效问题。

作者强调，其方法是环境感知的，承认多项式求值与自举之间的最佳平衡点并非普适，而是取决于特定的 HE 库和硬件。通过动态导航这一权衡，HE-DAP 确保了统计分析的基础构建模块（平方反根数）能以最高效率执行，从而在不损害同态加密隐私保证的前提下，提升复杂端到端统计工作流的性能。

文章总结道，虽然配置阶段（参数搜索）会产生一定的耗时（特别是在像 Lattigo 这样的 CPU 库中），但这属于一次性的设置成本，在实际的数据处理阶段会带来持续且显著的性能收益。作者建议未来的工作可以通过利用可测量的性能指标（proxies）而非穷举评估，来缩短这一探索时间。