# Multiparty Threshold Private Set Intersection Protocol with Low Communication Complexity

Authors: Xiaopeng Yu; Fagen Li; Wei Zhao; Zhengyi Dai; Dianhua Tang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Multiparty threshold private set intersection (MP-TPSI) protocol allowsn mutually untrusted parties P1,P2,…,Pn holding data sets A1,A2,…,An of size m respectively to jointly compute the intersection I=A1∩A2∩⋯∩An over all their private data sets only if the size of intersection is larger than m−t, while ensuring that no other private information of the data sets other than the intersection is revealed, where t is the threshold. In the MP-TPSI protocol, multiple parties first decide whether the size of the intersection is larger than the threshold t; then, they compute the intersection if the size of the intersection is larger than the threshold t. However, the existing MP-TPSI protocols use different forms of evaluation polynomials in the cardinality testing and intersection computing phases, so that parties need to transmit and calculate a large number of evaluation values, which leads to high communication and computational complexity. In addition, the existing MP-TPSI protocols cannot guarantee the security and the correctness of the results, that is, an adversary can know the additional information beyond the intersection, and the elements that are not in the intersection are calculated as the intersection. To solve these issues, based on the threshold fully homomorphic encryption (TFHE) and sparse polynomial interpolation, we propose an MP-TPSI protocol. In the star network topology, the theoretical communication complexity of the proposed MP-TPSI protocol depends on the threshold t and the number of parties n, not on the size of set m. Moreover, the proposed MP-TPSI protocol outperforms other related MP-TPSI protocols in terms of computational and communication overheads. Furthermore, the proposed MP-TPSI protocol tolerates up to n−1 corrupted parties in the semi-honest model, where no set of colluding parties can learn the input of an honest party in the strictest dishonest majority setting.


---

## Body

## 1. Introduction

The private set intersection (PSI) protocol [1] allows two mutually untrusted parties P1 and P2 holding data sets A1 and A2 to jointly compute the set intersection I=A1∩A2, and does not reveal anything except the intersection. PSI protocol has a large number of application scenarios, e.g., DNA matching [2], botnet detection [3], and private contact discovery [4]. Over the past few decades, in the semi-honest and malicious security model, a long line of work [5–23] has been made to effectively implement the PSI protocol. The main cryptographic primitives of the existing PSI protocols include: garbled circuits (GC) [24], oblivious transfer (OT) [25], homomorphic encryption (HE) [26] and pseudorandom functions (PRF) [27], etc. To support PSI among multiple parties, several multiparty PSI (MP-PSI) protocols [28–36] have been presented.However, in certain application scenarios, such as vertical federated learning (VFL) [37], the MP-PSI protocol mentioned above cannot satisfy the requirements. Specifically, in vertical federated machine learning, the training data is distributed among multiple parties, and each party has different features of the same object, multiple parties want to combine different features of common samples to train a better machine learning model. It is worth noting that all parties are willing to perform multiparty entity alignment only when the number of sample intersection is large. If the number of sample intersection is too small, the sample alignment will have no effect on improving the performance of the model, and the parties will not be interested in jointly computing the intersection of training samples. To meet such demands to determine whether the size of intersection is large enough before performing sample alignment, the multiparty threshold private set intersection (MP-TPSI) protocols [38–41] have been introduced, which enables n mutually distrusted parties P1,P2,…,Pn holding data sets A1,A2,…,An of size m respectively to jointly compute the intersection over all their private data sets only if the size of intersection is larger than m−t, while ensuring that no other private information of the data sets other than the intersection is revealed. The MP-TPSI protocol consists of two phases: the cardinality testing phase, where multiple parties decide whether the size of intersection is larger than a certain threshold t; and the intersection computing phase, where multiple parties calculate the intersection if the size of intersection is larger than a certain threshold t. Unfortunately, the existing MP-TPSI protocols [38–41] still have the heavy communication complexity. To solve this problem, using sparse polynomial interpolation and threshold fully homomorphic encryption (TFHE) [42], this paper proposes an MP-TPSI protocol with low communication complexity.The main contributions are as follows:(1)
Firstly, in a star network topology where the designated partyP1 can communicate with each party Pii=2,3,…,n, using an evaluation method that represents the set as a polynomial, we construct an MP-TPSI protocol based on the TFHE. To reduce the communication and computational cost, we use the same form of evaluation polynomial in the cardinality testing and intersection computing phases, which enables the parties to transmit and compute only a small number of evaluation values.(2)
Secondly, in the proposed MP-TPSI protocol, the theoretical communication complexity of the designated partyP1 and each party Pii=2,3,…,n are O (tn) and O (t), respectively, which are smaller than the existing MP-TPSI protocols [38–40] and TAHE-based MP-TPSI protocol [41]. In contrast to conventional MP-PSI protocols [28–36], the communication complexity of the proposed MP-TPSI protocol only depends on the threshold t and the number of parties n, not on the size of set m.(3)
Finally, we evaluate the proposed MP-TPSI protocol and the related TFHE-based MP-TPSI protocol [41] under n∈2,3,⋯,8, m∈210,211,212, and t∈29,210,211. The experimental results demonstrate that, compared with the TFHE-based MP-TPSI protocol [41], the computational and communication costs in the proposed MP-TPSI protocol are reduced by nearly 92.0%–97.3% and 67.2%–67.3%, respectively. The security analysis illustrates that the proposed MP-TPSI protocol can achieve semi-honest security in the dishonest majority model where up to n−1 parties can be allowed to corrupt.The remainder of the study is organized as follows. We introduce some related works in Section2. In Section 3, we review some preliminaries. In Section 4, our protocol is described in detail. The performance evaluation of our protocol is presented in Section 5. The security analysis of our protocol is shown in Section 6. Finally, we conclude in Section 7.


