Decision Tree Classification Model Based on Double Trapdoor Homomorphic Encryption

doi:10.3969/j.issn.1671-1122.2022.07.002

Abstract

Abstract:

Decision tree model is a simple and efficient classifier, which has been widely used in telemedicine, credit evaluation, text classification and other fields. Classification service providers usually obtain feature data from the client, input the feature data into the private classification model, get the classification results and return them to the client. In order to protect the privacy of client data and decision tree model parameters, this paper proposed a secure and efficient two-party comparison protocol based on double trapdoor homomorphic encryption technology, and designed an efficient privacy protection decision tree classification model. In the stage of threshold comparison, the model encrypted the user’s eigenvalue and the decision tree threshold of the model provider by using the double notch homomorphic encryption technology, and carried out the evaluation process of the decision tree by judging the positive and negative difference between them. In addition, this model simplified the user key management, and the user only needed to generate and store part of the public key. Security analysis show that this scheme has high privacy. The efficiency analysis shows that this model has low computational overhead.

Key words: machine learning, decision tree, privacy preserving, homomorphic encryption

CLC Number:

TP309

QIN Baodong, YU Peihang, ZHENG Dong. Decision Tree Classification Model Based on Double Trapdoor Homomorphic Encryption[J]. Netinfo Security, 2022, 22(7): 9-17.

Figures/Tables 5

References 18

[1]	TAN Zuowen, ZHANG Lianfu. Survey on Privacy Preserving Techniques for Machine Learning[J]. Journal of Software, 2020, 31(7): 2127-2156.
	谭作文, 张连福. 机器学习隐私保护研究综述[J]. 软件学报, 2020, 31(7):2127-2156.
[2]	WEN Yangdong, ZHANG Kaipeng, LI Zhifeng, et al. A Comprehensive Study on Center Loss for Deep Face Recognition[J]. International Journal of Computer Vision, 2019, 127(6): 668-683. doi: 10.1007/s11263-018-01142-4 URL
[3]	LI Yuqiang, CHEN Yunhao, LI Qi, et al. Random Forest Algorithm under Differential Privacy Based on Out-of-Bag Estimate[J]. Journal of Harbin Institute of Technology, 2021, 53(2): 146-153.
	李玉强, 陈鋆昊, 李琦, 等. 基于差分隐私下包外估计的随机森林算法[J]. 哈尔滨工业大学学报, 2021, 53(2):146-154.
