Privacy-Preserving Decision Tree Training and Prediction against Malicious Server
Privacy-Preserving Decision Tree Training and Prediction against Malicious Server
复制标题
针对恶意服务器的隐私保护决策树训练和预测
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Margarita Vald
中科院分区：
文献类型：
--
作者：
Adi Akavia;Max Leibovich;Yehezkel S. Resheff;Roey Ron;Shimon Shahar;Margarita Vald
隐私保护机器学习可以将机器学习任务安全地外包给不受信任的服务提供商（服务器），同时保护用户数据（客户端）的隐私。对于复杂的机器学习任务（如训练决策树），实现良好的具体效率是该领域的挑战之一。先前关于隐私保护决策树的工作要求各方具有可比的计算资源，并指示客户端执行与整个任务的复杂性成比例的计算。在这项工作中，我们提出了新的协议，隐私保护决策树的训练和预测，实现了以下理想的属性：1。效率：客户端的复杂度与训练过程中的训练集大小和预测过程中的树大小无关。2.安全性：隐私可以防止恶意服务器。3.实用性：在标准UCI数据集上证明了高精度、快速预测和可行的训练，并使用全同态加密进行加密。据我们所知，我们的协议是第一个同时提供所有这些属性的协议。我们工作的核心包括两个技术贡献。首先，一种新的函数的低次多项式近似，导致更快的加密数据训练和预测协议。第二，设计一个易于使用的机制，以证明隐私对恶意的对手，是适合于广泛的家庭的协议，特别是我们的协议，这种机制可能是独立的利益。
Privacy-preserving machine learning enables secure outsourcing of machine learning tasks to an untrusted service provider (server) while preserving the privacy of the user’s data (client). Attaining good concrete efficiency for complicated machine learning tasks, such as training decision trees, is one of the challenges in this area. Prior works on privacy-preserving decision trees required the parties to have comparable computational resources, and instructed the client to perform computation proportional to the complexity of the entire task. In this work we present new protocols for privacy-preserving decision trees, for both training and prediction, achieving the following desirable properties: 1. Efficiency: the client’s complexity is independent of the training-set size during training, and of the tree size during prediction. 2. Security: privacy holds against malicious servers. 3. Practical usability: high accuracy, fast prediction, and feasible training demonstrated on standard UCI datasets, encrypted with fully homomorphic encryption. To the best of our knowledge, our protocols are the first to offer all these properties simultaneously. The core of our work consists of two technical contributions. First, a new low-degree polynomial approximation for functions, leading to faster protocols for training and prediction on encrypted data. Second, a design of an easy-to-use mechanism for proving privacy against malicious adversaries that is suitable for a wide family of protocols, and in particular, our protocols; this mechanism could be of independent interest.