# Multi-Party Verifiable Privacy-Preserving Federatedk-Means Clustering in Outsourced Environment

Authors: Ruiqi Hou; Fei Tang; Shikai Liang; Guowei Ling
Journal: Security and Communication Networks
 (2021)

---

## Abstract

As a commonly used algorithm in data mining, clustering has been widely applied in many fields, such as machine learning, information retrieval, and pattern recognition. In reality, data to be analyzed are often distributed to multiple parties. Moreover, the rapidly increasing data volume puts heavy computing pressure on data owners. Thus, data owners tend to outsource their own data to cloud servers and obtain data analysis results for the federated data. However, the existing privacy-preserving outsourcedk-means schemes cannot verify whether participants share consistent data. Considering the scenarios with multiple data owners and sensitive information security in an outsourced environment, we propose a verifiable privacy-preserving federated k-means clustering scheme. In this article, cloud servers and participants perform k-means clustering algorithm over encrypted data without exposing private data and intermediate results in each iteration. In particular, our scheme can verify the shares from participants when updating the cluster centers based on secret sharing, hash function and blockchain, so that our scheme can resist inconsistent share attacks by malicious participants. Finally, the security and experimental analysis are carried out to show that our scheme can protect private data and get high-accuracy clustering results.


---

## Body

## 1. Introduction

Data mining technology can be used to analyze and extract potentially valuable information from large collections of data. Clustering algorithms are widely used in data mining and have an important role in research for medical, scientific, and commercial applications in practical life. In brief, clustering [1, 2] algorithms can divide data items into groups according to their features and attributes, such that the data items are sufficiently similar in the same group. As a well-known clustering algorithm, k-means clustering [3] algorithm has the advantages of simple process and good clustering results and it can assign data into k clusters based on the distances from cluster centers.Data analysis can extract a lot of useful information, but in the process of data analysis, a large amount of personal privacy data will be collected and analyzed, such as living habits, criminal records, and medical records. Furthermore, privacy data breaches often result in financial losses and panic for society and companies. Data privacy has gained more attention than before. There are some researches about privacy-preserving in [4–6]. Moreover, a lot of privacy-preserving data mining schemes can be found in [7–9] in recent years.The traditional privacy-preservingk-means schemes are primarily achieved through the interaction of participants. Vaidya and Clifton [10] firstly proposed the multi-party privacy-preserving k-means clustering protocol on vertically partitioned data, where the secure distance computation and comparison are supported by the secure permutation scheme and homomorphic encryption. Jha et al. [11] introduced a two-party privacy-preserving k-means clustering protocol based on oblivious polynomial evaluation and homomorphic encryption. Bunn and Ostrovsky [12] presented an efficient two-party clustering protocol on arbitrarily partitioned data, where the intermediate values are not disclosed by using division protocol and random values protocol. Yi and Zhang [13] introduced an equally contributory privacy-preserving k-means clustering protocol based on ElGamal, plaintext equivalence test protocol, and mix networks. Xing et al. [14] proposed a mutual privacy-preserving k-means scheme in the social scene where the parties are grouped with the help of a data analyst, and the scheme can resist collusion attacks. Zhang et al. [15] combined secure multi-party computing and differential privacy technology to train a privacy-preserving k-means clustering model. After that, privacy-preserving k-means schemes in the malicious model are proposed in [16, 17].Recently, explosive growth data poses a challenge for data owners in storing and computing, and a cloud server with high storage capacity and strong computing power is a good solution to the problem. Privacy protection and audit research in the cloud environment have also been studied in [18–22]. So there are some privacy-preserving k-means schemes in an outsourced environment. Liu et al. [23], following the framework in [24], presented a privacy-preserving outsourced k-means clustering protocol that one party outsourced the distance computation to a cloud server without revealing both the data and clustering results to any party and cloud server. Jiang et al. [25] introduced an efficient two-party privacy-preserving k-means clustering protocol, and this scheme can compute distance safely using subprotocols in [26] and update cluster centers using garbled circuit proposed in [27]. Zou et al. [28] proposed a highly secure privacy-preserving outsourced k−means clustering scheme using BCP homomorphic encryption and AES encryption under multiple keys. Sakellariou and Gounaris [29] introduced a privacy-preserving outsourced k-means scheme with low client-side load based on switch key and Paillier encryption. However, the existing privacy-preserving outsourced k-means schemes cannot verify whether participants share consistent data. In this article, we propose a multi-party verifiable privacy-preserving federated k-means scheme for horizontally partitioned data.Our main contributions can be summarized as follows:(1)
We propose a privacy-preservingk-means scheme based on Paillier cryptosystem, secret sharing, hash function, and blockchain. In the multi-party scenario, we outsource the main computing task to the cloud server and reduce the computing overhead of participants.(2)
Our scheme can protect the participants’ information and avoid leaking the clustering centers to participants in each iteration. Furthermore, the malicious participant can be detected using hash function and blockchain in the process of updating cluster centers.(3)
We carry out an experimental study to validate our scheme, and the experimental results show that the cloud server’s running time can reach 77 % in our scheme. Moreover, our scheme can obtain high-accuracy clustering results.The rest of the article is organized as follows. Section2 introduces the preliminaries about k-means clustering and cryptography knowledge. Section 3 presents the framework and specific entities in our scheme. Basic secure protocol and our scheme are detailed in Section 4. Security analysis is carried out in Section 5. Performance analysis is presented in Section 6. Moreover, we conclude this article in Section 7.


## 2. Preliminaries

For better elaboration, the notations used in this article and their semantic meanings are presented in Table1.Table 1
Notations and their semantic meanings.
NotationsMeaningsCiTheith cluster, 1 ≤i≤kμiTheith cluster centerE⋅Encryption operationD⋅Decryption operationCCloud serverPiTheith participantBBlockchainnNumber of participantsdpiSample size of theith participantSiSample of theith participanthvHash valueS.sumThe sum of samplesS.noThe number of samples


### 2.1.k-Means Clustering Algorithm

Thek-means clustering algorithm is one of the most well-performed unsupervised clustering algorithms. The process of k-means clustering algorithm is described as follows. Assume that there is a set of samples and each sample ai is an ℓ-dimensional data. Suppose that the samples need to be grouped into k clusters C1,…,Ck, where the cluster center of jth cluster is denoted by μj. Initially, randomly select k samples μ1,…,μk as the initial cluster centers. There are many iterations to measure the distances between each sample and k cluster centers. In this article, we adopt Euclidean distance as the criterion. Sample ai belongs to cluster Cj if the cluster center μj is the closest to ai. In each iteration, each sample is reassigned to the nearest cluster and recompute the cluster centers as in the following equation (1). The iteration terminates when there is no or little change in the cluster centers. The specific description of the k-means clustering algorithm is shown in Algorithm 1.(1)μj=∑ai∈CjaiCj.Algorithm 1:k-means clustering.
Randomly selectk cluster centers μ1,…,μk from the datasetRepeat(1)
Calculate the distances between each sample andk cluster centers μ1,…,μk(2)
Assign each sample to the closest cluster(3)
Replace each cluster centersμi with the mean of the i th clusteruntil Cluster centers do not change


### 2.2. Homomorphic Encryption

