Secure Outsourcing Evaluation for Sparse Decision Trees

doi:10.1109/TDSC.2024.3372505

Secure Outsourcing Evaluation for Sparse Decision Trees

2024-11-01

0

OA

AI

DOI：10.1109/TDSC.2024.3372505

Original

Original request for help

Save

Abstract

En 中文

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 486x more communication efficient in offline phase and 15x more communication efficient in online phase.

Keywords:

secure outsourcing

replicated secret sharing

Decision tree

secure outsourcing

replicated secret sharing

Secure Outsourcing Evaluation for Sparse Decision Trees

Abstract

Journal

Organization