# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 3 Algorithms
### Improvement of Secure CWC
Hence, the simulator for B can replace them with

Figure 1: An example run of Algorithm 2. For simplicity, we omit the clock time in each ciphertext. (1): Parties A and B jointly compute \(\textbf{B}_{i}\) and \(\|\textbf{B}_{i}\|\) for each feature \(F_{i}\) (same as the baseline algorithm). (2): A securely sends \(\textbf{B}_{i^{\prime}}\) B cannot learn anything. (3): A appends encrypted index \(i\) for each \(F_{i^{\prime}}\). (4): A sorts only \((F_{i^{\prime}}\|\textbf{B}_{i^{\prime}}\|)\) by \(\|\textbf{B}_{i}\|\). (5): A sends the sorted indices with random permutation; B cannot learn anything. (6): B sends \(\textbf{B}_{i^{\prime}}\) A cannot learn anything from it. (7): A decrypts the noise and obtains the correct order of \(\textbf{B}_{i^{\prime}}\); A cannot learn anything. (8): A simulates CWC the same as the baseline. (9): Party A,B share the resulting features. * \((E_{\mathsf{B}}[\mathbf{B}_{i}+r^{\prime\prime}_{i}|6],E_{\mathsf{A}}[r^{\prime \prime}_{i}|6])\) for \(i=1,\ldots,n\) and \(r^{\prime\prime}_{i}\), which are selected uniformly at random;
* \(E_{\mathsf{B}}[\tau^{\prime}(1)|6],\ldots,E_{\mathsf{B}}[\tau^{\prime}(n)|6]\) for \(\pi^{\prime}\in\mathfrak{S}_{n}\), which is selected uniformly at random. Note that, even if an adversary knows \(\mathbf{B}_{i}\), it is computationally impossible to distinguish between \(E_{\mathsf{B}}[\mathbf{B}_{i}+r^{\prime\prime}_{i}|6]\) and \(E_{\mathsf{B}}[r^{\prime\prime}_{i}|6]\) by the IND-CPA security of the cryptosystem \(E_{\mathsf{B}}\). Next, we construct a simulator \(\mathtt{Sim}\) for the party \(\mathsf{A}\). Although what \(\mathsf{A}\) can obtain from \(\mathsf{B}\) is

\[\Big{\{}\left(E_{\mathsf{B}}[\mathbf{B}_{i\
eq(i)}+r_{i\
eq(i)}+r^{\prime}_{i \
eq(i)}|4],E_{\mathsf{A}}[r_{i\
eq(i)}+r^{\prime}_{i\
eq(i)}|4]\right)\Big{|} j=1,\ldots,n\Big{\}}\]

this is equivalent to \(\{E_{\mathsf{B}}[\mathbf{B}_{i}|5]\mid j=1,\ldots,n\}\) after decryption and permutation. On the other hand, the sequence \((i_{1},\ldots,i_{n})\) is not explicitly given to \(\mathsf{A}\), and \(\mathsf{A}\) recognizes it through the alignment between

* \((E_{\mathsf{B}}[\|\mathbf{B}_{i_{1}}\|3],\ldots,E_{\mathsf{B}}[\|\mathbf{B}_{ i_{n}}\|3])\) and
* \((E_{\mathsf{B}}[\mathbf{B}_{i_{1}}|5],\ldots,E_{\mathsf{B}}[\mathbf{B}_{i_{n}}|5])\). Therefore, we define \(\mathsf{A}\)'s view to be

\[\mathtt{View}_{\mathsf{A}}=\Big{\{}\left(E_{\mathsf{B}}[\|\mathbf{B}_{i_{1}} \|3],E_{\mathsf{B}}[\mathbf{B}_{i_{j}}\|5]\right)\Big{|}j=1,\ldots,n\Big{\}}\]

with \(\|\mathbf{B}_{i_{1}}\|\leq\cdots\leq\|\mathbf{B}_{i_{n}}\|\). On the other hand, we define the view that \(\mathtt{Sim}\) should generate as follows. While \(\mathsf{A}\) can generate \(\{E_{\mathsf{B}}[\|\mathbf{B}_{i_{j}}\|3]\mid j=1,\ldots,n\}\) with \(\|\mathbf{B}_{i_{1}}\|\leq\cdots\leq\|\mathbf{B}_{i_{2}}\|\), \(\mathsf{A}\) needs \(\mathsf{B}\)'s cooperation to generate \(\{E_{\mathsf{B}}[\mathbf{B}_{i_{j}}]\mid j=1,\ldots,n\}\). Without \(\mathsf{B}\)'s cooperation, \(\mathtt{Sim}\) selects \(\pi^{\prime}\in\mathfrak{S}_{n}\) uniformly at random, and generates its own view to be

\[\mathtt{View}_{\mathtt{Sim}}=\Big{\{}\left(E_{\mathsf{B}}[\|\mathbf{B}_{i_{j}} \|3],E_{\mathsf{B}}[\mathbf{B}_{\pi^{\prime\prime}(j)}|*]\right)\Big{|}j=1, \ldots,n\Big{\}}.\]

\(\mathtt{Sim}\) can compute \(E_{\mathsf{B}}[\mathbf{B}_{\pi^{\prime\prime}(j)}|*]\) from \(E_{\mathsf{B}}[0|*]\) and \(E_{\mathsf{B}}[\mathbf{B}_{\pi^{\prime\prime}(j)}|0]\) taking advantage of the homomorphic property of the encryption system \(E_{\mathsf{B}}\). Furthermore, we define a distinguisher \(\mathcal{D}\) as a PPT Turing machine that tries to distinguish between \(\mathtt{View}_{\mathsf{A}}\) and \(\mathtt{View}_{\mathtt{Sim}}\) on the input of \(\{(E_{\mathsf{B}}[\|\mathbf{B}_{i}\|0],E_{\mathsf{B}}[\mathbf{B}_{i}|0])\mid i =1,\ldots,n\}\). When we let \(\Pr[Y=\mathsf{A}\mid X=\mathsf{A}]=1/2+\alpha_{1}\) and \(\Pr[Y=\mathtt{Sim}\mid X=\mathtt{Sim}]=1/2+\alpha_{2}\), the advantage of \(\mathcal{D}\) is defined as \(\alpha_{1}+\alpha_{2}\).