## 5 Privacy-Preserving Parallel k-Means Clustering Algorithm
### Parallel Preprocessing Phase  
In the preprocessing phase of the privacy-preserving k-means clustering algorithm that supports information protection, a parallel processing technique utilizing a thread pool is proposed. The execution process of the parallel preprocessing phase is outlined in Algorithm 5. 1. \(\mathrm{C_{A}}\) calculates the number of data points to be selected from each node based on the sampling ratio (_cnt_) (line 1). 2. \(\mathrm{C_{A}}\) initializes the initial center of the preprocessing phase (lines 2-5). In this case, as the Paillier encryption system cannot encrypt real numbers, the center point (initial_center) is represented by the sum of center points (initial_center.sum) and the count of center points (initial_center.cnt). 3. Each node selects and stores _cnt_ samples of data (i.e., E(sample_data)) (lines 7-9). 4. The thread pool performs parallel processing of the calculate_new_center procedure. The calculate_new_center procedure involves the following steps. First, each thread on \(\mathrm{C_{A}}\) calculates the distance between E(sample_data) and E(initial_center) using the SSED\({}_{\mathrm{op}}\) protocol. Then, it determines the smallest distance using the ASMIN\({}_{\mathrm{n}}\) protocol. Second, each thread on \(\mathrm{C_{A}}\) calculates the difference between E(dist_min) and each encrypted distance. After inserting random numbers and changing the order, this information is sent to \(\mathrm{C_{B}}\). Third, each thread on \(\mathrm{C_{B}}\) decrypts the received E(\(\beta\)), setting E(\(\mathrm{U_{i}}\)) to E(1) if \(\beta\) = 0; otherwise, E(\(\mathrm{U_{i}}\)) is set to E(0). \(\mathrm{C_{B}}\) then sends E(\(\mathrm{U}\)) back to \(\mathrm{C_{A}}\). Fourth, each thread on \(\mathrm{C_{A}}\) reverses E(\(\mathrm{U}\)) and stores it in E(\(\mathrm{V}\)). Fifth, each thread on \(\mathrm{C_{A}}\) performs the SM protocol on E(\(\mathrm{V_{i}}\)) and E(sample_data\({}_{i}\)). By summing the results for each dimension, it adds the sample data with a distance of E(dist_min) to the new center point E(new_center) = \(\mathtt{<}\)E(new_center.sum), E(new_center.cnt)\(>\). Sixth, the thread pool allows for the parallel computation of the new center point E(new_center) through the five steps mentioned above. 5. The SETC protocol calculates the termination condition (\(\alpha\)) between the initial center point and the new center point. Subsequently, new_center is stored in initial_center. If \(\alpha\) is 1, initial_center is returned; otherwise, clustering is re-executed from line 10 (lines 12-17). ```
Input: E(data), E(node), E(threshold) Output: E(initial_center) = \(\mathtt{<}\)E(initial_center),..., E(initial_center)> //E(initial_center) = \(\mathtt{<}\)E(initial_center;sum), E(initial_center;cnt)>, E(initial_center;sum) = \(\mathtt{<}\)E(initial_center;sum),..., E(initial_center;sum)>  CA:
01. cnt = node.cnt/sampling rate
02. for 1 \(\leq\) i \(\leq\) k
03. E(initial_center;cnt) \(\leftarrow\) E(1)
04. for 1 \(\leq\) j \(\leq\) m
05. select random number r from the random value pool
06. E(initial_center;sum) \(\leftarrow\) E(r)
07. for 1 \(\leq\) i \(\leq\) NumNode
08. for 1 \(\leq\) j \(\leq\) cnt
09. E(sample_data) \(\leftarrow\) E(node\({}_{\mathrm{i}}\).data)
10. for 1 \(\leq\) i \(\leq\) cnt
11. thread_pool_push(calculate_new_center(k, m, cnt, E(sample_data), E(initial_center),E(new_center)))
12. \(\alpha\) = SETC(E(initial_center), E(new_center), E(threshold))
13. E(initial_center) \(\leftarrow\) E(new_center)
14. if \(\alpha\) = 1
15. return E(initial_center)
16. else
17. go to line 10 in Algorithm 5



## 6 Security Analysis

### Security Analysis of Security Protocols

(1) ASMIN Protocol

In this section, the proposed ASMIN protocol is proven to be secure in the semi-honest attack model. To conduct a security analysis of the protocol, execution images based on input data were generated.