# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 3 Algorithms
### Improvement of Secure CWC
We should note that the baseline and improved algorithms both compute exactly the same solution as the CWC on plaintexts. We also show the details of the improved algorithm:'sorting' means the time for sorting of the triples \((F_{i},||\mathbf{B}_{i}||,i)\) of integers; 'other task' means the time for remaining tasks, including generating/adding/subtracting random noise \(r_{i}\), moving \(\mathbf{B}_{i}\), decrypting integers, etc. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(k\) & \(mn\) & **Task 1** & **Task 2** & **Task 3** \\ \hline \multirow{3}{*}{10} & 100 & 60.3 & **835.8** & 111.9 \\  & 500 & 300.5 & **4252.4** & 558.1 \\  & 1000 & 601.4 & **8867.0** & 1114.2 \\ \hline \multirow{3}{*}{50} & 100 & 301.8 & **6292.6** & 589.3 \\  & 500 & 1502.9 & **30,364.6** & 2941.0 \\  & 1000 & 3007.0 & **62,124.6** & 5919.7 \\ \hline \multirow{3}{*}{100} & 100 & 603.7 & **16,148.5** & 1179.0 \\  & 500 & 3005.9 & **76,315.2** & 5952.5 \\ \cline{1-1}  & 1000 & 6014.1 & **154,143.5** & 11,867.0 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Running time (s) of baseline algorithm (naive secure CWC). Task 1: computing \(\mathbf{B}_{i}\)s. Task 2: sorting \(\mathbf{B}_{i}\)s. Task 3: feature selection. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(k\) & \(mn\) & **Baseline** & **Improved:** & **Sorting** & **Other Tasks** \\ \hline \multirow{3}{*}{10} & 100 & **835.8** & **203.7** & 69.4 & 134.2 \\  & 500 & **4252.4** & **286.2** & 89.5 & 196.6 \\  & 1000 & **8867.0** & **302.5** & 98.9 & 203.6 \\ \hline \multirow{3}{*}{100} & 100 & **16,148.5** & **3311.2** & 1865.5 & 1445.7 \\  & 500 & **76,315.2** & **4601.9** & 2647.7 & 1954.1 \\ \cline{1-1}  & 1000 & **154,143.5** & **4671.4** & 2660.8 & 2010.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Running time (s) of baseline and improved algorithms. Here, ‘baseline’ is same as Task 2 in Table 6 (i.e., the bottleneck); ‘improved:’ is the running time of corresponding task in the improved algorithm, where ‘sorting’ and ‘other tasks’ are the details. Table 8 displays the running time of the improved algorithm for real data available from the UCI Machine Learning Repository ([[https://archive.ics.uci.edu/ml/index.php](https://archive.ics.uci.edu/ml/index.php)]([https://archive.ics.uci.edu/ml/index.php](https://archive.ics.uci.edu/ml/index.php)) (accessed on 26 January 2022)), because, since these datasets contain more than three feature/class values, we treated them as a binary classification between one feature/class and the other. We demonstrated that the proposed algorithm works well for real-world multi-level feature selection problems. We only evaluated the running time in this experiment, but the relevance of the extracted features is guaranteed because the secure CWC algorithm produces the same solution as the original [8]. ## 5 Conclusions

On the basis of fully homomorphic encryption, we proposed a faster private feature selection algorithm that allows us to securely compute functional features from distributed private datasets. Our algorithm can simulate the original CWC algorithm, which chooses favorable features by sorting. In addition to the improvement in computational complexity, the proposed algorithm solves the private feature selection problem in practical time for a variety of real data. One of the remaining challenges is to improve sorting at a lower cost because CWC does not always require exact sorting. Then, ambiguous sorting possibly reduces the computation time, maintaining solution quality. At this time, the proposed algorithm is not applicable to real numbers for feature value. This is because TFHE [21] is not suitable for floating-point operations. Extending the TFHE library to enable secure feature selection for real-valued data is a future challenge. A well-known feature selection method is to filter features by computing _Gini impurity_ scores [14]. In this method, the optimal threshold for filtering is determined by the order of sorting of each feature.