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

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

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

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.