## 3 Our Multiparty Private Set Intersection Protocol
### Protocol Description  
This section presents our new MPSI protocol, which is based on the Bloom filter and a threshold ElGamal encryption scheme. Firstly, the protocol uses an efficient data structure called the Bloom filter, which was also utilized in [27; 28], to minimize the computation on both the clients and the server. Secondly, the protocol adopts a relatively efficient ElGamal encryption algorithm instead of the Paillier algorithm. The ElGamal encryption algorithm cannot be used to encrypt 0, but we can avoid this issue by randomizing the 0s in the Bloom filter. Thirdly, in order to be suitable for multiparty environments, a threshold ElGamal encryption scheme was designed by incorporating the concept of the Shamir threshold secret-key-sharing scheme. This scheme divides the private key into \(n\) copies for \(n\) participants and requires no less than \(t\) participants to decrypt the data accurately. Finally, we incorporated time-consuming encryptions into a preprocessing phase, which facilitates efficient execution during the online interaction stage. The protocol is shown in Figure 1, which is described as follows:  
Data input: Participant \(P_{i}\)'s dataset \(S_{i}\), \(i\in\{1,2,\ldots,t\}\). Data output: The intersection set \(S=\{S_{1}\cap S_{2}\cap\cdots\cap S_{t}\}\). Initialization:  
(1) A trusted third-party generates an ElGamal public-private key pair \((pk,sk)\) and a \((t-1)\)-th polynomial \(f(x)=sk+a_{1}x+\cdots+a_{t-1}x^{t-1}\) for \(sk\), then distributes \(pk\) to \(P_{1},...,P_{t}\) and \(sk_{i}=f(i)\) to \(P_{i}\), \(i\in\{1,2,\ldots,t\}\). (2) Then, he/she picks \(k\) hash functions \(h_{1},\ldots,h_{k}\) and sends them to participants \(P_{1},\ldots,P_{t}\). Preprocessing stage:  
(1) Each client \(P_{i}\), \(i\in\{1,2,\ldots,t-1\}\), generates a hash-mapped Bloom filter \(BF_{i}\) for its own private set \(S_{i}\), which is then randomized to obtain \(RBF_{i}\), and finally, \(ERBF_{i}\) is computed by encrypting each value in the randomized Bloom filter \(RBF_{i}\) using public key \(pk\). (2) For each \(j\in\{1,2,\ldots,n_{t}\}\), the server \(P_{t}\) generates a random number \(r_{j}\) and, then, calculates \(w_{j}=Enc(r_{j})\times Enc(S_{t}[j])\)_mod_\(p\). Online stage: The server \(P_{t}\) receives the encrypted randomized Bloom filters \(\{ERBF_{1},ERBF_{2},\ldots,ERBF_{t-1}\}\) and starts the intersection calculation. (1) i. For each of the data \(S_{t}[j]\) of the server \(P_{t}\), the hash value \(h_{u}(S_{t}[j])\) is computed, where \(j\in\{1,\ldots,n_{t}\}\), \(u\in\{1,\ldots,k\}\). Eventually, \(n_{t}\) sets of data are obtained, each with \(k\) values, as follows:  
\[ \begin{array}{cccc}\{h_{1}(S_{t}[1])&\cdots h_{u}(S_{t}[1])&\cdots h_{k}(S_{t }[1])\}\\ \vdots&\vdots&\vdots\\ \{h_{1}(S_{t}[j])&\cdots h_{u}(S_{t}[j])&\cdots h_{k}(S_{t}[j])\}\\ \vdots&\vdots&\vdots\\ \{h_{1}(S_{t}[n_{t}])&\cdots h_{u}(S_{t}[n_{t}])&\cdots h_{k}(S_{t}[n_{t}])\} \end{array}  \tag{15}\]  
ii. Substitute \(h_{u}(S_{t}[j])\) into each client's encrypted randomized Bloom filter \(ERBF_{i}\) to obtain \(c_{j,i}^{u}\), where \(i\in\{1,\ldots,t-1\}\), \(j\in\{1,\ldots,n_{t}\}\), \(u\in\{1,\ldots,k\}\) and \(c_{j,i}^{u}=ERBF_{i}[h_{u}(S_{t}[j])]\), as follows:  
\[ \begin{array}{cccc}\{\{c_{1,1}^{1},\cdots,c_{1,1}^{k}\}&\cdots\{c_{1,i}^{1},\cdots,c_{1,i}^{k}\}&\cdots\{c_{1,t-1}^{1},\cdots,c_{1,t-1}^{k}\}\}\\ \vdots&\vdots&\vdots\\ \{\{c_{j,1}^{1},\cdots,c_{j,1}^{k}\}&\cdots\{c_{j,i}^{1},\cdots,c_{j,i}^{k}\}& \cdots\{c_{j,t-1}^{1},\cdots,c_{j,t-1}^{k}\}\}\\ \vdots&\vdots&\vdots\\ \{\{c_{n_{t},1}^{1},\cdots,c_{n_{t},1}^{k}\}&\cdots\{c_{n_{t},i}^{1},\cdots,c_ {n_{t},i}^{k}\}&\cdots\{c_{n_{t},t-1}^{1},\cdots,c_{n_{t},t-1}^{k}\}\}\end{array}  \tag{16}\]  
iii. For each set of data in Equation (16), a homomorphic multiplication is performed to compute \(c_{j,i}=c_{j,i}^{1}\times\cdots\times c_{j,i}^{k}\), where \(i\in\{1,\ldots,t-1\}\), \(j\in\{1,\ldots,n_{t}\}\). The resulting data are as follows:  
\[