## 2. Related Works

Some works [28–36, 38–41] closely related to this study are introduced in this section. For ease of description, we summarize the theoretical communication complexity of [28–36, 38–41] in Table 1.Table 1
Theoretical communication complexity comparison.
ProtocolsCommunication complexitySecurity modelDesignated partyP1PartyPi (i=2,3,…,n)[28]OmnOmwSemi-honest[29]OmnOmSemi-honest[30]OmnOmSemi-honest[30]Om+mlogm+nnOm+mlogm+nMalicious[31]OmnOmnSemi-honest[31]OmnOmAugmented-semi-honest[32]OmnhOmnhSemi-honest[32]OmnhOmhAugmented-semi-honest[33]On2+mnOmSemi-honest[34]OmnOmqSemi-honest[35]OmnOmkSemi-honest[36]OmnOmSemi-honest[38]Ot2nOt2Semi-honest[39]OmnwOmnwSemi-honest (t−PSI0)[39]OtmncOtmncSemi-honestt−PSI[40]Ot2nOt2Semi-honest[41]Ot2nOt2Semi-honest (TAHE-based)[41]O (tn)OtSemi-honest (TFHE-based)By representing the set as a polynomial, based on threshold additive HE (TAHE) that can be realized from Paillier encryption [43], Kissner et al. [28] implement the PSI operations in multiparty setting. Leveraging the Bloom filters (BF) [44] and exponential additive HE (AHE) [45], Miyaji et al. [29] presented a scalable MP-PSI protocol, they set a dealer to decrease the computational complexity of the parties. In a star network topology, based on the two-party protocol of [46], Hazay et al. [30] described the MP-PSI protocols in semi-honest and malicious settings. Kolesnikov et al. [31] proposed a method called oblivious programmable PRF (OPPRF), designed MP-PSI protocols based OPPRF in the semi-honest model, and further optimized it to the augmented-semi-honest model. Inbar et al. [32] extend the PSI construction of [12] to multiparty setting, and described the MP-PSI protocols for semi-honest and augmented-semi-honest settings in a star network topology. Setting the elements of its own set to the roots of a polynomial, based on the OLE, in a star network topology, Ghosh et al. [33] presented an approach to achieving secure MP-PSI. Lu et al. [34] proposed an MP-PSI protocol for VFL in a star network topology, which is able to compute the intersection in the event that some of the parties are offline. Combining of the star and path communication patterns which in the former, one party at the center can communicate with all other parties, and in the latter, each party can communicate with neighboring parties, Kavousi et al. [35] presented an efficient protocol for MP-PSI using oblivious PRF (OPRF). Based on the TAHE schemes and BF, in a star network topology, Bay et al. [36] proposed an MP-PSI protocol, which is secure in the semi-honest model. However, the communication and computational complexity of the MPSI protocol [28–36] mentioned above depend on the size of the input data set, which directly becomes a basic obstacle to efficiency.Based on the AHE, Ghosh et al. [38] introduced an MP-TPSI protocol, which is the first MP-TPSI protocol with communication complexity that depend on threshold t, not on the set size m. However, Abadi et al. [47] pointed out that [38]'s protocol is not secure because an adversary can learn other information about the sets of honest parties beyond the intersection. Using the OPRF and hash function, Mahdavi et al. [39] introduced two constructions for the MP-TPSI protocol, namely t−PSI0 and t−PSI, but the computational complexity is exponential in the threshold t, and thus have a poor performance. By employing the TAHE from Elgamal encryption [48] and Paillier encryption [43], Branco et al. [40] developed a protocol to securely compute linear algebra functions and proposed an MP-TPSI in a star network topology. Badrinarayanan et al. [41] pointed out that [38]'s protocol has a subtle issue, that is, elements that are not in the intersection may also be computed as elements in the intersection. To solve this issue, in the star network topology, they proposed the TAHE-based MP-TPSI and TFHE-based MP-TPSI protocols. However, their TFHE-based MP-TPSI protocol uses different forms of evaluation polynomials in the cardinality testing and intersection computing phases, which requires the transmission and calculation of a large number of evaluation values, and brings to heavy communication and computational cost.


## 3. Preliminaries

### 3.1. Notations

For ease of reading, the definitions of symbols in the proposed MP-TPSI protocol are described in Table2.Table 2
The definitions of the symbols.
SymbolsDefinitionsPiThei-th partyAiThe data set of partyPiIThe intersection ofA1,A2,⋯,AnIThe size of the intersectionInThe number of partiesmThe size of each setAitThe thresholdxThe ciphertext of plaintextxxiThe partial decryption ciphertext ofxλThe security parameterneglλThe negligible function onλ


### 3.2. Security Model