Homomorphic encryption allows certain computation over encrypted data. Paillier [30] cryptosystem is a popular homomorphic encryption scheme based on the decisional composite residuosity class problem. Furthermore, the Paillier cryptosystem can provide fast encryption and decryption, and it is widely used in privacy-preserving data mining. We adopt Paillier cryptosystem in our scheme. The Paillier cryptosystem is briefly introduced as follows:(i)
Key generation: an entity selects two large primes p and q and compute n=pq and λ=lcmp−1,q−1. Then randomly choose an integer g∈ℤN∗ and check whether gcdLgλmodn2,n=1, where Lx=x−1/n. The public key is pk=n,g and the secret key sk=λ.(ii)
Encryption: let m∈ℤN∗ be a message and r∈ℤN∗ be a random number. The ciphertext of m is computed by(2)Em=gm⋅rnmodn2,whereE⋅ denotes the encryption with the pk=n,g.(iii)
Decryption: decrypt the ciphertext of m by(3)DEm=LEmλmodn2Lgλmodn2modn,whereD⋅ denotes the decryption with the sk=λ.(iv)
Homomorphic: the Paillier cryptosystem is additive homomorphic, which satisfies the following equation:(4)Em1⋅Em2=Em1+m2,Emc=Ec⋅m.


### 2.3. Blockchain

Blockchain is the underlying technology of Bitcoin [31], which is essentially a distributed database. Blockchain is a very new network form, which uses cryptography, hash function, and proof of work (Pow). There are a lot of nice features of blockchain, such as decentralization, tamper resistance, and transparency.(i)
Decentralization: the data on the blockchain are maintained by all nodes in the peer-to-peer networks. Moreover, all nodes compete to generate a block of block without relying on a centralized third party to record transactions.(ii)
Tamper resistance: each node in the peer-to-peer networks saves a copy of data on the blockchain, so it is impossible to tamper with the data once the data has been recorded on the blockchain.(iii)
Transparency: the records on the blockchain are transparent to all nodes, and anyone can access the data on the blockchain.


## 2.1.k-Means Clustering Algorithm

Thek-means clustering algorithm is one of the most well-performed unsupervised clustering algorithms. The process of k-means clustering algorithm is described as follows. Assume that there is a set of samples and each sample ai is an ℓ-dimensional data. Suppose that the samples need to be grouped into k clusters C1,…,Ck, where the cluster center of jth cluster is denoted by μj. Initially, randomly select k samples μ1,…,μk as the initial cluster centers. There are many iterations to measure the distances between each sample and k cluster centers. In this article, we adopt Euclidean distance as the criterion. Sample ai belongs to cluster Cj if the cluster center μj is the closest to ai. In each iteration, each sample is reassigned to the nearest cluster and recompute the cluster centers as in the following equation (1). The iteration terminates when there is no or little change in the cluster centers. The specific description of the k-means clustering algorithm is shown in Algorithm 1.(1)μj=∑ai∈CjaiCj.Algorithm 1:k-means clustering.
Randomly selectk cluster centers μ1,…,μk from the datasetRepeat(1)
Calculate the distances between each sample andk cluster centers μ1,…,μk(2)
Assign each sample to the closest cluster(3)
Replace each cluster centersμi with the mean of the i th clusteruntil Cluster centers do not change


## 2.2. Homomorphic Encryption

Homomorphic encryption allows certain computation over encrypted data. Paillier [30] cryptosystem is a popular homomorphic encryption scheme based on the decisional composite residuosity class problem. Furthermore, the Paillier cryptosystem can provide fast encryption and decryption, and it is widely used in privacy-preserving data mining. We adopt Paillier cryptosystem in our scheme. The Paillier cryptosystem is briefly introduced as follows:(i)
Key generation: an entity selects two large primes p and q and compute n=pq and λ=lcmp−1,q−1. Then randomly choose an integer g∈ℤN∗ and check whether gcdLgλmodn2,n=1, where Lx=x−1/n. The public key is pk=n,g and the secret key sk=λ.(ii)
Encryption: let m∈ℤN∗ be a message and r∈ℤN∗ be a random number. The ciphertext of m is computed by(2)Em=gm⋅rnmodn2,whereE⋅ denotes the encryption with the pk=n,g.(iii)
Decryption: decrypt the ciphertext of m by(3)DEm=LEmλmodn2Lgλmodn2modn,whereD⋅ denotes the decryption with the sk=λ.(iv)
Homomorphic: the Paillier cryptosystem is additive homomorphic, which satisfies the following equation:(4)Em1⋅Em2=Em1+m2,Emc=Ec⋅m.


## 2.3. Blockchain

Blockchain is the underlying technology of Bitcoin [31], which is essentially a distributed database. Blockchain is a very new network form, which uses cryptography, hash function, and proof of work (Pow). There are a lot of nice features of blockchain, such as decentralization, tamper resistance, and transparency.(i)
Decentralization: the data on the blockchain are maintained by all nodes in the peer-to-peer networks. Moreover, all nodes compete to generate a block of block without relying on a centralized third party to record transactions.(ii)
Tamper resistance: each node in the peer-to-peer networks saves a copy of data on the blockchain, so it is impossible to tamper with the data once the data has been recorded on the blockchain.(iii)
Transparency: the records on the blockchain are transparent to all nodes, and anyone can access the data on the blockchain.


## 3. Scheme Model

The scheme model is illustrated in Figure1, where the multi-party verifiable privacy-preserving federated k-means model includes three entities. The first entity is participants; the data owners provide the original data for the k-means algorithm, such as hospitals, scientific research companies, and government agencies. The second entity is a cloud server with adequate storage and computing resources, where the cloud server is responsible for storing the encrypted samples of the participants and undertakes the main computational task in privacy-preserving k-means clustering. The last entity is blockchain, which is used to store hash values of secret shares. Because of the tamper-resistant nature of blockchain, once the hash values have been uploaded to the blockchain, it can be guaranteed that they will not change.Figure 1
Model of multi-party verifiable privacy-preserving federatedk-means clustering.In the multi-party verifiable privacy-preserving federatedk-means scheme, the specific descriptions of entities are shown below.(i)
Participants: the samples data to be analyzed are horizontally distributed on the participants, where the n participants are denoted by P1,…,Pn. Moreover, each participant Pi holds dpi samples, where the samples are ℓ-dimensional. Participants in red represent malicious participants. Malicious participants may not follow the protocol and share inconsistent data information. In our scheme, participants generate their public key and secret key and upload the encrypted samples to the cloud server. Besides, participants need to share data with a secret sharing scheme when updating the cluster centers. In order to verify the secret shares, participants need to compute the hash values of secret shares and upload them to the blockchain in advance.(ii)
Cloud Server: all encrypted samples are stored on the cloud server. The cloud server is responsible for interacting with participants and calculating and comparing the distances between encrypted samples and cluster centers. Then, the cloud server assigns samples to different clusters.(iii)
Blockchain: blockchain is responsible for storing hash values generated by the participants.The aim of our scheme is to build a multi-party verifiable federatedk-means scheme. In our scheme, participants only get the final k-means clustering results, and the cluster centers in each iteration are only known to the cloud server. Furthermore, participants and cloud servers cannot know or infer private information about the other side. In the process of updating the cluster centers, participants send secret shares to other participants and verify the secret shares received from other participants with hash values. Once there exists a secret share that fails to verify, it means that malicious participants have sent inconsistent secret shares so that malicious participants can be detected in time and avoid losses due to incorrect k-means results.


## 4. Our Construction

We construct a multi-party verifiable privacy-preserving federatek-means scheme. In our scheme, we use Paillier encryption to protect the information of participants. Furthermore, secret sharing, hash function, and blockchain technology are used to verify and update new cluster centers.


### 4.1. Basic Secure Protocol

