SAFEDT: A Privacy-Preserving Decision Tree Inference Framework Using Homomorphic Encryption

Abstract

With the increasing application of machine learning in sensitive domains such as healthcare, the demand for privacy-preserving techniques in decision tree inference has grown urgent. Traditional decision trees, when executed in untrusted environments, pose a risk of exposing sensitive data to untrusted parties. Therefore, we propose SAFEDT, a privacy-preserving decision tree inference framework based on homomorphic encryption (HE). To enable efficient homomorphic evaluation of comparison functions, we employ Chebyshev polynomials to approximate compar- ison functions and propose the Polynomial Degree Multi-Objective Optimization (PD-MOO) algorithm. PD-MOO dynamically adjusts the approximation strategy through layered hybrid-degree polynomials, enabling flexible adaptation to diverse tree structures while enhancing model accuracy and reducing ciphertext computation overhead. Furthermore, building on CKKS SIMD batching, we develop a parallel evaluation strategy based on column-wise packing and path splitting to tackle the computational inefficiency of HE, optimizing the inference process from root to leaf nodes and significantly reducing latency. Experiments on standard UCI datasets validate the effectiveness of SAFEDT. Results demonstrate that SAFEDT achieves impressive performance across multiple datasets, with accuracy reaching 99% on the Iris and Wine datasets, which represents an improvement of about 2% over state-of-the-art HE-based methods. Additionally, inference time is reduced by at least 54.7% compared to prior approaches across various datasets. Comprehensive evaluations demonstrate that SAFEDT supports privacy-preserving decision tree inference while balancing practicality and efficiency, offering a practical optimization path for HE-based machine learning inference.