Efficient and Privacy-Preserving Decision Tree Inference via Homomorphic Matrix Multiplication and Leaf Node Pruning
Source abstract
Abstract
Cloud computing is widely used by organizations and individuals to outsource computation and data storage. With the growing adoption of machine learning as a service (MLaaS), machine learning models are being increasingly deployed on cloud platforms. However, operating MLaaS on the cloud raises significant privacy concerns, particularly regarding the leakage of sensitive personal data and proprietary machine learning models. This paper proposes a privacy-preserving decision tree (PPDT) framework that enables secure predictions on sensitive inputs through homomorphic matrix multiplication within a three-party setting involving a data holder, a model holder, and an outsourced server. Additionally, we introduce a leaf node pruning (LNP) algorithm designed to identify and retain the most informative leaf nodes during prediction with a decision tree. Experimental results show that our approach reduces prediction computation time by approximately 85% compared to conventional protocols, without compromising prediction accuracy. Furthermore, the LNP algorithm alone achieves up to a 50% reduction in computation time compared to approaches that do not employ pruning.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cryptography and Data Security · Privacy-Preserving Technologies in Data · Stochastic Gradient Optimization Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Graduate School of Engineering, Kobe University, Kobe 657-8501, Japan
Cybersecurity Research Institute, National Institute of Information and Communications Technology, Tokyo 184-8795, Japan
Funding
JST CREST · JST AIP accelerated program
References (24)
Show source-provided references
1. Konečný, J., McMahan, H.B., Ramage, D., and Richtárik, P. (2016). Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv.
2. Ray, I., Li, N., and Kruegel, C. (2015, January 12–16). Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.
3. On Data Banks and Privacy Homomorphisms
4. Gentry, C. (2009). A Fully Homomorphic Encryption Scheme. [Ph.D. Thesis, Stanford University].10.1145/1536414.1536440 ↗
5. Privacy-Preserving Decision Trees Training and Prediction
6. Privacy-Preserving Tree-Based Inference with TFHE
7. Hao, Y., Qin, B., and Sun, Y. (2023). Privacy-Preserving Decision-Tree Evaluation with Low Complexity for Communication. Sensors, 23.10.3390/s23052624 ↗
8. Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest10.1007/978-3-031-70896-1_11 ↗
9. Yin, H., Stavrou, A., Cremers, C., and Shi, E. (2022, January 7–11). SortingHat: Efficient Private Decision Tree Evaluation via Homomorphic Encryption and Transciphering. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA.
10. Privacy-Preserving Decision Trees Evaluation via Linear Functions10.1007/978-3-319-66399-9_27 ↗
11. Securely and Efficiently Outsourcing Decision Tree Inference10.1109/TDSC.2020.3040012 ↗
12. Privately Evaluating Decision Trees and Random Forests10.1515/popets-2016-0043 ↗
13. Yin, H., Stavrou, A., Cremers, C., and Shi, E. (2022, January 7–11). Federated Boosted Decision Trees with Differential Privacy. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA.
14. A correction to ’efficient and secure comparison for on-line auctions’10.1504/IJACT.2009.028031 ↗
15. Kim, J., Ahn, G., Kim, S., Kim, Y., López, J., and Kim, T. (2018, January 4–8). Non-interactive and Output Expressive Private Comparison from Homomorphic Encryption. Proceedings of the 2018 on Asia Conference on Computer and Communications Security, AsiaCCS 2018, Incheon, Republic of Korea.
16. An Efficient Privacy-Preserving Comparison Protocol
17. Enhanced Secure Comparison Schemes Using Homomorphic Encryption
18. Efficient Secure Matrix Multiplication Over LWE-Based Homomorphic Encryption
19. Practical Packing Method in Somewhat Homomorphic Encryption
20. Kelly, M., Longjohn, R., and Nottingham, K. (2025, March 31). The UCI Machine Learning Repository. Available online: https://archive.ics.uci.edu.
21. Fan, J., and Vercauteren, F. (2025, March 31). Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive 2012. Available online: https://eprint.iacr.org/2012/144.
22. (2019). Microsoft SEAL (Release 3.3), Microsoft Research. Available online: https://github.com/Microsoft/SEAL.
23. Albrecht, M., Chase, M., Chen, H., Ding, J., Goldwasser, S., Gorbunov, S., Halevi, S., Hoffstein, J., Laine, K., and Lauter, K. (2018). Homomorphic Encryption Security Standard, HomomorphicEncryption.org. Technical report.
24. Fukui, S., Wang, L., Hayashi, T., and Ozawa, S. (2019, January 21–24). Privacy-Preserving Decision Tree Classification Using Ring-LWE-Based Homomorphic Encryption. Proceedings of the Computer Sequrity Symposium 2019, Nagasaki, Japan.