Secure Constant-Round Multi-User k-Means Clustering Protocol
-
摘要: 在多数聚类计算的实际应用中,样本数据通常来自于不同的用户,聚类算法往往需要在用户的联合数据集上进行计算. 而出于隐私保护的目的,用户并不希望与其他参与方共享其私有数据. 因此,如何以隐私保护的方式实现多用户的聚类计算便得到了人们的广泛关注.针对多用户持有数据的场景,研究了k-均值(k-means)聚类算法的安全计算问题,设计了常数轮交互的多用户k-means聚类安全计算协议. 在该协议中,用户使用加法同态加密方案对样本数据加密并上传至独立的辅助计算服务器. 服务器通过与持有私钥的聚类计算方交互,实现了乘法和欧氏距离的安全计算. 此外,基于ABY混合协议框架设计了针对同态密文的最小元素标记协议和除法协议. 协议通过常数轮交互,实现了同态密文、算术分享份额、Yao分享份额之间的相互转换,并利用Yao混乱电路技术实现了对同态密文的最小元素标记以及除法运算,该过程无需使用昂贵的比特分解技术. 在半诚实模型下给出了主协议及所有子协议的安全性证明.Abstract: In most of the practical applications of cluster calculation, the data usually comes from different users, and the cluster algorithm often needs to be calculated on the joint data of them. For privacy protection purposes, users do not want to share their private data with others. Therefore, how to implement multi-user cluster calculation in a privacy-preserving way has attracted widespread attention. In this paper, we research the secure computation of k-means cluster algorithm in the scenario where multiple users hold data, and design a constant round secure multi-user k-means cluster protocol. In this protocol, users encrypt data using additive homomorphic encryption and upload data to an independent assisted server. Then, this server implements the secure computation of multiplication and Euclidean distance by interacting with cluster calculator holding the private key. In addition, we also design a minimal element marking protocol and a division protocol for homomorphic ciphertext based on the ABY framework. The protocol realizes the conversion among homomorphic ciphertexts, arithmetic shares and Yao shares through constant round interaction without expensive bit-decomposition technology. We give the formal security proof of main protocol and all sub-protocols in the semi-honest model. Finally, we give the efficiency analysis and performance test of our scheme.
-
Keywords:
- privacy-preserving /
- k-means clustering /
- homomorphic encryption /
- secret sharing /
- mixed protocol
-
-
期刊类型引用(8)
1. 李晶,贾园园,张磊. MuSig多重签名的实用拜占庭容错共识算法. 计算机应用研究. 2025(02): 352-356 . 百度学术
2. 时小虎,姚鑫,孙延风,马德印. 基于贡献度和数据有效性检验的共识机制. 东北大学学报(自然科学版). 2024(02): 160-169+178 . 百度学术
3. 万林. 基于区块链技术的P2P网络分布式数字签名系统设计. 安徽水利水电职业技术学院学报. 2024(03): 43-48 . 百度学术
4. 唐淑敏,金瑜. 区块链中基于中国剩余定理投票方案的共识机制. 计算机应用. 2023(02): 458-466 . 百度学术
5. 张宝,田有亮,高胜. 基于博弈论抗共谋攻击的全局随机化共识算法. 网络与信息安全学报. 2022(04): 98-109 . 百度学术
6. 刘恒飞,张毅. 区块链技术及其应用. 福建电脑. 2021(01): 174-175 . 百度学术
7. 李杰,李雷孝,孔冬冬. 一种基于中文助记词的椭圆曲线密钥生成方案. 内蒙古工业大学学报(自然科学版). 2020(02): 128-135 . 百度学术
8. 张彭奕,宋杰. 区块链共识算法效能优化研究进展. 计算机科学. 2020(12): 296-303 . 百度学术
其他类型引用(9)
计量
- 文章访问数: 864
- HTML全文浏览量: 3
- PDF下载量: 267
- 被引次数: 17