Privacy-preserving density-based clustering

Bozdemir, Beyza; Canard, Sébastien; Ermis, Orhan; Möllering, Helen; Önen, Melek; Schneider, Thomas
ASIACCS 2021, 16th ACM ASIA Conference on Computer and Communications Security, 7-11 June 2021, Hong-Kong, China (Virtual Conference)

Clustering is an unsupervised machine learning technique that outputs clusters containing similar data items. In this work, we investigate privacy-preserving density-based clustering which is, for example, used in financial analytics and medical diagnosis. When (multiple) data owners collaborate or outsource the computation,
privacy concerns arise. To address this problem, we design, implement, and evaluate the first practical and fully private density-based clustering scheme based on secure two-party computation. Our protocol privately executes the DBSCAN algorithm without disclosing any information (including the number and size of clusters). It can be used for private clustering between two parties as well as for private outsourcing of an arbitrary number of data owners to two non-colluding servers. Our implementation of the DBSCAN algorithm privately clusters data sets with 400 elements in 7 minutes
on commodity hardware. Thereby, it flexibly determines the number of required clusters and is insensitive to outliers, while being only factor 19x slower than today’s fastest private K-means protocol (Mohassel et al., PETS’20) which can only be used for specific data sets. We then show how to transfer our newly designed protocol to related clustering algorithms by introducing a private approximation of the TRACLUS algorithm for trajectory clustering which has interesting real-world applications like financial time series forecasts and the investigation of the spread of a disease like COVID-19.

Type:
Conference
City:
Hong-Kong
Date:
2021-06-06
Department:
Digital Security
Eurecom Ref:
6475
Copyright:
© ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ASIACCS 2021, 16th ACM ASIA Conference on Computer and Communications Security, 7-11 June 2021, Hong-Kong, China (Virtual Conference)

PERMALINK : https://www.eurecom.fr/publication/6475