We define the security of the proposed MP-TPSI protocol in universal composability (UC) framework [49]. Considering a multiparty protocol Π that realizes the ideal functionality ℱ, we can define the security of the protocol Π in the ideal/real world.In an ideal world: n parties transmit all inputs to ℱ, and receive the computation result. Simulator S is regarded as an adversary in an ideal world, has complete control of the parties that are corrupted, and simulates Z's view of on the execution of the real protocol.In a real world: n parties perform Π, Π is permitted to call an ideal functionality G. Environment Z selects all inputs of n parties, simulates anything outside Π. Z can represent the adversary and corrupt any subset of the parties.AssumingIdealZ,S,ℱ and RealZ,Π,G are the output of Z in the ideal and real world, respectively, we define Π securely realizes ℱ, if there is a S so that for any Z we have(1)PrIdealZ,S,ℱ=1−PrRealZ,Π,G=1≤neglλ.


### 3.3. The definition of Threshold Fully Homomorphic Encryption

A TFHE scheme [42] consists of the distributed setup (TFHE.DisSet), encryption (TFHE.Enc), addition (TFHE.Add), multiplication (TFHE.Mul), partial decryption (TFHE.PartDec), and combination (TFHE.Comb) algorithms.TFHE.DisSet1λ,i⟶pk,ski: On input λ and party’s number i, TFHE.DisSet algorithm returns the secret key share ski and public key pk for the party Pi.TFHE.Encpk,x⟶x: On input pk and plaintext x, TFHE.Enc algorithm returns the ciphertext x.TFHE.Addx1,x2⟶x1+x2: On input the ciphertexts x1 and x2, TFHE.Add algorithm outputs the ciphertext x1+x2.TFHE.Mulx1,x2⟶x1∗x2: On input the ciphertexts x1 and x2, TFHE.Mul algorithm outputs the ciphertext x1∗x2.TFHE.PartDecski,y⟶yi: On input the secret key share ski and ciphertext y, TFHE.PartDec algorithm outputs the partial decryption ciphertext yi.TFHE.Comby1,y2,⋯,yn⟶y: On input a set of partial decryption ciphertexts y1,y2,⋯,yn, TFHE.Comb algorithm outputs the plaintext y=y1+y2+⋯+yn.


### 3.4. Functionality

Ideal functionalityFMP−TPSI−CTfor MP-TPSI cardinality testing: In a star network topology, for n parties P1,P2,⋯,Pn holding data sets A1,A2,⋯,An of equal size m, respectively, the goal of the ℱMP−TPSI−CT is to execute a multiparty protocol Π, at the end of Π, every party Pi can know whether if its data set Ai and intersection I=A1∩A2∩⋯∩An differ by at most t, namely I≥m−t. The formal definition of ℱMP−TPSI−CT is depicted in Figure 1.Figure 1
Ideal functionalityℱMP−TPSI−CT for MP-TPSI cardinality testing.Ideal functionalityFMP−TPSI−Cfor MP-TPSI computing: In a star network topology, for n parties P1,P2,⋯,Pn holding data sets A1,A2,⋯,An of equal size m, respectively, the goal of the ℱMP−TPSI−C is to execute an multiparty protocol Π, at the end of Π, either every party Pi outputs an intersection I=A1∩A2∩⋯∩An or outputs none ⊥. The formal definition of ℱMP−TPSI−C is described Figure 2.Figure 2
Ideal functionalityℱMP−TPSI−C for MP-TPSI computing.


## 3.1. Notations

For ease of reading, the definitions of symbols in the proposed MP-TPSI protocol are described in Table2.Table 2
The definitions of the symbols.
SymbolsDefinitionsPiThei-th partyAiThe data set of partyPiIThe intersection ofA1,A2,⋯,AnIThe size of the intersectionInThe number of partiesmThe size of each setAitThe thresholdxThe ciphertext of plaintextxxiThe partial decryption ciphertext ofxλThe security parameterneglλThe negligible function onλ


## 3.2. Security Model

We define the security of the proposed MP-TPSI protocol in universal composability (UC) framework [49]. Considering a multiparty protocol Π that realizes the ideal functionality ℱ, we can define the security of the protocol Π in the ideal/real world.In an ideal world: n parties transmit all inputs to ℱ, and receive the computation result. Simulator S is regarded as an adversary in an ideal world, has complete control of the parties that are corrupted, and simulates Z's view of on the execution of the real protocol.In a real world: n parties perform Π, Π is permitted to call an ideal functionality G. Environment Z selects all inputs of n parties, simulates anything outside Π. Z can represent the adversary and corrupt any subset of the parties.AssumingIdealZ,S,ℱ and RealZ,Π,G are the output of Z in the ideal and real world, respectively, we define Π securely realizes ℱ, if there is a S so that for any Z we have(1)PrIdealZ,S,ℱ=1−PrRealZ,Π,G=1≤neglλ.


## 3.3. The definition of Threshold Fully Homomorphic Encryption