We present a set of subprotocols that will be used in constructing the multi-party verifiable privacy-preserving federatek-means scheme.(i)
Secure Multiplication (SM) Protocol. In this protocol, participants P have input Epkx,Epky and output Epkx∗y to cloud server C, where neither P nor C knows x and y. Furthermore, information concerning x and y is not leaked to P or C.(ii)
Secure Squared Euclidean Distance (SSED) Protocol. There exist two ℓ-dimensional vectors denoted by X=x1,…,xℓ and Y=y1,…,yℓ, where EX=<Ex1,…,Exℓ> and EY=<Ey1,…,Eyℓ> denote the encrypted components sets of X and Y. The cloud server C with the input EX,EY and participants P with sk securely compute the encrypted value of the squared Euclidean distance between vectors X and Y.(iii)
Secure Bit-Decomposition (SBD) Protocol. SBD [32] protocol considers cloud server C with input Epkz and participants P securely compute encrypted values of the individual bits of z, where 0≤z≤2α−1 and z is not known to C and P. No information regarding output z=Epkz1,…,Epkzα is revealed to P. Here, z1,zα are the most and least significant bits of z.(iv)
Secure Minimum out of 2 Numbers (SMIN2) Protocol. We assume that u∈0,1α and v∈0,1α are two α-bit strings and 0≤u,v≤2α−1. Let u=Eu1,…,Euα and v=Ev1,…,Evα represent the encrypted bits of u and v, respectively, where ui and vi denote each bit of u and v. This protocol considers cloud server C with input u,v and participants P with sk securely output the encrypted values of the individual bits of minu,v, where u1,uα and v1,vα are the most and least significant bits of u and v, respectively.(v)
Secure Minimum out of k Numbers (SMINk) Protocol. In this protocol, di∈0,1α1≤i≤k is a distance and di,j1≤j≤α denotes a bit of di. Let di=Edi,1,…,Edi,α, where di,1,di,α is the most and least significant bits of di. Consider cloud server C with k encrypted vectors d1,…,dk and participants P with sk. The goal of this protocol is to compute the mind1,…,dk without revealing any information regarding di1≤i≤k to C and P.(vi)
Secure and Verifiable Vector Share (SVVS) Protocol. Participant Pi has a dataset, Si=Si,j|1≤j≤dpi1≤i≤n. Samples Si,j=si,j,t|1≤t≤ℓ are ℓ-dimensional vectors. In this protocol, Pi securely share samples using a secret sharing scheme. Firstly, Pi generate polynomial fi,jx=ai,j,n−1∗xn−1+⋯+ai,j,1∗x+ai,j,0,1≤i≤n,1≤j≤dpi and compute shares fi,jxh1≤h≤n. Then, Pi computes the hash values hv of fi,jxh and upload them to the blockchain.(vii)
Verify and Recovery Secret (VRS) Protocol. In this protocol, participants Pi with input clustering results Ci=Cji|1≤j≤k. Pi sends shares fxj to Pj and receives shares fxj from Pj. Then, Pi computes hash values of fxj and verifies whether hash values are on the blockchain. If all hash values exist on the blockchain, Pi computes the sum of shares Fxi=∑j=1nfxi1≤i≤n , where Fxi is not known to other participants. Pi sends Fxi to cloud server C, and C solves the set of Fx using Lagrange’s interpolation to recovery the sum of the secret values.


### 4.2. The Proposed Scheme

This section presents the detailed steps of the multi-party verifiable privacy-preserving federatedk-means scheme.


#### 4.2.1. Step 1: Assign Samples to Clusters

This step aims to assign each sample to its nearest cluster. Where the cluster centers are initialized by cloud serverC.(i)
Step 1.1: participants generate polynomials and compute hash values. For each sample Si,j of Pi, participant Pi runs the SVVS protocol to generate polynomial values fi,jx and computes hash values hv of fi,jx. We use SHA256 in the SVVS protocol. Then, participants upload hash values to blockchain B.(ii)
Step 1.2: participants encrypt samples and upload ciphertext to cloud server. Each participant Pi encrypts their samples, and CTi represents encrypted samples of Pi, where CTi=CTi,j|1≤j≤dpi, CTi,j=CTi,j,t=Epksi,j,t|1≤t≤ℓ and uploads ciphertext to cloud server.(iii)
Step 1.3: cloud server randomly chooseskcluster centers. Cloud server C randomly chooses k cluster centers φ=μc|1≤c≤k, where μc=μc,t|1≤t≤ℓ. Cloud server encrypts k cluster centers using the pk of each participant to get Cμi1≤i≤n, where Cμi=Cμ,ci|1≤c≤k, Cμ,c,ti=Epkμc,t|1≤t≤ℓ.(iv)
Step 1.4: cloud server and participants compute distances. Cloud server C has Pi’s encrypted samples CTi and cluster centers Cμ,ci, and Pi has the secret key sk. C and Pi run SSED protocol to compute encrypted distances between each sample and k cluster centers. The distances are represented as disi=disji=disj,ci=SSEDCTi,j,Cμ,ci|1≤i≤n,1≤j≤dpi,1≤c≤k. The disji denotes the encrypted distances between Pi’s sample Si,j and k cluster centers in encrypted form.(v)
Step 1.5: cloud server assigns samples tokclusters. To compare the encrypted distances, C and Pi run SMINk protocol to get the minimum distance mini=mini,j=SMINkdisji|1≤i≤n,1≤j≤dpi of sample Si,j. The sample Si,j will be assigned to the cth cluster if the minimum distance mini,j is equal to disj,ci. Finally, the cloud server gets the clustering results of each participant’s samples C=Ci|1≤i≤n, where Ci=Cji|1≤j≤k and Cji denotes the set of Pi’s samples in the jth cluster. Then, cloud server sends samples clustering results to the corresponding participants. In other words, participants only know the clustering results of their own samples, and they do not know the clustering results of other participants’ samples.


#### 4.2.2. Step 2: Update Cluster Centers

This step aims to compute the new cluster centers.(i)
Step 2.1: participants send and receive shares of samples. After assigning all samples to k clusters, participants run VRS protocol to update cluster centers. Because each sample’s shares have been calculated by participants through the SVVS protocol in Step 1, it is very easy to get the shares of each sample. Suppose we want to update the cth cluster center, participants send shares of their samples in cth cluster to corresponding participants and receive shares of other participants’ samples in cth cluster. After receiving shares from other participants, participants need to compute hash values of shares and verify whether these hash values exist on the blockchain. If the hash values exist on the blockchain, it indicates that other participants share the consistent values. Then, participants compute the sum of shares Fxi and send Fxi to the cloud server.(ii)
Step 2.2: calculate the new centers. The cloud server receives the sum of shares Fxi1≤i≤n from participants and uses Lagrange’s interpolation to find the sum of samples S.sum. Because the cluster server has the clustering results of all samples, it can easily get the number of samples S.no in each cluster. Then, the cluster server computes the new centers μ′=S.sumc/S.noc. Moreover, the new cluster centers cannot be leaked to participants.


#### 4.2.3. Step 3: Stop Iteration

This step aims to determine whether to terminate the privacy-preserving federatedk-means algorithm. After Step 1 and Step 2, the cloud server should compare the new cluster centers μ′ with previous cluster centers μ. If they are close enough (e.g., the difference is no more than the threshold set earlier), the k-means ends and the clustering results have been sent to participants in Step 1.5. Otherwise, the cloud server encrypts the k new cluster centers using each participants’ public key. Then, go to Step 1.4 and iterate.


## 4.1. Basic Secure Protocol

