Paper 2026/936

Efficient and Privacy-preserving Outsourced Training of Decision Tree Models Based on (Leveled) Fully Homomorphic Encryption

Abstract

Training machine learning models is computationally intensive, making cloud-based outsourcing an attractive solution to alleviate local resource constraints. However, untrusted cloud environments pose serious privacy risks to both training data and resulting models. Existing works primarily rely on multi-party computation (MPC) or lattice-based Homomorphic Encryption (HE), which often incur high communication or computation overheads. To address these challenges, we propose an efficient privacy-preserving scheme for outsourced decision tree training. Specifically, we leverage Symmetric Homomorphic Encryption (SHE) to achieve faster training speed. However, since SHE only supports integer-based homomorphic operations, we propose a Modified Gini Impurity Index (MGII) to adapt to this restriction and use Single Instruction Multiple Data (SIMD) packing to accelerate processing. Experimental results demonstrate that our scheme significantly reduces overall execution time compared to related works and achieves comparable (and for deeper trees, better) accuracy, while security analysis confirms that data and model confidentiality are preserved.