Paper 2026/1389

SC-DT: Scalable Constant Round Secure Comparison and its Application to Privacy Decision Tree Evaluation

Abstract

Numerous private decision tree evaluation (PDTE) protocols based on secure multi-party computation (MPC) have been proposed to protect sensitive data during evaluation. However, existing MPC-based PDTE protocols primarily focus on the two or three-party setting. Moreover, their core building block, secure threshold comparison, typically incurs logarithmic-round communication and dominates the online cost of tree evaluation. These limitations motivate the design of scalable and efficient secure comparison protocols for large-scale PDTE. In this paper, inspired by Falcon (PETs’2020), we propose a scalable constant round secure comparison protocol based on Shamir secret sharing in the honest-majority setting. Concretely, we leverage random shuffle to achieve zero detection with constant-round communication. Furthermore, we reduce random shuffle to random shift, thereby significantly decreasing the offline communication overhead. Besides, we reformulate feature selection and path selection in PDTE as private lookup table functionalities and integrate PLUT with our scalable comparison protocol to achieve scalable PDTE. Finally, we extend the above Shamir secret sharing-based protocols to the packed secret sharing variants and further optimize the online communication efficiency of these packed variants. We instantiate the above protocols as a framework SC-DT and report their improved performance: i) For secure comparison, our packed secure comparison achieves a speedup of $1.7-2.3\times$ and reduce communication by $1.7-2.5\times$ in the online phase compared with Helix (Cryptology ePrint’2025). ii) For large-scale PDTE, our packed secret sharing-based protocol improves online communication efficiency by up to $1.9\times$ over our Shamir-based protocol. In a 21-party WAN setting, it evaluates a 50-tree random forest with 42,550 nodes at an amortized latency of about one second per tree.