高效的决策树隐私分类服务协议

doi:10.11959/j.issn.1000-436x.2021149

通信学报 ›› 2021, Vol. 42 ›› Issue (8): 80-89.doi: 10.11959/j.issn.1000-436x.2021149

高效的决策树隐私分类服务协议

马立川¹^,², 彭佳怡¹^,², 裴庆祺¹^,², 朱浩瑾³

¹ 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
² 陕西省区块链与安全计算重点实验室，陕西西安 710071
³ 上海交通大学计算机学院，上海 200240

修回日期:2021-06-15 出版日期:2021-08-25 发布日期:2021-08-01
作者简介:马立川（1988- ），男，山东潍坊人，博士，西安电子科技大学讲师，主要研究方向为信任管理机制、隐私保护、边缘计算安全等
彭佳怡（1997- ），女，陕西西安人，西安电子科技大学硕士生，主要研究方向为隐私保护、安全多方计算等
裴庆祺（1975- ），男，广西玉林人，博士，西安电子科技大学教授，主要研究方向为认知网络、物联网与边缘计算安全、无线网络物理层安全、区块链技术、分布式协同攻防技术等
朱浩瑾（1980- ），男，湖北武穴人，博士，上海交通大学教授，主要研究方向为车联网安全、移动网络安全与隐私保护等
基金资助:
国家重点研发计划基金资助项目(2020YFB1807500);国家自然科学基金资助项目(61902292);国家自然科学基金资助项目(61972453);国家自然科学基金资助项目(62072355);陕西省重点研发计划基金资助项目(2021ZDLGY06-03);陕西省重点研发计划基金资助项目(2019ZDLGY13-07);陕西省重点研发计划基金资助项目(2019ZDLGY13-04);中央高校基本科研业务费基金资助项目(XJS201502)

Efficient privacy-preserving decision tree classification protocol

Lichuan MA¹^,², Jiayi PENG¹^,², Qingqi PEI¹^,², Haojin ZHU³

¹ The State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China
² Shaanxi Key Laboratory of Blockchain and Secure Computing, Xi’an 710071, China
³ The Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Revised:2021-06-15 Online:2021-08-25 Published:2021-08-01
Supported by:
The National Key Research and Development Program of China(2020YFB1807500);The National Natural Science Foundation of China(61902292);The National Natural Science Foundation of China(61972453);The National Natural Science Foundation of China(62072355);The Key Research and Development Programs of Shaan-xi(2021ZDLGY06-03);The Key Research and Development Programs of Shaan-xi(2019ZDLGY13-07);The Key Research and Development Programs of Shaan-xi(2019ZDLGY13-04);The Fundamental Research Funds for the Central Univer-sities(XJS201502)

摘要/Abstract

摘要：

为了有效解决物联网大数据场景中的决策树隐私分类服务问题，将决策树分类模型与安全多方计算技术相结合，提出了一种高效的决策树隐私分类服务协议。该协议包括：决策树分类模型混淆、基于布尔共享的隐私比较和基于不经意传输的隐私分类结果获取3个阶段。该协议能够同时保护服务提供商决策树分类模型参数及结构特征和用户需要进行分类的特征数据不被泄露。安全性分析表明，所提决策树隐私分类服务协议能够抵抗“诚实好奇”的攻击者。将所提协议用于通过公开数据集得到的决策树分类模型，以分类准确率和完成隐私分类服务的时间效率为指标与现有方法进行对比，实验结果验证了所提出隐私分类服务协议的准确性和高效性。

关键词: 决策树, 隐私保护, 不经意传输, 安全多方计算

Abstract:

To provide privacy-preserving decision tree classification services in the Internet of things (IoT) big data scenario, an efficient privacy-preserving decision tree classification protocol was proposed by adopting the secure multiparty computation framework into the classification model.The entire protocol consisted of three parts: the original decision tree model mixing, the Boolean share-based privacy-preserving comparing, and the 1-out-of-n oblivious transfer-based classification result obtaining.Via the proposed protocol, the service providers could protect the parameters of their decision tree models and the users were able to derive the classification result without exposing their privately hold data.Through a concrete security analysis, the proposed protocol was proved to be secure against semi-honest adversaries.By implementing the proposed protocol on various practical decision tree models from open datasets, the classification accuracy and the average time cost for completing one privacy-preserving classification service were evaluated.After compared with existing related works, the performance superiority of the proposed protocol is demonstrated.

Key words: decision tree, privacy preserving, oblivious transfer, secure multiparty computation

中图分类号:

TN92

