# Privacy-Preserving Feature Selection with Fully Homomorphic Encryption
## 2 Preliminaries
### Security Model
#### 2.3.2 Security of Multi-Party Computation (MPC)  
Although the discussion of this section can be extended to MPC schemes which involve more than two parties, merely for simplicity, we focus on the case where only two parties are involved. A two-party protocol is a pair \(\Pi=(\mathcal{P}_{1},\mathcal{P}_{2})\) of PPT Turing machines with input and random tapes. Let \(x_{i}\) be an input of \(\mathcal{P}_{i}\) and \(y_{i}\) be an output of \(\mathcal{P}_{i}\), respectively. We assume a _semi-honest adversary_\(\mathcal{A}\) and consider a protocol \((\mathcal{A},\mathcal{P}_{2})\), replacing \(\mathcal{P}_{1}\) in \(\Pi\) by \(\mathcal{A}\), where \(\mathcal{A}\) takes \(x_{1}\) as input and apparently follows the protocol. Let \(\texttt{REAL}_{\Pi,\mathcal{A}}(x_{1},x_{2})\) denote the random variable representing the output \((y_{1},y_{2})\) of \((\mathcal{A},\mathcal{P}_{2})\), and we define the class \(\texttt{REAL}_{\Pi,\mathcal{A}}=\{\texttt{REAL}_{\Pi,\mathcal{A}}(x_{1},x_{2 })\}_{x_{1},x_{2}}=\{y_{1},y_{2}\}_{x_{1},x_{2}}\). On the other hand, let \(\mathcal{F}\) denote the functionality that the protocol \(\Pi\) is trying to realize, i.e., \(\mathcal{F}\) is a PPT that simulates the honest \((\mathcal{P}_{1},\mathcal{P}_{2})\) so that \(\mathcal{F}(x_{1},x_{2})\equiv(\mathcal{P}_{1}(x_{1}),\mathcal{P}_{2}(x_{2}))\). Here, we assume a completely reliable third party, denoted by \(\mathcal{F}\). In this _ideal_ world, for this \(\mathcal{F}\) and any adversary \(\mathcal{B}\) acting as \(\mathcal{P}_{1}\) with input \(x_{1}^{\prime}\), possibly \(x_{1}^{\prime}\
eq x_{1}\), we define the random variable \(\texttt{IDEAL}_{\mathcal{F},\mathcal{B}}(x_{1},x_{2})=(\mathcal{B}(x_{1}, \mathcal{F}_{1}(x_{1}^{\prime},x_{2}),\mathcal{F}_{2}(x_{1}^{\prime},x_{2})))\), where \(\mathcal{F}_{i}(\cdot,\cdot)\) denotes the \(i\)-th component of the output of \(\mathcal{F}(\cdot,\cdot)\) for \(i=1,2\). Similarly, we denote the class \(\texttt{IDEAL}_{\mathcal{F},\mathcal{B}}=\{\texttt{IDEAL}_{\mathcal{F}, \mathcal{B}}(x_{1},x_{2})\}_{x_{1},x_{2}}\). Using such random variables, we define the security of protocol \(\Pi\) as follows. Definition 1: It is said that a protocol \(\Pi\) securely realizes a functionality \(\mathcal{F}\) if, for any attacker \(\mathcal{A}\) against \(\Pi\), there exists an adversary \(\mathcal{B}\), and \(\texttt{REAL}_{\Pi,\mathcal{A}}\equiv_{c}\texttt{IDEAL}_{\mathcal{F},\mathcal{B}}\) holds. The definitions stated above can be intuitively explained as follows. Exactly conforming to the protocol, a semi-honest adversary \(\mathcal{A}\) plays the role of \(\mathcal{P}_{1}\) to steal any secrets. The information sources which \(\mathcal{A}\) can take advantage of are the following three:  
1. the input tape to \(\mathcal{P}_{1}\);
2. the conversation with \(\mathcal{P}_{2}\);
3. the execution of the protocol. While the information that \(\mathcal{A}\) can obtain from the first and third sources is exactly \(x_{1}\) and \(y_{1}\), respectively, we call the information from the second source a _view_. To denote it, we use the symbol \(\texttt{View}_{\mathcal{P}_{1}}\). Since the protocol inevitably requires that \(\mathcal{A}\) obtains the information of \(x_{1}\) and \(y_{1}\), the security of the protocol questions what \(\mathcal{A}\) can obtain, in addition to what can be computationally inferred from \(x_{1}\) and \(y_{1}\). If there exists such information, its source must be \(\texttt{View}_{\mathcal{P}_{1}}\). The security criterion of _simulatability_ requires that \(\texttt{View}_{\mathcal{P}_{1}}\) can be simulated on the input of \(x_{1}\) and \(y_{1}\). In more formal terms, there exists a PPT Turing machine \(\mathsf{Sim}\) that outputs a view on the input of \(x_{1}\) and \(y_{1}\) such that the output view cannot be distinguished from \(\texttt{View}_{\mathcal{P}_{1}}\) by any PPT Turing machine. When \(\texttt{View}_{\mathcal{P}_{1}}\) is simulatable, we see that \(\mathsf{Sim}\) can generate by itself what \(\mathsf{Sim}\) can obtain from \(\texttt{View}_{\mathcal{P}_{1}}\).