Privacy-Preserving and Outsourced Multi-Party K-Means Clustering Based on Multi-Key Fully Homomorphic Encryption

The clustering algorithm is a useful tool for analyzing medical data. For instance, the k-means clustering can be used to study precipitating factors of a disease. In order to implement the clustering algorithm efficiently, data computation is outsourced to cloud servers, which may leak the private data. Encryption is a common method for solving this problem. But cloud servers are difficult to calculate ciphertexts from multiple parties. Hence, we choose multi-key fully homomorphic encryption (FHE), which supports computations on the ciphertexts that have different secret keys, to protect the private data. In this paper, based on Chen's multi-key FHE scheme, we first propose secure squared euclidean, comparison, minimum, and average protocols. Then, we design the basic and advanced schemes for implementing the secure multi-party k-means clustering algorithm. In the basic scheme, the implementation of homomorphic multiplication includes the process of transforming ciphertexts under different keys. In order to implement homomorphic multiplication efficiently, the advanced scheme uses an improved method to transform ciphertexts. Meanwhile, almost all computations are completely outsourced to cloud servers. We prove that the proposed protocols and schemes are secure and feasible. Simulation results also show that our improved method is helpful for improving the homomorphic multiplication of Chen's multi-key FHE scheme.

1 Introduction

Medical data usually include the patients’ full names, date of births, addresses, medical history, medication records, etc. The analysis of medical data is helpful for improving medical diagnostics, drug discovery, clinical trials, and patient outcomes. The clustering algorithm is an efficient analysis method, which can identify underlying relationships and rules from these data. As a typical clustering algorithm, k-means is used to study precipitating factors of a disease. Because the patients lack of powerful computation capability, medical data are usually outsourced to cloud servers for the efficient implementation of the k-means clustering algorithm. However, cloud servers may illegally leak, falsify, or delete medical data.