马立川, 彭佳怡, 裴庆祺, 朱浩瑾. 高效的决策树隐私分类服务协议[J]. 通信学报, 2021, 42(8): 80-89.

Lichuan MA, Jiayi PENG, Qingqi PEI, Haojin ZHU. Efficient privacy-preserving decision tree classification protocol[J]. Journal on Communications, 2021, 42(8): 80-89.

图/表 6

图1

表1

数学符号及含义"

参数	含义
S	拥有决策树分类模型的云服务器
C	请求决策树隐私分类的用户
T	决策树分类模型
$x$	用户数据
z_x	$x$ 所对应的分类结果
$I : V \to [1, \dots, d]$	标记函数
$I V_{0}$	原始决策树分类模型内部节点标号序列
$I X_{0}$	与 $I V_{0}$ 对应的属性标号序列
$W_{0}$	与 $I V_{0}$ 对应的内部节点阈值序列
δ_r	定义在 $I V_{0}$ 上的随机置换
$L V$	$I V_{0}$ 经过函数δ_r作用后的随机置换
$L X$	与 $I V_{r}$ 对应的属性标号序列
$W_{r}$	与 $I V_{r}$ 对应的内部节点阈值序列
[x]	x的二进制表示
$[x]_{S}, [x]_{C}$	[x]的布尔共享，且 $[x] = [x]_{S} \oplus [x]_{C}$
⊕	“异或”运算
?	“与”运算
$(_{1}^{n}) O T_{λ}$	1-out-of-n不经意传输过程

表1

图2

表2

图3

图4

参考文献 26

[1]	NESHENKO N , BOU-HARB E , CRICHIGNO J ,et al. Demystifying IoT security:an exhaustive survey on IoT vulnerabilities and a first empirical look on Internet-scale IoT exploitations[J]. IEEE Communications Surveys ＆ Tutorials, 2019,21(3): 2702-2733.
[2]	CVITI? I , PERAKOVI? D ， PERI? ,et al. Novel approach for detection of IoT generated DDoS traffic[J]. Wireless Networks, 2021,27(3): 1573-1586.
[3]	MOHAMMADI M , AL-FUQAHA A , SOROUR S ,et al. Deep learning for IoT big data and streaming analytics:a survey[J]. IEEE Communications Surveys ＆ Tutorials, 2018,20(4): 2923-2960.
[4]	陈立南, 刘阳, 马严 ,等. 基于统计的高效决策树分组分类算法[J]. 通信学报, 2014,35(Z1): 58-64.
	CHEN L N , LIU Y , MA Y ,et al. Efficient-cutting packet classification algorithm based on the statistical decision tree[J]. Journal on Communications, 2014,35(Z1): 58-64.
[5]	LI T , LI X , ZHONG X Y ,et al. Communication-efficient outsourced privacy-preserving classification service using trusted processor[J]. Information Sciences, 2019,505: 473-486.
[6]	PINHEIRO A J , DE M BEZERRA J , BURGARDT C A P ,et al. Identifying IoT devices and events based on packet length from encrypted traffic[J]. Computer Communications, 2019,144: 8-17.
[7]	STALLINGS W . Handling of personal information and deidentified,aggregated,and pseudonymized information under the California consumer privacy act[J]. IEEE Security ＆ Privacy, 2020,18(1): 61-64.
[8]	SHASTRI S , WASSERMAN M , CHIDAMBARAM V . GDPR anti-patterns[J]. Communications of the ACM, 2021,64(2): 59-65.
[9]	QI A M , SHAO G S , ZHENG W T . Assessing China's cybersecurity law[J]. Computer Law ＆ Security Review, 2018,34(6): 1342-1354.
[10]	LIANG J W , QIN Z , XIAO S ,et al. Efficient and secure decision tree classification for cloud-assisted online diagnosis services[J]. IEEE Transactions on Dependable and Secure Computing, 2021,18(4): 1632-1644.
[11]	BOST R , POPA R A , TU S ,et al. Machine learning classification over encrypted data[C]// Proceedings 2015 Network and Distributed System Security Symposium. VA:Internet Society, 2015: 4324-4325.
[12]	WU D J , FENG T , NAEHRIG M ,et al. Privately evaluating decision trees and random forests[J]. Proceedings on Privacy Enhancing Technologies, 2016,2016(4): 335-355.
[13]	TUENO A , KERSCHBAUM F , KATZENBEISSER S . Private evaluation of decision trees using sublinear cost[J]. Proceedings on Privacy Enhancing Technologies, 2019,2019(1): 266-286.
[14]	刘琳岚, 高声荣, 舒坚 . 基于随机森林的链路质量预测[J]. 通信学报, 2019,40(4): 202-211.
	LIU L L , GAO S R , SHU J . Link quality prediction based on random forest[J]. Journal on Communications, 2019,40(4): 202-211.
