Paper 2018/1099

SoK: Modular and Efficient Private Decision Tree Evaluation

Ágnes Kiss, Masoud Naderpour, Jian Liu, N. Asokan, and Thomas Schneider

Abstract

Decision trees and random forests are widely used classifiers in machine learning. Service providers often host classification models in a cloud service and provide an interface for clients to use the model remotely. While the model is sensitive information of the server, the input query and prediction results are sensitive information of the client. This motivates the need for private decision tree evaluation, where the service provider does not learn the client's input and the client does not learn the model except for its size and the result. In this work, we identify the three phases of private decision tree evaluation protocols: feature selection, comparison, and path evaluation. We systematize protocols for each of these phases to identify the best available instantiations using the two main paradigms for secure computation: garbling techniques and homomorphic encryption. There is a natural tradeoff between runtime and communication considering these two paradigms: garbling techniques use fast symmetric-key operations but require a large amount of communication, while homomorphic encryption is computationally heavy but requires little communication. Our contributions are as follows: Firstly, we systematically review and analyse state-of-the-art protocols for the three phases of private decision tree evaluation. Our methodology allows us to identify novel combinations of these protocols that provide better tradeoffs than existing protocols. Thereafter, we empirically evaluate all combinations of these protocols by providing communication and runtime measures, and provide recommendations based on the identified concrete tradeoffs.

Note: Updated figures with slightly more efficient HHH implementation

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Proceedings on Privacy Enhancing Technologies 2019 (PoPETs'19)
Keywords
Privacy-preserving protocolssecure computationhomomorphic encryptiondecision tree evaluationmachine learning
Contact author(s)
kiss @ encrypto cs tu-darmstadt de
History
2018-12-14: last of 3 revisions
2018-11-15: received
See all versions
Short URL
https://ia.cr/2018/1099
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1099,
      author = {Ágnes Kiss and Masoud Naderpour and Jian Liu and N.  Asokan and Thomas Schneider},
      title = {SoK: Modular and Efficient Private Decision Tree Evaluation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1099},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1099}},
      url = {https://eprint.iacr.org/2018/1099}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.