2026年4月2日 • 10 分钟阅读

全同态加密数据上的 GBDT 之〇：总览

加密数据上的梯度提升树系列

0. 背景

0.1 全同态加密方案

实用的全同态加密方案从Gentry的开创性工作开始，陆续发展到位级（bit-wise）和字长级（word-wise）全同态加密方案。前者的代表是FHEW和TFHE，支持密文上任意逻辑门运算，密钥和密文都比较大，运算比较慢；后者如BFV和CKKS，基于代数结构的格构造，支持打包多个消息并在密文上批量操作，且对算术运算支持更好。

方案	年份	作者	基础	特点
Gentry方案¹	2009	Craig Gentry	格	自举
DGHV²	2010	van Dijk et al.	整数	近似GCD
BGV³	2011	Brakerski et al.	LWE	模切换
B/FV⁴	2012	Fan, Vercauteren	环LWE	缩放不变性
GSW⁵	2013	Gentry, Sahai, Waters	LWE	近似特征向量
FHEW⁶	2014	Ducas, Micciancio	LWE	快速自举
TFHE⁷	2016	Chillotti et al.	LWE/环LWE	快速自举
CKKS⁸	2017	Cheon et al.	环LWE	近似算术

0.2 决策树模型

模型	描述
ID3（Iterative Dichotomiser 3）	使用信息增益分裂节点，早期分类决策树算法
CART（Classification and Regression Trees）	使用基尼不纯度，支持分类和回归
RF（Random Forrest，随机森林）	基于Bagging的决策树集成学习，改进决策树的泛化能力和方差
AdaBoost（Adaptive Boosting）	弱学习器的串行集成学习，每个学习器修正错误的分类
GBDT（Gradient Boosted Decision Trees）	使用梯度下降去拟合残差的Boosting集成学习，支持更大树深
XGBoost（eXtreme Gradient Boosting）	性能优化的GBDT实现，使用二阶梯度提速，通过正则化减少过拟合
LightGBM（Light Gradient Boosting Machine）	高性能可扩展的GBDT实现，采用基于直方图的分裂和按页节点增长
CatBoost（Categorical Boosting）	GBDT变种实现，原生支持分类特征的处理

1. 基础理论

1.1 CKKS 同态加密方案

CKKS（Cheon-Kim-Kim-Song）方案⁹由 Cheon 等人于 2017 年提出，是面向近似计算的半同态/全同态加密方案，专为机器学习等需要浮点运算的场景设计。

核心流程：

编码（Encoding）： 将实数向量 $\mathbf{x} \in \mathbb{C}^N/2$ 编码为多项式 $m(X) \in \mathbb{Z}[X]/(X^N+1)$ ，通常使用标准的编码映射，将复数向量通过逆离散傅里叶变换（IDFT）映射到多项式系数。
加密（Encryption）： 基于环上带误差学习问题（Ring-LWE），使用公钥对编码后的多项式进行加密。密文通常为两个多项式 $(c_0, c_1)$ 。
同态加法（Homomorphic Addition）： 密文加法为 $\text{Add}(\mathbf{ct}_1, \mathbf{ct}_2) = (c_0^{(1)} + c_0^{(2)}, c_1^{(1)} + c_1^{(2)})$ ，噪声线性增长。
同态乘法（Homomorphic Multiplication）： 密文乘法产生三元组密文，噪声二次增长。乘法后通常需要 relinearization 操作将密文缩减回二元组。
自举/Bootstrapping： CKKS 的核心创新之一。通过自举操作可以刷新密文中的噪声，使其恢复到较低水平，从而支持任意深度的同态计算电路。自举包括编码变换、模提升、稀疏子集和（SSS）评估、插值等步骤。
噪声管理： CKKS 密文中的噪声随同态运算不断增长，需要通过参数选择（ $N$ 、 $\Delta$ 、密文模 $q$ ）和运算深度规划来管理。Relinearization、Rescaling（除以 $\Delta$ ）和 Bootstrapping 是三大噪声管理工具。

