## 3 Cryptographic Preliminaries
### Threat Model and Security  
We prove the security of our proposed protocols against a semi-honest adversary by following the simulation paradigm in [21]. We consider two parties, \(\mathcal{C}\) and \(\mathcal{S}\), and jointly compute a function \(f=(f_{\mathcal{C}},f_{\mathcal{S}})\) by running a protocol \(\Pi\). A computationally bounded adversary \(\mathcal{A}\) corrupts either \(\mathcal{C}\) or \(\mathcal{S}\) at the beginning of the protocol \(\Pi\) and follows the protocol specification honestly but attempts to infer additional sensitive information (e.g., information about the input of the other party) from the observed messages during protocol execution. We now give the formal definition of security within the semi-honest model. Intuitively, the definition guarantees that everything a party observes from the received message of a legitimate execution is essentially inferred from its output (coupledwith its corresponding input). In other words, any knowledge the party acquires from the protocol execution is fundamentally implied in the output itself, leaving the party with only the output as new knowledge.  
**Definition 1**.: _A protocol \(\Pi\) between a party \(\mathcal{C}\) and a party \(\mathcal{S}\) is said to securely compute a function \(f\) in semi-honest model if it satisfies the following guarantees:_  
* _Correctness:_ _For any_ \(\mathcal{C}\)_'s input_ \(\mathbf{x}\) _and_ \(\mathcal{S}\)_'s input_ \(\mathbf{y}\)_, the probability that, at the end of the protocol,_ \(\mathcal{C}\) _outputs_ \(f_{\mathcal{C}}(\mathbf{x},\mathbf{y})\) _and_ \(\mathcal{S}\) _outputs_ \(f_{\mathcal{S}}(\mathbf{x},\mathbf{y})\) _is 1._  
* _Corrupted_ \(\mathcal{C}\)_: For_ \(\mathcal{C}\) _that follows the protocol, there exists a simulator_ \(\mathsf{Sim}_{\mathcal{C}}\) _such that_ \(\mathsf{View}_{\mathcal{C}}\approx_{c}\mathsf{Sim}_{\mathcal{C}}(\mathbf{x},f_{ \mathcal{C}}(\mathbf{x},\mathbf{y}))\) _where_ \(\mathsf{View}_{\mathcal{C}}\) _denotes the view of_ \(\mathcal{C}\) _in the execution of_ \(\Pi\) _(the view includes the_ \(\mathcal{C}\)_'s input, randomness, and the message_ \(\mathcal{C}\) _received during the protocol), and_ \(f_{\mathcal{C}}(\mathbf{x},\mathbf{y})\) _denotes the ultimate output_ \(\mathcal{C}\) _received at the end of_ \(\Pi\)_._
* _Corrupted_ \(\mathcal{S}\)_: For_ \(\mathcal{S}\) _that follows the protocol, there exists a simulator_ \(\mathsf{Sim}_{\mathcal{S}}\) _such that_ \(\mathsf{View}_{\mathcal{S}}\approx_{c}\mathsf{Sim}_{\mathcal{S}}(\mathbf{x},f_{ \mathcal{S}}(\mathbf{x},\mathbf{y}))\) _where_ \(\mathsf{View}_{\mathcal{S}}\) _denotes the view of_ \(\mathcal{S}\) _in the execution of_ \(\Pi\)_, and_ \(f_{\mathcal{S}}(\mathbf{x},\mathbf{y})\) _denotes the ultimate output_ \(\mathcal{S}\) _received at the end of_ \(\Pi\)_._  
Our framework (Section 4) is created by composing sequential secure protocols. To prove the security of our framework, we invoke modular sequential composition, as introduced in [22]. The details of the modular sequential composition are out of the scope of this work. Please refer to [22] for details. We now briefly describe the idea of modular sequential composition, which we used to prove security for our framework. The idea is that two parties \(\mathcal{C}\) and \(\mathcal{S}\) run a protocol \(\Pi\) and use calls to an ideal functionality \(\mathcal{F}\) to compute a function \(f\) (e.g., \(\mathcal{C}\) and \(\mathcal{S}\) may privately compute \(f\) by transmitting their inputs to a trusted third party and subsequently receiving the output) in \(\Pi\). If we can prove that \(\Pi\) is secure in the semi-honest model and if we have a protocol \(\rho\) that privately computes \(f\) in the same model, then we can replace the ideal calls to \(\mathcal{F}\) by the execution of \(\rho\) in \(\Pi\); the new protocol denoted \(\Pi_{\rho}\) is then secure in the semi-honest model.