抗理性敌手共谋的安全K-prototype聚类

doi:10.19665/j.issn1001-2400.20230305

西安电子科技大学学报 ›› 2024, Vol. 51 ›› Issue (2): 196-210.doi: 10.19665/j.issn1001-2400.20230305

• 计算机科学与技术&网络空间安全 • 上一篇下一篇

抗理性敌手共谋的安全K-prototype聚类

田有亮¹^,²^,³^,⁴(), 赵敏¹^,²^,³^,⁴(), 毕仁万⁵(), 熊金波¹^,²^,⁵()

1.贵州大学公共大数据国家重点实验室,贵州贵阳 550025
2.贵州大学计算机科学与技术学院,贵州贵阳 550025
3.贵州大学密码学与数据安全研究所,贵州贵阳 550025
4.贵州省密码学与区块链技术特色重点实验室,贵州贵阳 550025
5.福建师范大学计算机与网络空间安全学院,福建福州 350117

收稿日期:2022-10-31 出版日期:2024-04-20 发布日期:2023-10-07
通讯作者: 熊金波(1981—),男,教授,Email:jbxiong@fjnu.edu.cn
作者简介:田有亮(1982—),男,教授,E-mail:youliangtian@163.com;
赵敏(1995—),女,贵州大学硕士研究生,E-mail:2233174061@qq.com;
毕仁万(1996—),男,福建师范大学博士研究生,E-mail:brw2806@163.com
基金资助:
国家重点研发计划(2021YFB3101100);国家自然科学基金(62272123);国家自然科学基金(62272102);贵州省高层次创新型人才(黔科合平台人才[2020]6008);贵阳市科技计划(筑科合[2021]1-5);贵阳市科技计划(筑科合[2022]2-4);贵州省科技计划(黔科合平台人才[2020]5017);贵州省科技计划(黔科合支撑[2022]一般065)

Secure K-prototype clustering against the collusion of rational adversaries

TIAN Youliang¹^,²^,³^,⁴(), ZHAO Min¹^,²^,³^,⁴(), BI Renwan⁵(), XIONG Jinbo¹^,²^,⁵()

1. State Key Laboratory of Public Big Date,Guizhou University,Guiyang 550025,China
2. College of Computer Science and Technology,Guizhou University,Guiyang 550025,China
3. Institute of Cryptography & Data Security,Guizhou University,Guiyang 550025,China
4. Guizhou Provincial Key Laboratory of Cryptography & Blockchain Technology,Guiyang 550025,China
5. College of Computer and Cyber Security,Fujian Normal University,Fuzhou 350117,China

Received:2022-10-31 Online:2024-04-20 Published:2023-10-07

摘要/Abstract

摘要：

针对云环境下数据隐私泄露及聚类过程中云服务器间共谋的问题,提出一种抗理性敌手共谋的安全协作K-prototype聚类方案,目的在不泄露各方隐私数据情况下根据距离度量将相似的数据进行聚类。首先,考虑到同态加密不直接支持非线性计算,基于同态加密和加性秘密共享技术设计安全比较协议和安全大于协议,并确保输入数据、中间结果及模型参数均为加性秘密份额形式,以防止单个服务器能够获得完整数据,且能实现非线性函数的精确计算,在已设计的安全计算协议基础上,实现安全距离计算、安全聚类标签更新、安全聚类中心更新、聚类标签及聚类中心重构;其次,根据博弈均衡理论设计多种高效激励机制,构造互制合约及举报合约以约束云服务器诚实非共谋地执行聚类任务;最后,对所提的安全计算协议及合约进行理论分析,并对该方案的性能进行实验验证。实验结果表明,与明文环境下的模型精度相比,该方案的模型精度损失控制在0.22%内,进而验证了所提方案的有效性。

关键词: 加性秘密共享, 同态加密, 安全计算协议, 抗共谋, 安全协作

Abstract:

