## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
Given the individual security proofs for the SM, \(\rm{SSED_{op}}\), and \(\rm{ASMIN_{n}}\) protocols, Algorithm 6 is secure in the semi-honest attack model according to the composition theory [33]. In conclusion, each phase of the privacy-preserving parallel k-means clustering algorithm is secure in the semi-honest attack model. Therefore, the entire parallel k-means clustering algorithm is secure in the semi-honest attack model according to the composition theory [33]. ## 7 Performance Analysis

This section evaluates the performances of both the proposed privacy-preserving k-means clustering algorithm and the proposed parallel k-means clustering algorithm. The evaluations were conducted in the Linux Ubuntu 18.04.2 environment with an Intel(R) Xeon(R) CPU E5-2630 2.20 GHz 10-Core 3.10 GHz processor and 64 GB (16 GB \(\times\) 4 AE) DDR3 UDIMM 1600 MHz RAM. The algorithms were implemented in C++ and, to represent the range 0 to 2 key_size in the Paillier encryption system, the GMP library's mpz_t data type was used instead of basic data types. The GMP library supports operations on larger numbers compared with typical numeric data types (e.g., short, int, long). \begin{table}
\begin{tabular}{c c c} \hline \hline  & **Information Obtainable by \(\rm{C_{B}}\)** & **Simulation Image** \\ \hline Encrypted Data Received & E(data) & E(sim\_data) \\ from \(\rm{C_{A}}\) & & \\ Decrypted Data & data & \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Information obtainable by \(\rm{C_{B}}\) in the k-means clustering algorithm. The performance evaluation focused on the execution time, measured as the difference between the timestamp just before the algorithm's execution and the timestamp just after its completion. The dataset used for the performance evaluation was the synthetic uniform dataset [34] as shown in Table 6.

In this section, we evaluate the performance of both the Secure k-Means Clustering algorithm with Advanced Secure Protocol (SkMC\({}_{\text{A}}\)) proposed in Section 4 and the Parallel Secure k-Means Clustering algorithm with Advanced Secure Protocol (PSkMC\({}_{\text{A}}\)) proposed in Section 5. To measure the performance improvement of SkMC\({}_{\text{A}}\), we compare it with [25] (i.e., the Secure k-Means Clustering algorithm with Index filtering (SkMC\({}_{\text{I}}\))), which provides a similar level of information protection (data protection, query protection, and access pattern protection). Additionally, as no parallel k-means clustering algorithm that supports information protection currently exists, we created the parallel processing version of SkMC\({}_{\text{I}}\) (i.e., PSkMC\({}_{\text{I}}\)) in order to compare it with PSkMC\({}_{\text{A}}\). The query accuracy of both the existing k-means clustering algorithm and the proposed k-means clustering algorithm is 100%. Table 7 summarizes the comparison targets for the proposed k-means clustering algorithms. The performance evaluation of the k-means clustering algorithm was performed by selecting random data points as queries from the generated data. The performance evaluation compared the query processing times of the proposed algorithms and the existing algorithms with changes in the number of data points (n), k, and threads. The threshold for the k-means clustering algorithm was set to 10. Table 8 lists the parameters considered in the performance evaluation. Figure 7 illustrates the performance of SkMC\({}_{\text{A}}\) and SkMC\({}_{\text{I}}\) with varying total data sizes when k = 10, m = 2, and K = 512. When n = 2k, SkMC\({}_{\text{A}}\) takes approximately 1807 s, while SkMC\({}_{\text{I}}\) requires around 14,456 s. The significant performance improvement is attributed to the faster execution time of the proposed ASMIN and ASMIN\({}_{\text{n}}\) protocols compared with the SMIN and SMIN\({}_{\text{n}}\) protocols used in SkMC\({}_{\text{I}}\). Through the enhanced efficiency of