We present a set of subprotocols that will be used in constructing the multi-party verifiable privacy-preserving federatek-means scheme.(i)
Secure Multiplication (SM) Protocol. In this protocol, participants P have input Epkx,Epky and output Epkx∗y to cloud server C, where neither P nor C knows x and y. Furthermore, information concerning x and y is not leaked to P or C.(ii)
Secure Squared Euclidean Distance (SSED) Protocol. There exist two ℓ-dimensional vectors denoted by X=x1,…,xℓ and Y=y1,…,yℓ, where EX=<Ex1,…,Exℓ> and EY=<Ey1,…,Eyℓ> denote the encrypted components sets of X and Y. The cloud server C with the input EX,EY and participants P with sk securely compute the encrypted value of the squared Euclidean distance between vectors X and Y.(iii)
Secure Bit-Decomposition (SBD) Protocol. SBD [32] protocol considers cloud server C with input Epkz and participants P securely compute encrypted values of the individual bits of z, where 0≤z≤2α−1 and z is not known to C and P. No information regarding output z=Epkz1,…,Epkzα is revealed to P. Here, z1,zα are the most and least significant bits of z.(iv)
Secure Minimum out of 2 Numbers (SMIN2) Protocol. We assume that u∈0,1α and v∈0,1α are two α-bit strings and 0≤u,v≤2α−1. Let u=Eu1,…,Euα and v=Ev1,…,Evα represent the encrypted bits of u and v, respectively, where ui and vi denote each bit of u and v. This protocol considers cloud server C with input u,v and participants P with sk securely output the encrypted values of the individual bits of minu,v, where u1,uα and v1,vα are the most and least significant bits of u and v, respectively.(v)
Secure Minimum out of k Numbers (SMINk) Protocol. In this protocol, di∈0,1α1≤i≤k is a distance and di,j1≤j≤α denotes a bit of di. Let di=Edi,1,…,Edi,α, where di,1,di,α is the most and least significant bits of di. Consider cloud server C with k encrypted vectors d1,…,dk and participants P with sk. The goal of this protocol is to compute the mind1,…,dk without revealing any information regarding di1≤i≤k to C and P.(vi)
Secure and Verifiable Vector Share (SVVS) Protocol. Participant Pi has a dataset, Si=Si,j|1≤j≤dpi1≤i≤n. Samples Si,j=si,j,t|1≤t≤ℓ are ℓ-dimensional vectors. In this protocol, Pi securely share samples using a secret sharing scheme. Firstly, Pi generate polynomial fi,jx=ai,j,n−1∗xn−1+⋯+ai,j,1∗x+ai,j,0,1≤i≤n,1≤j≤dpi and compute shares fi,jxh1≤h≤n. Then, Pi computes the hash values hv of fi,jxh and upload them to the blockchain.(vii)
Verify and Recovery Secret (VRS) Protocol. In this protocol, participants Pi with input clustering results Ci=Cji|1≤j≤k. Pi sends shares fxj to Pj and receives shares fxj from Pj. Then, Pi computes hash values of fxj and verifies whether hash values are on the blockchain. If all hash values exist on the blockchain, Pi computes the sum of shares Fxi=∑j=1nfxi1≤i≤n , where Fxi is not known to other participants. Pi sends Fxi to cloud server C, and C solves the set of Fx using Lagrange’s interpolation to recovery the sum of the secret values.


## 4.2. The Proposed Scheme

This section presents the detailed steps of the multi-party verifiable privacy-preserving federatedk-means scheme.


### 4.2.1. Step 1: Assign Samples to Clusters

This step aims to assign each sample to its nearest cluster. Where the cluster centers are initialized by cloud serverC.(i)
Step 1.1: participants generate polynomials and compute hash values. For each sample Si,j of Pi, participant Pi runs the SVVS protocol to generate polynomial values fi,jx and computes hash values hv of fi,jx. We use SHA256 in the SVVS protocol. Then, participants upload hash values to blockchain B.(ii)
Step 1.2: participants encrypt samples and upload ciphertext to cloud server. Each participant Pi encrypts their samples, and CTi represents encrypted samples of Pi, where CTi=CTi,j|1≤j≤dpi, CTi,j=CTi,j,t=Epksi,j,t|1≤t≤ℓ and uploads ciphertext to cloud server.(iii)
Step 1.3: cloud server randomly chooseskcluster centers. Cloud server C randomly chooses k cluster centers φ=μc|1≤c≤k, where μc=μc,t|1≤t≤ℓ. Cloud server encrypts k cluster centers using the pk of each participant to get Cμi1≤i≤n, where Cμi=Cμ,ci|1≤c≤k, Cμ,c,ti=Epkμc,t|1≤t≤ℓ.(iv)
Step 1.4: cloud server and participants compute distances. Cloud server C has Pi’s encrypted samples CTi and cluster centers Cμ,ci, and Pi has the secret key sk. C and Pi run SSED protocol to compute encrypted distances between each sample and k cluster centers. The distances are represented as disi=disji=disj,ci=SSEDCTi,j,Cμ,ci|1≤i≤n,1≤j≤dpi,1≤c≤k. The disji denotes the encrypted distances between Pi’s sample Si,j and k cluster centers in encrypted form.(v)
Step 1.5: cloud server assigns samples tokclusters. To compare the encrypted distances, C and Pi run SMINk protocol to get the minimum distance mini=mini,j=SMINkdisji|1≤i≤n,1≤j≤dpi of sample Si,j. The sample Si,j will be assigned to the cth cluster if the minimum distance mini,j is equal to disj,ci. Finally, the cloud server gets the clustering results of each participant’s samples C=Ci|1≤i≤n, where Ci=Cji|1≤j≤k and Cji denotes the set of Pi’s samples in the jth cluster. Then, cloud server sends samples clustering results to the corresponding participants. In other words, participants only know the clustering results of their own samples, and they do not know the clustering results of other participants’ samples.


### 4.2.2. Step 2: Update Cluster Centers

This step aims to compute the new cluster centers.(i)
Step 2.1: participants send and receive shares of samples. After assigning all samples to k clusters, participants run VRS protocol to update cluster centers. Because each sample’s shares have been calculated by participants through the SVVS protocol in Step 1, it is very easy to get the shares of each sample. Suppose we want to update the cth cluster center, participants send shares of their samples in cth cluster to corresponding participants and receive shares of other participants’ samples in cth cluster. After receiving shares from other participants, participants need to compute hash values of shares and verify whether these hash values exist on the blockchain. If the hash values exist on the blockchain, it indicates that other participants share the consistent values. Then, participants compute the sum of shares Fxi and send Fxi to the cloud server.(ii)
Step 2.2: calculate the new centers. The cloud server receives the sum of shares Fxi1≤i≤n from participants and uses Lagrange’s interpolation to find the sum of samples S.sum. Because the cluster server has the clustering results of all samples, it can easily get the number of samples S.no in each cluster. Then, the cluster server computes the new centers μ′=S.sumc/S.noc. Moreover, the new cluster centers cannot be leaked to participants.


### 4.2.3. Step 3: Stop Iteration

This step aims to determine whether to terminate the privacy-preserving federatedk-means algorithm. After Step 1 and Step 2, the cloud server should compare the new cluster centers μ′ with previous cluster centers μ. If they are close enough (e.g., the difference is no more than the threshold set earlier), the k-means ends and the clustering results have been sent to participants in Step 1.5. Otherwise, the cloud server encrypts the k new cluster centers using each participants’ public key. Then, go to Step 1.4 and iterate.


## 4.2.1. Step 1: Assign Samples to Clusters

