Efficient privacy preserving K-means clustering in a three-party setting

Michael Beye; Zekeriya Erkin; Reginald L. Lagendijk

doi:10.1109/WIFS.2011.6123148

Efficient privacy preserving K-means clustering in a three-party setting

Michael Beye, Zekeriya Erkin, Reginald L. Lagendijk

Research output: Contribution to conference › Paper

28 Citations (Scopus)

68 Downloads (Pure)

Abstract

User clustering is a common operation in online social networks, for example to recommend new friends. In previous work [5], 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.

Original language	English
Pages	1-6
Number of pages	6
DOIs	https://doi.org/10.1109/WIFS.2011.6123148
Publication status	Published - 2011
Event	IEEE International Workshop on Information Forensics and Security, WIFS 2011 - Iguacu Falls, Brazil Duration: 29 Nov 2011 → 2 Dec 2011

Workshop

Workshop	IEEE International Workshop on Information Forensics and Security, WIFS 2011
Period	29/11/11 → 2/12/11
Other	29 November - 02 December 2011

Access to Document

10.1109/WIFS.2011.6123148

Cite this

@conference{f148561206c04d6486a2a77cb8978396,

title = "Efficient privacy preserving K-means clustering in a three-party setting",

abstract = "User clustering is a common operation in online social networks, for example to recommend new friends. In previous work [5], 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{\textquoteright}s protocol, 2) it minimizes user interaction and allows clustering of offline users (through a central party acting on users{\textquoteright} 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.",

author = "Michael Beye and Zekeriya Erkin and Lagendijk, {Reginald L.}",

year = "2011",

doi = "10.1109/WIFS.2011.6123148",

language = "English",

pages = "1--6",

note = "IEEE International Workshop on Information Forensics and Security, WIFS 2011 ; Conference date: 29-11-2011 Through 02-12-2011",

}

TY - CONF

T1 - Efficient privacy preserving K-means clustering in a three-party setting

AU - Beye, Michael

AU - Erkin, Zekeriya

AU - Lagendijk, Reginald L.

PY - 2011

Y1 - 2011

N2 - User clustering is a common operation in online social networks, for example to recommend new friends. In previous work [5], 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.

AB - User clustering is a common operation in online social networks, for example to recommend new friends. In previous work [5], 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.

U2 - 10.1109/WIFS.2011.6123148

DO - 10.1109/WIFS.2011.6123148

M3 - Paper

SP - 1

EP - 6

T2 - IEEE International Workshop on Information Forensics and Security, WIFS 2011

Y2 - 29 November 2011 through 2 December 2011

ER -

Efficient privacy preserving K-means clustering in a three-party setting

Abstract

Workshop

Access to Document

Fingerprint

Cite this