Practical Privacy-Preserving K-means Clustering
Authors: Payman Mohassel (Facebook), Mike Rosulek (Oregon State University), Ni Trieu (University of California, Berkeley)
Volume: 2020
Issue: 4
Pages: 414–433
DOI: https://doi.org/10.2478/popets-2020-0080
Abstract: Clustering is a common technique for data analysis, which aims to partition data into similar groups. When the data comes from different sources, it is highly desirable to maintain the privacy of each database. In this work, we study a popular clustering algorithm (K-means) and adapt it to the privacypreserving context. Specifically, to construct our privacy-preserving clustering algorithm, we first propose an efficient batched Euclidean squared distance computation protocol in the amortizing setting, when one needs to compute the distance from the same point to other points. Furthermore, we construct a customized garbled circuit for computing the minimum value among shared values. We believe these new constructions may be of independent interest. We implement and evaluate our protocols to demonstrate their practicality and show that they are able to train datasets that are much larger and faster than in the previous work. The numerical results also show that the proposed protocol achieve almost the same accuracy compared to a K-means plain-text clustering algorithm.
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
