Keller, Hannah ; Möllering, Helen ; Schneider, Thomas ; Yalame, Hossein (2021)
Privacy - Preserving Clustering.
32. Kryptotag - crypto day matters. virtual Conference (15.01.2021-15.01.2021)
doi: 10.18420/cdm-2021-32-42
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

Clustering is an unsupervised machine learning technique that divides a data set into groups. The manifold applications of clustering range from segmenting a market using consumer preferences to grouping photos of diseased organs in medical imaging. These scenarios inevitably require sensitive data such as business secrets or personal health records. We consider multiple mutually distrusting parties, e.g., corporations or hospitals that do not want to or are not permitted to share their clients’ or patients’ data due to legislation such as GDPR or HIPAA or to protect their market position and business secrets. Nevertheless, these parties wish to cluster their joint data, since a larger data pool usually results in a better result providing more insights. A growing body of research proposes privacy-preserving variants of clus- tering algorithms. These algorithms operate in a semi-honest security model, which assumes that all parties honestly follow the protocol. However, exist- ing implementations are impractical for real-world usage due to immense computational costs or privacy-compromising data leakage during the cluster- ing process. To the best of our knowledge, the few clustering schemes that fully preserve privacy focus on the simple and efficient k-means algorithm; however, the effectiveness of k-means depends on many assumptions. For example, the number of clusters must be known in advance, and the input data cannot include nominal variables or outliers. These assumptions often do not hold for real-world clustering applications, limiting k-means’ practicality. In our work, we explore the suitability of advanced clustering algorithms for efficient crypto-oriented clustering. We identify affinity propagation to be the most promising algorithm candidate. Affinity propagation and k-means have comparable computational complexities of O(n2), and affinity propagation provides more flexibility in terms of tolerance to outliers, compatibility with var- ious data types, and the selection of tunable parameters. Furthermore, affinity propagation involves only operations that can be implemented relatively effi- ciently using secure computation techniques, such as addition and comparison. The algorithm was also successfully applied for privacy-relevant use cases, e.g., the detection of genes from chromosomal data. Based on our insights, we design the first privacy-preserving affinity propa- gation clustering protocol using secure computation techniques. Moreover, our protocol was implemented and benchmarked with the SPDZ framework and enables private clustering in a malicious security model for the first time, providing protection from strong adversaries that deviate from the protocol.

Frage zum Eintrag

Redaktionelle Details anzeigen