# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 1 Introduction
### Motivation
Furthermore, modern public key encryption must be _probabilistic_: when the same message \(m\) is encrypted multiple times, the encryption algorithm produces different ciphertexts of \(E[m]\). Various homomorphic encryption schemes have been proposed to satisfy these homomorphic properties over the last two decades. The first additive homomorphic encryption was proposed by [PERSON] [15]. _Somewhat_ homomorphic encryption that allows a sufficient number of additions and a limited number of multiplications has also been proposed [16; 17; 18], and we can use these cryptosystems to compute more difficult problems, such as the inner product of two vectors. [PERSON] [19] proposed the first fully homomorphic encryption (FHE) with an unlimited number of additions and multiplications, and since then, useful libraries for fully homomorphic encryption have been developed, particularly for bitwise operations and floating-point operations. TFHE [20; 21] is known as the fastest fully homomorphic encryption that is optimized for bitwise operations. For the private feature selection problem, we use TFHE to design and implement our algorithm. In this case, we assume two _semi-honest_ parties A and B: each party complies with the protocol but tries to infer as much as possible about the secret from the information obtained. The parties have their own private data \(D_{\textsf{A}}\) and \(D_{\textsf{B}}\) and they jointly compute advantageous features for \(D_{\textsf{A}}\cup D_{\textsf{B}}\) while maintaining their privacy. The goal is to jointly compute the CWC algorithm result on \(D=D_{\textsf{A}}\cup D_{\textsf{B}}\) without revealing any other information. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(D\) & \(F_{1}\) & \(F_{2}\) & \(F_{3}\) & \(F_{4}\) & \(F_{5}\) & \(C\) \\ \hline \(x_{1}\) & 1 & 0 & 1 & 1 & 1 & 0 \\ \(x_{2}\) & 1 & 1 & 0 & 0 & 0 & 0 \\ \(x_{3}\) & 0 & 0 & 0 & 1 & 1 & 0 \\ \(x_{4}\) & 1 & 0 & 1 & 0 & 0 & 0 \\ \(x_{5}\) & 1 & 1 & 1 & 1 & 0 & 1 \\ \(x_{6}\) & 0 & 1 & 0 & 1 & 0 & 1 \\ \(x_{7}\) & 0 & 1 & 0 & 0 & 1 & 1 \\ \(x_{8}\) & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \(I(F_{i};C)\) & 0.189 & 0.189 & 0.049 & 0.000 & 0.000 & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example dataset shown in [7]. In this paper, we describe the simplest case where there are two data owners, and they perform the cooperative secure computation. More generally, there are many data owners, and they encrypt with their own public keys. Since homomorphic operations cannot be applied to two data encrypted with different public keys, a simple approach would be for the server to attempt to re-encrypt them with some common public key. However, there is no guarantee that the server or the new public key can be trusted. To solve this problem, the framework of multi-key homomorphic encryption was proposed. This allows FHE operations on data encrypted with different keys, i.e., we can extend the two-party computation model to a more general case because TFHE has the required property. Using this property, its application to the framework of oblivious neural network inference [22] has been proposed. This should be a realistic requirement, if one wants to draw some conclusions from data that are privately distributed over more than one party. Multi-party computation (MPC) can provide effective technical solutions to realize this requirement in many cases. In MPC, certain computations that essentially rely on the distributed data are performed through cooperation among the parties. In particular, fully homomorphic encryption (FHE) is one of the critical tools of MPC.