A TFHE scheme [42] consists of the distributed setup (TFHE.DisSet), encryption (TFHE.Enc), addition (TFHE.Add), multiplication (TFHE.Mul), partial decryption (TFHE.PartDec), and combination (TFHE.Comb) algorithms.TFHE.DisSet1λ,i⟶pk,ski: On input λ and party’s number i, TFHE.DisSet algorithm returns the secret key share ski and public key pk for the party Pi.TFHE.Encpk,x⟶x: On input pk and plaintext x, TFHE.Enc algorithm returns the ciphertext x.TFHE.Addx1,x2⟶x1+x2: On input the ciphertexts x1 and x2, TFHE.Add algorithm outputs the ciphertext x1+x2.TFHE.Mulx1,x2⟶x1∗x2: On input the ciphertexts x1 and x2, TFHE.Mul algorithm outputs the ciphertext x1∗x2.TFHE.PartDecski,y⟶yi: On input the secret key share ski and ciphertext y, TFHE.PartDec algorithm outputs the partial decryption ciphertext yi.TFHE.Comby1,y2,⋯,yn⟶y: On input a set of partial decryption ciphertexts y1,y2,⋯,yn, TFHE.Comb algorithm outputs the plaintext y=y1+y2+⋯+yn.


## 3.4. Functionality

Ideal functionalityFMP−TPSI−CTfor MP-TPSI cardinality testing: In a star network topology, for n parties P1,P2,⋯,Pn holding data sets A1,A2,⋯,An of equal size m, respectively, the goal of the ℱMP−TPSI−CT is to execute a multiparty protocol Π, at the end of Π, every party Pi can know whether if its data set Ai and intersection I=A1∩A2∩⋯∩An differ by at most t, namely I≥m−t. The formal definition of ℱMP−TPSI−CT is depicted in Figure 1.Figure 1
Ideal functionalityℱMP−TPSI−CT for MP-TPSI cardinality testing.Ideal functionalityFMP−TPSI−Cfor MP-TPSI computing: In a star network topology, for n parties P1,P2,⋯,Pn holding data sets A1,A2,⋯,An of equal size m, respectively, the goal of the ℱMP−TPSI−C is to execute an multiparty protocol Π, at the end of Π, either every party Pi outputs an intersection I=A1∩A2∩⋯∩An or outputs none ⊥. The formal definition of ℱMP−TPSI−C is described Figure 2.Figure 2
Ideal functionalityℱMP−TPSI−C for MP-TPSI computing.


## 4. Multiparty Threshold Private Set Intersection

In a star network topology where partyP1 to be the designated party that can communicate with other parties P2,P3,⋯,Pn, suppose n, parties P1,P2,⋯,Pn with input sets A1,A2,⋯,An of equal size m, respectively, based on TFHE with distributed setup, we propose an MP-TPSI protocol, in which each party Pi can compute the intersection I=A1∩A2∩⋯∩An only if I≥m−t. The proposed MP-TPSI protocol is formally described in Figure 3.Figure 3
Multiparty threshold private set intersection.


### 4.1. Correctness

MP-TPSI cardinality testing: First we consider the situation where the MP-TPSI cardinality testing outputs true. Based on the correctness of the TFHE, we only need to illustrate b=0 only if Ai/I≤t for any i=1,2,⋯,n. Observe the rational interpolation polynomial(2)y1x=aA1x+aA2x+⋯+aAnxaA1x=aA1\Ix+aA2\Ix+⋯+aAn\IxaA1\Ix=∑i=1nri⋅∏ai,j∈Ai\Ix−ai,jr1⋅∏a1,j∈A1\Ix−a1,j,we can see that the degree of numerator aA1\Ix+aA2\Ix+⋯+aAn\Ix and denominator aA1\Ix is at most t, and the degree of rational polynomial y1x is at most 2t. Therefore, y1x can be computed from a total of 2t+1 evaluation values, and the equation y1x|x=z=fz/aA1z=aA1z+aA2z+⋯+aAnz/aA1z holds. Next, we consider the situation where the MP-TPSI cardinality testing outputs false. From the above equation, we can observe that gcdaA1\Ix+aA2\Ix+⋯+aAn\Ix,aA1\Ix=1. Since Ai\I≥t+1, the degree of aA1\Ix+aA2\Ix+⋯+aAn\Ix and aA1\Ix are at least t+1, the degree of rational polynomial y1x is at least 2t+3, and hence calculating y1x requires at least 2t+3 evaluation values. However, there are only 2t+1 evaluation values in the MP-TPSI cardinality testing. Therefore, the equation y1x|x=z=fz/aA1z=aA1z+aA2z+⋯+aAnz/aA1z does not hold. From the above analysis, we are able to obtain that the MP-TPSI cardinality testing is correct.MP-TPSI computing: If Ai\I>t for any i=1,2,⋯,n, the MP-TPSI computing quits after the MP-TPSI cardinality testing. If |Ai\I|≤t, observe the rational interpolation polynomial(3)yix=aA1x+aA2x+⋯+aAnxaAix=aA1\Ix+aA2\Ix+⋯+aAn\IxaAi\Ix=∑i=1nri⋅∏ai,j∈Ai\Ix−ai,jri⋅∏a1,j∈A1\Ix−a1,j,we can see that the degree of numerator aA1\Ix+aA2\Ix+⋯+aAn\Ix and denominator aAi\Ix are at most t, and hence yix is a random polynomial with degree at most 2t+1. Since gcdaA1\Ix+aA2\Ix+⋯+aAn\Ix,aAi\Ix=1, no other terms will be canceled out in the numerator and denominator. Therefore, based on the correctness of the TFHE, each party Pi is able to interpolate the rational random polynomial yix by utilizing 2t+1 evaluation values. Finally, each Pi can easily compute intersection I from the set Ai\I of the roots of the denominator of polynomial yix.


## 4.1. Correctness