[4]	BOST R, POPA R A, TU S, et al. Machine Learning Classification over Encrypted Data[C]// The Internet Society. Network and Distributed System Security Symposium. New York: The Internet Society, 2015: 1-34.
[5]	WU D J, FENG T, NAEHRIG M, et al. Privately Evaluating Decision Trees and Random Forests[J]. Proceedings on Privacy Enhancing Technologies, 2016(4): 335-355.
[6]	BELLARE M, HOANG V T, KEELVEEDHI S, et al. Efficient Garbling from a Fixed-Key Blockcipher[C]// IEEE. 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013: 478-492.
[7]	TAI R K H, MA J P K, ZHAO Yongjun, et al. Privacy-Preserving Decision Trees Evaluation via Linear Functions[C]// Springer. European Symposium on Research in Computer Security 2017. Heidelberg: Springer, 2017: 494-512.
[8]	ZHENG Yifeng, DUAN Huayi, WANG Cong. Towards Secure and Efficient Outsourcing of Machine Learning Classification[C]// Springer. European Symposium on Research in Computer Security 2019. Heidelberg: Springer, 2019: 22-40.
[9]	LIU Lin, SU Jinshu, CHEN Rongmao, et al. Secure and Fast Decision Tree Evaluation on Outsourced Cloud Data[C]// Springer. International Conference on Machine Learning for Cyber Security. Heidelberg: Springer, 2019: 361-377.
[10]	LIU Lin, CHENN Rongmao, LIU Ximeng, et al. Towards Practical Privacy-Preserving Decision Tree Training and Evaluation in the Cloud[J]. IEEE Transactions on Information Forensics and Security, 2020, 15: 2914-2929. doi: 10.1109/TIFS.2020.2980192 URL
[11]	WANG Chen, WANG Andi, XU Jian, et al. Outsourced Privacy-Preserving Decision Tree Classification Service over Encrypted Data[J]. Journal of Information Security and Applications, 2020, 53: 1-13.
[12]	VEUGEN T. Improving the DGK Comparison Protocol[C]// IEEE. IEEE International Workshop on Information Forensics & Security. New York: IEEE, 2013: 49-54.
[13]	XUE Liang, LIU Dongxiao, HUANG Cheng, et al. Secure and Privacy-Preserving Decision Tree Classification with Lower Complexity[J]. Journal of Communications and Information Networks, 2020, 5(1): 16-25. doi: 10.23919/JCIN.2020.9055107 URL
[14]	CAO Laicheng, LI Yuntao, WU Rong, et al. Multi-key Privacy Protection Decision Tree Evaluation Scheme[EB/OL]. (2021-10-14)[2022-01-11]. https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CJFD&dbname=CJFDLAST2022&filename=QHXB202205006&uniplatform=NZKPT&v=MAkv1cVpNtMGZ3oOJJerSQcJR-na4ZmWNfqPgON8h4o905p-Ukc7aFnwGgRhP-LX.
	曹来成, 李运涛, 吴蓉, 等. 多密钥隐私保护决策树评估方案[EB/OL]. (2021-10-14)[2022-01-11]. https://kns.cnki.net/kcms/detail/detail.aspx?dbcode=CJFD&dbname=CJFDLAST2022&filename=QHXB202205006&uniplatform=NZKPT&v=MAkv1cVpNtMGZ3oOJJerSQcJR-na4ZmWNfqPgON8h4o905p-Ukc7aFnwGgRhP-LX.
[15]	QUINLAN J R. Induction of Decision Trees[J]. Machine Learning, 1986, 1(1): 81-106.
[16]	QUINLAN J R. C4.5: Programs for Machine Learning[M]. Amsterdam: Elsevier, 2014.
[17]	BREIMAN L, FRIEDMAN J H, OLSHEN R, et al. Classification and Regression Trees[M]. New York: Routledge, 1984.
[18]	BRESSON E, CATALANO D, POINTCHEVAL D. A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications[C]// Springer. Advances in Cryptology-ASIACRYPT 2003. Heidelberg: Springer, 2003: 37-54.

模型	计算复杂度		通信复杂度
模型	用户方	模型提供方	用户方	模型提供方
文献[13]	$O\left( n+m \right)~$	$O\left( m \right)$	$O\left( n+m \right)$	$O\left( n+m \right)$
文献[14]	$O\left( \left( n+m \right)t \right)$	$O\left( \left( n+m \right)t \right)$	$O\left( (n+m)t \right)$	$O\left( (n+m)t \right)$
本文	$O\left( n+m \right)~$	$O\left( m \right)$	$O\left( n+m \right)$	$O\left( n+m \right)$

数据集	n	d	m	模型	密钥生成 /s	用户方评估时间 /s	模型提供方评估时间 /s	计算开销 /s	通信开销 /kB
BCW	9	8	12	文献[13]	0.935	0.590	0.535	2.060	6.144
				文献[14]	—	2.784	9.346	12.13	120.832
				本文	0.015	0.625	0.987	1.627	12.032
HD	13	3	5	文献[13]	0.935	0.293	0.252	1.480	3.968
				文献[14]	—	0.969	3.223	4.192	39.936
				本文	0.015	0.277	0.432	0.724	7.680
S	57	17	58	文献[13]	0.935	7.605	7.306	15.846	34.688
				文献[14]	—	22.998	89.743	112.74	1184.256
				本文	0.015	8.375	11. 227	19.617	69.120