# Secure K-Means Clustering Scheme for Confidential Data Based on Paillier Cryptosystem
###### Abstract  
In this paper, we propose a secure homomorphic K-means clustering protocol based on the Paillier cryptosystem to address the urgent need for privacy-preserving clustering techniques in sensitive domains such as healthcare and finance. The protocol uses the additive homomorphism property of the Paillier cryptosystem to perform K-means clustering on the encrypted data, which ensures the confidentiality of the data during the whole calculation process. The protocol consists of three main components: secure computation distance (SCD) protocol, secure cluster assignment (SCA) protocol and secure cluster center update (SUCC) protocol. The SCD protocol securely computes the squared Euclidean distance between the encrypted data point and the encrypted cluster center. The SCA protocol securely assigns data points to clusters based on these cryptographic distances. Finally, the SUCC protocol securely updates the cluster centers without leaking the actual data points as well as the number of intermediate sums. Through security analysis and experimental verification, the effectiveness and practicability of the protocol are proved. This work provides a practical solution for secure clustering based on homomorphic encryption and contributes to the research in the field of privacy-preserving data mining. Although this protocol solves the key problems of secure distance computation, cluster assignment and centroid update, there are still areas for further research. These include optimizing the computational efficiency of the protocol, exploring other homomorphic encryption schemes that may provide better performance, and extending the protocol to handle more complex clustering algorithms. K-means; privacy preserving; multi-key; fully homomorphic encryption; outsourced computing +
Footnote †: journal: Applied sciences  
0000-0001-9300-3300]Z.Z. notable for its additive homomorphic properties, which are useful for performing arithmetic operations on encrypted data. In this study, we propose a secure homomorphic K-means clustering protocol using the Paillier cryptosystem [3]. Our protocol allows the K-means clustering algorithm to be executed on encrypted data, ensuring that sensitive information remains confidential throughout the computation. This is achieved by exploiting the additive homomorphism property of the Paillier cryptosystem and a privacy-preserving [4] framework for the outsourced computation of rational numbers, allowing operations such as sums and averages to be computed securely in the K-means algorithm. The proposed protocol consists of three main components: the secure computation distance (SCD) protocol, the secure cluster assignment (SCA) protocol, and the secure update cluster center (SUCC) protocol. Each of these components addresses specific challenges in ensuring the privacy and security of the clustering process. The secure computation distance (SCD) protocol ensures that the squared Euclidean distance between data points and cluster centers is computed securely without decrypting the data, thereby preserving the privacy of both data points and cluster centers. The secure cluster assignment (SCA) protocol securely assigns data points to clusters using the encrypted squared distances between data points and cluster centers, ensuring that cluster assignments are made without revealing the actual distances or cluster memberships. Finally, the secure update cluster center (SUCC) protocol securely updates the cluster centers without revealing the actual data points or intermediate sums and counts, maintaining the confidentiality of sensitive information throughout the update process. Previous research has explored various approaches to privacy-preserving clustering, such as differential privacy [5] and secure multi-party computation (SMPC) [6; 7; 8; 9]. However, these methods often involve trade-offs between accuracy, complexity, and computational efficiency.