ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (10): 2188-2200.doi: 10.7544/issn1000-1239.2020.20200407

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

Previous Articles     Next Articles

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).

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

CLC Number: