Hierarchical Clustering via Single and Complete Linkage Using Fully Homomorphic Encryption
Open Access
Abstract
Hierarchical clustering is a widely used data analysis technique. Typically, tools for this method operate on data in its original, readable form, raising privacy concerns when a clustering task involving sensitive data that must remain confidential is outsourced to an external server. To address this issue, we developed a method that integrates Cheon-Kim-Kim-Song homomorphic encryption (HE), allowing the clustering process to be performed without revealing the raw data. In hierarchical clustering, the two nearest clusters are repeatedly merged until the desired number of clusters is reached. The proximity of clusters is evaluated using various metrics. In this study, we considered two well-known metrics: single linkage and complete linkage. Applying HE to these methods involves sorting encrypted distances, which is a resource-intensive operation. Therefore, we propose a cooperative approach in which the data owner aids the sorting process and shares a list of data positions with a computation server. Using this list, the server can determine the clustering of the data points. The proposed approach ensures secure hierarchical clustering using single and complete linkage methods without exposing the original data.Keywords
Funding Information
- National Research Foundation of Korea (RS-2023-00209294, RS-2022-00155915, 2022-0-01047)
- Institute of Information and communications Technology Planning and evaluation (IITP) (RS-2023-00209294, RS-2022-00155915, 2022-0-01047)
- Inha University Research Grant (RS-2023-00209294, RS-2022-00155915, 2022-0-01047)
This publication has 18 references indexed in Scilit:
- Survey on Fully Homomorphic Encryption, Theory, and ApplicationsProceedings of the IEEE, 2022
- SoK: Efficient Privacy-preserving ClusteringProceedings on Privacy Enhancing Technologies, 2021
- Practical Privacy-Preserving K-means ClusteringProceedings on Privacy Enhancing Technologies, 2020
- Data Mining and Machine Learning2020
- Unsupervised Machine Learning on Encrypted Data2019
- Homomorphic Encryption for Arithmetic of Approximate Numbers2017
- K-Means Clustering Using Homomorphic Encryption and an Updatable Distance Matrix: Secure Third Party Data Clustering with Limited Data Owner Interaction2017
- Method for Determining the Optimal Number of Clusters Based on Agglomerative Hierarchical ClusteringIEEE Transactions on Neural Networks and Learning Systems, 2016
- Minimum spanning tree based split-and-merge: A hierarchical clustering methodInformation Sciences, 2011
- Privacy Preserving Clustering2005