[15]	CHEN X , ZHU C C , YIN J . Ensemble of decision tree reveals potential miRNA-disease associations[J]. PLoS Computational Biology, 2019,15(7): 1-24.
[16]	李佳, 云晓春, 李书豪 ,等. 基于混合结构深度神经网络的 HTTP恶意流量检测方法[J]. 通信学报, 2019,40(1): 24-33.
	LI J , YUN X C , LI S H ,et al. HTTP malicious traffic detection method based on hybrid structure deep neural network[J]. Journal on Communications, 2019,40(1): 24-33.
[17]	LI F H , LI H , NIU B ,et al. Privacy computing:concept,computing framework,and future development trends[J]. Engineering, 2019,5(6): 1179-1192.
[18]	RAN C . Security and composition of multiparty cryptographic protocols[J]. Journal of Cryptology, 2000,13(1): 143-202.
[19]	BRAKERSKI Z , GENTRY C , VAIKUNTANATHAN V . Fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014,6(3): 1-36.
[20]	DAMGARD I , GEISLERR M , KROIGAARD M . Efficient and secure comparison for on-line auctions[C]// 2007Australasian conference on information security and privacy. Berlin:Springer, 2007: 416-430.
[21]	ERKIN Z , FRANZ M , GUAJARDO J ,et al. Privacy-preserving face recognition[C]// International Symposium on Privacy Enhancing Technologies Symposium. Berlin:Springer, 2009: 235-253.
[22]	GOLDREICH O , MICALI S , WIGDERSON A . How to play any mental game,or a completeness theorem for protocols with honest majority[C]// Proceedings of the 19th Symposium on Theory of Computing. New York:ACM Press, 2019: 307-328.
[23]	KOLESNIKOV V , SADEGHI A R , SCHNEIDER T . Improved garbled circuit building blocks and applications to auctions and computing minima[C]// International Conference on Cryptology and Network Security. Berlin:Springer, 2009: 1-20.
[24]	BEAVER D , . Efficient multiparty protocols using circuit randomization[C]// Annual International Cryptology Conference. Berlin:Springer, 1991: 420-432.
[25]	NAOR M , PINKAS B . Computationally secure oblivious transfer[J]. Journal of Cryptology, 2005,18(1): 1-35.
[26]	ASHAROV G , LINDELL Y , SCHNEIDER T ,et al. More efficient oblivious transfer and extensions for faster secure computation[C]// 2013 ACM SIGSAC conference on Computer ＆ communications security. New York:ACM Press, 2013: 535-548.

数据集	分类准确率
数据集	明文状态	本文协议
Breast-cancer	0.894	0.894
Nursery	0.936	0.936
ECG	0.886	0.886
Credit-screening	0.877	0.877
Housing	1.000	1.000
Spambase	0.990	0.990

高效的决策树隐私分类服务协议

Efficient privacy-preserving decision tree classification protocol

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 26

相关文章 15

Metrics

推荐阅读 0

[1]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	夏莹杰, 朱思雨, 刘雪娇. 区块链架构下具有条件隐私的车辆编队跨信任域高效群组认证研究[J]. 通信学报, 2023, 44(4): 111-123.
[4]	胡柏吉, 张晓娟, 李元诚, 赖荣鑫. 支持多功能的V2G网络隐私保护数据聚合方案[J]. 通信学报, 2023, 44(4): 187-200.
[5]	徐明, 张保俊, 伍益明, 应晨铎, 郑宁. 面向网络攻击和隐私保护的多智能体系统分布式共识算法[J]. 通信学报, 2023, 44(3): 117-127.
[6]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[7]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[8]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[9]	封化民, 史瑞, 袁峰, 李艳俊, 杨旸. 高效的强隐私保护和可转让的属性票据方案[J]. 通信学报, 2022, 43(3): 63-75.
[10]	于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.
[11]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[12]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[13]	熊金波, 周永洁, 毕仁万, 万良, 田有亮. 边缘协同的轻量级隐私保护分类框架[J]. 通信学报, 2022, 43(1): 127-137.
[14]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.
[15]	刘辉, 刘鑫衍, 许艳, 仲红, 王梦. 隐私保护的VANET警告消息发布协议[J]. 通信学报, 2021, 42(8): 120-129.