MP-TPSI cardinality testing: First we consider the situation where the MP-TPSI cardinality testing outputs true. Based on the correctness of the TFHE, we only need to illustrate b=0 only if Ai/I≤t for any i=1,2,⋯,n. Observe the rational interpolation polynomial(2)y1x=aA1x+aA2x+⋯+aAnxaA1x=aA1\Ix+aA2\Ix+⋯+aAn\IxaA1\Ix=∑i=1nri⋅∏ai,j∈Ai\Ix−ai,jr1⋅∏a1,j∈A1\Ix−a1,j,we can see that the degree of numerator aA1\Ix+aA2\Ix+⋯+aAn\Ix and denominator aA1\Ix is at most t, and the degree of rational polynomial y1x is at most 2t. Therefore, y1x can be computed from a total of 2t+1 evaluation values, and the equation y1x|x=z=fz/aA1z=aA1z+aA2z+⋯+aAnz/aA1z holds. Next, we consider the situation where the MP-TPSI cardinality testing outputs false. From the above equation, we can observe that gcdaA1\Ix+aA2\Ix+⋯+aAn\Ix,aA1\Ix=1. Since Ai\I≥t+1, the degree of aA1\Ix+aA2\Ix+⋯+aAn\Ix and aA1\Ix are at least t+1, the degree of rational polynomial y1x is at least 2t+3, and hence calculating y1x requires at least 2t+3 evaluation values. However, there are only 2t+1 evaluation values in the MP-TPSI cardinality testing. Therefore, the equation y1x|x=z=fz/aA1z=aA1z+aA2z+⋯+aAnz/aA1z does not hold. From the above analysis, we are able to obtain that the MP-TPSI cardinality testing is correct.MP-TPSI computing: If Ai\I>t for any i=1,2,⋯,n, the MP-TPSI computing quits after the MP-TPSI cardinality testing. If |Ai\I|≤t, observe the rational interpolation polynomial(3)yix=aA1x+aA2x+⋯+aAnxaAix=aA1\Ix+aA2\Ix+⋯+aAn\IxaAi\Ix=∑i=1nri⋅∏ai,j∈Ai\Ix−ai,jri⋅∏a1,j∈A1\Ix−a1,j,we can see that the degree of numerator aA1\Ix+aA2\Ix+⋯+aAn\Ix and denominator aAi\Ix are at most t, and hence yix is a random polynomial with degree at most 2t+1. Since gcdaA1\Ix+aA2\Ix+⋯+aAn\Ix,aAi\Ix=1, no other terms will be canceled out in the numerator and denominator. Therefore, based on the correctness of the TFHE, each party Pi is able to interpolate the rational random polynomial yix by utilizing 2t+1 evaluation values. Finally, each Pi can easily compute intersection I from the set Ai\I of the roots of the denominator of polynomial yix.


## 5. Performance Evaluation

The proposed MP-TPSI protocol is an improvement of the TFHE-based MP-TPSI protocol [41], so we evaluate the proposed MP-TPSI protocol and the TFHE-based MP-TPSI protocol [41]. In the star network topology, we implement the proposed MP-TPSI protocol on top of the lattice-based multiparty HE library Lattigo [50] that implements the full-RNS BFV scheme [51] and its multiparty versions in Go. We run all experiments on a 32-core Intel Xeon CPU with 256 GB of RAM. For the multiparty BFV scheme in Go, to ensure 128 bits security, we choose that polynomial-degree is 4096, ciphertext-modulus is 109 bits, and plaintext-modulus is 17 bits. For ease of comparison, we perform all experiments on the same machine with 16 threads, emulate the networks latency by utilizing the Linux tc command, and consider a LAN with a 10 Gbps throughput and 0.2 ms round-trip time. It is worth noting that the authors of [41] did not implement their TFHE-based MP-TPSI protocol, for a fair comparison, we implement the TFHE-based MP-TPSI protocol [41] in the same experimental environment.


### 5.1. Analysis of Computational Cost

The computational cost of the proposed MP-TPSI protocol and the TFHE-based MP-TPSI protocol [41] under n∈2,3,⋯,8, m∈210,211,212, and t∈29,210,211 are shown in Table 3. All running times are shown as an average of 10 experiments.Table 3
Comparison of computational cost.
Set sizeThresholdProtocolsComputation cost (seconds)n=2n=3n=4n=5n=6n=7n=8m=210t=29[41]395.48410.51437.93489.15555.43641.92792.88Ours29.9732.1235.1838.6042.1745.6749.43m=211t=210[41]919.64964.691011.611095.701277.491478.641821.63Ours49.5452.0955.3560.9175.0380.1286.56m=212t=211[41]2815.103077.363307.963593.904177.394864.736011.38Ours92.23100.14108.83121.60134.56147.71161.87As shown in Figure4, compared with the TFHE-based MP-TPSI protocol [41], the proposed MP-TPSI protocol has a better performance in terms of computational cost. Specifically, under m=210 and t=29, for n∈2,3,⋯,8, the computational cost in the proposed MP-TPSI protocol is almost reduced by 92.4%, 92.2%, 92.0%, 92.1%, 92.4%, 92.9%, and 93.8%, respectively, compared with the TFHE-based MP-TPSI protocol [41]. Under m=211 and t=210, with regard to n∈2,3,⋯,8, the proposed MP-TPSI protocol decreases by almost 94.6%, 94.6%, 94.5%, 94.4%, 94.1%, 94.6% and 95.2% respectively in computational cost in comparison with the TFHE-based MP-TPSI protocol [41]. Under m=212 and t=211, regarding n∈2,3,⋯,8, the proposed MP-TPSI protocol reduces the computational cost by almost 96.7%, 96.7%, 96.7%, 96.6%, 96.8%, 97.0%, and 97.3%, respectively, than the TFHE-based MP-TPSI protocol [41].Figure 4
Comparison of computational cost.
(a)(b)(c)