This step aims to assign each sample to its nearest cluster. Where the cluster centers are initialized by cloud serverC.(i)
Step 1.1: participants generate polynomials and compute hash values. For each sample Si,j of Pi, participant Pi runs the SVVS protocol to generate polynomial values fi,jx and computes hash values hv of fi,jx. We use SHA256 in the SVVS protocol. Then, participants upload hash values to blockchain B.(ii)
Step 1.2: participants encrypt samples and upload ciphertext to cloud server. Each participant Pi encrypts their samples, and CTi represents encrypted samples of Pi, where CTi=CTi,j|1≤j≤dpi, CTi,j=CTi,j,t=Epksi,j,t|1≤t≤ℓ and uploads ciphertext to cloud server.(iii)
Step 1.3: cloud server randomly chooseskcluster centers. Cloud server C randomly chooses k cluster centers φ=μc|1≤c≤k, where μc=μc,t|1≤t≤ℓ. Cloud server encrypts k cluster centers using the pk of each participant to get Cμi1≤i≤n, where Cμi=Cμ,ci|1≤c≤k, Cμ,c,ti=Epkμc,t|1≤t≤ℓ.(iv)
Step 1.4: cloud server and participants compute distances. Cloud server C has Pi’s encrypted samples CTi and cluster centers Cμ,ci, and Pi has the secret key sk. C and Pi run SSED protocol to compute encrypted distances between each sample and k cluster centers. The distances are represented as disi=disji=disj,ci=SSEDCTi,j,Cμ,ci|1≤i≤n,1≤j≤dpi,1≤c≤k. The disji denotes the encrypted distances between Pi’s sample Si,j and k cluster centers in encrypted form.(v)
Step 1.5: cloud server assigns samples tokclusters. To compare the encrypted distances, C and Pi run SMINk protocol to get the minimum distance mini=mini,j=SMINkdisji|1≤i≤n,1≤j≤dpi of sample Si,j. The sample Si,j will be assigned to the cth cluster if the minimum distance mini,j is equal to disj,ci. Finally, the cloud server gets the clustering results of each participant’s samples C=Ci|1≤i≤n, where Ci=Cji|1≤j≤k and Cji denotes the set of Pi’s samples in the jth cluster. Then, cloud server sends samples clustering results to the corresponding participants. In other words, participants only know the clustering results of their own samples, and they do not know the clustering results of other participants’ samples.


## 4.2.2. Step 2: Update Cluster Centers

This step aims to compute the new cluster centers.(i)
Step 2.1: participants send and receive shares of samples. After assigning all samples to k clusters, participants run VRS protocol to update cluster centers. Because each sample’s shares have been calculated by participants through the SVVS protocol in Step 1, it is very easy to get the shares of each sample. Suppose we want to update the cth cluster center, participants send shares of their samples in cth cluster to corresponding participants and receive shares of other participants’ samples in cth cluster. After receiving shares from other participants, participants need to compute hash values of shares and verify whether these hash values exist on the blockchain. If the hash values exist on the blockchain, it indicates that other participants share the consistent values. Then, participants compute the sum of shares Fxi and send Fxi to the cloud server.(ii)
Step 2.2: calculate the new centers. The cloud server receives the sum of shares Fxi1≤i≤n from participants and uses Lagrange’s interpolation to find the sum of samples S.sum. Because the cluster server has the clustering results of all samples, it can easily get the number of samples S.no in each cluster. Then, the cluster server computes the new centers μ′=S.sumc/S.noc. Moreover, the new cluster centers cannot be leaked to participants.


## 4.2.3. Step 3: Stop Iteration

This step aims to determine whether to terminate the privacy-preserving federatedk-means algorithm. After Step 1 and Step 2, the cloud server should compare the new cluster centers μ′ with previous cluster centers μ. If they are close enough (e.g., the difference is no more than the threshold set earlier), the k-means ends and the clustering results have been sent to participants in Step 1.5. Otherwise, the cloud server encrypts the k new cluster centers using each participants’ public key. Then, go to Step 1.4 and iterate.


## 5. Security Analysis

In this section, we discuss the privacy protection capabilities offered by our scheme. Firstly, we define the goals in privacy protection for different entities.For each participant in the federatedk-means scheme, it should not access to the following information:(1)
Samples’ information from other participants(2)
Clustering results for other participants’ samples(3)
Clustering centers in each iterationFor the cloud server, it can only get the cluster centers in each iteration and cannot obtain the samples’ information of participants.The blockchain is only used to store hash values, which is publicly available and does not interact with the participants or the cloud server, so it does not access any private information about participants or the cloud server.


### 5.1. Privacy-Preserving Analysis for Assigning Samples

In the stage of assigning samples, each participant encrypts samples with the Paillier cryptosystem. Because Paillier’s cryptosystem is semantically secure, other participants and cloud servers cannot decrypt and deduce additional information from the encrypted data.According to our scheme, we should compute the distances between samples and cluster centers with theSM and SSED protocols. In SM protocol, the cloud server has the encrypted values Ex and Ey, and the participants hold the secret key sk. The aim of the SM protocol is to return encrypted values of x∗y (e.g., Ex∗y) to cloud server with the interaction between cloud server and participants. The idea of SM protocol is based on the following property:(5)x∗y=x+rx∗y+ry−x∗ry−y∗rx−rx∗ry.The detailedSM protocol is shown in Algorithm 2. Firstly, the cloud server chooses two random numbers rx,ry, which are only known to the cloud server. Then, the cloud server computes x′=Ex+rx=Ex∗Erx,y′=Ey+ry=Ey∗Ery and sends x′,y′ to the participant. After receiving x′ and y′, participant decrypts hx=Dx′,hy=Dy′ and computes h=hx∗hy=x+rx∗y+ry. Then, the participant sends h′=Eh to the cloud server. Finally, the cloud server computes Ex∗y=h′∗ExN−ry∗EyN−rx∗Erx∗ryN−1=Ex+rx∗y+ry∗Ex−ry∗Ey−rx∗Erx∗ry−1. Note that N−x is equivalent to −x for any x∈ZN. During the SM protocol, no information about x and y except for Ex∗y is revealed to the cloud server.Algorithm 2: SM Epkx,Epky⟶Epkx∗y.
Require:C has Epkx,Epky; P has sk(1)
C:(a)
Pick two random numbersrx,ry∈ZN(b)
x′⟵Ex∗Erx,y′⟵Ey∗Ery(c)
Sendx′,y′ to P(2)
P:(a)
hx⟵Dx′,hy⟵Dy′, h⟵hx∗hymodN,h′⟵Eh(b)
Sendh′ to C(3)
C:(a)
s⟵h′∗ExN−ry, s′⟵s∗EyN−rx(b)
ComputeEx∗y⟵s′∗Erx∗ryN−1In theSSED protocol shown in Algorithm 3, the cloud server has the encrypted vectors EX=<Ex1,…,Exℓ>,EY=<Ey1,…,Eyℓ> and the participants hold the secret key sk. The goal of the SSED protocol is to compute the distance between X and Y. Cloud server computes Exi−yi2 using the SM protocol and then computes EX−Y2=∏i=1ℓExi−yi2 because the Paillier cryptosystem has additive homomorphism. Since the SM protocol does not reveal private information to the cloud server, SSED does not leak information either.Algorithm 3: SSED EpkX,EpkY⟶EpkX−Y2.
Require:C has EpkX,EpkY; P has sk(1)
C:for1≤i≤ℓdo:Epkxi−yi←Epkxi∗EpkyiN−1(2)
C and P:For1≤i≤ℓdo:Use SM to computeEpkxi−yi2 with Epkxi−yi(3)
C:ComputeEpkX−Y2←∏i=1ℓEpkxi−yi2After computing the distances between samples and each cluster center, each sample is assigned to the closest cluster withSBD, SMIN2, and SMINk protocols. In SBD protocol, for random z0≤z≤2ℓ, the cloud server only can get the individual bits of the binary representation of z. During the process, the cloud server has Ez and participants have sk, and z is not known to both of them. The detailed SBD protocol is described in [32].TheSMIN2 protocol is described in Algorithm 4, and this protocol can help cloud server get the encrypted results of the individual bits of minu,v. The participant can not only directly obtain u or v but also send an identifier α to the cloud server. Then, cloud server can access minu,v without decrypting or knowing u,v. Similarly, the SMINk protocol shown in Algorithm 5 is private and secure.Algorithm 4: SMIN2 u,v⟶minu,v.
Require:C has u and v, where 0≤u,v≤2α−1; P has sk(1)
C:(a)
Randomly choose the functionalityF(b)
for1≤i≤αdo:Epkui∗vi⟵SMEpkui,EpkviifF:u>vthen:Wi⟵Epkui∗Epkui∗viN−1, Γi⟵Epkvi−ui∗Epkri^; ri^∈ZNelseWi⟵Epkvi∗Epkui∗viN−1, Γi⟵Epkui−vi∗Epkri^; ri^∈ZNGi⟵Epkui⊕vi, Hi⟵Hi−1ri∗Gi; ri∈ZN and H0=Epk0Φi⟵Epk−1∗Hi, Li⟵Wi∗Φiri′; ri′∈ZN(c)
Γ′⟵π1Γ, L′⟵π2L. Send Γ′ and L′ to P(2)
P:(a)
Mi⟵DskLi′; for 1≤i≤α(b)
if∃j such that Mj=1then:λ⟵1elseλ⟵0(c)
Mi′⟵Γi′λ; for 1≤i≤α, Send Mi′ and Epkλ to C(3)
C:(a)
M˜⟵π1−1M′(b)
for1≤i≤αdo:ηi⟵M˜∗EpkλN−ri′ifF:u>vthen:Epkminu,vi⟵Epkui∗ηielseEpkminu,vi⟵Epkvi∗ηi(c)
Get theEpkminu,vAlgorithm 5: SMINk d1,…,dk⟶dmin.
Require:C has d1,…,dk; P has sk(1)
C:di′←di; for 1≤i≤k, num←k(2)
C and P:(a)
for1≤i≤⌈log2k⌉do:for1≤j≤⌊num/2⌋do:ifi=1then:d2j−1′← SMIN2 d2j−1′,d2j′, d2j′←0elsed2ij−1+1′← SMIN2 d2ij−1+1′,d2ij−1′, d2ij−1′←0(b)
num←⌈num/2⌉(3)
C:dmin←d1′, Get dmin