Aiming at the problem of data privacy leakage in cloud environment and collusion between cloud servers in the process of clustering,an cooperative secure K-prototype clustering scheme(CSKC) against the adversaries of rational collusion is proposed.First,considering that homomorphic encryption does not directly support nonlinear computing,secure computing protocols are designed based on homomorphic encryption and additive secret sharing to ensure that the input data and intermediate results are in the form of additive secret share,and to achieve accurate calculation of the security comparison function.Second,according to the game equilibrium theory,a variety of efficient incentive mechanisms are designed,and the mutual condition contract and report contract are constructed to constrain cloud servers to implement secure computing protocols honestly and non-collusively.Finally,the proposed protocols and contracts are analyzed theoretically,and the performance of the CSKC scheme is verified by experiment.Experimental results show that compared with the model accuracy in plaintext environment,the model accuracy loss of the CSKC scheme is controlled within 0.22%.

Key words: additive secret sharing, homomorphic encryption, secure computing protocol, collusion-resistance, cooperative securely

中图分类号:

TP309.7

田有亮, 赵敏, 毕仁万, 熊金波. 抗理性敌手共谋的安全K-prototype聚类[J]. 西安电子科技大学学报, 2024, 51(2): 196-210.

TIAN Youliang, ZHAO Min, BI Renwan, XIONG Jinbo. Secure K-prototype clustering against the collusion of rational adversaries[J]. Journal of Xidian University, 2024, 51(2): 196-210.

图/表 12

图1

图2

图3

表1

表2

表3

表4

图4

表5

图5

图6

表6

参考文献 45