### 5.2. Analysis of Communication Cost

In a star network topology, according to the selected parameters in Section5.1, we can obtain the size of ciphertext, partial decryption ciphertext and plaintext are x=2×4096×109 bits, xi=4096×109 bits, and x=4096×17 bits, respectively. The comparison of communication cost between the proposed MP-TPSI protocol and the TFHE-based MP-TPSI protocol [41] are shown in Table 4.Table 4
Comparison of communication costs.
Set sizeThresholdProtocolsCommunication cost (GB)n=2n=3n=4n=5n=6n=7n=8m=210t=29[41]0.841.682.523.364.205.045.88Ours0.270.550.821.101.371.651.92m=211t=210[41]1.683.355.036.718.3910.0611.74Ours0.551.101.652.202.753.303.85m=212t=211[41]3.356.7010.0613.4116.7620.1123.46Ours1.102.203.294.395.496.597.69For the TFHE-based MP-TPSI protocol [41], n parties first run the MPSI cardinality testing. Each Pii=2,3,⋯,n sends 2t+3 ciphertexts ei,j|j∈2t+3 and one ciphertext ei′ to P1. P1 returns one ciphertext b to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends one partial decryption ciphertext b:ski to P1. P1 returns one plaintext b to each Pii=2,3,⋯,n. If the MP-TPSI cardinality testing passes, n parties then run the MP-TPSI computing. Each Pii=2,3,⋯,n sends 3t+4 ciphertexts Rij|j∈3t+4 to P1. P1 returns 3t+4 ciphertexts ei,j|j∈3t+3 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 3t+4 ciphertexts vi,j|j∈3t+3 to P1. P1 returns 3t+4 ciphertexts vj|j∈3t+3 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 3t+4 partial decryption ciphertexts vj:ski|j∈3t+4 to P1. P1 returns 3t+4 plaintexts vj|j∈3t+3 to each Pii=2,3,⋯,n. Therefore, the communication cost of the designated party P1 is n−1×6t+9×x+n−1×3t+5×x (namely, O (tn)), the communication cost of each Pii=2,3,⋯,n is 8t+12×x+3t+5×xi (namely, O (t)), and the total communication cost is n−1×14t+21×x+3t+5×xi+3t+5×x bits.For our MP-TPSI protocol,n parties first run the MP-TPSI cardinality testing. Each Pii=2,3,⋯,n sends 2t+1 ciphertexts aAik|k∈2t+1 and one ciphertext aAiz to P1. P1 returns one ciphertext b to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends one partial decryption ciphertext bi to P1. P1 returns one plaintext b to each Pii=2,3,⋯,n. If the MP-TPSI cardinality testing passes, n parties then run the MP-TPSI computing. P1 returns 2t+1 ciphertexts fk|k∈2t+1 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 2t+1 partial decryption ciphertexts fki|k∈2t+1 to P1. P1 returns 2t+1 plaintexts fk|k∈2t+1 to each Pii=2,3,⋯,n. Therefore, the communication cost of the designated party P1 is n−1×2t+9×x+n−1×2t+2×x (namely, O (tn)), the communication cost of each Pii=2,3,⋯,n is 2t+2×x+2t+2×xi (namely, O (t)), the total communication cost is n−1×4t+4×x+2t+2×xi+2t+2×x bits.As shown in Figure5, compared with the TFHE-based MP-TPSI protocol [41], the proposed MP-TPSI protocol has a better performance in terms of communication cost. Specifically, when comparing with m=210 and t=29, for n∈2,3,⋯,8 parties, the communication cost in the proposed MP-TPSI protocol is almost reduced by 67.3%, 67.3%, 67.3%, 67.3%, 67.3%, 67.3%, and 67.3%, respectively, compared with the TFHE-based MP-TPSI protocol [41]. When comparing with m=211 and t=210, with regard to n∈2,3,⋯,8 parties, the proposed MP-TPSI protocol decreases by almost 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, and 67.2%, respectively, in communication cost in comparison with the TFHE-based MP-TPSI protocol [41]. When comparing with m=212 and t=211, regarding n∈2,3,⋯,8 parties, the proposed MP-TPSI protocol reduces the communication cost by almost 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, 67.2% and 67.2% respectively than the TFHE-based MP-TPSI protocol [41].Figure 5
Comparison of communication cost.
(a)(b)(c)


## 5.1. Analysis of Computational Cost

