ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (10): 2188-2200.doi: 10.7544/issn1000-1239.2020.20200407

所属专题: 2020密码学与数据隐私保护研究专题

• 信息安全 • 上一篇    下一篇



  1. 1(山东师范大学信息科学与工程学院 济南 250358);2(广西密码学与信息安全重点实验室(桂林电子科技大学) 广西桂林 541004) (
  • 出版日期: 2020-10-01
  • 基金资助: 
    国家自然科学基金项目(61602287,61802235);山东省重点研发计划项目(2018GGX101037);山东省重大科技创新工程项目(2018CXGC0702); 广西密码学与信息安全重点实验室研究课题(GCIS201901);山东半岛国家自主创新示范区建设项目(S190101010001)

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

Qin Hong1, Wang Hao1,2, Wei Xiaochao1, Zheng Zhihua1   

  1. 1(School of Information Science and Engineering, Shandong Normal University, Jinan 250358);2(Guangxi Key Laboratory of Cryptography and Information Security (Gulin University of Electronic Technology), Guilin, Guangxi 541004)
  • Online: 2020-10-01
  • Supported by: 
    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.

Key words: privacy-preserving, k-means clustering, homomorphic encryption, secret sharing, mixed protocol