# Secure K-Means Clustering Scheme for Confidential Data Based on Paillier Cryptosystem
## 8 Performance Analysis
### Comparative Evaluation  
In the field of secure computation and privacy-preserving data mining, several studies have addressed these issues. This paper contrasts our protocol with those presented in existing literature [21; 22; 23], highlighting the advantages of our approach in terms of user operation requirements and multi-party cloud outsourcing support. Comparisons with the existing literature are shown in Table 6.  
\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Operation** & **2D/4D Count** & **8D Count** & **Complexity** \\ \hline Encrypptions & \(2n\) & \(4n\) & \(\mathcal{O}(n)\) \\ Distance Calculations & \(nk\) & \(2 nk\) & \(\mathcal{O}(nk)\) \\ Hom. Multiplications & \(2 nk\) & \(4 nk\) & \(\mathcal{O}(nkd)\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Homomorphic operations per iteration.  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Dataset** & **2D** & **3D** & **4D** & **8D** \\ \hline Wine & 97.2 & 198.3 & 296.5 & – \\ Breast Cancer & 199.1 & 287.4 & 399.2 & – \\ Ionosphere & 289.7 & 377.6 & 478.3 & – \\ Yeast & 387.4 & 498.1 & 587.9 & 896.2 \\ \hline \hline \end{tabular}
\end{table}
Table 5: Communication costs per iteration (MB).  
User Operation Requirements: The protocols discussed in [21; 22; 23] generally require users to be online and participate in intermediate steps. For instance, these schemes often involve continuous interaction between users and the computation server or cloud service provider to complete each computational step. While this design ensures data privacy, it introduces additional communication overhead and user operational burdens, thereby reducing overall efficiency. In contrast, our protocol eliminates the need for users to be online. Users only need to upload encrypted data at the initial stage, and all subsequent computations are performed by the computation server (CS) and cloud service provider (CSP) within the encrypted domain. This approach not only reduces the number of communications but also decreases user involvement and operational complexity, significantly improving the protocol's efficiency.  
Multi-Party Cloud Outsourcing Support: Regarding multi-party cloud outsourcing, the scheme in [22] is somewhat limited as it only supports single-party data outsourcing, meaning only one data owner can outsource their data to the cloud for processing. This limitation makes the scheme less effective when handling data from multiple parties. Our protocol overcomes this limitation by supporting multi-party cloud outsourcing for K-means clustering. Multiple data owners can securely outsource their encrypted data to the cloud service provider for clustering analysis without concerns about data privacy breaches. By employing Paillier homomorphic encryption, we ensure that data from all parties remains encrypted throughout the computation process, enabling secure and efficient multi-party cloud outsourcing for clustering.  
Compared to the protocols in [21; 22; 23], our approach demonstrates clear advantages in the following two areas: Firstly, it eliminates the need for users to be online, thereby significantly enhancing efficiency, simplifying user operations, and reducing communication overhead. Secondly, it supports multi-party cloud outsourcing, leveraging Paillier homomorphic encryption to achieve secure and efficient clustering computation, expanding the applicability of the protocol. These improvements not only enhance the practical utility of the protocol but also provide new insights and methods for secure computation and privacy-preserving data mining research.