Paper 2021/768

Privacy-Preserving Decision Trees Training and Prediction

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

Abstract

In the era of cloud computing and machine learning, data has become a highly valuable resource. Recent history has shown that the benefits brought forth by this data driven culture come at a cost of potential data leakage. Such breaches have a devastating impact on individuals and industry, and lead the community to seek privacy preserving solutions. A promising approach is to utilize Fully Homomorphic Encryption (FHE) to enable machine learning over encrypted data, thus providing resiliency against information leakage. However, computing over encrypted data incurs a high computational overhead, thus requiring the redesign of algorithms, in an ``FHE-friendly" manner, to maintain their practicality. In this work we focus on the ever-popular tree based methods (e.g., boosting, random forests), and propose a new privacy-preserving solution to training and prediction for trees. Our solution employs a low-degree approximation for the step-function together with a lightweight interactive protocol, to replace components of the vanilla algorithm that are costly over encrypted data. Our protocols for decision trees achieve practical usability demonstrated on standard UCI datasets encrypted with fully homomorphic encryption. In addition, the communication complexity of our protocols is independent of the tree size and dataset size in prediction and training, respectively, which significantly improves on prior works.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision.Machine Learning and Knowledge Discovery in Databases - European Conference, {ECML} {PKDD} 2020, Ghent, Belgium, September 14-18, 2020, Proceedings
DOI
10.1007/978-3-030-67658-2_9
Keywords
fully homomorphic encryptionprivacy preserving machine learningdecision treestrainingprediction
Contact author(s)
adi akavia @ gmail com
margarita vald @ cs tau ac il
History
2021-06-09: received
Short URL
https://ia.cr/2021/768
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/768,
      author = {Adi Akavia and Max Leibovich and Yehezkel S.  Resheff and Roey Ron and Moni Shahar and Margarita Vald},
      title = {Privacy-Preserving Decision Trees Training and Prediction},
      howpublished = {Cryptology ePrint Archive, Paper 2021/768},
      year = {2021},
      doi = {10.1007/978-3-030-67658-2_9},
      note = {\url{https://eprint.iacr.org/2021/768}},
      url = {https://eprint.iacr.org/2021/768}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.