## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase
\[BFAtime(sec)=\frac{2^{512}}{4 GHz}\approx\frac{1.3\times 10^{154}}{4 GHz} \tag{12}\]

It is impossible to break down a Paillier cryptosystem because it takes about \(4.2\times 10^{146}\) years with a 512-bit key size. This means that the proposed privacy-preserving k-means clustering algorithm is secure in terms of data privacy even if the ciphertext is exposed. Figure 11 shows the time taken for a brute force attack in C\({}_{\text{A}}\) as the key size is changed. In C\({}_{\text{B}}\), an attacker only obtains plaintext data that add a random number to the original data. In the Paillier cryptosystem, because the range of the plaintext data is \(0\leq\text{m}\leq 2^{512}\), the brute force attack time in C\({}_{\text{B}}\) is the same as that in C\({}_{\text{A}}\). (2) Theoretical analysis of query privacy

In C\({}_{\text{A}}\), an attacker only obtains the ciphertext of a query. Because the query is 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. Since our Paillier cryptosystem uses a 512-bit encryption key size, the time required to decrypt the ciphertext by changing the key is as shown in Equation (10), where the CPU cycle is 4 GHz. It is impossible to break down a Paillier cryptosystem because it takes about \(4.2\times 10^{146}\) years with a 512-bit key size. This means that the proposed privacy-preserving k-means clustering algorithm is secure in terms of query privacy even if the ciphertext is exposed. The time taken in a brute force attack on C\({}_{\text{A}}\) is the same as that for data privacy in C\({}_{\text{A}}\) (Figure 11). In C\({}_{\text{B}}\), query privacy is preserved because C\({}_{\text{B}}\) does not receive the query. (3) Theoretical analysis of access pattern privacy

An access pattern describes the access sequence for a data item. In the proposed algorithm, the sequence for accessing a data item consists of accessing the leaf node of the kd-tree and accessing the data in the leaf node. In C\({}_{\text{A}}\), an attacker only obtains the ciphertext of the leaf node. Because all the leaf nodes have the same number of data items, an attacker cannot distinguish the leaf node by using the density of data items. If the kd-tree level is h, the number of leaf nodes is \(2^{\text{h}-1}\). The probability that an attacker can distinguish a node (node\({}_{\text{i}}\)) from the others, i.e., P(node\({}_{\text{i}}\)), is \(\frac{1}{2^{\text{h}-1}}\). Because node\({}_{\text{i}}\) includes the same number of data items as fanout, the probability that an attacker can distinguish a data item

Figure 11: Time taken in a brute force attack on the Paillier encryption system. from the others in node\({}_{i}\), i.e., P(node\({}_{i}\).data\({}_{j}\)), is \(\frac{1}{famout}=\frac{1}{\frac{m}{m-1}\times\frac{data}{2^{b-1}}}=\frac{2^{b-1}} {n}\). Therefore, the probability of data access pattern leakage (P\({}_{\text{APL}}\)) is as shown in Equation (13). \[P_{APL}=P(node_{i})\times P\big{(}node_{i},data_{j}\big{)}=\frac{1}{2^{h-1}} \times\frac{2^{h-1}}{n}=\frac{1}{n} \tag{13}\]

P\({}_{\text{APL}}\) is equal to the probability that an attacker distinguishes a specific data item from the others in the entire set of data items. Therefore, the proposed algorithm can preserve the access pattern privacy in C\({}_{\text{A}}\). In C\({}_{\text{B}}\), the access pattern privacy is preserved because C\({}_{\text{B}}\) does not have any data items. ### Practical Example of the Proposed k-Means Clustering Algorithm

The proposed secure k-means clustering algorithm can be used in various fields. For example, the proposed algorithm can be applied in healthcare to diagnose diseases using big data by clustering patients' symptoms. This allows for the assessment of the adaptability of the proposed algorithm in practical applications [31; 35]. Because the existing disease diagnosis system depends only on the doctor's knowledge and experience, it may cause harm to patients due to misdiagnoses.