# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 3 Algorithms
### Improvement of Secure CWC  
Sorting is a major bottleneck for private CWC. The reason for this is that pointers cannot be moved across ciphertexts. For example, consider the case of a secure integer. Let  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c c} \hline \(i\) & \(\pi(i)\) & \(\textbf{B}_{\pi(i)}\) & & & & & & & & & & & & & & & & & & & & & & & & \\ \hline
1 & 2 & \(\textbf{B}_{2}=1\) & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & \(Z_{1}=1\) & 1 & 1 & 1 & 1 the variables \(x\) and \(y\) contain integers \(a\) and \(b\), respectively. In this case, by performing the secure operation \(a<?b\), the result is obtained as \(a<?b=c\in\{0,1\}\). Using this logical bit \(c\), we can swap the values of \(x\) and \(y\) in \(O(1)\) time, satisfying \(x<y\) by the secure operation \(x\gets c\cdot a+\bar{c}\cdot b\) and \(y\leftarrow\bar{c}\cdot a+c\cdot b\). In the case of CWC, however, each integer \(i\) of feature \(F_{i}\) is associated with the bit string \(\mathbf{B}_{i}\). Since any \(x\) cannot be decrypted, we cannot swap the pointers appropriately. Therefore, the baseline algorithm swaps \(\mathbf{B}_{i}\) explicitly. As a result, the computation time for sorting increases to \(O(mnk\log^{2}k)\). Our main contribution is to improve this complexity to \(O(mnk+k\log^{2}k)\) by reducing the cost for such explicit sorting. Based on the FHE, we propose the improved secure CWC (Algorithm 2), which reduces the time complexity to \(O(mnk+k\log^{2}k)\). An example run of Algorithm 2 is illustrated in Figure 1. As shown in this example, the party A can securely sort \(k\) randomized features in \(O(k\log^{2}k)\) time using a suitable _sorting network_, and then, according to the result of sorting, A swaps each associated bit string of length \(nm\) in \(O(kmn)\) time. Following this preprocessing, the parties securely obtain minimal consistent features by decrypting the output of CWC. Finally, we have the following result. ```
1:Preprocessing:
2:Party A has \(E_{\mathbf{B}}[\mathcal{F}]=E_{\mathbf{B}}[\mathcal{F}_{1},\ldots,\mathcal{F }_{k}]\) for \(\mathcal{F}_{i}=(F_{i_{l}}\|\mathbf{B}_{i}\|,\mathbf{B}_{i})\) encrypted with party B's public key, where each datum \(x\) is encrypted at time \(0\) as \(E_{\mathbf{B}}[x|0]\). 3:Party A:
4:Generate \(r_{i}\) for \(i=1,\ldots,n\) uniformly at random. 5:Sends \((E_{\mathbf{B}}[\mathbf{B}_{i}+r_{i}|1],E_{\mathbf{A}}[r_{i}|1])\) for \(i=1,\ldots,n\). 6:Party A:
7:Calculates \(E_{\mathbf{B}}[i|2]\) for \(i=1,\ldots,n\). 8:Securly sorts \((E_{\mathbf{B}}[F_{i}|0],E_{\mathbf{B}}[\|\mathbf{B}_{i}\|0],E_{\mathbf{B}}[ i|2])\) for \(i=1,\ldots,n\) in increasing order of \(\|\mathbf{B}_{i}\|\). As a result, obtains \((E_{\mathbf{B}}[F_{i}|3],E_{\mathbf{B}}[|\mathbf{B}_{i_{j}}\|3],E_{\mathbf{B} }[i_{j}|3])\) for \(j=1,\ldots,n\). 9:Generate a permutation \(\pi\in\Theta_{n}\) uniformly at random and memorizes it. 10:Sends \((E_{\mathbf{B}}[\pi_{(1)}|3],\ldots,E_{\mathbf{B}}[i_{\pi(n)}|3])\). 11:Party B:
12:Decrypts \((i_{\pi(1)},\ldots,i_{\pi(n)})\). 13:Generate \(r^{\prime}_{i}\) for \(i=1,\ldots,n\) uniformly at random. 14:Sends \((E_{\mathbf{B}}[\mathbf{B}_{i_{\pi(j)}}+r_{i_{\pi(j)}}^{\prime}+r^{\prime}_{i _{\pi(j)}}|4],E_{\mathbf{A}}[r_{i_{\pi(j)}}+r^{\prime}_{i_{\pi(j)}}|4])\) for \(j=1,\ldots,n\). 15:Party A:
16:Decrypts \(r_{i_{\pi(j)}}+r^{\prime}_{i_{\pi(j)}}\) for \(j=1,\ldots,n\). 17:Obtains \(E_{\mathbf{B}}[\mathbf{B}_{i_{\pi(j)}}|5]\)\(j=1,\ldots,n\). 18:Obtains \(E_{\mathbf{B}}[\mathbf{B}_{i_{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{\bar{ \bar{\bar{\bar{\bar

**Theorem 3**. : _Algorithm 2 is secure under the assumption that the employed FHE is IND-CPA secure._

Proof. : We show the security by constructing simulators for parties A and B, respectively. B's view (what B can obtain from A) is the following:

* \((E_{\text{B}}[\textbf{B}_{i}+r_{i}|1],E_{\text{A}}[r_{i}|1])\) for \(i=1,\ldots,n\);
* \(E_{\text{B}}[i_{\pi(1)}|3],\ldots,E_{\text{B}}[i_{\pi(n)}|3]\). Their probability distributions are uniform and independent of each other.