Privacy Preserving Outsourced K-means Clustering Using Kd-tree

Nowadays, more and more resource-constrained individuals and corporations tend to outsource their data and machine learning tasks to cloud servers, enjoying high-quality data storage and computing services ubiquitously. However, outsourcing sensitive data can bring data security and privacy issues, arousing public concerns. In this work, we propose an efficient privacy-preserving outsourced scheme of K-means clustering on encrypted data in the twin-cloud model using the paradigm of secret sharing. The state-of-the-art outsourced K-means clustering scheme using fully homomorphic encryption is efficient but not secure enough. To better solve this problem, we utilize the kd-tree data structure and design a set of secure protocols, presenting a new scheme that is almost as efficient as the state-of-the-art schemes but more secure. In our scheme, the clustering process is performed by two cloud servers without leaking any intermediate information. We provide formal security analyses and evaluate the performance of our scheme on both synthetic and real-world datasets. The experiment results show that our scheme is efficient and practical.