参数选择：

$N$ ：多项式度数，决定安全等级（通常 8192–32768）
$\Delta$ ：缩放因子（如 $2^{40}$ ）
多级模数链：用于支持多轮 rescaling

1.2 GBDT 算法基本流程

梯度提升决策树（Gradient Boosting Decision Tree，GBDT）是一种集成学习方法，通过迭代地训练决策树来最小化损失函数。

核心步骤：

初始化： 使用常数或简单模型初始化预测值 $F_0(x)$
迭代训练（ $t = 1, 2, ..., T$ ）：
- 计算负梯度（伪残差）： $r_i = -\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}$
- 构建决策树： 基于伪残差拟合一棵回归树
- 直方图构建： 对特征值进行分桶，统计每个桶中的梯度之和 $G$ 和二阶梯度之和 $H$
- 最优分裂点搜索： 遍历所有候选分裂点，计算增益 $\text{Gain} = \frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda} - \gamma$
- 叶子节点值计算： $w_j = -\frac{G_j}{H_j + \lambda}$
- 更新模型： $F_t(x) = F_{t-1}(x) + \eta \cdot \sum_j w_j \cdot \mathbb{1}(x \in R_j)$
输出： 最终模型 $F_T(x)$

1.3 密文上做 GBDT 的挑战

挑战	说明
比较操作困难	决策树的核心操作是特征值与分裂阈值的比较（ $x \leq \text{threshold}$ ），这在同态加密下是非线性操作，无法直接用同态加法/乘法实现
非线性激活	GBDT 中的符号函数、指示函数（indicator function）需要多项式近似或特殊协议
精度损失	CKKS 是近似方案，多次 rescaling 和 bootstrapping 会累积精度误差
计算开销大	每个密文运算的开销是明文运算的数万至数百万倍
通信开销	密文体积远大于明文（单个 CKKS 密文数百 KB 至数 MB）
直方图构建	需要对密文数据排序和分桶，排序在 HE 环境下非常困难
深度限制	不使用 bootstrapping 时，乘法深度受限；使用 bootstrapping 则开销激增

2. 主要技术方案分类与对比

2.1 纯密文训练方案（Fully Homomorphic Training）

此类方案尝试在 CKKS 密文上直接完成 GBDT 的全部训练流程。

核心问题与解决方法：

比较操作处理：
- Chebyshev 多项式近似： 将符号函数 $\text{sign}(x)$ 用 Chebyshev 多项式逼近，通常需要较高次多项式（数十至数百阶）才能达到可接受的精度，但这会带来巨大的计算开销。
- 分段多项式近似： 将比较函数分解为多个区间上的低阶多项式，利用 CKKS 的同态乘法逐段评估。这种方法需要在每个区间内使用条件选择（multiplexer），但条件选择本身也需要同态运算。
- Softplus/Sigmoid 近似： 使用 $f(x) = \frac{1}{1+e^{-\alpha x}}$ 来近似阶跃函数，参数 $\alpha$ 控制近似精度。
密文直方图构建与分裂点搜索：
- 预定义分桶： 在加密前预先确定特征值的分桶范围（如 XGBoost 的 quantile sketch），将连续值映射到离散桶索引。
- 密文加法聚合： 在每个桶内对密文梯度进行加法聚合（CKKS 原生支持），计算 $G$ 和 $H$ 。
- 密文增益比较： 对各分裂点的增益值进行密文比较（通过多项式近似），选择最优分裂点。

代表工作：