### 5.2. Privacy-Preserving Analysis for Updating Cluster Centers

In the step of updating the cluster centers, we mainly used Shamir’s secret sharing. TheSSVS protocol is described in Algorithm 6. In the SSVS protocol, each participant generates a polynomial for each sample fx=an−1∗xn−1+⋯+a1∗x+a0. Participants compute shares and hash values of shares. Then, participants upload hash values to the blockchain. The VRS protocol is described in Algorithm 1. In the VRS protocol, participants send and receive shares with each other. The secret values of a participant cannot be revealed even if all remaining participants exchange their shares. Because each participant executes Shamir’s secret sharing algorithm with a random polynomial of degree n−1. In order to compute the coefficients of the corresponding polynomial, at least n values of the polynomial are needed. In theVRS protocol, each participant actually computes n values of polynomial but only sends n−1 polynomial values to the other participants, keeping one polynomial value for itself. Thus, as long as the participants do not reveal the polynomial value they hold, the secret value cannot be deduced even if the remaining participants combine their shares. So the VRS protocol can protect the privacy of the participants.Algorithm 6: SSVS S⟶fx,hv.
Require:C has a random number generate; P has sk(1)
C:(a)
Choosen publicly known random numbers xi,…,xn(b)
Sendxi to Pi(2)
P:(a)
for1≤i≤ndo:For1≤j≤dpido:Pi chooses a random polynomial fi,jx=ai,j,n−1∗xn−1+⋯+ai,j,1∗x+ai,j,0, where ai,j,0←Si,j,Si,j=si,j,t|1≤t≤ℓ(b)
for1≤h≤ndo:Pi computes shares fi,jxh=ai,j,n−1∗xhn−1+⋯+ai,j,1∗xh+ai,j,0Pi computes hv=SHA256fi,jxh and uploads hv to blockchain BAlgorithm 7: VRS fx⟶S.sum.
Require:P has the clustering results Ci=Cji|1≤j≤k(1)
P:Inc th cluster, P1,P2,…,Pn have the set of samples Cc1,Cc2,…,Ccn. For ease of expression, we assume here that Cci=Si,1. In fact, Cci may contains a lot of samples.(a)
for1≤i≤ndo:Pi has computed the polynomial values of Si,1 and hash values in SVVS protocol, where the polynomial values are fi,1xh,1≤h≤nfor1≤h≤ndo:Pi sends fi,1xh to Ph and receive fh,1xi form Ph.Pi computes hv=SHA256fh,1xi.whilehv is not on B do:CallPh resend fh,1xi.(b)
for1≤i≤ndo:Pi computes Fxi=f1,1xi+f2,1xi+⋯+fn,1xi.Pi sends Fxi to C.(2)
C:Solves the set ofFx using Lagrange’s interpolation to find sum of samples S.sum, where S.sum=S1,1+S2,1+⋯+Sn,1.


### 5.3. Resisting Attacks from Malicious Participants

In our multi-party verifiable privacy-preserving federatedk-means scheme, we make no assumption that all participants are semihonest. Thus, there will be malicious participants in the privacy-preserving k-means scheme. In the following, we will show that our scheme can resist inconsistent sharing attacks from malicious participants. We assume that the cloud server is semihonest and will follow the proposed protocol.Because a malicious participant may send inconsistent shares (e.g., shares of samples that do not belong to him) to other participants in the process of updating cluster centers. When participants receive shares from others, they should compute the hash values of shares and verify whether the hash values are on the blockchain. Furthermore, once the information has been agreed and added to the blockchain, it is recorded by all nodes together and is cryptographically guaranteed to be interlinked backward and forward, making tampering very difficult and costly. Therefore, if participants receive a share that cannot be verified, it indicates that other participants have sent inconsistent data share. And we can conclude that the participant does not follow the proposed protocol, and it is considered to be a malicious participant. So incorrectk-Means results due to inconsistent shares by malicious participants can be avoided.


## 5.1. Privacy-Preserving Analysis for Assigning Samples

