安全的常数轮多用户k-均值聚类计算协议

秦红; 王皓; 魏晓超; 郑志华

doi:10.7544/issn1000-1239.2020.20200407

安全的常数轮多用户k-均值聚类计算协议

¹(山东师范大学信息科学与工程学院济南 250358)
²(广西密码学与信息安全重点实验室(桂林电子科技大学) 广西桂林 541004) (1512699058@qq.com)

基金项目: 国家自然科学基金项目(61602287,61802235)；山东省重点研发计划项目(2018GGX101037)；山东省重大科技创新工程项目(2018CXGC0702); 广西密码学与信息安全重点实验室研究课题(GCIS201901)；山东半岛国家自主创新示范区建设项目(S190101010001)

详细信息

中图分类号: TP391
计量
- 文章访问数: 863
- HTML全文浏览量: 3
- PDF下载量: 267
出版历程
- 发布日期: 2020-09-30

Secure Constant-Round Multi-User k-Means Clustering Protocol

¹(School of Information Science and Engineering, Shandong Normal University, Jinan 250358)
²(Guangxi Key Laboratory of Cryptography and Information Security (Gulin University of Electronic Technology), Guilin, Guangxi 541004)

Funds: This work was supported by the National Natural Science Foundation of China (61602287, 61802235), the Key Research and Development Program of Shandong Province (2018GGX101037), the Major Innovation Project of Science and Technology of Shandong Province (2018CXGC0702), the Project of Guangxi Key Laboratory of Cryptography and Information Security (GCIS201901), and the Development and Construction Funds Project of National Independent Innovation Demonstration Zone in Shandong Peninsula (S190101010001).

摘要

摘要: 在多数聚类计算的实际应用中，样本数据通常来自于不同的用户，聚类算法往往需要在用户的联合数据集上进行计算. 而出于隐私保护的目的，用户并不希望与其他参与方共享其私有数据. 因此，如何以隐私保护的方式实现多用户的聚类计算便得到了人们的广泛关注.针对多用户持有数据的场景，研究了k-均值(k-means)聚类算法的安全计算问题，设计了常数轮交互的多用户k-means聚类安全计算协议. 在该协议中，用户使用加法同态加密方案对样本数据加密并上传至独立的辅助计算服务器. 服务器通过与持有私钥的聚类计算方交互，实现了乘法和欧氏距离的安全计算. 此外，基于ABY混合协议框架设计了针对同态密文的最小元素标记协议和除法协议. 协议通过常数轮交互，实现了同态密文、算术分享份额、Yao分享份额之间的相互转换，并利用Yao混乱电路技术实现了对同态密文的最小元素标记以及除法运算，该过程无需使用昂贵的比特分解技术. 在半诚实模型下给出了主协议及所有子协议的安全性证明.
- 隐私保护 /
- k-均值聚类 /
- 同态加密 /
- 秘密分享 /
- 混合协议
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.
- privacy-preserving /
- k-means clustering /
- homomorphic encryption /
- secret sharing /
- mixed protocol

HTML全文

参考文献(0)

施引文献(6)

期刊类型引用(3)

1.	舒晓苓，吴雪琴. 云计算网络下虚拟机负载均衡方法仿真. 计算机仿真. 2022(03): 358-361+412 . 百度学术
2.	魏辉，陈泽茂，张立强. 一种基于顺序和频率模式的系统调用轨迹异常检测框架. 计算机科学. 2022(06): 350-355 . 百度学术
3.	农嘉，王代远，潘梅勇，覃志松. 云计算环境下船舶监控网络异常数据检测方法. 舰船科学技术. 2021(08): 190-192 . 百度学术