## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
Figure 10: Memory usage of the proposed k-means clustering algorithm and the existing algorithm. Figure 9: Performance evaluation of k-means clustering algorithms with a changing number of threads. ## 8 Discussion

### The Time Complexity of the Proposed Secure Protocols

To measure the time complexity of the proposed secure protocols, we analyzed the number of homomorphic operations performed in each protocol. For this, let \(n\) represent the number of input data points, \(m\) the number of dimensions, and \(l\) the number of bits. The time complexities of each secure protocol are as shown in Table 9. For the ASMIN protocol, a total of eight homomorphic operations were performed to obtain the result of the comparison. Therefore, the time complexity of the ASMIN protocol is constant time, and can be simplified to O(1). In the case of the ASMIN protocol, it performs ASMIN protocols \(\log^{\text{2}}\) times, so the time complexity of the ASMIN\({}_{\text{n}}\) protocol is O(\(\log^{\text{2}}\)). The proposed secure protocols have constant time complexity regardless of the number of bits, while the existing secure protocols exhibit a time complexity that is proportional to the number of bits. ### The Time Complexity of the Proposed k-Means Clustering Algorithm

The time complexity of the proposed k-means clustering algorithm (SkMC\({}_{\text{A}}\)) and that of SkMC\({}_{\text{I}}\) are shown in Table 10. The time complexity of SkMC\({}_{\text{A}}\) is proportional to the number of data points \(\times\) k \(\times\) (dimension + log2k), while that of SkMC\({}_{\text{I}}\) is proportional to k \(\times\) (dimension \(\times\) number of data + log2k \(\times\) bit length). When comparing the time complexity of the proposed k-means clustering algorithm with that of the existing algorithm, the proposed k-means clustering algorithm exhibits a time complexity that is independent of the bit length. In contrast, the existing algorithm shows a time complexity that is proportional to the bit length. ### Theoretical Analysis of the Proposed Algorithm in Terms of Privacy

Assuming that an attacker does not have any information on original data items, an adversary needs a tremendous amount of time to obtain the original plaintext from a Paillier cryptosystem while using a brute force attack. This means that it is impossible to do an experiment to prove that data, queries, and access patterns are all protected. Therefore, instead of an experimental analysis, we conducted a theoretical analysis of data privacy, query privacy, and access pattern privacy to support the security analysis of the proposed algorithm. For this, we estimated the time it takes for the original data to be exposed and calculated the probability of access pattern leakage. (1) Theoretical analysis of data privacy

In C\({}_{\text{A}}\), an attacker only obtains the ciphertext of data. Because the data are protected by the Paillier cryptosystem, the security performance is measured through the time complexity of the brute force attack used to break down the Paillier cryptosystem. Our Paillier cryptosystem uses a 512-bit encryption key size. Assuming that the CPU cycle \begin{table}
\begin{tabular}{c c} \hline \hline
**k-Means Clustering Algorithm** & **Time Complexity** \\ \hline SkMC\({}_{\text{A}}\) (proposed) & O(n \(\times\) k \(\times\) (log2k + m)) \\ SkMC\({}_{\text{I}}\)[23] & O(n \(\times\) k \(\times\) (l \(\times\) log2k + m)) \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Time complexity of the k-means clustering algorithms. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Encryption Operation Protocol** & **Function** & **Time Complexity** \\ \hline ASMIN protocol & MIN operation & O(8) \(\approx\) O(1) \\ ASMIN\({}_{\text{n}}\) protocol & MIN operation among n inputs & O(8 \(\times\) log2\({}^{\text{n}}\)) \(\approx\) O(log2\({}^{\text{n}}\)) \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Time complexity of each secure protocol. is 4 GHz, the time required to decrypt the ciphertext by changing the key is as shown in Equation (12).