纵向决策树的高效两方密码框架

纵向决策树的高效两方密码框架

垂直联邦学习中的隐私保护决策树 (DT) 是促进现实中各种隐私关键应用程序的最有效工具之一。 然而，当前解决方案的主要瓶颈是其巨大的开销，主要是由于采用通信密集型位分解来实现复杂的非线性操作，例如比较和除法。 在本文中，我们介绍了 PriVDT，这是一种有效的两方框架，用于离线/在线范式中的私有垂直 DT 训练和推理。 具体来说，我们根据高级原语函数秘密共享 (FSS) 定制了几个加密构建块。 首先，我们构建了一个优化的比较协议，通过减少 FSS 评估的调用来提高效率。 其次，我们设计了一种高效且增强隐私的除法协议，而无需透露除数的范围，该协议利用了上述比较协议，更重要的是，新设计的基于 FSS 的安全范围和数字分解协议。 此外，我们通过采用基于轻量级伪随机函数的 Beaver 三元组技术进一步降低了线性运算的开销。 基于上述高效组件，我们实现了 PriVDT 框架，并在 LAN 和 WAN 上的 5 个真实数据集上对其进行了评估。 实验结果表明，PriVDT 的端到端运行时间在 LAN 上优于现有技术 42 ∼ 510×，在 WAN 上优于现有技术 16 ∼ 70×。 此外，PriVDT 提供与非私有设置相当的准确性。

作为一种高效且可解释的机器学习算法，决策树 (DT) 已被用于各种实际应用，例如金融风险管理、医疗诊断和股票交易。 实际上，DT 的构建和实际应用面临两个挑战。 首先，训练数据是垂直分布的，其中各方持有相同样本的不相交特征。 其次，训练数据也是隐私敏感的。 例如，在金融风险管理任务中，个人的司法和贷款信息通常分别由法院和银行掌握，而这些隐私的个人信息由于目前严格的政策不允许直接公开例如通用数据保护条例 (GDPR)。 在这些挑战的推动下，隐私保护垂直 DT 被提议作为一种新兴范例。

探索保护隐私的垂直 DT 的现有努力可以分为两类。 (1) 泄漏容差。 有几种方法会牺牲一些隐私保证以换取较低的密码开销，例如样本标签、内部节点的最佳拆分、评估路径（ 详见第二节）。 然而，这种泄露与隐私保护的要求背道而驰。 (2) 零隐私泄露。 Wu等最近提出了 Pivot，这是第一个在不泄露任何敏感信息的情况下为垂直 DT 提供隐私保护的解决方案。 在构造 DT 时，Pivot 利用 gini 杂质增益作为度量来找到树节点的最佳分割。 评估包括线性运算、除法和比较（详见第 IV-A 节）。 为了保护隐私，Pivot 在技术上使用 Paillier 同态加密（HE)进行线性运算，并使用秘密共享（SS）技术（更准确地说，SPDZ 框架[14]）进行比较和划分。 尽管有如此理想的隐私保证，但 Pivot 中的一个内在问题是其开销过高，这主要是因为（1）基于 SS 的比较和除法协议依赖于大量的位分解，然后是逐位求值，这引入了多线程间的高通信量 回合，以及 (2) Pivot 需要昂贵的 HE 操作以及 HE 密文和秘密共享值之间的转换。 例如，它需要在每个树节点中进行 3k + 2 次同态标量乘法和 4k 次转换，其中 k 是类别数。 综上所述，这些不恰当的用法造成了巨大的通信和计算开销，减少密码学开销是这项工作的主要重点。

PriVDT是一种用于垂直决策树训练和推理的高效两方加密框架。 两方设置对于现实世界的应用程序是合理的，并且已广泛应用于隐私保护机器学习 。 具体来说，PriVDT 建立在类似于 Pivot的离线/在线范式之上，并采用了几个新的构建块来提高效率，尤其是在在线阶段。 首先，利用高级密码原语，函数秘密共享 (FSS)，我们提出了一个有效的比较协议来选择最佳拆分。 主要挑战是直接使用通用 FSS 方案会导致高评估开销，因为它需要两次 FSS 调用来处理环绕问题。通过提供一种新颖的理论分析来解决这个问题，该分析表明即使只调用一个 FSS 评估，在适当的参数设置下发生环绕问题的可能性也可以忽略不计。 与最有效的 FSS 方案相比，这实现了大约 2 倍的在线运行时间减少，同时在树的训练中导致轻微的精度损失（小于 0.6%）。 对于通信，协议只需要一个具有 2 个环元素的通信轮。

其次，在迭代的Goldschmidt的范式上设计了一种高效且具有隐私增强的分区协议。上述协议揭示了除数的范围，这可能会导致DTS构建中分裂统计的泄漏。通过集成上述比较协议，更重要的是设计新的基于FSS的安全范围和数字分解协议来解决此隐私泄漏问题。新见解是将除数分解为子弦，因此在隐藏中间值的同时评估了较小的位长的范围。 结果，我们的部门协议在提供严格的安全保证的同时，在先前的工作替代方案方面取得了数量级的改善。 值得注意的是，比较和部分协议可以在其他关键隐私应用程序中使用，这可能具有独立的利益。 此外，采用轻巧的添加秘密共享原始图来改善线性操作的评估开销，即加法和乘法，而与之前相似，利用PRF来生成相关的随机性，以进一步降低通信成本。对设计的构建块给出了形式化的安全证明和具体的复杂性分析，并实施它们以验证效率优势。 比较和除法协议在经验上比 Pivot 的替代方案好几个数量级，无论是在在线运行时还是在通信方面。

在数据稀缺且多方分布的场景下，决策树的隐私保护协同学习受到了广泛关注。 在这种学习模式下，全局数据集可以用两种不同的方式进行划分。 (1) 垂直划分：各方持有具有不同特征的相同样本。 比如金融风险管理任务的一个例子。（2）水平划分：不同方拥有各自的样本但共享相同的特征。 例如，两家地区性银行可能拥有来自各自地区的不同用户群。 但是他们的业务很相似，所以特征空间是一样的。 在本文中，我们重点关注垂直分区设置。