# Secure K-Means Clustering Scheme for Confidential Data Based on Paillier Cryptosystem
## 6 Secure Homomorphic K-Means Clustering Protocol
### Secure Update Cluster Center (SUCC) Protocol  
Algorithm 4 ensures that \(E(b_{ij})\) will be 1 if and only if all individual comparisons indicate that \(x_{i}\) is greater than or equal to \(c_{j}\) in every dimension. This protocol ensures the cluster center updates are performed securely without revealing the actual data points or intermediate sums and counts.  
In this step, the protocol initializes by taking encrypted data points \(\{E(x_{i})\}_{i=1}^{N}\) and encrypted cluster centers \(\{E(c_{j})\}_{j=1}^{K}\) as input. The aim is to produce updated encrypted cluster centers \(\{E(c_{i}^{*})\}_{j=1}^{K}\). This sub-step is performed by the user for each cluster \(C_{j}\). Firstly, an accumulator \(E(c_{j}^{*})\) is initialized to zero. This accumulator will be utilized to compute the sum of encrypted data points belonging to each cluster. Secondly, a counter \(|C_{j}|\) is initialized to zero. This counter will keep track of the number of encrypted data points assigned to each cluster. In this step, the cloud server (CS) processes each encrypted data point \(E(x_{i})\). For each data point, the server iterates over each cluster \(C_{j}\). It determines whether the data point belongs to the cluster, sets a binary indicator \(E(b_{ij})\) accordingly, accumulates the encrypted data points belonging to the cluster in the accumulator \(E(c_{i}^{*})\), and updates the counter \(|C_{j}|\) encryptedly. This final step involves updating the encrypted cluster centers by the cloud server (CS) and the cloud service provider (CSP). For each cluster \(C_{j}\), the accumulator \(E(c_{j}^{*})\) is updated using the modular inverse of the counter\(E(|C_{j}|)\) to compute the encrypted average of the cluster. The updated encrypted cluster centers \(\{E(c_{j}^{*})\}_{j=1}^{K}\) are then returned.  
To determine if \(x_{i}\) belongs to \(C_{j}\) using a secure comparison protocol, we can compare each coordinate of the encrypted data point \(E(x_{i})\) with the corresponding coordinate of the encrypted cluster center \(E(c_{j})\). Let \(d\) denote the number of dimensions.  
* The SEQ protocol is used to determine whether the ciphertext belongs to the cluster center. SEQ protocol can output ciphertext \(f\), if \(f=0\), then \(x=y\); otherwise, \(x\
eq y\). Compute the encrypted boolean \(E(b_{ijk})\), indicating whether \(x_{ik}\) is less than \(c_{jk}\): \[E(b_{ijk})=\begin{cases}1&otherwise\\ 0&\text{f}=0\end{cases}\]
* Aggregate the results of the comparisons for all dimensions. Let \(E(b_{ij})\) be the logical AND operation applied to all \(E(b_{ijk})\) values for \(k=1\) to \(d\): \[E(b_{ij})=\prod_{k=1}^{d}E(b_{ijk})\]  
```
1:Input: Encrypted data points \(\{E(x_{i})\}_{i=1}^{N}\), encrypted cluster centers \(\{E(c_{j})\}_{j=1}^{K}\).
2:Output: Updated encrypted cluster centers \(\{E(c_{j}^{*})\}_{j=1}^{K}\).
3:Performed by User:
4:for each cluster \(C_{j}\)do
5: Initialize an accumulator \(E(c_{j}^{*})\) to zero.
6: Initialize a counter \(|C_{j}|\) to zero.
7:endfor
8:Performed by CS:
9:for each encrypted data point \(E(x_{i})\)do
10:for each cluster \(C_{j}\)do
11: Determine whether \(x_{i}\) belongs to \(C_{j}\):
12:if \(E(x_{i})\) belongs to \(E(c_{j})\)then
13:\(E(b_{ij})=1\)
14:else
15:\(E(b_{ij})=0\)
16:endif
17: If \(x_{i}\) belongs to \(C_{j}\), add \(E(x_{i})\) to the accumulator \(E(c_{j}^{*})\):
18:\(E(c_{j}^{*})=E(c_{j}^{*})+E(x_{i})\times E(b_{ij})\)
19: If \(x_{i}\) belongs to \(C_{j}\), \(E(|C_{j}|)=\prod_{k=1}^{d}E(b_{ij})\)
20:endfor
21:endfor
22:Performed by CS and CSP:
23:for each cluster \(C_{j}\)do
24: Update the accumulator by the modular inverse to compute the encrypted average:
25:\(E(c_{j}^{*})=SDIV(E(|C_{j}|),E(c_{j}^{*}))\)
26:endfor
27:return Updated encrypted cluster centers \(\{E(c_{j}^{*})\}_{j=1}^{K}\).
```  
**Algorithm 4** Secure Update Cluster Centers (SUCC) Protocol using Paillier Cryptosystem