Akavia et al. (2021) ¹⁰提出了一种基于 FHE（ePrint 2021/768），实现了无需解密的完整训练和推理流程。Intuit 公司开源了基于此方法的实现。
Shin et al. (2024) ¹¹在 ePrint 2024/529 上提出了一种使用 CKKS 方案在云环境中训练二值决策树和随机森林的方法，支持多数据源隐私保护。
Masalha et al. (2026) ¹²提出了一种高效的非交互式 XGBoost 训练系统，实现了相较于 Shin et al. (2024) 高达 360x 的加速。核心贡献是 Hierarchical Argmax 算法，利用 SIMD 槽位的冗余将 Argmax 复杂度从 $O(\log_2 s)$ 降低到 $O(\log_2 \log_2 s)$ 。

2.2 密文推理方案（Inference on Encrypted Data）

此类方案在明文数据上训练 GBDT 模型，然后在密文数据上进行推理。

核心技术：

决策树路径选择的密文实现：
- 每个内部节点执行比较操作 $[x] \leq \text{threshold}$ （明文阈值），得到密文布尔值
- 使用同态乘法沿路径传播：对左子树路径乘以比较结果，对右子树路径乘以 $(1 - \text{比较结果})$
- 叶子节点值为明文，最终预测值为所有激活叶子值的加权和
叶子节点值查找：
- 使用 accumulators（累加器）模式：将所有叶子节点的激活指示值乘以对应叶子值后同态相加
- 对于深度为 $d$ 的树，需要 $O(2^d)$ 次同态乘法和 $O(2^d)$ 次同态加法
GBDT 的密文推理：
- 将 GBDT 的每棵树的密文推理结果同态相加
- 若使用 TFHE/CGGI 方案（如 Zama Concrete）¹³，可以更高效地实现比较操作（通过 programmable bootstrapping）
- 若使用 CKKS，需要用多项式近似来近似比较操作

代表工作：

Frery et al. (2023) — Zama 团队（Cryptology ePrint 2023/258） ¹⁴ ，提出了基于 FHE 的树模型推理方案，支持决策树、随机森林和 GBDT。该方法已在 Concrete ML 中实现，在多个基准数据集上精度接近明文版本。
Concrete ML（Zama）： 基于 TFHE 方案实现了 XGBoost/LightGBM 的密文推理，提供 sklearn-like API。使用查表（lookup table, LUT）代替多项式近似来实现非线性操作，精度损失极小（通常 < 1%）。

2.3 混合/外包计算方案（Hybrid / Outsourced Computation）

2.3.1 安全多方计算 + 同态加密（SMPC + HE）

SecureGBM (Feng et al., 2019)¹⁵：结合 HE 和秘密共享实现多方安全 GBDT 训练。使用 SEAL 库的同态加密保护梯度信息，通过混淆电路（Garbled Circuit）实现比较操作。推理阶段通过安全协议在各参与方之间分配计算。
SecureBoost+ (Fan et al., 2024)¹⁶：大规模高性能垂直联邦 GBDT，使用同态加密保护标签信息和梯度，结合量化和直方图策略提升效率。

2.3.2 服务端辅助计算 + 客户端轻量解密

客户端加密数据发送到服务器，服务器执行大部分线性运算（同态加法/乘法），将中间结果返回客户端
客户端解密后执行非线性操作（如比较），再将结果加密回传
这种模式显著减少了服务端 bootstrapping 的需求，但增加了通信轮次

2.3.3 TEE + HE 混合方案

在可信执行环境（如 Intel SGX、ARM TrustZone）中执行部分明文计算
对敏感数据使用 HE 保护，在 TEE 内解密执行复杂操作
优点是可以避免 HE 中的 bootstrapping 开销，缺点是信任硬件安全假设

2.3.4 NVIDIA FLARE + XGBoost

NVIDIA 于 2024 年发布了 CUDA 加速的同态加密联邦 XGBoost 方案¹⁷，基于 NVIDIA FLARE 框架实现。
利用 GPU 加速 HE 运算，在联邦学习场景下保护数据隐私
支持垂直和水平联邦学习两种模式

2.4 近似方案（Approximation-based Approaches）

2.4.1 多项式近似