The computational cost of the proposed MP-TPSI protocol and the TFHE-based MP-TPSI protocol [41] under n∈2,3,⋯,8, m∈210,211,212, and t∈29,210,211 are shown in Table 3. All running times are shown as an average of 10 experiments.Table 3
Comparison of computational cost.
Set sizeThresholdProtocolsComputation cost (seconds)n=2n=3n=4n=5n=6n=7n=8m=210t=29[41]395.48410.51437.93489.15555.43641.92792.88Ours29.9732.1235.1838.6042.1745.6749.43m=211t=210[41]919.64964.691011.611095.701277.491478.641821.63Ours49.5452.0955.3560.9175.0380.1286.56m=212t=211[41]2815.103077.363307.963593.904177.394864.736011.38Ours92.23100.14108.83121.60134.56147.71161.87As shown in Figure4, compared with the TFHE-based MP-TPSI protocol [41], the proposed MP-TPSI protocol has a better performance in terms of computational cost. Specifically, under m=210 and t=29, for n∈2,3,⋯,8, the computational cost in the proposed MP-TPSI protocol is almost reduced by 92.4%, 92.2%, 92.0%, 92.1%, 92.4%, 92.9%, and 93.8%, respectively, compared with the TFHE-based MP-TPSI protocol [41]. Under m=211 and t=210, with regard to n∈2,3,⋯,8, the proposed MP-TPSI protocol decreases by almost 94.6%, 94.6%, 94.5%, 94.4%, 94.1%, 94.6% and 95.2% respectively in computational cost in comparison with the TFHE-based MP-TPSI protocol [41]. Under m=212 and t=211, regarding n∈2,3,⋯,8, the proposed MP-TPSI protocol reduces the computational cost by almost 96.7%, 96.7%, 96.7%, 96.6%, 96.8%, 97.0%, and 97.3%, respectively, than the TFHE-based MP-TPSI protocol [41].Figure 4
Comparison of computational cost.
(a)(b)(c)


## 5.2. Analysis of Communication Cost

In a star network topology, according to the selected parameters in Section5.1, we can obtain the size of ciphertext, partial decryption ciphertext and plaintext are x=2×4096×109 bits, xi=4096×109 bits, and x=4096×17 bits, respectively. The comparison of communication cost between the proposed MP-TPSI protocol and the TFHE-based MP-TPSI protocol [41] are shown in Table 4.Table 4
Comparison of communication costs.
Set sizeThresholdProtocolsCommunication cost (GB)n=2n=3n=4n=5n=6n=7n=8m=210t=29[41]0.841.682.523.364.205.045.88Ours0.270.550.821.101.371.651.92m=211t=210[41]1.683.355.036.718.3910.0611.74Ours0.551.101.652.202.753.303.85m=212t=211[41]3.356.7010.0613.4116.7620.1123.46Ours1.102.203.294.395.496.597.69For the TFHE-based MP-TPSI protocol [41], n parties first run the MPSI cardinality testing. Each Pii=2,3,⋯,n sends 2t+3 ciphertexts ei,j|j∈2t+3 and one ciphertext ei′ to P1. P1 returns one ciphertext b to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends one partial decryption ciphertext b:ski to P1. P1 returns one plaintext b to each Pii=2,3,⋯,n. If the MP-TPSI cardinality testing passes, n parties then run the MP-TPSI computing. Each Pii=2,3,⋯,n sends 3t+4 ciphertexts Rij|j∈3t+4 to P1. P1 returns 3t+4 ciphertexts ei,j|j∈3t+3 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 3t+4 ciphertexts vi,j|j∈3t+3 to P1. P1 returns 3t+4 ciphertexts vj|j∈3t+3 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 3t+4 partial decryption ciphertexts vj:ski|j∈3t+4 to P1. P1 returns 3t+4 plaintexts vj|j∈3t+3 to each Pii=2,3,⋯,n. Therefore, the communication cost of the designated party P1 is n−1×6t+9×x+n−1×3t+5×x (namely, O (tn)), the communication cost of each Pii=2,3,⋯,n is 8t+12×x+3t+5×xi (namely, O (t)), and the total communication cost is n−1×14t+21×x+3t+5×xi+3t+5×x bits.For our MP-TPSI protocol,n parties first run the MP-TPSI cardinality testing. Each Pii=2,3,⋯,n sends 2t+1 ciphertexts aAik|k∈2t+1 and one ciphertext aAiz to P1. P1 returns one ciphertext b to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends one partial decryption ciphertext bi to P1. P1 returns one plaintext b to each Pii=2,3,⋯,n. If the MP-TPSI cardinality testing passes, n parties then run the MP-TPSI computing. P1 returns 2t+1 ciphertexts fk|k∈2t+1 to each Pii=2,3,⋯,n. Each Pii=2,3,⋯,n sends 2t+1 partial decryption ciphertexts fki|k∈2t+1 to P1. P1 returns 2t+1 plaintexts fk|k∈2t+1 to each Pii=2,3,⋯,n. Therefore, the communication cost of the designated party P1 is n−1×2t+9×x+n−1×2t+2×x (namely, O (tn)), the communication cost of each Pii=2,3,⋯,n is 2t+2×x+2t+2×xi (namely, O (t)), the total communication cost is n−1×4t+4×x+2t+2×xi+2t+2×x bits.As shown in Figure5, compared with the TFHE-based MP-TPSI protocol [41], the proposed MP-TPSI protocol has a better performance in terms of communication cost. Specifically, when comparing with m=210 and t=29, for n∈2,3,⋯,8 parties, the communication cost in the proposed MP-TPSI protocol is almost reduced by 67.3%, 67.3%, 67.3%, 67.3%, 67.3%, 67.3%, and 67.3%, respectively, compared with the TFHE-based MP-TPSI protocol [41]. When comparing with m=211 and t=210, with regard to n∈2,3,⋯,8 parties, the proposed MP-TPSI protocol decreases by almost 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, and 67.2%, respectively, in communication cost in comparison with the TFHE-based MP-TPSI protocol [41]. When comparing with m=212 and t=211, regarding n∈2,3,⋯,8 parties, the proposed MP-TPSI protocol reduces the communication cost by almost 67.2%, 67.2%, 67.2%, 67.2%, 67.2%, 67.2% and 67.2% respectively than the TFHE-based MP-TPSI protocol [41].Figure 5
Comparison of communication cost.
(a)(b)(c)


