Abstract
This paper introduces a new method for training decision trees and random forests using CKKS homomorphic encryption (HE) in cloud environments, enhancing data privacy from multiple sources. The innovative Homomorphic Binary Decision Tree (HBDT) method utilizes a modified Gini Impurity index (MGI) for node splitting in encrypted data scenarios. Notably, the proposed training approach operates in a single cloud security domain without the need for decryption, addressing key challenges in privacy-preserving machine learning. We also propose an efficient method for inference utilizing only addition for path evaluation even when both models and inputs are encrypted, achieving O(1) multiplicative depth. Experiments demonstrate that this method surpasses the previous study by Akavia et al.’s by at least 3.7 times in the speed of inference. The study also expands to privacy-preserving random forests, with GPU acceleration ensuring feasibly efficient performance in both training and inference.
This work was supported in part by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) [NO. 2022-0-01047, Development of statistical analysis algorithm and module using homomorphic encryption based on real number operation]. Also, it was supported by Korea Institute for Advancement of Technology (KIAT) grant funded by the Korea Government (MOTIE) (P0017123, The Competency Development Program for Industry Specialist).
H. Shin and J. Choi—Co-first authors.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This is \(\textsf{FindMinPosGroup}()\) where # of group is 1 and group size is M. It can be implemented easily with \(\textsf{FindMaxPosGroup}()\), explained in Appendix A in [36].
- 2.
References
I Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 439–450 (2000)
Akavia, A., Leibovich, M., Resheff, Y.S., Ron, R., Shahar, M., Vald, M.: Privacy-preserving decision trees training and prediction. ACM Trans. Privacy Secur. 25(3), 1–30 (2022)
Akhavan Mahdavi, R., Ni, H., Linkov, D., Kerschbaum, F.: Level up: Private non-interactive decision tree evaluation using levelled homomorphic encryption. In: Proc. 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS’23), pp. 2945–2958 (2023)
De Cock, M., et al.: Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation. IEEE Trans. Dependable Secure Comput. 16(2), 217–230 (2017)
Azogagh, S., Delfour, V., Gambs, S., Killijian, M.O.: Probonite: private one-branch-only non-interactive decision tree evaluation. In: Proc. 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC’22), pp. 23–33. ACM (2022). https://doi.org/10.1145/3560827.3563377
Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.-R., Schneider, T.: Secure evaluation of private linear branching programs with medical applications. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 424–439. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04444-1_26
Bost, R., Popa, R.A., Tu, S., Goldwasser, S.: Machine learning classification over encrypted data. In: NDSS Symposium 2015, p. 04_1_2. Internet Society (2015)
Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and regression trees belmont. Wadsworth International Group, CA (1984)
Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: Proceedings of the 14th ACM Conference on Computer and communications Security, pp. 498–507 (2007)
Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: A full rns variant of approximate homomorphic encryption. In: International Conference on Selected Areas in Cryptography, pp. 347–368. Springer (2018)
Cheon, J.H., Hong, S., Kim, D.: Remark on the security of ckks scheme in practice. Cryptology ePrint Archive (2020)
Cheon, J.H., Kim, D., Kim, D.: Efficient homomorphic comparison methods with optimal complexity. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12492, pp. 221–256. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_8
Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 409–437. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_15
Chicco, D., Jurman, G.: Sepsis Survival Minimal Clinical Records. UCI Machine Learning Repository (2023). https://doi.org/10.24432/C53C8N
Cong, K., Das, D., Park, J., Pereira, H.V.: Sortinghat: efficient private decision tree evaluation via homomorphic encryption and transciphering. In: Proc. 2022 ACM CCS, pp. 563–577 (2022)
CryptoLab: HEAAN library (2022). https://heaan.it/
de Hoogh, S., Schoenmakers, B., Chen, P., op den Akker, H.: Practical secure decision tree learning in a teletreatment application. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 179–194. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_12
Du, W., Zhan, Z.: Building decision tree classifier on private data. In: Proceedings of the IEEE international conference on Privacy, security and data mining-Volume 14. pp. 1–8 (2002)
Emekçi, F., Sahin, O.D., Agrawal, D., El Abbadi, A.: Privacy preserving decision tree learning over multiple parties. Data Knowl. Eng. 63(2), 348–361 (2007)
Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 364–390. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40186-3_16
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer (2009)
Joye, M., Salehi, F.: Private yet efficient decision tree evaluation. In: Kerschbaum, F., Paraboschi, S. (eds.) DBSec 2018. LNCS, vol. 10980, pp. 243–259. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-95729-6_16
Jung, W., Kim, S., Ahn, J.H., Cheon, J.H., Lee, Y.: Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with gpus. IACR Trans. Cryptographic Hardware Embedded Syst., 114–148 (2021)
Kiss, Á., Naderpour, M., Liu, J., Asokan, N., Schneider, T.: Sok: modular and efficient private decision tree evaluation. Proceedings on Privacy Enhancing Technologies 2019(2), 187–208 (2019)
Lee, D., Choi, J., Kim, K., Lee, Y.: Heaan-id3: Fully homomorphic privacy-preserving id3-decision trees using ckks. In submission (2023)
Lee, J.W., Lee, E., Lee, Y., Kim, Y.S., No, J.S.: High-precision bootstrapping of rns-ckks homomorphic encryption using optimal minimax polynomial approximation and inverse sine function. In: Proc. Eurocrypt 2021, pp. 618–647 (2021)
Lee, Y., Seo, J., Nam, Y., Chae, J., Cheon, J.H.: Heaan-stat: a privacy-preserving statistical analysis toolkit for large-scale numerical, ordinal, and categorical data. IEEE Trans. Dependable Secure Comput. (2023). https://doi.org/10.1109/TDSC.2023.3275649
Li, B., Micciancio, D.: On the security of homomorphic encryption on approximate numbers. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 648–677. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_23
Li, Y., Jiang, Z.L., Wang, X., Yiu, S.: Privacy-preserving id3 data mining over encrypted data in outsourced environments with multiple keys. In: IEEE Intl. Conf. on CSE and EUC, vol. 1, pp. 548–555 (2017)
Liang, J., Qin, Z., Xue, L., Lin, X., Shen, X.: Efficient and privacy-preserving decision tree classification for health monitoring systems. IEEE Internet Things J. 8(16), 12528–12539 (2021)
Liu, L., Chen, R., Liu, X., Su, J., Qiao, L.: Towards practical privacy-preserving decision tree training and evaluation in the cloud. IEEE Trans. Inf. Forensics Secur. 15, 2914–2929 (2020)
Lu, W.j., Huang, Z., Zhang, Q., Wang, Y., Hong, C.: Squirrel: a scalable secure \(\{\)Two-Party\(\}\) computation framework for training gradient boosting decision tree. In: 32nd USENIX Security Symposium (USENIX Security 23), pp. 6435–6451 (2023)
Lu, W.j., Zhou, J.J., Sakuma, J.: Non-interactive and output expressive private comparison from homomorphic encryption. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, pp. 67–74 (2018)
Markelle Kelly, Rachel Longjohn, K.N.: The uci machine learning repository (2023), https://archive.ics.uci.edu
Scott, D.W.: On optimal and data-based histograms. Biometrika 66(3), 605–610 (1979)
Shin, H., Choi, J., Lee, D., Kim, K., Lee, Y.: Fully homomorphic training and inference on binary decision tree and random forest. Cryptology ePrint Archive, Paper 2024/529 (2024), https://eprint.iacr.org/2024/529, https://eprint.iacr.org/2024/529
Tai, R.K.H., Ma, J.P.K., Zhao, Y., Chow, S.S.M.: Privacy-preserving decision trees evaluation via linear functions. In: Foley, S.N., Gollmann, D., Snekkenes, E. (eds.) ESORICS 2017. LNCS, vol. 10493, pp. 494–512. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66399-9_27
Tueno, A., Boev, Y., Kerschbaum, F.: Non-interactive private decision tree evaluation. In: Data and Applications Security and Privacy XXXIV: 34th Annual IFIP WG 11.3 Conference, DBSec 2020, Regensburg, Germany, June 25–26, 2020, Proceedings 34. pp. 174–194. Springer (2020)
Tueno, A., Kerschbaum, F., Katzenbeisser, S.: Private evaluation of decision trees using sublinear cost. Proce. Privacy Enhancing Technol. 2019(1), 266–286 (2019)
Vaidya, J., Kantarcıoğlu, M., Clifton, C.: Privacy-preserving naive bayes classification. VLDB J. 17(4), 879–898 (2008)
Wang, K., Xu, Y., She, R., Yu, P.S.: Classification spanning private databases. In: Proceedings of the National Conference on Artificial Intelligence, vol. 21, p. 293. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999 (2006)
Wu, D.J., Feng, T., Naehrig, M., Lauter, K.: Privately evaluating decision trees and random forests. Proceedings on Privacy Enhancing Technologies 4, 335–355 (2016)
Zheng, W., Deng, R., Chen, W., Popa, R.A., Panda, A., Stoica, I.: Cerebro: A platform for \(\{\)Multi-Party\(\}\) cryptographic collaborative learning. In: 30th USENIX Security Symposium (USENIX Security 21), pp. 2723–2740 (2021)
Zheng, Y., Duan, H., Wang, C., Wang, R., Nepal, S.: Securely and efficiently outsourcing decision tree inference. IEEE Trans. Dependable Secure Comput. 19(3), 1841–1855 (2022)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Shin, H., Choi, J., Lee, D., Kim, K., Lee, Y. (2024). Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest. In: Garcia-Alfaro, J., Kozik, R., Choraś, M., Katsikas, S. (eds) Computer Security – ESORICS 2024. ESORICS 2024. Lecture Notes in Computer Science, vol 14984. Springer, Cham. https://doi.org/10.1007/978-3-031-70896-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-70896-1_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-70895-4
Online ISBN: 978-3-031-70896-1
eBook Packages: Computer ScienceComputer Science (R0)