A Review on Private Decision Tree

通过同态加密和转码进行高效的私有决策树评估

机器学习即服务场景通常需要客户端信任服务器并以明文形式提供敏感数据。然而，随着最近对全同态加密 (FHE) 方案的改进，许多此类应用程序可以以保护隐私的方式设计。在这项工作中，我们关注这样一个问题，私有决策树评估（PDTE）——服务器有一个决策树分类模型，而客户端希望使用该模型对他的私有数据进行分类，而不泄露数据或分类结果到服务器。我们提出了一种基于 FHE 技术的高效非交互式 PDTE 设计，我们称之为 SortingHat。作为我们设计的一部分，我们解决了与 FHE 相关的多个密码问题： (1）我们提出了一种快速同态比较函数，其中一个输入可以是明文格式； (2) 我们在 FHE 设置中设计了一种高效的二叉决策树评估技术，我们称之为同态遍历，并将其与我们的同态比较一起应用来评估私有决策树分类器，获得比当前状态更快的运行时间数量级艺术; (3) 通过将我们的同态比较应用于 FiLIP 流密码，我们提高了通信成本和转码的时间复杂度。 通过原型实现，我们证明我们改进的转码解决方案的运行速度比以前的工作快 400 倍左右。我们最终在 PDTE 设计方面提出了一个选择：我们提出了一个没有转码的 SortingHat 版本，与之前的工作相比，它在计算成本方面实现了显着的改进；另一个带有转译的版本，其通信成本小约 2 万倍，但运行时间相当。

机器学习 (ML) 作为一种基于云的服务来提供有用的服务，如自动健康评估、财产价值评估、数据分类等，对机器学习 (ML) 的需求不断增长。这通常需要用户向服务提供敏感数据，例如用户的 DNA 资料、医疗信息或财务记录。因此，至关重要的是询问消费者是否可以在不放弃数据隐私的情况下使用这种机器学习作为服务。 在这项工作中，我们专注于决策树算法 [Qui86,RM05,AEM13,RM14]，它是机器学习中的一类重要分类器，在健康分析、信用风险评估、垃圾邮件过滤、等 [WFH11,FPS02,AEM13,KTG06,SG11] 我们的场景由一个服务器组成，该服务器持有一个决策树模型，一个客户端希望使用服务器的决策树模型对其私有数据进行分类，而不会将数据透露给服务器。一个明显的解决方案是服务器将决策树模型发送给客户端，客户端在本地运行计算——然而，这超出了 ML 作为服务的目的。那么，我们是否可以设计一种高效的私有决策树评估（PDTE）算法，其中服务器具有决策树分类模型，并且客户端希望使用服务器的计算能力和模型对其私有数据进行分类，而不会将数据泄露给服务器？

Such we have $\log n > \mu / 2 ^ k$ for some $k$, and we research the communication overhead of SortingHat using standard