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

doi:10.19665/j.issn1001-2400.20230305

Abstract

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

CLC Number:

TP309.7

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.

Figures/Tables 12

References 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

Secure K-prototype clustering against the collusion of rational adversaries

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 45

Related Articles 11

Metrics

Comments

Recommended 0

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

[1]	CAO Laicheng,WU Wentao,FENG Tao,GUO Xian. Privacy preserving multi-classification LR scheme for data quality [J]. Journal of Xidian University, 2023, 50(5): 188-198.
[2]	SONG Cheng,CHENG Daochen,PENG Weiping. Efficient federated learning privacy protection scheme [J]. Journal of Xidian University, 2023, 50(5): 178-187.
[3]	WANG Bo,LI Hongtao,WANG Jie,GUO Yina. Federated learning scheme for privacy-preserving of medical data [J]. Journal of Xidian University, 2023, 50(5): 166-177.
[4]	LI Wenhua,DONG Lihua,ZENG Yong. Analysis and improvement of the security of the key-nets homomorphic encryption scheme [J]. Journal of Xidian University, 2023, 50(1): 192-202.
[5]	WANG Kaiwen,WANG Shulan,WANG Haiyan,DING Yong. Top-k multi-keyword ciphertext retrieval scheme supporting attribute revocation [J]. Journal of Xidian University, 2022, 49(1): 26-34.
[6]	CHE Xiaoliang,ZHOU Haonan,YANG Xiaoyuan,ZHOU Tanping,LIU Longfei,LI Ningbo. Efficient multi-key fully homomorphic encryption scheme from RLWE [J]. Journal of Xidian University, 2021, 48(1): 87-95.
[7]	ZHAO Zijun,YING Zuobin,YANG Zhao,LIU Ximeng,MA Jianfeng. Recommendation of platoon members by combining the blockchain and vehicular social network [J]. Journal of Xidian University, 2020, 47(5): 122-129.
[8]	HAN Kun;ZHANG Hailin;XIN Dan;WU Bo;KANG Yuanji. Design method of an identity-based fully homomorphic encryption library [J]. Journal of Xidian University, 2017, 44(4): 56-61.
[9]	YING Zuobin;MA Jianfeng;CUI Jiangtao. Attribute-based encryption with location verification and policy adjusting supporting the cloud mobile office [J]. Journal of Xidian University, 2017, 44(2): 57-62+190.
[10]	ZHANG Xue-jun1;2;WANG Dong-yong3;ZENG Zhi-yong2;YIN Zhong-hai2. A new traitor tracing scheme with extra properties [J]. J4, 2007, 34(2): 274-278.
[11]	ZHANG Xue-jun(1;2);ZENG Zhi-yong(1);ZHOU Li-hua(1). A multi-service oriented collusion-resistant asymmetric public-key traitor tracing scheme [J]. J4, 2006, 33(3): 471-475.