Cryptology ePrint Archive: Report 2019/1282

Privacy-Preserving Decision Tree Training and Prediction against Malicious Server

Adi Akavia and Max Leibovich and Yehezkel S. Resheff and Roey Ron and Moni Shahar and Margarita Vald

Abstract: 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.

Category / Keywords: cryptographic protocols / privacy-preserving machine learning, decision trees, training, prediction, fully homomorphic encryption, secure outsourcing

Date: received 5 Nov 2019, last revised 5 Nov 2019

Contact author: adi akavia at gmail com, margarita vald at cs tau ac il, max fhe phd at gmail com, hezi_Resheff at intuit com, roey1rg at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20191105:152723 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]