Privacy of Outsourced k-mean Clustering

It is attractive for an organization to outsource its data analytics to a service provider who has powerful platforms and advanced an- alytics skills. However, the organization (data owner) may have concerns about the privacy of its data. In this paper, we present a method that allows the data owner to encrypt its data with a homo- morphic encryption scheme and the service provider to perform k- means clustering directly over the encrypted data. However, since the ciphertexts resulting from homomorphic encryption do not pre- serve the order of distances between data objects and cluster cen- ters, we propose an approach that enables the service provider to compare encrypted distances with the trapdoor information pro- vided by the data owner. The efficiency of our method is validated by extensive experimental evaluation