使用低阶多项式近似 GBDT 中的非线性操作：
- $\text{sign}(x) \approx \frac{2}{\pi} \arctan(kx)$ ，再用 Chebyshev 多项式近似 $\arctan$
- 比较操作 $x \leq t$ 近似为 $\frac{1}{2}(1 - \text{sign}(x - t))$
典型多项式阶数：30–100 阶，精度取决于数据范围和近似区间

2.4.2 量化方案（Quantization）

整数量化： 将浮点 GBDT 模型量化为整数版本（如 8-bit 整数），更适合 BFV/BGV 等整数同态加密方案
Concrete ML 的量化策略： 将树模型中的比较操作转化为查表操作，使用 TFHE 的 programmable bootstrapping 一步完成
精度影响： 适当的量化策略（如量化感知训练）可以将精度损失控制在 1–3% 以内

2.4.3 模型简化

限制树深度： 减少树的深度可以指数级减少密文推理的计算量
限制叶子节点数： 每棵树的叶子节点数直接影响累加器模式的复杂度
树剪枝： 在明文训练后剪枝，去除贡献较小的子树

3. 代表性论文与项目

3.1 学术论文

论文	作者/机构	年份	方案类型	核心贡献
Privacy-Preserving Decision Trees Training and Prediction	Akavia et al. / Intuit	2021	纯密文训练	首个完整的 FHE 决策树训练范式
Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest	Shin et al.	2024	CKKS 纯密文训练	多数据源 CKKS 密文训练
Argmax and XGBoost Training over Fully Homomorphic Encryption	Masalha et al.	2026	CKKS 纯密文训练	提出 Hierarchical Argmax，实现 360x 训练加速
Privacy-Preserving Tree-Based Inference with FHE	Frery et al. / Zama	2023	FHE 密文推理	Concrete-ML 的理论基础，支持 GBDT
SecureGBM: Secure Multi-Party Gradient Boosting	Feng et al.	2019	SMPC + HE	多方安全 GBDT，使用 SEAL
SecureBoost+	Fan et al.	2021	HE + 联邦学习	大规模垂直联邦 GBDT
Efficient and Privacy-Preserving Tree-Based Inference via Additive Homomorphic Encryption	Zhao et al.	2023	加法同态加密	高效树模型密文推理
Privacy-Preserving Ensemble Learning Using Fully Homomorphic Encryption	Sharma et al.	2024	FHE	集成学习的 FHE 保护
Approximate Homomorphic Encryption Based Privacy-Preserving Machine Learning: A Survey	Yuan et al.	2025	综述	HE 在 PPML 中的全面综述

3.2 开源项目

项目	链接	加密库	支持的模型	说明
Concrete ML	github.com/zama-ai/concrete-ml	Concrete (TFHE)	XGBoost, LightGBM, Random Forest, 神经网络	最成熟的 FHE ML 框架，提供密文推理
Decision-Trees-over-FHE	github.com/intuit/Decision-Trees-over-FHE	SEAL (BFV/CKKS)	决策树	Intuit 开源，支持训练和推理
XGBoost	github.com/dmlc/xgboost	支持 HE 集成（Issue #9987）	XGBoost	计划集成垂直联邦学习安全特征
NVIDIA FLARE + XGBoost	github.com/NVIDIA/NVFlare	CUDA 加速 HE	XGBoost	GPU 加速的同态加密联邦 XGBoost
OpenFHE	openfhe.org	多方案（CKKS/BFV/BGV/TFHE）	通用 HE 库	提供 CKKS 完整实现，可自行实现 GBDT
HEAAN	github.com/snucrypto/heaan	CKKS	通用 HE 库	韩国首尔大学，CKKS 原始实现
Microsoft SEAL	github.com/microsoft/SEAL	CKKS/BFV	通用 HE 库	微软出品，SecureGBM 使用此库

3.3 HE 库对 GBDT 的支持情况