In the stage of assigning samples, each participant encrypts samples with the Paillier cryptosystem. Because Paillier’s cryptosystem is semantically secure, other participants and cloud servers cannot decrypt and deduce additional information from the encrypted data.According to our scheme, we should compute the distances between samples and cluster centers with theSM and SSED protocols. In SM protocol, the cloud server has the encrypted values Ex and Ey, and the participants hold the secret key sk. The aim of the SM protocol is to return encrypted values of x∗y (e.g., Ex∗y) to cloud server with the interaction between cloud server and participants. The idea of SM protocol is based on the following property:(5)x∗y=x+rx∗y+ry−x∗ry−y∗rx−rx∗ry.The detailedSM protocol is shown in Algorithm 2. Firstly, the cloud server chooses two random numbers rx,ry, which are only known to the cloud server. Then, the cloud server computes x′=Ex+rx=Ex∗Erx,y′=Ey+ry=Ey∗Ery and sends x′,y′ to the participant. After receiving x′ and y′, participant decrypts hx=Dx′,hy=Dy′ and computes h=hx∗hy=x+rx∗y+ry. Then, the participant sends h′=Eh to the cloud server. Finally, the cloud server computes Ex∗y=h′∗ExN−ry∗EyN−rx∗Erx∗ryN−1=Ex+rx∗y+ry∗Ex−ry∗Ey−rx∗Erx∗ry−1. Note that N−x is equivalent to −x for any x∈ZN. During the SM protocol, no information about x and y except for Ex∗y is revealed to the cloud server.Algorithm 2: SM Epkx,Epky⟶Epkx∗y.
Require:C has Epkx,Epky; P has sk(1)
C:(a)
Pick two random numbersrx,ry∈ZN(b)
x′⟵Ex∗Erx,y′⟵Ey∗Ery(c)
Sendx′,y′ to P(2)
P:(a)
hx⟵Dx′,hy⟵Dy′, h⟵hx∗hymodN,h′⟵Eh(b)
Sendh′ to C(3)
C:(a)
s⟵h′∗ExN−ry, s′⟵s∗EyN−rx(b)
ComputeEx∗y⟵s′∗Erx∗ryN−1In theSSED protocol shown in Algorithm 3, the cloud server has the encrypted vectors EX=<Ex1,…,Exℓ>,EY=<Ey1,…,Eyℓ> and the participants hold the secret key sk. The goal of the SSED protocol is to compute the distance between X and Y. Cloud server computes Exi−yi2 using the SM protocol and then computes EX−Y2=∏i=1ℓExi−yi2 because the Paillier cryptosystem has additive homomorphism. Since the SM protocol does not reveal private information to the cloud server, SSED does not leak information either.Algorithm 3: SSED EpkX,EpkY⟶EpkX−Y2.
Require:C has EpkX,EpkY; P has sk(1)
C:for1≤i≤ℓdo:Epkxi−yi←Epkxi∗EpkyiN−1(2)
C and P:For1≤i≤ℓdo:Use SM to computeEpkxi−yi2 with Epkxi−yi(3)
C:ComputeEpkX−Y2←∏i=1ℓEpkxi−yi2After computing the distances between samples and each cluster center, each sample is assigned to the closest cluster withSBD, SMIN2, and SMINk protocols. In SBD protocol, for random z0≤z≤2ℓ, the cloud server only can get the individual bits of the binary representation of z. During the process, the cloud server has Ez and participants have sk, and z is not known to both of them. The detailed SBD protocol is described in [32].TheSMIN2 protocol is described in Algorithm 4, and this protocol can help cloud server get the encrypted results of the individual bits of minu,v. The participant can not only directly obtain u or v but also send an identifier α to the cloud server. Then, cloud server can access minu,v without decrypting or knowing u,v. Similarly, the SMINk protocol shown in Algorithm 5 is private and secure.Algorithm 4: SMIN2 u,v⟶minu,v.
Require:C has u and v, where 0≤u,v≤2α−1; P has sk(1)
C:(a)
Randomly choose the functionalityF(b)
for1≤i≤αdo:Epkui∗vi⟵SMEpkui,EpkviifF:u>vthen:Wi⟵Epkui∗Epkui∗viN−1, Γi⟵Epkvi−ui∗Epkri^; ri^∈ZNelseWi⟵Epkvi∗Epkui∗viN−1, Γi⟵Epkui−vi∗Epkri^; ri^∈ZNGi⟵Epkui⊕vi, Hi⟵Hi−1ri∗Gi; ri∈ZN and H0=Epk0Φi⟵Epk−1∗Hi, Li⟵Wi∗Φiri′; ri′∈ZN(c)
Γ′⟵π1Γ, L′⟵π2L. Send Γ′ and L′ to P(2)
P:(a)
Mi⟵DskLi′; for 1≤i≤α(b)
if∃j such that Mj=1then:λ⟵1elseλ⟵0(c)
Mi′⟵Γi′λ; for 1≤i≤α, Send Mi′ and Epkλ to C(3)
C:(a)
M˜⟵π1−1M′(b)
for1≤i≤αdo:ηi⟵M˜∗EpkλN−ri′ifF:u>vthen:Epkminu,vi⟵Epkui∗ηielseEpkminu,vi⟵Epkvi∗ηi(c)
Get theEpkminu,vAlgorithm 5: SMINk d1,…,dk⟶dmin.
Require:C has d1,…,dk; P has sk(1)
C:di′←di; for 1≤i≤k, num←k(2)
C and P:(a)
for1≤i≤⌈log2k⌉do:for1≤j≤⌊num/2⌋do:ifi=1then:d2j−1′← SMIN2 d2j−1′,d2j′, d2j′←0elsed2ij−1+1′← SMIN2 d2ij−1+1′,d2ij−1′, d2ij−1′←0(b)
num←⌈num/2⌉(3)
C:dmin←d1′, Get dmin


## 5.2. Privacy-Preserving Analysis for Updating Cluster Centers

In the step of updating the cluster centers, we mainly used Shamir’s secret sharing. TheSSVS protocol is described in Algorithm 6. In the SSVS protocol, each participant generates a polynomial for each sample fx=an−1∗xn−1+⋯+a1∗x+a0. Participants compute shares and hash values of shares. Then, participants upload hash values to the blockchain. The VRS protocol is described in Algorithm 1. In the VRS protocol, participants send and receive shares with each other. The secret values of a participant cannot be revealed even if all remaining participants exchange their shares. Because each participant executes Shamir’s secret sharing algorithm with a random polynomial of degree n−1. In order to compute the coefficients of the corresponding polynomial, at least n values of the polynomial are needed. In theVRS protocol, each participant actually computes n values of polynomial but only sends n−1 polynomial values to the other participants, keeping one polynomial value for itself. Thus, as long as the participants do not reveal the polynomial value they hold, the secret value cannot be deduced even if the remaining participants combine their shares. So the VRS protocol can protect the privacy of the participants.Algorithm 6: SSVS S⟶fx,hv.
Require:C has a random number generate; P has sk(1)
C:(a)
Choosen publicly known random numbers xi,…,xn(b)
Sendxi to Pi(2)
P:(a)
for1≤i≤ndo:For1≤j≤dpido:Pi chooses a random polynomial fi,jx=ai,j,n−1∗xn−1+⋯+ai,j,1∗x+ai,j,0, where ai,j,0←Si,j,Si,j=si,j,t|1≤t≤ℓ(b)
for1≤h≤ndo:Pi computes shares fi,jxh=ai,j,n−1∗xhn−1+⋯+ai,j,1∗xh+ai,j,0Pi computes hv=SHA256fi,jxh and uploads hv to blockchain BAlgorithm 7: VRS fx⟶S.sum.
Require:P has the clustering results Ci=Cji|1≤j≤k(1)
P:Inc th cluster, P1,P2,…,Pn have the set of samples Cc1,Cc2,…,Ccn. For ease of expression, we assume here that Cci=Si,1. In fact, Cci may contains a lot of samples.(a)
for1≤i≤ndo:Pi has computed the polynomial values of Si,1 and hash values in SVVS protocol, where the polynomial values are fi,1xh,1≤h≤nfor1≤h≤ndo:Pi sends fi,1xh to Ph and receive fh,1xi form Ph.Pi computes hv=SHA256fh,1xi.whilehv is not on B do:CallPh resend fh,1xi.(b)
for1≤i≤ndo:Pi computes Fxi=f1,1xi+f2,1xi+⋯+fn,1xi.Pi sends Fxi to C.(2)
C:Solves the set ofFx using Lagrange’s interpolation to find sum of samples S.sum, where S.sum=S1,1+S2,1+⋯+Sn,1.


## 5.3. Resisting Attacks from Malicious Participants

