Mutual Privacy Preserving k-Means Clustering in Social Participatory Sensing

In this paper, we consider the problem of mutual privacy protection in social participatory sensing in which individuals contribute their private information to build a (virtual) community. Particularly, we propose a mutual privacy preserving k-means clustering scheme that neither discloses an individual's private information nor leaks the community's characteristic data (clusters). Our scheme contains two privacy-preserving algorithms called at each iteration of the k-means clustering. The first one is employed by each participant to find the nearest cluster while the cluster centers are kept secret to the participants; and the second one computes the cluster centers without leaking any cluster center information to the participants while preventing each participant from figuring out other members in the same cluster. An extensive performance analysis is carried out to show that our approach is effective for k-means clustering, can resist collusion attacks, and can provide mutual privacy protection even when the data analyst colludes with all except one participant.