Secure Outsourcing Evaluation for Sparse Decision Trees

Decision tree classifiers are pervasively applied in a wide range of areas, such as healthcare, credit-risk assessment, spam detection, and many more. To ensure effectiveness and efficiency, clients usually choose to adopt classification services that are offered by model providers. However, the required data interactions in the evaluation process raise privacy concerns for both the provider and the client, indicating an imminent need for private decision tree evaluation (PDTE). Recently, some works, e.g., Zheng et al. (2019) (ESORICS'19) and Ma et al. (2021) (NDSS'21), try to achieve PDTE by secure outsourcing computation. However, to hide the decision tree structure, Zheng et al. (2019) and Ma et al. (2021) require non-complete decision trees to be made complete by padding dummy nodes, which lead to exponential (provider-side and cloud-side) computation and communication complexity in the depth of the decision tree. This is especially impractical for deep but sparse decision trees. In this paper, we propose a secure and efficient outsourced PDTE protocol with a focus on sparse trees. We avoid padding dummy nodes by vector dot products in outsourcing settings. Through experiments, we show the competitive performance of our design. Compared with Ma et al. (2021) on Spambase dataset in the cloud-side, we are 486× more communication efficient in offline phase and 15× more communication efficient in online phase.