库	CKKS 支持	内置 GBDT	可扩展性	成熟度
Concrete ML	使用 TFHE（非 CKKS）	✅ XGBoost/LightGBM 密文推理	高，sklearn-like API	⭐⭐⭐⭐⭐
Microsoft SEAL	✅	❌ 需自行实现	中	⭐⭐⭐⭐
OpenFHE	✅	❌ 需自行实现	高，C++ API	⭐⭐⭐⭐
HEAAN	✅（原始 CKKS）	❌ 需自行实现	中	⭐⭐⭐

3.4 商业/工业界应用

Zama（法国）： 开源 Concrete ML 框架，已获得大额融资，目标是让 FHE 成为机器学习的标准隐私保护方案。已在反洗钱（AML）场景中使用 FHE XGBoost 进行图机器学习。
NVIDIA： 通过 FLARE 框架将 HE 集成到 XGBoost 联邦学习中，利用 GPU 加速。
蚂蚁集团： SecureBoost 是其隐私计算平台（FATE）的核心组件，已在金融风控等场景中部署。
微众银行： FATE 框架集成了 SecureGBM，支持多方安全 GBDT 训练和推理。
Intuit： 在 TurboTax 等产品中探索使用 FHE 保护用户财务数据的机器学习。

4. 性能对比

4.1 各方案综合对比

维度	纯密文训练 (CKKS)	密文推理 (TFHE)	密文推理 (CKKS)	混合方案 (SMPC+HE)	Concrete ML
训练时间	明文的 10⁴–10⁶ 倍	N/A（明文训练）	N/A	明文的 10²–10³ 倍	N/A
推理延迟	明文的 10⁴–10⁶ 倍	~1–10 秒/样本	~0.1–1 秒/样本	~10–100 ms	~1–5 秒/样本
内存占用	GB–TB 级	MB–GB 级	MB–GB 级	MB 级/方	MB–GB 级
精度损失	1–5%	< 1%	1–3%	< 1%	< 1%
通信开销	高（密文传输）	中（单轮）	中	高（多轮交互）	低（单轮）
安全等级	128-bit (N=8192+)	128-bit	128-bit	计算安全	128-bit

4.2 具体性能数据（来自文献）

Concrete ML (Zama, TFHE, 密文推理)：

使用 XGBoost 在 Adult Income 数据集上：精度损失 < 0.5%
推理时间：树深度 ≤ 7 时，约 1–5 秒/样本（CPU）
使用 8-bit 量化时，精度损失通常 < 1%

Frery et al. (2023, FHE 密文推理)：

随机森林（100棵树，深度≤10）：推理时间约 2 分钟/样本（CPU，未优化）
精度：与明文版本几乎完全一致

SecureGBM (SMPC+HE)：

训练时间：比明文 XGBoost 慢约 50–100 倍（3方场景）
推理延迟：约 10–50 ms/样本
精度损失：可忽略不计

Akavia et al. ¹⁰ (2023, FHE 训练)：

训练单棵决策树（1000 样本，10 特征）：约数小时（CKKS，CPU）
精度损失：约 2–5%

Masalha et al. (2026, FHE 训练)：

训练 XGBoost 模型（100 棵树，深度 6）：在 sepsis 数据集上约 5.5 小时
训练加速：相较于 Shin et al. (2024) 在深度 4 树训练上实现了 360x 的加速
核心指标：Hierarchical Argmax 在 $2^{15}$ 槽位配置下比传统 Tournament 方法快 1.6 倍以上

5. 技术挑战与未来方向

5.1 当前主要瓶颈

计算开销： FHE 运算比明文慢 4–6 个数量级，训练阶段的 GBDT 训练在纯 FHE 下尚不实用
Bootstrapping 代价： CKKS bootstrapping 是最昂贵的操作之一，单次 bootstrapping 需要数百毫秒到数秒（GPU 优化后）
比较操作效率： 决策树的核心是比较操作，在 CKKS 下需要高阶多项式近似（30–100 阶），计算量巨大
内存占用： 密文体积大（单个 CKKS 密文数百 KB），处理大规模数据集时内存成为瓶颈
工程复杂度： FHE 参数调优（模数链规划、噪声预算管理）需要深厚的专业知识

