# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 2 Preliminaries
### TFHE: A Faster Fully Homomorphic Encryption  
The proposed private feature selection is based on FHE. We review the TFHE [21], one of the fastest libraries for bitwise addition (this means XOR '\(\oplus\)') and bitwise multiplication (AND '\(\cdot\)') over ciphertext. On TFHE, any integer is encrypted bitwise: For \(\ell\)-bit integer \(m=(m_{1},\ldots,m_{\ell})\), we denote its bitwise encryption by \(E[m]\equiv(E[m_{1}],\ldots,E[m_{\ell}])\), for short. These bitwise operations are denoted by \(f_{\oplus}(E[x],E[y])\equiv E[x\oplus y]\) and \(f.(E[x],E[y])\equiv E[x\cdot y]\) for \(x,y\in\{0,1\}\) and the ciphertexts \(E[x]\) and \(E[y]\). The same symbol is used to represent an encrypted array. For example, when \(x\) and \(y\) are integers of length \(\ell\) and \(\ell^{\prime}\), respectively, \(E(x,y)\) denotes  
\[E[x,y]\equiv(E[x],E[y])\equiv((E[x_{1}],\ldots,E[x_{\ell}]),(E[y_{1}],\ldots, E[y_{\ell^{\prime}}])).\]  
TFHE allows all arithmetic and logical operations via the elementary operations \(E[x\oplus y]\) and \(E[x\cdot y]\). In this section, we will consider how to build the adder and comparison operations. Let \(x,y\) represent \(\ell\)-bit integers and \(x_{i},y_{i}\) represent the \(i\)-th bit of \(x,y\), respectively. Let \(c_{i}\) represent the \(i\)-th carry-in bit and \(s_{i}\) is the \(i\)-th bit of the sum \(x+y\). Then, we can obtain \(E[x+y]\) by the bitwise operations of ciphertexts using \(s_{i}=x_{i}\oplus y_{i}\oplus c_{i}\) and \(c_{i+1}=(x_{i}\oplus c_{i})\cdot(y_{i}\oplus c_{i})\oplus c_{i}\). We can construct other operations such as subtraction, multiplication, and division based on the adder. For example, \(E[x-y]\) is obtained by \(E[x+(-y)]\), where \((-y)\) is the bit complement of \(y\) obtained by \(y_{i}\oplus 1\) for all \(i\)-th bits. On the other hand, we examine the comparison. We want to obtain \(E[x<\!\!\gamma y]\) without decrypting \(x\) and \(y\) where \(x<\!\!\gamma y=1\) if \(x<y\) and \(x<\!\!\gamma y=0\) otherwise. We can obtain the logical bit for \(x<\!\!\gamma y\) as the most significant bit of \(x+(-y)\) over ciphertexts here. Similarly, for the equality test, we can compute the encrypted bit \(E[x=\!\!\gamma y]\).  
Adopting these operations of TFHE, we design a secure multi-party CWC. In this paper, we omit the details of TFHE (see, e.g., [20; 21]).  
We should note that the secrecy of TFHE definitely impacts the security of our scheme. In fact, in our two-party feature selection scheme, the party B sends his/her inputs in an encrypted form to the party A, and A performs the computation of feature selection on the encrypted inputs. If the encrypted inputs could be easily infiltrated, any ingenious devices to secure the scheme would be meaningless.  
Therefore, in designing our scheme, it was a matter of course to require our FHE cryptosystem to be IND-CPA secure. In fact, TFHE is known to be IND-CPA secure. Regarding this, we should note the following:By definition, encryption with an ID-CPA cryptosystem is probabilistic. That is, the result \(E[x]\) of encryption unpredictably differs every time the encryption is performed. For this reason, by \(E[x|t]\), we denote a ciphertext generated at time \(t\). In particular, the notation of \(E[x|*)\) means that the ciphertext has been generated at a time different from any other encryption events.
* When we consider the IND-CPA security of an FHE cryptosystem, we should note that the way in which the oracle \(\mathcal{O}\) generates \(c\) with \(D(c)=m_{b}\) is not unique. For example, the oracle may compute \(c\) from two ciphertexts of additive shares of \(m_{b}\), say \(E[r]\) and \(E[m_{b}\oplus r]\), by \(c=f_{\oplus}(E[r],E[m_{b}\oplus r])\). The IND-CPA security of an FHE cryptosystem should require that \(\mathcal{A}\) cannot guess \(b\) with effective advantage, no matter how \(c\) has been generated. This, however, holds, if the result of performing \(E[x],f_{\oplus}(E[x],E[y])\) and \(f.(E[x],E[y])\) distributes uniformly, and TFHE is known to satisfy this condition.