# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 3 Algorithms
### Improvement of Secure CWC
However, since sorting is time-consuming even for secret sharing-based MPC [38], a simpler method of determining the threshold by calculation has been proposed [30], and its effectiveness has been confirmed by experiments. On the other hand, this study focuses on consistency measure-based feature selection. As we mentioned previously, the consistency measure-based method has been confirmed to have advantages over other methods. This study proposes the first secure protocol that enables consistency measure-based feature selection in practical time. We next compare our proposal with other methods in the framework of private feature selection. A secret sharing-based MPC using the distributed secure sum is proposed [29]. In this method, it is known that statistical information about the data is leaked during the computation. The authors in [30] propose an honest-majority three-party protocol that improves on the drawback of [29]. This method is fast but requires at least two trusted parties. In addition, [30] considered both semi-honest and malicious adversaries, but in this study, the parties are assumed to be semi-honest. A feature selection using homomorphic encryption was proposed in [26]. This method uses only the additive homomorphic property in a two-party model, which limits its computational power. Therefore, statistical information about the data is leaked because partial decryption is required during communication between the parties. Moreover, this protocol has not been implemented. The recent approach by [39] is not based on cryptography and does not provide a formal privacy guarantee, and it leaks information through the disclosure of intermediate representations. Although our method is inferior to secret sharing-based MPC in terms of practical computing time, it \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dataset** & \(\mathbf{k}\) & \(\mathbf{mn}\) & **Time** & **Sorting** & **Other Tasks** \\ \hline Letter & 16 & 196 & **252.2** & 80.6 & 171.4 \\ Breast & 10 & 2464 & **312.6** & 103.1 & 209.5 \\ Cancer & 54 & 979 & **1653.5** & 836.9 & 816.6 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Running time (s) of improved algorithm for real data in UCI Machine Learning Repository. can handle feature selection from many data owners, even in situations where only they themselves can be trusted, and does not leak information during computation. In addition, we discuss future issues and prospects related to secret computation with FHE, which were not discussed in detail in this study. First, this study assumes that the data are consistent, which cannot be applied to real-world data. If the data are inconsistent, e.g., when the data are merged, there are two entries with the same feature values they but are classified into different classes, the party can ignore these entries without decoding. Since the outsourced party can perform a comparison of two integers without decoding, they can use the encrypted logical bit to change the class label of these irrelevant entries to a special value, effectively ignoring them. Next, we consider how to speed up the computation of real numbers using FHE. CKKS [40] and TFHE are the current state-of-the-art methods for computing real numbers on FHE. CKKS speeds up arithmetic operations on real numbers by converting reals to integers through scaling, performing arithmetic operations on the integers, and then converting the results back to reals. However, CKKS has the drawback that it cannot compute nonlinear functions (e.g., ReLU) or perform comparison operations, making it difficult to apply to ML. On the other hand, TFHE can evaluate comparison operations and NAND circuits, making all computations theoretically possible. Unfortunately, the runtime on TFHE has an overhead of approximately 10,000 times that on the plaintext, and thus the GPGPU-based architecture is currently being studied for speedup. Currently, the fastest implementation is around 20 times faster than algorithms on CPUs [41].