## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
### Security Analysis of the k-Means Clustering Algorithm

To demonstrate the safety of the proposed k-means clustering algorithm in the semi-honest attack model, security analyses were performed for both C\({}_{\text{A}}\) and C\({}_{\text{B}}\). First, the information accessible to C\({}_{\text{A}}\) is described. The information accessible to C\({}_{\text{A}}\) includes encrypted data and encrypted queries (Table 4). The encrypted data are the encryption of the original data by the Paillier encryption system. The encryption threshold is the encryption of the user query by the Paillier encryption system. Therefore, through Equation (10), the impossibility of computation between the execution image and the simulation image in the k-means clustering algorithm can be demonstrated. \[ \begin{aligned} E(threshold)=g^{threshold}r^{m}\ mod\ N^{2}\\ \
eq E(sim\_threshold)=g^{threshold}r^{N}\ mod\ N^{2},\ where\ r<N\end{aligned}  \tag{10}\]

Secondly, let us describe the information that C\({}_{\text{B}}\) can obtain. The information obtainable by C\({}_{\text{B}}\) includes the encrypted data received from C\({}_{\text{A}}\) (i.e., E(data)) and the decrypted data (i.e., data) (Table 5). \begin{table}
\begin{tabular}{c c c} \hline \hline \multicolumn{3}{c}{**C\({}_{\text{A}}\)’s Accessible Execution Image**} & **Simulation Image** \\ \hline Encrypted Data & E(data) & E(sim\_data) \\ Encrypted Query & E(threshold) & E(sim\_threshold) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Information accessible to C\({}_{\text{A}}\) in the k-means clustering algorithm. The encrypted data received from \(\rm{C_{A}}\) are identical to the encrypted data in Table 4, making it impossible to perform calculations between the execution image and the simulation image. The decryption data in the simulation image, \(\rm{sim\_data}\), consist of random number additions. Therefore, the probability of identifying the data in the execution image is \(\frac{1}{sim\_data}\). Since the minimum value of the random number is 3, the probability \(\frac{1}{sim\_data}\) is lower than \(\frac{1}{2}\), making identification impossible (Equation (11)). \[\left\{ \begin{array}{l}data=data+r_{1}\
eq sim\_data+r_{2},\;where\;3<r_{1}, \;r_{2}<N\\ P(\text{The probability of identifying data through }\text{sim\_data})=\frac{1}{sim\_data}\leq \frac{1}{2},\;where\;sim\_data>3\end{array} \right. \tag{11}\]

Finally, as demonstrated earlier, each step of the k-means clustering algorithm is secure under the semi-honest attack model. Therefore, the proposed privacy-preserving k-means clustering algorithm is secure under the semi-honest attack model according to the composition theory [33]. ### Security Analysis of the Parallel k-Means Clustering Algorithm

The proposed privacy-preserving parallel k-means clustering algorithm consists of two phases: the parallel preprocessing phase (Algorithm 5) and the parallel k-means clustering phase (Algorithm 6). To demonstrate the security of the parallel k-means clustering algorithm in the semi-honest attack model, security analyses were performed for each phase. Firstly, Algorithm 5 is secure, as it was proven to be a secure version of Algorithm 3, and the execution images on the \(\rm{C_{A}}\) and \(\rm{C_{B}}\) sides are identical. The difference between Algorithm 5 and Algorithm 3 lies in the use of a thread pool to parallelize the SM, \(\rm{SSED_{op}}\), and \(\rm{ASMIN_{n}}\) protocols. Since the SM, \(\rm{SSED_{op}}\), and \(\rm{ASMIN_{n}}\) protocols were individually proven to be secure, Algorithm 5 is secure in the semi-honest attack model according to the composition theory [33]. Secondly, Algorithm 6 is secure, having been proven to be a secure version of Algorithm 4, and the execution images on the \(\rm{C_{A}}\) and \(\rm{C_{B}}\) sides are identical. The difference between Algorithm 6 and Algorithm 4 lies in the use of a thread pool to parallelize the SM, \(\rm{SSED_{op}}\), and \(\rm{ASMIN_{n}}\) protocols.