[1]	LIU Y, MA Z, LIU X, et al. Privacy-Preserving Object Detection for Medical Images with Faster R-CNN[J]. IEEE Transactions on Information Forensics and Security, 2022,17:69-84.
[2]	GUO Y, BI L, AHN E, et al. A Spatiotemporal Volumetric Interpolation Network for 4d Dynamic Medical Image[C]//2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition(CVPR). Piscataway:IEEE, 2020: 4725-4734.
[3]	LUO X, LI L, WAN H, et al. Phone Keypad Voice Recognition:An Integrated Experiment for Digital Signal Processing Education[C]//2020 IEEE Frontiers in Education Conference(FIE). Piscataway:IEEE, 2020: 1-4.
[4]	XIONG J, BI R, TIAN Y, et al. Toward Lightweight,Privacy-Preserving Cooperative Object Classification for Connected Autonomous Vehicles[J]. IEEE Internet of Things Journal, 2022, 9(4):2787-2801.
[5]	XIONG J, BI R, ZHAO M, et al. Edge-Assisted Privacy-Preserving Raw Data Sharing Framework for Connected Autonomous Vehicles[J]. IEEE Wireless Communications, 2020, 27(3):24-30.
[6]	ZENG Y, ZHANG Z Y, LIU J L, et al. Pri-EMO:A Universal Perturbation Method for Privacy Preserving Facial Emotion Recognition[J]. Journal of Information and Intelligence, 2023, 1(4):330-340.
[7]	CARTER H, MOOD B, TRAYNOR P, et al. Secure Outsourced Garbled Circuit Evaluation for Mobile Devices[J]. Journal of Computer Security, 2016, 24(2):137-180.
[8]	LUO Y K, LUO W J, ZHANG R Z, et al. RobustPeer-to-Peer Learning via Secure Multi-Party Computation[J]. Journal of Information and Intelligence, 2023, 1(4):341-351.
[9]	MOHASSEL P, ROSULEK M, TRIEU N. Practical Privacy Preserving K-means Slustering[J]. Proceedings on Privacy Ehancing Technologies, 2020(4):414-433.
[10]	张馨予. 基于博弈系统论的安全多方计算协议的分析与设计[D]. 贵阳: 贵州大学, 2021.
[11]	JAGANNATHAN G, WRIGHT R N. Privacy-Preserving Distributed K-means Clustering over Arbitrarily Partitioned Data[C]//Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. New York: ACM, 2005:593-599.
[12]	XING K, HU C, YU J, et al. Mutual Privacy Preserving K-means Clustering in Social Participatory Sensing[J]. IEEE Transactions on Industrial Informatics, 2017, 13(4):2066-2076.
[13]	BUNN P, OSTROVSKY R. Secure Two-Party K-means Clustering[C]//Proceedings of the 14th ACM Conference on Computer and Communications Security. New York: ACM, 2007:486-497.
[14]	LIU D, BERTINO E, YI X. Privacy of Outsourced K-means Clustering[C]//Proceedings of the 9th ACM Symposium on Information,Computer and Communications Security. New York: ACM. 2014:123-134.
[15]	JIANG Z L, GUO N, JIN Y, et al. Efficient Two-Party Privacy-Preserving Collaborative K-means Clustering Protocol Supporting Both Storage and Computation Outsourcing[J]. Information Sciences, 2020,518:168-180.
[16]	JHA S, KRUGER L, MCDANIEL P. Privacy Preserving Clustering[C]//Computer Security(ESORICS 2005). Berlin:Springer, 2005:397-417.
[17]	FAN Y, BAI J, LEI X, et al. PPMCK:Privacy-Preserving Multi-Party Computing for K-means Clustering[J]. Journal of Parallel and Distributed Computing, 2021,154:54-63.
[18]	YUAN J, TIAN Y. Practical Privacy-Preserving Mapreduce Based K-means Clustering over Large-Scale Dataset[J]. IEEE Transactions on Cloud Computing, 2019, 7(2):568-579.
[19]	BUNN P, OSTROVSKY R. Oblivious Sampling with Applications to Two-Party K-means Clustering[J]. Journal of Cryptology, 2020, 33(3):1362-1403.
[20]	ZOU Y, ZHAO Z, SHI S, et al. Highly Secure Privacy-Preserving Outsourced K-means Clustering under Multiple Keys in Cloud Computing[J]. Security and Communication Networks, 2020,1238505:1-11.
[21]	WU W, LIU J, WANG H M, et al. Secure and Efficient Outsourced K-means Clustering Using Fully Homomorphic Encryption with Ciphertext Packing Technique[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(10):3424-3437.
[22]	车小亮, 周昊楠, 杨晓元, 等. 环LWE上高效的多密钥全同态加密方案[J]. 西安电子科技大学学报, 2021, 48(1):87-95.
	CHE Xiaoliang, ZHOU Haonan, YANG Xiaoyuan, et al. Efficient Multi-Key Fully Homomorphic Encryption Scheme from RLWE[J]. Journal of Xidian University, 2021, 48(1):87-95.
[23]	BLUM A, DWORK C, MCSHERRY F, et al. Practical Privacy:the SuLQ Framework[C]//Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2005:128-138.
[24]	FELDMAN D, FIAT A, KAPLAN H, et al. Private Coresets[C]//Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. New York: ACM, 2009:361-370.
[25]	FELDMAN D, XIANG C, ZHU R, et al. Coresets for Differentially Private K-means Clustering and Applications to Privacy in Mobile Sensor Networks[C]//Proceedings of the 2017 16th ACM/IEEE International Conference on Information Processing in Sensor Networks(IPSN). Piscataway:IEEE, 2017:3-16.
[26]	NGUYEN HH. Privacy-Preserving Mechanisms for K-Modes Clustering[J]. Computers & Security, 2018,78:60-75.
[27]	YUAN L, ZHANG S, ZHU G, et al. Privacy Preserving Mechanism for Mixed Data Clustering with Local Differential Privacy[J]. Concurrency and Computation:Practice and Experience, 2023, 35(19):e6503.1- e6503.15.
[28]	ZHANG E, LI H, HUANG Y, et al. Practical Multi-Party Private Collaborative K-means Clustering[J]. Neurocomputing, 2022,467:256-265.
[29]	BI R, XIONG J, LIN J, et al. Outsourced and Practical Privacy-Preserving K-prototype Clustering Supporting Mixed Data[C]//Proceedings of the IEEE International Conference on Communications. Piscataway:IEEE, 2022:5645-5650.
[30]	KÜPÇÜ A. Incentivized Outsourced Computation Resistant to Malicious Contractors[J]. IEEE Transactions on Dependable and Secure Computing, 2017, 14(6):633-649.
[31]	WU S, CHEN Y, WANG Q, et al. CReam:A Smart Contract Enabled Collusion-Resistant E-Auction[J]. IEEE Transactions on Information Forensics and Security, 2019, 14(7):1687-1701.
[32]	LI Q, TIAN Y. Rational Eelegation Computing Using Information Theory and Game Theory Approach[C]//MultiMedia Modeling(MMM 2020). Berlin:Springer, 2020:669-680.
[33]	DONG C, WANG Y, ALDWEESH A, et al. Betrayal,Distrust,and Rationality:Smart Counter-Collusion Contracts for Verifiable Cloud Computing[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017:211-227.
[34]	CHEN Z, TIAN Y, XIONG J, et al. Towards Reducing Delegation Overhead in Replication-Based Verification:An Incentive- Compatible Rational Delegation Computing Scheme[J]. Information Sciences, 2021,568:286-316.
[35]	HUANG Z. Clustering Large Data Sets with Mixed Numeric and Categorical Values[C]//Proceedings of the 1st Pacific-Asia Conference on Knowledge Discovery and Data Mining(PAKDD). Singapore:PAKDD, 1997:21-34.
[36]	SHAMIR A. How to Share a Secret[J]. Communications of the ACM, 1979, 22(11):612-613.
[37]	PAILLIER P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]//Advances in Cryptology(EUROCRYPT 1999). Berlin:Springer, 1999:223-238.
[38]	CHEN Z, TIAN Y, PENG C. An Incentive-Compatible Rational Secret Sharing Scheme Using Blockchain and Smart Contract[J]. Science China Information Sciences, 2021, 64(202301):1-21.
[39]	赵敏, 田有亮, 熊金波, 等. 基于同态加密的神经网络模型训练方法[J]. 计算机科学, 2023, 50(5):372-381. doi: 10.11896/jsjkx.220300239
	ZHAO Min, TIAN Youliang, XIONG Jinbo, et al. Neural Network Model Training Method Based on Homomorphic Encryption[J]. Computer Science, 2023, 50(5):372-381. doi: 10.11896/jsjkx.220300239
[40]	王伊蕾, 徐秋亮. 理性安全多方计算研究[J]. 密码学报, 2014, 1(5):481-490. doi: 10.13868/j.cnki.jcr.000045
	WANG Yilei, XU Qiuliang. Survey on Rational Secure Multi-Party Computation[J]. Journal of Cryptologic Research, 2014, 1(5):481-490.
[41]	张恩, 朱君哲, 范海菊, 等. 基于电路计算的理性安全多方求和协议[J]. 密码学报, 2019, 6(1):123-132. doi: 10.13868/j.cnki.jcr.000289
	ZHANG En, ZHU Junzhe, FAN Haiju, et al. Rational Secure Multiparty Sum Protocol Based on Circuit Computing[J]. Journal of Cryptologic Research, 2019, 6(1):123-132.
[42]	LIU Y, MA Z, LIU X M, et al. Privacy-Preserving Object Detection for Medical Images with Faster R-CNN[J]. IEEE Transactions on Information Forensics and Security, 2022,17:69-84.
[43]	熊金波, 毕仁万, 陈前昕, 等. 边缘协作的轻量级安全区域建议网络[J]. 通信学报, 2020, 41(10):188-201. doi: 10.11959/j.issn.1000-436x.2020186
	XIONG Jinbo, Bi Renwan, CHEN Qianxin, et al. Towards Edge-Collaborative,Lightweight and Secure Region Proposal Network[J]. Journal on Communications, 2020, 41(10):188-201. doi: 10.11959/j.issn.1000-436x.2020186
[44]	WAGH S, TOPLE S, BENHAMOUDA F, et al. Falcon:Honest-Majority Maliciously Secure Framework for Private Deep Learning[J]. Proceedings on Privacy Enhancing Technologies, 2021(1):188-208.
[45]	HUANG K, LIU X M, FU S, et al. A Lightweight Privacy-Preserving CNN Feature Extraction Framework for Mobile Sensing[J]. IEEE Transactions on Dependable and Secure Computing, 2021, 18(3):1441-1455.

协议	Enc	PAdd	PMult	Dec
SComp	n	n	n	n
SGP	n	n	n	n

协议	文献[44]	文献[45]	CSKC
SComp	2+log l	l+1	2
SGP			2

协议	通信开销
SComp	2‖C‖+2‖M‖
SGP	2‖C‖+2‖M‖

方案	客户端与服务器通信轮数	总通信复杂度
文献[12]		O(qmt(t-1)+qmt)
文献[15]	O(t(m₁+m₂))	O(qmt)
CSKC	0	O(2qmt)

参与方	SComp	SGP
S'_i	1.9	1.9
S″_i	1.9	1.9

抗理性敌手共谋的安全K-prototype聚类

Secure K-prototype clustering against the collusion of rational adversaries

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 45

相关文章 11

Metrics

本文评价

推荐阅读 0

方案	客户端离线	数据保护	簇中心保护	混合属性	抗共谋	可验证
文献[15]	×	√	×	×	×	×
文献[14]	×	√	×	×	×	×
文献[17]	×	√	√	×	×	×
文献[9]	√	√	√	×	×	×
文献[12]	×	√	√	×	√	×
文献[29]	√	√	√	√	×	×
CSKC	√	√	√	√	√	√

[1]	曹来成,吴文涛,冯涛,郭显. 面向数据质量的隐私保护多分类LR方案[J]. 西安电子科技大学学报, 2023, 50(5): 188-198.
[2]	宋成,程道晨,彭维平. 一种高效的联邦学习隐私保护方案[J]. 西安电子科技大学学报, 2023, 50(5): 178-187.
[3]	王波,李洪涛,王洁,郭一娜. 面向医疗数据的隐私保护联邦学习架构[J]. 西安电子科技大学学报, 2023, 50(5): 166-177.
[4]	李文华,董丽华,曾勇. key-nets同态加密方案的安全性分析及改进[J]. 西安电子科技大学学报, 2023, 50(1): 192-202.
[5]	王凯文,王树兰,王海燕,丁勇. 一种支持属性撤销的top-k多关键词密文检索方案[J]. 西安电子科技大学学报, 2022, 49(1): 26-34.
[6]	车小亮,周昊楠,杨晓元,周潭平,刘龙飞,李宁波. 环LWE上高效的多密钥全同态加密方案[J]. 西安电子科技大学学报, 2021, 48(1): 87-95.
[7]	赵子军,应作斌,杨钊,刘西蒙,马建峰. 结合区块链和车辆社交网络的车队成员推荐[J]. 西安电子科技大学学报, 2020, 47(5): 122-129.
[8]	韩鹍;张海林;辛丹;吴波;康元基. 利用身份的全同态加密函数库设计方法[J]. 西安电子科技大学学报, 2017, 44(4): 56-61.
[9]	应作斌;马建峰;崔江涛. 支持位置验证和策略变更的属性加密方案[J]. 西安电子科技大学学报, 2017, 44(2): 57-62+190.
[10]	张学军1;2;王东勇3;曾智勇2;尹忠海2. 一种新的具有附加特性的叛逆者追踪方案 [J]. J4, 2007, 34(2): 274-278.
[11]	张学军(1;2);曾智勇(1);周利华(1). 一种面向多服务的抗共谋非对称公钥叛逆者追踪方案[J]. J4, 2006, 33(3): 471-475.