Paper 2023/1307

Constant-Round Private Decision Tree Evaluation for Secret Shared Data

Nan Cheng, University of St.Gallen
Naman Gupta, Indian Institute of Technology Delhi
Aikaterini Mitrokotsa, University of St.Gallen
Hiraku Morita, Aarhus University, University of Copenhagen
Kazunari Tozawa, The University of Tokyo

Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private decision tree evaluation protocol based on the three-party replicated secret sharing (RSS) scheme. This enables us to securely classify inputs without any leakage of the provided input or the trained decision tree model. Our protocol only requires constant rounds of communication among servers, which is useful in a network with longer delays. Ma et al. (NDSS 2021) presented a lightweight PDTE protocol with sublinear communication cost with linear round complexity in the size of the input data. This protocol works well in the low latency network such as LAN while its total execution time is unfavourably increased in the WAN setting. In contrast, Tsuchida et al. (ProvSec 2020) constructed a constant round PDTE protocol at the cost of communication complexity, which works well in the WAN setting. Although their construction still requires 25 rounds, it showed a possible direction on how to make constant round PDTE protocols. Ji et al. (IEEE Transactions on Dependable and Secure Computing) presented a simplified PDTE with constant rounds using the function secret sharing (FSS) at the cost of communication complexity. Our proposed protocol only requires five rounds among the employed three servers executing secret sharing schemes, which is comparable to previously proposed protocols that are based on garbled circuits and homomorphic encryption. To further demonstrate the efficiency of our protocol, we evaluated it using real-world classification datasets. The evaluation results indicate that our protocol provides better concrete performance in the WAN setting that has a large network delay.

Available format(s)
Cryptographic protocols
Publication info
Secure multiparty computationmachine learningdecision tree evaluation
Contact author(s)
nan cheng @ unisg ch
naman gupta1003 @ gmail com
katerina mitrokotsa @ unisg ch
hiraku @ cs au dk
tozawa kazunari @ mail u-tokyo ac jp
2023-09-02: approved
2023-09-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nan Cheng and Naman Gupta and Aikaterini Mitrokotsa and Hiraku Morita and Kazunari Tozawa},
      title = {Constant-Round Private Decision Tree Evaluation for Secret Shared Data},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1307},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.