A Privacy-Preserving k-Means Clustering Algorithm Using Secure Comparison Protocol and Density-Based Center Point Selection

Since studies on privacy-preserving database outsourcing have been spotlighted in a cloud computing, databases need to be encrypted before being outsourced to the cloud. Rao et al. proposed a k-Means clustering algorithm that supports the protection of sensitive data by using a paillier cryptosystem[1]. However, the existing algorithm is inefficient due to bit-array based comparison. To solve this problem, we propose an efficient privacy-preserving k-Means clustering algorithm. First, we provide a new secure comparison protocol that performs the fast comparison of encrypted data. Second, we select center points by considering the distribution of the entire data. Finally, we show from our performance analysis that our clustering algorithm achieves about 300% better performance on average than the existing algorithm.