## 3 Our Multiparty Private Set Intersection Protocol
### Security Analysis  
We employed the widely accepted simulation paradigm [40] to demonstrate the security of the new protocol. The essence of the simulation paradigm is that an actual multiparty computation protocol is considered secure if the participants do not gain more information from it than they would from an ideal protocol. We simulated the protocols for two scenarios: one where the adversary-controlled participant includes the server and another where the adversary-controlled participant does not include the server. We demonstrate that the information obtained from the actual protocol in both scenarios is computationally indistinguishable from that obtained from the ideal protocol, assuming a semi-honest adversary model. If the threshold ElGamal encryption scheme in Section 2.2.5 is secure, then the unbalanced MPSI protocol \(\prod\) in this paper is secure in the case of semi-honest adversaries. To analyze the security of our protocol, we assumed that there are \(\ell\) participants controlled by an adversary, where \(\ell<t\). In the execution of our protocol, there were \(t\) participants, and we only considered the case where \(\ell<t\). If all participants are controlled by the adversary, the analysis is meaningless. We divided the analysis into two cases: one is that the adversary controls \(\ell\) clients and the server \(P_{t}\) is not among the \(\ell\) participants controlled by the adversary; the other is that the server \(P_{t}\) is among the \(\ell\) participants controlled by the adversary, and the adversary controls \(\ell-1\) clients and the server \(P_{t}\). Scenario 1: Server \(P_{t}\) is not among the \(\ell\) participants controlled by the adversary. Suppose there are \(\ell\) participants \(P_{1},\ldots,P_{\ell}\) is controlled by the adversary, and the adversary can access the inputs of these \(\ell\) participants, as well as the intermediates generated by the computation. From the Shamir threshold secret-sharing scheme, it is clear that, when \(\ell<t\), the private key corresponding to the public key cannot be inferred from the information of the \(\ell\) participants in our protocol. We denote the participants', \(P_{1},\ldots,P_{\ell}\), views of the real protocol as \(View_{RN}^{\Pi}\), shown in Equation (21), where \(\{S_{1},\ldots,S_{\ell}\}\) denote the original datasets of the participants \(\{P_{1},\ldots,P_{\ell}\}\), \(\{ERBF_{1},\ldots,ERBF_{\ell}\}\) are the encrypted randomized Bloom filters, and finally, \(\{sh_{1},\ldots,sh_{\ell}\}\) denote the intermediate results of the computation. \[View_{RN}^{\Pi}=(\{S_{1},\ldots,S_{\ell}\},\{ERBF_{1},\ldots,ERBF_{\ell}\},\{ sh_{1},\ldots,sh_{\ell}\}) \tag{21}\]  
Construct a simulator \(Sim_{N}\) to simulate a situation where the adversary controls \(\ell\) participants, with inputs from these \(\ell\) participants, and performs the following steps:  
(1) Create an empty view \(Sim_{N}(\{S_{1},\ldots,S_{\ell}\},\bot)\), and add the sets \(\{S_{1},\ldots,S_{\ell}\}\) and the encrypted randomized Bloom filters \(\{ERBF_{1},\ldots,ERBF_{\ell}\}\) to the view. (2) Simulate the inputs of the participants \(\{P_{\ell+1},\ldots,P_{t}\}\), and create random sets \(\{S^{{}^{\prime}}_{\ell+1},\ldots,S^{{}^{\prime}}_{t-1}\}\) and a random set \(S^{{}^{\prime}}_{t}\) containing \(n_{t}\) elements. (3) Use the sets \(\{S^{{}^{\prime}}_{\ell+1},\ldots,S^{{}^{\prime}}_{t-1}\}\) to generate the Bloom filters \(\{BF^{{}^{\prime}}_{\ell+1},\ldots,BF^{{}^{\prime}}_{t-1}\}\) and the encrypted randomized Bloom filters \(\{ERBF^{{}^{\prime}}_{\ell+1},\ldots,ERBF^{{}^{\prime}}_{t-1}\}\). (4) Generate random values \(r^{{}^{\prime}}_{j}\), then compute \(w^{{}^{\prime}}_{j}\), where \(j\in\{1,2,\ldots,n_{t}\}\).