5.2 未来可能的突破方向

硬件加速： 专用 FHE 加速芯片（如 DARPA DPRIVE 项目中的 DPRIVE 加速器、Intel HEXL、GPU 加速库）将显著缩小性能差距
算法-加密协同设计： 设计”HE-friendly”的 GBDT 变体，如使用线性分裂代替阈值比较、使用低深度电路
混合方案优化： HE + TEE、HE + SMPC 的深度融合，取各方所长
近似算法改进： 更高效的多项式近似方法和量化策略
CKKS 2.0： 如 HEaaN.io 等新一代 CKKS 实现，优化了 bootstrapping 和内存管理
自动化工具链： 如 Concrete ML 的编译器自动将 sklearn/xgboost 模型编译为 FHE 等价物，降低使用门槛

5.3 实际部署需要解决的问题

密钥管理： 大规模部署时的密钥生成、分发和轮换
合规性： 满足 GDPR、数据安全法等法规要求的安全证明
可扩展性： 分布式 FHE 计算、多节点并行化
互操作性： 与现有 ML 框架（scikit-learn、XGBoost、LightGBM）的无缝集成
成本效益分析： FHE 方案的总成本（计算、存储、通信）与传统脱敏/差分隐私方案的比较

6. 参考文献

Gentry, C., (2009). Fully Homomorphic Encryption using Ideal Lattices. STOC’09. ↩
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V., (2010). Fully Homomorphic Encryption over the Integers. ePrint 2009/616. ↩
Brakerski, Z., Vaikuntanathan, V., (2011). Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. CRYPTO 2011 ↩
Fan, J., Vercauteren, F., (2012). Somewhat Practical Fully Homomorphic Encryption. ePrint 2012/144. ↩
Gentry, C., Sahai, A., Waters, B. (2013). Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. ePrint 2013/340. ↩
Ducas, L., Micciancio, D., (2014). FHEW: Bootstrapping Homomorphic Encryption in less than a second. ePrint 2014/816. ↩
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.. (2016). Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds. ePrint 2016/870. ↩
Cheon, J., Kim, A., Kim, M., Song, Y. (2016). Homomorphic Encryption for Arithmetic of Approximate Numbers. ePrint 2016/421. ↩
Cheon, J.H., Kim, A., Kim, M., & Song, Y. (2017). Homomorphic Encryption for Arithmetic of Approximate Numbers. ASIACRYPT 2017. ↩
Akavia, A., Leibovich, M., et al. (2021). Privacy-Preserving Decision Trees Training and Prediction. ePrint 2021/768. ↩ ↩²
Shin, H., et al. (2024). Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest. ePrint 2024/529. ↩
Masalha, R., Akavia, A., Adir, A., Aharoni, E., & Kushnir, E. (2026). Argmax and XGBoost Training over Fully Homomorphic Encryption. Proceedings on Privacy Enhancing Technologies 2026(1). ↩
Zama AI. Concrete ML Documentation. https://github.com/zama-ai/concrete-ml. ↩
Frery, J., Stoian, A., Bredehoft, R., et al. (2023). Privacy-Preserving Tree-Based Inference with Fully Homomorphic Encryption. ePrint 2023/258. ↩
Feng, Z., Xiong, H., et al. (2019). SecureGBM: Secure Multi-Party Gradient Boosting. arXiv:1911.11997. ↩
Fan, T., Chen, W., et al. (2024). SecureBoost+: Large Scale and High-Performance Vertical Federated Gradient Boosting Decision Tree. arXiv:2110.10927. ↩
NVIDIA (2024). Security for Data Privacy in Federated Learning with CUDA-Accelerated Homomorphic Encryption in XGBoost. NVIDIA Technical Blog. ↩