Efficient Privacy Preserving K-means Clustering in a Three-Party Setting

TitleEfficient Privacy Preserving K-means Clustering in a Three-Party Setting
Publication TypeConference Paper
Year of Publication2011
AuthorsBeye, M, Erkin, Z, Lagendijk, RL
Refereed DesignationRefereed
Conference NameIEEE Workshop on Information Forensics and Security (WIFS’11)
Date Published11/2011
Conference LocationFoz do Iguaçu, Brazil
Keywordsclustering, garbled circuits, Homomorphic Encryption, Privacy, Social networks

User clustering is a common operation in online social networks, for example to recommend new friends. In previous work, Erkin et al. proposed a privacy-preserving K-means clustering algorithm for the semi-honest model, using homomorphic encryption and multi-party computation. This paper makes three contributions: 1) it addresses remaining privacy weaknesses in Erkin’s protocol, 2) it minimizes user interaction and allows clustering of offline users (through a central party acting on users’ behalf), and 3) it enables highly efficient non-linear operations, improving overall efficiency (by its three-party structure). Our complexity and security analyses underscore the advantages of the solution.