Paper 2019/1282

Privacy-Preserving Decision Tree Training and Prediction against Malicious Server

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


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.

Available format(s)
Cryptographic protocols
Publication info
privacy-preserving machine learningdecision treestrainingpredictionfully homomorphic encryptionsecure outsourcing
Contact author(s)
adi akavia @ gmail com
margarita vald @ cs tau ac il
max fhe phd @ gmail com
hezi_Resheff @ intuit com
roey1rg @ gmail com
2019-11-05: received
Short URL
Creative Commons Attribution


      author = {Adi Akavia and Max Leibovich and Yehezkel S.  Resheff and Roey Ron and Moni Shahar and Margarita Vald},
      title = {Privacy-Preserving Decision Tree Training and Prediction against Malicious Server},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1282},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.