In our multi-party verifiable privacy-preserving federatedk-means scheme, we make no assumption that all participants are semihonest. Thus, there will be malicious participants in the privacy-preserving k-means scheme. In the following, we will show that our scheme can resist inconsistent sharing attacks from malicious participants. We assume that the cloud server is semihonest and will follow the proposed protocol.Because a malicious participant may send inconsistent shares (e.g., shares of samples that do not belong to him) to other participants in the process of updating cluster centers. When participants receive shares from others, they should compute the hash values of shares and verify whether the hash values are on the blockchain. Furthermore, once the information has been agreed and added to the blockchain, it is recorded by all nodes together and is cryptographically guaranteed to be interlinked backward and forward, making tampering very difficult and costly. Therefore, if participants receive a share that cannot be verified, it indicates that other participants have sent inconsistent data share. And we can conclude that the participant does not follow the proposed protocol, and it is considered to be a malicious participant. So incorrectk-Means results due to inconsistent shares by malicious participants can be avoided.


## 6. Performance Analysis

### 6.1. Experimental Analysis

We use two datasets of different sizes for the experiments. The first one is a 2-dimensional synthetic dataset S1 [33], which is a clustering benchmark. S1 contains 2000 samples and 7 cluster centers. The second dataset is the HCV [34], which contains laboratory values of blood donors and hepatitis C patients. HCV consists of 588 10-dimensional samples and 4 cluster centers.To show that our scheme is suitable for multi-party scenarios, we assume that samples are randomly distributed among three participants, and we choose SHA256 as the required hash function. In the process of calculating metadata, the blockchain needs to run a consensus algorithm. The consensus time depends on the specific blockchain system selected. Therefore, this section only conducts experimental analysis on the proposed scheme and does not consider the execution cost of the blockchain itself.Running time of the experiment on datasets S1 and HCV is shown in Tables2 and 3, respectively, where n, k, C, and P represent the data size, number of clusters, cloud server, and participants. The unit of time is seconds. We record the running time under different data size in one iteration, and it is obvious that the running time increases proportionally with the number of data size increasing.Table 2
Running time of privacy-preservingk-means clustering on S1 dataset in one iteration.
nkC (S)P (S)100714.244.18200729.178.53500774.7720.8210007142.4139.5420007278.7980.56Table 3
Running time of privacy-preservingk-means clustering on HCV dataset in one iteration.
nkC (S)P (S)10044.361.3720048.462.69588428.228.78We calculate the respective time proportions of cloud server and participants to judge the performance of our scheme. In the process of our scheme, the cloud server undertakes the main computing tasks, and running time accounts for 77%.


### 6.2. Accuracy Analysis

We calculate the percentage of correctly classified samples as the standard for the accuracy of our scheme. For dataset S1, we compare the result of our privacy-preservingk-means clustering with plaintext k-means clustering to measure the accuracy of our scheme. The result of privacy-preserving k-means clustering on S1 is shown in Figure 2 and the accuracy of the S1 dataset is 99.25%. In the same way, we calculated the accuracy of the HCV dataset to be 99.14%. So, we can conclude that our scheme can get high-accuracy clustering results.Figure 2
Result of privacy-preservingk-means clustering on S1 dataset.


### 6.3. Functional Analysis

We analyze our scheme’s function and compare it with schemes proposed in [13, 14, 25] from different properties, including parties, participants’ information protection, cluster centers protection, and verifiability. The result is shown in Table 4. In [25], Jiang et al. combined homomorphic encryption and garbled circuit to design an outsourced two-party privacy-preserving k-means clustering scheme. Compared with the scheme in [25], our scheme extends to multi-party. Furthermore, our scheme can verify the shares from other participants with secret sharing, hash function, and blockchain technology. In the step of updating cluster centers, the shares are verified by hash values calculated in advance, and the blockchain is used to ensure that once the hash value is verified, the participants can be guaranteed to share the consistent data. From Table 4, the significant advantages of our scheme compared to the other three schemes are verifiable.Table 4
Function comparison with [13, 14, 25].
SchemePartyParticipants’ information protectionCluster centers protectionVerifiable[25]Two✓××[14]Multi✓✓×[13]Two✓××Our schemeMulti✓✓✓


## 6.1. Experimental Analysis

We use two datasets of different sizes for the experiments. The first one is a 2-dimensional synthetic dataset S1 [33], which is a clustering benchmark. S1 contains 2000 samples and 7 cluster centers. The second dataset is the HCV [34], which contains laboratory values of blood donors and hepatitis C patients. HCV consists of 588 10-dimensional samples and 4 cluster centers.To show that our scheme is suitable for multi-party scenarios, we assume that samples are randomly distributed among three participants, and we choose SHA256 as the required hash function. In the process of calculating metadata, the blockchain needs to run a consensus algorithm. The consensus time depends on the specific blockchain system selected. Therefore, this section only conducts experimental analysis on the proposed scheme and does not consider the execution cost of the blockchain itself.Running time of the experiment on datasets S1 and HCV is shown in Tables2 and 3, respectively, where n, k, C, and P represent the data size, number of clusters, cloud server, and participants. The unit of time is seconds. We record the running time under different data size in one iteration, and it is obvious that the running time increases proportionally with the number of data size increasing.Table 2
Running time of privacy-preservingk-means clustering on S1 dataset in one iteration.
nkC (S)P (S)100714.244.18200729.178.53500774.7720.8210007142.4139.5420007278.7980.56Table 3
Running time of privacy-preservingk-means clustering on HCV dataset in one iteration.
nkC (S)P (S)10044.361.3720048.462.69588428.228.78We calculate the respective time proportions of cloud server and participants to judge the performance of our scheme. In the process of our scheme, the cloud server undertakes the main computing tasks, and running time accounts for 77%.


## 6.2. Accuracy Analysis

We calculate the percentage of correctly classified samples as the standard for the accuracy of our scheme. For dataset S1, we compare the result of our privacy-preservingk-means clustering with plaintext k-means clustering to measure the accuracy of our scheme. The result of privacy-preserving k-means clustering on S1 is shown in Figure 2 and the accuracy of the S1 dataset is 99.25%. In the same way, we calculated the accuracy of the HCV dataset to be 99.14%. So, we can conclude that our scheme can get high-accuracy clustering results.Figure 2
Result of privacy-preservingk-means clustering on S1 dataset.


## 6.3. Functional Analysis

We analyze our scheme’s function and compare it with schemes proposed in [13, 14, 25] from different properties, including parties, participants’ information protection, cluster centers protection, and verifiability. The result is shown in Table 4. In [25], Jiang et al. combined homomorphic encryption and garbled circuit to design an outsourced two-party privacy-preserving k-means clustering scheme. Compared with the scheme in [25], our scheme extends to multi-party. Furthermore, our scheme can verify the shares from other participants with secret sharing, hash function, and blockchain technology. In the step of updating cluster centers, the shares are verified by hash values calculated in advance, and the blockchain is used to ensure that once the hash value is verified, the participants can be guaranteed to share the consistent data. From Table 4, the significant advantages of our scheme compared to the other three schemes are verifiable.Table 4
Function comparison with [13, 14, 25].
SchemePartyParticipants’ information protectionCluster centers protectionVerifiable[25]Two✓××[14]Multi✓✓×[13]Two✓××Our schemeMulti✓✓✓


## 7. Conclusion

In this article, we propose a multi-party verifiable privacy-preserving federatedk-means scheme that provides a validation mechanism in an outsourced environment. By computing hash values of secret shares in advance, we can detect malicious participants that send inconsistent shares and avoid incorrect k-means clustering results. The security and experimental analysis show that our scheme can protect privacy and get high clustering results.



---

*Source: 3630312-2021-12-28.xml*