Paper 2022/757

SortingHat: Efficient Private Decision Tree Evaluation via Homomorphic Encryption and Transciphering

Kelong Cong, KU Leuven
Debajyoti Das, KU Leuven
Jeongeun Park, KU Leuven
Hilder V. L. Pereira, KU Leuven

Machine learning as a service scenario typically requires the client to trust the server and provide sensitive data in plaintext. However, with the recent improvements in fully homomorphic encryption (FHE) schemes, many such applications can be designed in a privacy preserving way. In this work, we focus on such a problem, private decision tree evaluation (PDTE) --- where a server has a decision tree classification model, and a client wants to use the model to classify her private data without revealing the data or the classification result to the server. We present an efficient non-interactive design of PDTE, that we call SortingHat, based on FHE techniques. As part of our design, we solve multiple cryptographic problems related to FHE: (1) we propose a fast homomorphic comparison function where one input can be in plaintext format; (2) we design an efficient binary decision tree evaluation technique in the FHE setting, which we call homomorphic traversal, and apply it together with our homomorphic comparison to evaluate private decision tree classifiers, obtaining running times orders of magnitude faster than the state of the art; (3) we improve both the communication cost and the time complexity of transciphering, by applying our homomorphic comparison to the FiLIP stream cipher. Through a prototype implementation, we demonstrate that our improved transciphering solution runs around 400 times faster than previous works. We finally present a choice in terms of PDTE design: we present a version of SortingHat without transciphering that achieves significant improvement in terms of computation cost comparing to prior works; and another version with transciphering that has a communication cost about 20 thousand times smaller but comparable running time.

Note: Source code link is available in the paper.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
PDTEFHEPrivate Decision Tree
Contact author(s)
kelong cong @ esat kuleuven be
debajyoti das @ esat kuleuven be
Jeongeun Park @ esat kuleuven be
HilderVitor LimaPereira @ esat kuleuven be
2023-04-03: last of 3 revisions
2022-06-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kelong Cong and Debajyoti Das and Jeongeun Park and Hilder V. L. Pereira},
      title = {SortingHat: Efficient Private Decision Tree Evaluation via Homomorphic Encryption and Transciphering},
      howpublished = {Cryptology ePrint Archive, Paper 2022/757},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.