## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
The information obtainable by \(\mathrm{C_{A}}\) and \(\mathrm{C_{B}}\) during the execution of the ASMIN protocol is summarized in Table 3. Here, the information about \(\mathrm{r_{1}}\) and \(\mathrm{r_{2}}\) is safe from exposure since they are random variables. First, the simulation image of the ASMIN protocol on the \(\mathrm{C_{A}}\) side is given by Equation (4). The indistinguishability of the simulation images of \(E(u)\), \(E(\beta)\), \(E(min^{\prime})\) and the execution images of \(E(\alpha)\), \(E(\beta)\), \(E(min)\) can be proven through Equations (5) and (6). Since the Paillier encryption system generates random numbers during ciphertext creation, attackers cannot identify the execution image from the simulation image. \[\prod\
olimits_{\mathrm{C_{A}^{\prime}}}\left(ASC(E(u),\ E(v))\right)=\left\{E (u),\ E(v),\ r_{1},R_{2},\left(E(\gamma)\right\}\right. \tag{4}\]

\[E(u)=g^{u}r^{N}\ mod\ N^{2}\ \
eq E(\alpha)=g^{u}r^{N}\ mod\ N^{2},\ where\ 0<r<N \tag{5}\]

\begin{table}
\begin{tabular}{c c c} \hline \hline
**Input: E(data), E(node), E(threshold), E(initial\_center)** & **Output: cluster\_center** \\ \(\mathrm{C_{A}}\): & 01. for \(1\leq i\leq n\) & 02. thread\_pool\_push(calculate\_new\_center(k,m,cnt,E(data),E(initial\_center),E(new\_center)))//calculate\_new\_center() is the Procedure 1 in Algorithm 5 \\ \(\alpha=\mathrm{SETC}(E(initial\_center),E(new\_center),E(threshold))\) & 03. if \(\alpha=1\) & 04. if \(\alpha=1\) \\ \(\mathrm{C_{C_{B}}}\): & 05. for \(1\leq i\leq k\)



\[E\left(min^{\prime}\right)=g^{min^{\prime}}r^{N}\ mod\ N^{2}\
eq E(\min)=g^{min}r^{N} \ mod\ N^{2},\ where\ 0<r<N \tag{6}\]

On the C\({}_{\text{B}}\) side, the simulation image of the ASMIN protocol is given by Equation (7). The indistinguishability of the simulation images of \(x\), \(y\), \(E(w_{1})\), \(E(w_{2})\) and the execution images of \(X\), \(Y\), \(E(\gamma_{1})\), \(E(\gamma_{2})\) can be proven through Equations (8) and (9). The variable x in the simulation image involves the addition and multiplication of two random numbers, making the probability of identifying the execution image of \(X\) be \(1/(x-1)\). Since the minimum value of the random numbers is 3, the probability \(1/(x-1)\) is less than \(1/2\), making identification impossible. \(E(w_{1})\), \(E(w_{2})\), \(E(\gamma_{1})\), and \(E(\gamma_{2})\) involve random numbers generated during ciphertext creation in the Paillier encryption system, making it impossible for the attacker to distinguish between the execution and simulation images. \[\prod_{\text{C}_{A}^{{}^{\prime}}}\left(ASMIN(x,\ y)\right)=\{x,\ y,\ (E(w_{1}),\ E(w_{2})\} \tag{7}\]

\[\left\{ \begin{aligned} x=ur_{1}+r_{2}\
eq X=\alpha r_{1}^{ \prime}+r_{2}^{\prime}\ where\ 3<r_{1},r_{2},r_{1}^{\prime},r_{2}^{\prime}<N\\ P(\text{The probability of}\ identifying\ X\ through\ x)=\frac{1}{x-1}\leq \frac{1}{2},\ where\ x>3\end{aligned} \right. \tag{8}\]

\[\left\{ \begin{aligned} E(w_{1})=g^{w_{1}}r^{N}mod\ N^{2}\
eq E( \gamma)=g^{\gamma_{1}}r^{N}\ mod\ N^{2},\ where\ 0<r<N\\ E(w_{2})=g^{w_{2}}r^{N}mod\ N^{2}\
eq E(\gamma)=g^{\gamma_{2}}r^{N}\ mod\ N^{2},\ where\ 0<r<N\end{aligned} \right. \tag{9}\]

In summary, the analysis demonstrates that no information is exposed during the execution of the ASMIN protocol on the C\({}_{\text{A}}\) and C\({}_{\text{B}}\) sides. Therefore, the ASMIN protocol is secure under the semi-honest attack model. (2) ASMIN\({}_{\text{n}}\) Protocol

The part where C\({}_{\text{A}}\) and C\({}_{\text{B}}\) exchange data in the ASMIN\({}_{\text{n}}\) protocol is the execution part of the ASMIN protocol. Therefore, if the ASMIN protocol is secure under the semi-honest attack model, by the composition theory [33], we can conclude that the ASMIN\({}_{\text{n}}\) protocol is also secure under the semi-honest attack model. Since the security of the ASMIN protocol has been demonstrated earlier, it follows that the ASMIN\({}_{\text{n}}\) protocol is secure under the semi-honest attack model.