Abstract
Decision trees are famous machine learning classifiers which have been widely used in many areas, such as healthcare, text classification and remote diagnostics, etc. The service providers usually host a decision tree model on the cloud server and provide some classification service for clients to use such a model remotely. In such a scenario, the model is a valuable asset to the cloud which should not be disclosed to the clients, while the query data and classification results are private to the client. To solve such a problem, we propose several building blocks, i.e., secure comparison and secure polynomial calculation, in a two-cloud model. Based on these building blocks, we design a privacy-preserving decision tree evaluation scheme. Compared with the most recent works, our scheme can fully protect the tree model and clients’ data privacy simultaneously. Besides, our scheme also supports offline service users which is essential to the system’s scalability. Moreover, through theoretical analysis and real-world experimental test, it is oblivious that our scheme is quite efficient.
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.
UC Irvine Machine Learning Repository https://archive.ics.uci.edu/ml/datasets.htm.
References
The health insurance portability and accountability act of privacy and security rules. http://www.hhs.gov/ocr/privacy
Singh, A., Guttag, J.V.: A comparison of non-symmetric entropy-based classification trees and support vector machine for cardiovascular risk stratification, pp. 79–82 (2011)
Azar, A.T., El-Metwally, S.M.: Decision tree classifiers for automated medical diagnosis. Neural Comput. Appl. 23(23), 2387–2403 (2013)
Koh, H.C., Tan, W.C., Goh, C.P.: A two-step method to construct credit scoring models with data mining techniques. Int. J. Bus. Inf. 1(1), 96–118 (2006)
Rago, A., Marcos, C., Diaz-Pace, J.A.: Using semantic roles to improve text classification in the requirements domain. Lang. Resour. Eval. 52(3), 801–837 (2018)
Lindell, Y., Pinkas, B.: Privacy preserving data mining. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 36–54. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_3
Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: ACM SIGMOD Record, vol. 29, pp. 439–450. ACM (2000)
Bost, R., Popa, R.A., Tu, S., Goldwasser, S.: Machine learning classification over encrypted data. In NDSS, vol. 4324, p. 4325 (2015)
Wu, D.J., Feng, T., Naehrig, M., Lauter, K.: Privately evaluating decision trees and random forests. Proc. Priv. Enhanc. Technol. 2016(4), 335–355 (2016)
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
Du, W., Zhan, Z.: Building decision tree classifier on private data. In IEEE International Conference on Privacy, Security and Data Mining (2002)
Ma, X., Chen, X., Zhang, X.: Non-interactive privacy-preserving neural network prediction. Inf. Sci. 481, 507–519 (2019)
Ma, X., Zhang, F., Chen, X., Shen, J.: Privacy preserving multi-party computation delegation for deep learning in cloud computing. Inf. Sci. 459, 103–116 (2018)
Yong, Y., Li, H., Chen, R., Zhao, Y., Yang, H., Xiaojiang, D.: Enabling secure intelligent network with cloud-assisted privacy-preserving machine learning. IEEE Netw. 33(3), 82–87 (2019)
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. ACM (2007)
Yao, A.C.-C.: How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science, pp. 162–167. IEEE (19860)
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
Damgard, I., Geisler, M., Kroigard, M.: Homomorphic encryption and secure comparison. Int. J. Appl. Crypt. 1(1), 22–31 (2008)
Schneider, T., Zohner, M.: GMW vs. Yao? efficient secure two-party computation with low depth circuits. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 275–292. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_23
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, 217–230 (2017)
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
Tueno, A., Kerschbaum, F., Katzenbeisser, S.: Private evaluation of decision trees using sublinear cost. Proc. Priv. Enhanc. Technol. 2019(1), 266–286 (2019)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16
Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T., Nicolosi, A.A.: Efficient RSA key generation and threshold Paillier in the two-party setting. J. Cryptol. 32(2), 265–323 (2019)
Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)
Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34
Riazi, M.S., Weinert, C., Tkachenko, O., Songhori, E.M., Schneider, T., Koushanfar, F.: Chameleon: a hybrid secure computation framework for machine learning applications. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, pp. 707–721. ACM (2018)
Liu, X., Choo, R., Deng, R., Lu, R., Weng, J.: Efficient and privacy-preserving outsourced calculation of rational numbers. IEEE Trans. Dependable Secure Comput. 15, 27–39 (2016)
Elmehdwi, Y., Samanthula, B.K., Jiang, W.: Secure k-nearest neighbor query over encrypted data in outsourced environments. In: 2014 IEEE 30th International Conference on Data Engineering (ICDE), pp. 664–675. IEEE (2014)
Liu, L., et al.: Privacy-preserving mining of association rule on outsourced cloud data from multiple parties. In: Susilo, W., Yang, G. (eds.) ACISP 2018. LNCS, vol. 10946, pp. 431–451. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93638-3_25
Wang, D., Wang, P.: Two birds with one stone: two-factor authentication with security beyond conventional bound. IEEE Trans. Dependable Secure Comput. 15(4), 708–722 (2016)
Wang, D., Cheng, H., He, D., Wang, P.: On the challenges in designing identity-based privacy-preserving authentication schemes for mobile devices. IEEE Syst. J. 12(1), 916–925 (2016)
Liu, X., Deng, R.H., Choo, K.-K.R., Weng, J.: An efficient privacy-preserving outsourced calculation toolkit with multiple keys. IEEE Trans. Inf. Forensics Secur. 11(11), 2401–2414 (2016)
Nikolaenko, V., Weinsberg, U., Ioannidis, S., Joye, M., Boneh, D., Taft, N.: Privacy-preserving ridge regression on hundreds of millions of records. In: 2013 IEEE Symposium on Security and Privacy (SP), pp. 334–348. IEEE (2013)
Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J.B., Toft, T.: Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 285–304. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_15
Huang, K., Liu, X., Fu, S., Guo, D., Xu, M.: A lightweight privacy-preserving CNN feature extraction framework for mobile sensing. IEEE Trans. Dependable Secure Comput. (2019)
Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, Cambridge (2009)
Bogdanov, D., Laur, S., Willemson, J.: Sharemind: a framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88313-5_13
Acknowledgement
The work is supported by the National Key Research and Development Program under grant 2017YFB0802300, the National Natural Science Foundation of China (No. 61702541, No. 61702105), the Young Elite Scientists Sponsorship Program by CAST (2017QNRC001), the Science and Technology Research Plan Program by NUDT (Grant No. ZK17-03-46), and Guangxi Cloud Computing and Large Data Collaborative Innovation Center Project.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, L., Su, J., Chen, R., Chen, J., Sun, G., Li, J. (2019). Secure and Fast Decision Tree Evaluation on Outsourced Cloud Data. In: Chen, X., Huang, X., Zhang, J. (eds) Machine Learning for Cyber Security. ML4CS 2019. Lecture Notes in Computer Science(), vol 11806. Springer, Cham. https://doi.org/10.1007/978-3-030-30619-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-30619-9_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30618-2
Online ISBN: 978-3-030-30619-9
eBook Packages: Computer ScienceComputer Science (R0)