基于双陷门同态加密的决策树分类模型

doi:10.3969/j.issn.1671-1122.2022.07.002

信息网络安全 ›› 2022, Vol. 22 ›› Issue (7): 9-17.doi: 10.3969/j.issn.1671-1122.2022.07.002

基于双陷门同态加密的决策树分类模型

秦宝东(), 余沛航, 郑东

西安邮电大学网络空间安全学院,西安 710121

收稿日期:2022-03-07 出版日期:2022-07-10 发布日期:2022-08-17
通讯作者: 秦宝东 E-mail:qinbaodong@xupt.edu.cn
作者简介:秦宝东（1982—）,男,江苏,教授,博士,主要研究方向为公钥密码学|余沛航（1998—）,男,陕西,硕士研究生,主要研究方向为机器学习、隐私保护|郑东（1964—）,男,山西,教授,博士,主要研究方向为密码学与信息安全
基金资助:
国家自然科学基金(61872292);国家自然科学基金(62072371);陕西省重点研发计划(2021ZDLGY06-02);青海省基础研究计划(2020-ZJ-701)

Decision Tree Classification Model Based on Double Trapdoor Homomorphic Encryption

QIN Baodong(), YU Peihang, ZHENG Dong

School of Cyberspace Security, Xi’an University of Posts and Telecommunications, Xi’an 710121, China

Received:2022-03-07 Online:2022-07-10 Published:2022-08-17
Contact: QIN Baodong E-mail:qinbaodong@xupt.edu.cn

摘要/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

中图分类号:

TP309

秦宝东, 余沛航, 郑东. 基于双陷门同态加密的决策树分类模型[J]. 信息网络安全, 2022, 22(7): 9-17.

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

图/表 5

图1

图2

图3

表1

表2

参考文献 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

基于双陷门同态加密的决策树分类模型

Decision Tree Classification Model Based on Double Trapdoor Homomorphic Encryption

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王鹃, 王蕴茹, 翁斌, 龚家新. 机器学习在x86二进制反汇编中的应用研究综述[J]. 信息网络安全, 2022, 22(6): 9-25.
[2]	刘嘉微, 马兆丰, 王姝爽, 罗守山. 基于区块链的隐私信用数据受限共享技术研究[J]. 信息网络安全, 2022, 22(5): 54-63.
[3]	吕国华, 胡学先, 杨明, 徐敏. 基于联邦随机森林的船舶AIS轨迹分类算法[J]. 信息网络安全, 2022, 22(4): 67-76.
[4]	陈彬杰, 魏福山, 顾纯祥. 基于KNN的具有隐私保护功能的区块链异常交易检测[J]. 信息网络安全, 2022, 23(3): 78-84.
[5]	段晓毅, 李邮, 令狐韫行, 胡荣磊. 基于RF算法的侧信道攻击方法研究[J]. 信息网络安全, 2022, 22(1): 19-26.
[6]	徐硕, 张睿, 夏辉. 基于数据属性修改的联邦学习隐私保护策略[J]. 信息网络安全, 2022, 22(1): 55-63.
[7]	路宏琳, 王利明, 杨婧. 一种新的参数掩盖联邦学习隐私保护方案[J]. 信息网络安全, 2021, 21(8): 26-34.
[8]	靳姝婷, 何泾沙, 朱娜斐, 潘世佳. 基于本体推理的隐私保护访问控制机制研究[J]. 信息网络安全, 2021, 21(8): 52-61.
[9]	郭春, 蔡文艳, 申国伟, 周雪梅. 基于关键载荷截取的SQL注入攻击检测方法[J]. 信息网络安全, 2021, 21(7): 43-53.
[10]	刘子昂, 黄缘缘, 马佳利, 周睿. 基于区块链的医疗数据滥用监控平台设计与实现[J]. 信息网络安全, 2021, 21(5): 58-66.
[11]	王健, 赵曼莉, 陈志浩, 石波. 基于假名的智能交通条件隐私保护认证协议[J]. 信息网络安全, 2021, 21(4): 49-61.
[12]	林文兵, 张敏情, 周能, 孔咏骏. 基于同态加密的密文域可逆信息隐藏技术研究[J]. 信息网络安全, 2021, 21(4): 73-80.
[13]	任航, 程相国, 张睿, 夏辉. 基于议价贝叶斯博弈模型的防欺诈策略[J]. 信息网络安全, 2021, 21(4): 81-88.
[14]	周由胜, 王明, 刘媛妮. 支持区间查询的基于位置服务外包数据隐私保护方案[J]. 信息网络安全, 2021, 21(3): 26-36.
[15]	路宏琳, 王利明. 面向用户的支持用户掉线的联邦学习数据隐私保护方法[J]. 信息网络安全, 2021, 21(3): 64-71.