# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 3 Algorithms
### Improvement of Secure CWC
We show that, if \(\mathcal{D}\)'s advantage \(\alpha\) is not negligible, we can construct a PPT attacker \(\mathtt{Attck}\) that can break the IND-CPA security of the encryption system \(E_{\mathsf{B}}\) with a non-negligible advantage. Our attacker \(\mathtt{Attck}\) plays the IND-CPA game, exploiting an oracle \(\mathcal{O}_{\text{IND}}\) as follows:

1. \(\mathtt{Attck}\) generates \(\mathbf{B}_{1},\mathbf{B}_{2}\) with \(\|\mathbf{B}_{1}\|\leq\|\mathbf{B}_{2}\|\);
2. \(\mathtt{Attck}\) lets \(x_{1}=\|\mathbf{B}_{1}\|\) and \(x_{2}=\|\mathbf{B}_{2}\|\) and throws a query \((x_{1},x_{2})\) to \(\mathcal{O}_{\text{IND}}\);
3. \(\mathcal{O}_{\text{IND}}\) selects \(i\in\{1,2\}\) uniformly at random and sends \(c=E_{\mathsf{B}}[x_{i}-1]\) to \(\mathtt{Attck}\);
4. \(\mathtt{Attck}\) initializes \(\mathcal{D}\) by inputting \((E_{\mathsf{B}}[\|\mathbf{B}_{1}\|0],E_{\mathsf{B}}[\|\mathbf{B}_{1}\|0])\), \((E_{\mathsf{B}}[\|\mathbf{B}_{2}\|0],E_{\mathsf{B}}[\|\mathbf{B}_{2}\|0])\);
5. \(\mathtt{First}\)\(\mathtt{Query}\). \(\mathtt{Attck}\) throws to \(\mathcal{D}\) the query: \((E_{\mathsf{B}}[\|\mathbf{B}_{2}\|2],c)\), \((E_{\mathsf{B}}[\|\mathbf{B}_{2}\|2],E_{\mathsf{B}}[\mathbf{B}_{2}\|2])\);
6. If \(\mathcal{D}\) replies with \(\mathsf{A}\), \(\mathtt{Attck}\) outputs \(1\) and terminates. 7. \(\mathtt{Second}\)\(\mathtt{Query}\). \(\mathtt{Attck}\) generates \(c^{\prime}\) by adding \(E_{\mathsf{B}}[0]\) to \(c\). Note that \(\mathcal{D}_{\mathsf{B}}(c^{\prime})=\mathcal{D}_{\mathsf{B}}(c)\) holds. \(\mathtt{Attck}\) throws to \(\mathcal{D}\) the query: \((E_{\mathsf{B}}[\|\mathbf{B}_{1}\|3],E_{\mathsf{B}}[\mathbf{B}_{2}|3])\), \((E_{\mathsf{B}}[\|\mathbf{B}_{2}\|3],c^{\prime})\). 8. If \(\mathcal{D}\) replies with \(\mathtt{Sim}\), \(\mathtt{Attck}\) outputs \(1\) and terminates. 9. \(\mathtt{Attck}\) outputs \(2\). We evaluate \(\mathtt{Attck}\)'s advantage as follows. We assume \(\mathcal{D}_{\mathsf{B}}(c)=x_{1}\). The probability of this case is \(1/2\). The probability that \(\mathcal{D}\) replies with \(\mathsf{A}\) to the first query or \(\mathcal{D}\) replies with \(\mathsf{Sim}\) to the second query is

\[\frac{1}{2}+\alpha_{1}+\frac{1}{2}+\alpha_{2}-(\frac{1}{2}+\alpha_{1})(\frac{1}{ 2}+\alpha_{2})=\frac{3}{4}+\frac{\alpha}{2}-\alpha_{1}\alpha_{2}\geq\frac{3 }{4}+\frac{\alpha}{4},\]since the first and second queries are mutually independent. When assuming \(D_{B}(c)=x_{2}\), we see that \(\Pr[\mathcal{D}\text{ outputs Sim at the first query }]-1/2\) is negligible. Otherwise, \(\mathcal{D}\) can be used as an attacker to break the IND-CPA security of \(E_{B}\). Therefore, \(\Pr[\texttt{Attck}\text{ outputs }2]-1/4\) is negligible. Consequently, we have

\[\Pr[\texttt{[PERSON]'s guess is right}]\geq\frac{1}{2}\bigg{(}\frac{3}{4}+\frac{ \alpha}{4}\bigg{)}+\frac{1}{2}\cdot\frac{1}{4}=\frac{1}{2}+\frac{\alpha}{8}.\]

Since we assume that \(\alpha\) is not negligible, neither is \(\alpha/4\). ## 4 Experiments

We implemented the baseline and improved algorithms for secure CWC in C++ using the TFHE library ([[https://tfhe.github.io/tfhe](https://tfhe.github.io/tfhe)]([https://tfhe.github.io/tfhe](https://tfhe.github.io/tfhe)) (accessed on 28 January 2021)). The experiments were carried out on a machine equipped with an Intel Core i7-6567U (3.30 GHz) processor and 16 GB of RAM. In the following, \(m\) (resp. \(n\)) is the number of positive (resp. negative) data and \(k\) is the number of features. Table 6 summarizes the running time of the baseline algorithm (naive implementation of Algorithm 1 using TFHE) for random data generated for \(k\in\{10,50,100\}\) and \(mn\in\{100,500,1000\}\). The complexity analysis shows that the running time increases in proportion to \(mn\). This experimental result confirms this in real data. The table clearly shows that the sorting process is the bottleneck. Table 7 compares the running time of preprocessing in the baseline and improved algorithms. According to the results, the proposed algorithm significantly improves the bottleneck in naive CWC for secure computing.