## 6. Security Analysis

In security model, we assume an environmentZ who is able to corrupt the set A∗ of n∗<n parties, a simulator S knows the output value w∈true,false of the ideal functionality ℱMP−TPSI−CT. If w=true, S sets b=0, otherwise sets b=1. S also has the output value I or ⊥ of the ideal functionality ℱMP−TPSI−C. In addition, for each corrupt party Ai∈A∗, S has the input data set Ai and random value ri of Ai. The simulation strategy of S is described as follows.Initialization. S represents each honest party Pi running the distributed setup TFHE.DisSet algorithm just like in the real world. S also knows the secret key share skiAi∈A∗ of all corrupt parties A∗.MP-TPSI Cardinality Testing. S does the following:In Step 1,S encodes the intersection set I=a1,a2,⋯,aI as a rational polynomial aIx=∏ai∈Ix−ai, chooses randomly a rational polynomial ux of degree t, and computes a rational polynomial fx=aIx⋅ux.In Steps 2–4, whenever each honest partyPi sends any encrypted value, S computes the ciphertext 0=TFHE.Enc0 employing fresh random value on behalf of Pi just like in the real world.In Steps 5–6, instead of computing the valuebi by executing the partial decryption algorithm TFHE.PartDecski,b on behalf of every honest party Pi just like in the real world, S calculates the value bi by executing the simulator algorithm biPi∈P=TFHE.SC,b,b,skiAi∈A∗, where C represents the computation circuit performed by P1 to calculate the value b just like in the real world, this corresponds to the idealworld, P denotes the set of the honest parties. If P1 is honest, S sends the evaluation value b just like in the real world.MPSI Computing. S does the following:In steps 1, instead of computing the valuefki by executing the partial decryption algorithm TFHE.PartDecski,fk on behalf of every honest party Pi just like in the real world, S calculates the value fki by executing the simulator algorithm fkiPi∈P=TFHE.SC,fk,fki,skiAi∈A∗, where C represents the computation circuit performed by P1 to calculate the value fk just like in the real world, this corresponds to the ideal world. If P1 is honest, S sends the evaluation value fk just like in the real world.In steps 2,S outputs the interpolation polynomial yix and set intersection I on behalf of every honest party Pi just like in the real world.Next, suppose a simulatorSh, we show that the proposed MP-TPSI protocol is secure against the environment Z in the semi-honest setting through a set of computationally indistinguishable consecutive hybrids.Hybrid0: Sh simulates all operations of honest parties just like in the real world.Hybrid1: Sh simulates a ideal functionality ℱMP−TPSI−CT. If Ai\I≤t, Sh returns true, otherwise returns false.Hybrid2: Sh simulates the partial decryption performed by the honest parties just like in the ideal world. For each k∈2t+1, Sh computes the partial decryption as fkiPi∈P=TFHE.SC,fk,fki,skiAi∈A∗. The rational polynomial fk is still calculated as in the real world.Hybrid3: Instead of calculating the rational polynomial fk just like in the real world, Sh selects randomly a rational polynomial ux of degree t, and computes a rational polynomial fx=aIx⋅ux.Hybrid4: Sh simulates the ciphertexts computed by any honest parties as encryption of 0, just like S does in the ideal world.Theorem 1.
Assuming that the TFHE scheme is secure, the proposed MP-TPSI protocolΠMP−TPSI securely realizes ℱMP−TPSI−CT and ℱMP−TPSI−C in a star network topology, and resists a semi-honest adversary who has the ability to corrupt up to n−1 parties. It can be proved by Lemma 1–4 in Appendix.


## 7. Conclusion

In this study, using sparse polynomial interpolation and TFHE, we introduce a MP-TPSI protocol with low communication complexity, in which the communication complexity only depends on the thresholdt and the number of parties n, not on the size of data set m. Compared with the existing MP-TPSI protocols, the proposed MP-TPSI protocol utilizes the same form of evaluation polynomial in the cardinality testing and intersection computing phases, which enables the parties to transmit and compute only a small number of evaluation values, and hence reduces the communication and computational cost. Performance evaluation demonstrates that our MP-TPSI protocol requires 92.0% and 67.2% less computational and communication costs respectively than the competitive MP-TPSI protocol. Moreover, the proposed MP-TPSI protocol can achieve the correctness of the intersection result, and ensure the security of the data of the parties, that is, the semi-honest adversary cannot learn additional information beyond the intersection. In the future, we will explore the MP-TPSI protocol in the broadcast communication setting, optimize the rounds of MP-TPSI, and design a more efficient MP-TPSI protocol with malicious security.



---

*Source: 9245516-2022-09-27.xml*