# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 1 Introduction
### Our Contribution and Related Work  
Table 2 summarizes the complexities of the proposed algorithms in comparison to the original CWC on plaintext. The _baseline_ is a naive algorithm that can simulate the original CWC [8] over ciphertext using TFHE operations. The bottleneck of private feature selection exists in the sorting task over ciphertext, as we mention in the related work below. Our main contribution is the improved algorithm, shown as 'improved', which significantly reduces the time complexity caused by the sorting task. We also implement the improved algorithm and demonstrate its efficiency through experiments in comparison to the baseline. There are mainly two private computation models, secret sharing-based MPC and public key-based MPC, and secret sharing-based MPC currently has an advantage. On the other hand, we focus on the convenience of FHE. Public key-based MPC can establish a simple mechanism to obtain results while keeping the learning model possessed by the server and the personal information of many data owners confidential from each other, relying only on cryptographic strength. The secret sharing-based MPC is faster but requires at least two trusted parties that do not collude with each other, which creates a different problem to cryptographic strength. Other drawbacks of public key-based MPC are its security against the chosen plaintext attack (CPA) and computational cost. TFHE is, however, computationally secure against the chosen ciphertext attack (CCA), which assumes a stronger adversary than CPA so that an attacker cannot obtain meaningful information from plaintext or ciphertext within polynomial time. In this section, we discuss related work on private feature selection as well as the benefits of our method. [PERSON] [26] et al. proposed a homomorphic encryption-based private feature selection algorithm. Their protocol allows the additive homomorphic property only, which invariably leaks statistical information about the data. [PERSON] and [PERSON] [27] proposed a different method based on the rough set theory, but their method suffers from the same limitations as [PERSON] et al., and neither method has been implemented. [PERSON] et al. [28], and [PERSON] and [PERSON] [29] have proposed MPC-based algorithms that guarantee security by decomposing the plaintext into shares, as a different approach to the private feature selection, while achieving cooperative computation. [PERSON] et al. [30] improved the MPC protocol on the aforementioned flaw and demonstrated its effectiveness through experiments. These methods avoid partial decoding under the assumption that the mean of feature values provides a good criterion for feature selection. This assumption, however, is heavily dependent on data. The most important task in general feature selection is feature value-based sorting, and CWC and its variants [7; 8; 11] demonstrated the effectiveness of sorting with the consistency measure and its superiority over other methods. On ciphertext, this study realizes the sorting-based feature selection algorithm (e.g., CWC). We focus on the learning decision tree by MPC [31] as another study that employs sorting for private ML, where the sorting is limited to the comparison of \(N\) values of fixed length in \(O(N\log^{2}N)\) time by a sorting network. In the case of CWC, however, the algorithm must sort \(N\) data points, each of which has a variable length of up to \(M\), so a naive method requires \(O(MN\log N+N\log^{2}N)\) time. Our algorithm reduces this \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Time** & **Space** \\ \hline CWC on plaintext [8] & \(O(kmn+k\log k)\) & \(O(kmn)\) \\ secure CWC (baseline) & \(O(kmn\log k+k\log^{2}k)\) & \(O(kmn)\) \\ improved & \(O(kmn+k\log^{2}k+k\log k\log mn)\) & \(O(kmn)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Time and space complexities of the baseline and improved algorithms for secure CWC, where \(k\) is the number of features and \(m\), \(n\) are the numbers of positive and negative data, respectively.