## 3 Our Multiparty Private Set Intersection Protocol
### Security Analysis
\[w^{{}^{\prime}}_{j}=Enc(r^{{}^{\prime}}_{j})\times Enc(S_{t}[j]^{{}^{\prime}} )\mod\quad p \tag{22}\]  
(5) For each \(S_{t}[j]^{{}^{\prime}}\), \(j\in\{1,2,\ldots,n_{t}\}\), and each \(ERBF_{i}\) (\(i\in\{1,...,t\}\)) and each \(ERBF_{i}^{{}^{\prime}}\) (\(i\in\{\ell+1,...,t-1\}\)), compute \(\{(c^{1}_{j,i})^{{}^{\prime}},\ldots,(c^{k}_{j,i})^{{}^{\prime}}\}\) and \(c^{{}^{\prime}}_{j,i}\):  
\[c^{{}^{\prime}}_{j,i}=(c^{1}_{j,i})^{{}^{\prime}}\times\cdots\times(c^{k}_{j,i} )^{{}^{\prime}}\mod\quad p \tag{23}\](6) For \(j\in\{1,2,\ldots,n_{t}\}\), yield \(c_{j}^{{}^{\prime}}\) by a homomorphic multiplication operation on all the mapped values in the encrypted Bloom filters corresponding to \(S_{t}[j]^{{}^{\prime}}\). \[c_{j}^{{}^{\prime}}=c_{j,1}^{{}^{\prime}}\times\cdots\times c_{j,t-1}^{{}^{ \prime}}\times w_{j}^{{}^{\prime}}\mod\quad p \tag{24}\]  
(7) Compute \(sh_{i}^{{}^{\prime}}=\{sh_{1,i}^{{}^{\prime}},\ldots,sh_{n_{t},i}^{{}^{\prime }}\}\) by the shareddecryption of \(c_{j}^{{}^{\prime}}\) with private key sharings\(k_{i}\), which is expressed as Equation (25), where \(\Delta_{i}=\prod\limits_{j^{{}^{\prime}}=1,j^{{}^{\prime}}\
eq i}^{t}\frac{j^{{} ^{\prime}}}{f-i}\), \(i\in\{1,\ldots,\ell\}\), \(j\in\{1,2,\ldots,n_{t}\}\). \[sh_{j,i}^{{}^{\prime}}=(c_{j}^{{}^{\prime}})^{\Delta_{i}\cdot sk_{i}}\mod\quad p \tag{25}\]  
(8) Insert \(\{sh_{1}^{{}^{\prime}},\ldots,sh_{\ell}^{{}^{\prime}}\}\) into the view. Thus, the view of simulator \(Sim_{N}\) is:  
\[Sim_{N}(\{S_{1},\ldots,S_{\ell}\},\bot)= (\{S_{1},\ldots,S_{\ell}\},\{ERBF_{1},\ldots,ERBF_{\ell}\},\] \[\{sh_{1}^{{}^{\prime}},\ldots,sh_{\ell}^{{}^{\prime}}\}) \tag{26}\]  
Because the simulator \(Sim_{N}\) controls only \(\ell\) participants other than the server, it can only obtain the key shares of these \(\ell\) participants, and the joint computation of the data in the threshold ElGamal encryption requires at least \(t\) participants' shares of decrypted data, so the simulator \(Sim_{N}\) cannot perform the joint computation in the threshold ElGamal to obtain the final decryption result. \(View_{RN}^{\Pi}=(\{S_{1},\ldots,S_{\ell}\},\{ERBF_{1},\ldots,ERBF_{\ell}\},\{ sh_{1},\ldots,sh_{\ell}\})\) represents the view of the real protocol with participants \(P_{1},\ldots,P_{\ell}\), and \(Sim_{N}(\{S_{1},\ldots,S_{\ell}\},\bot)=(\{S_{1},\ldots,S_{\ell}\},\{ERBF_{1},\ldots,ERBF_{\ell}\},\{sh_{1}^{{}^{\prime}},\ldots,sh_{\ell}^{{}^{\prime}}\})\) represents the view of the simulator \(Sim_{N}\), where \(\{S_{1},\ldots,S_{\ell}\}\) and \(\{ERBF_{1},\ldots,ERBF_{\ell}\}\) are the same. Since the threshold ElGamal encryption algorithm and random values are used, \(\{sh_{1},\ldots,sh_{\ell}\}\) and \(\{sh_{1}^{{}^{\prime}},\ldots,sh_{\ell}^{{}^{\prime}}\}\) are computationally indistinguishable. Thus,  
\[View_{RN}^{\Pi}\simeq Sim_{N}(\{S_{1},\ldots,S_{\ell}\},\bot) \tag{27}\]  
Scenario 2: Server \(P_{t}\) is among the \(\ell\) participants controlled by the adversary. Suppose that clients \(\{P_{1},\ldots,P_{\ell-1}\}\) and server \(P_{t}\) are controlled by the adversary and the adversary can access the inputs and outputs of these \(\ell\) participants. As in case 1, it is known that, when \(\ell<t\), the private key corresponding to the public key cannot be inferred from the information of the \(\ell\) participants. In the real protocol, the views of these \(\ell\) participants are represented as \(View_{RY}^{\Pi}\), as in Equation (28), where \(\{S_{1},\ldots,S_{\ell-1}\}\) denote the input sets of clients \(\{P_{1},\ldots,P_{\ell-1}\}\), \(S_{t}\) is the original set of server \(P_{t}\), \(\{ERBF_{1},\ldots,ERBF_{\ell-1}\}\) are the encrypted randomized Bloom filters, \(\{sh_{1},\ldots,sh_{\ell-1},sh_{t}\}\) denote the intermediate results of the computation, and \(\cap\) is the final intersection obtained by server \(P_{t}\).