Efficient two-party privacy-preserving collaborative k-means clustering protocol supporting both storage and computation outsourcing

Abstract Nowadays, cloud computing has developed well and been applied in many kinds of areas. However, privacy is still the most challenging problem which obstructs it being applied in some privacy-sensitive fields, such as finance and government. Advanced cryptographic algorithms provide data privacy with encryption, which can also support computation on such encrypted data. However, new challenge arises when such ciphertexts come from different parties. In particular, how to execute collaboratively data mining on encrypted data coming from different parties is a key issue from cloud service point of view. This paper focuses on privacy problem on outsourced k-means clustering scheme for two parties. In particular, each party’s data are encrypted only once and then stored in cloud. The proposed privacy-preserving k-means collaborative clustering protocol is executed mainly at the cloud, with O ( k ( m + n ) ) rounds of interactions among the two parties and the cloud, where m and n represent the total numbers of records for the two parties, respectively. It is shown that the protocol is secure in the semi-honest security model and in the malicious model in which only one party is corrupted during the process of centroids re-computation. Both theoretical and experimental analysis of the proposed scheme are also provided.