Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 2, No. 3, 2022 68 Multi-party Privacy Set Intersection protocol with an Untrusted Cloud Server He Tian, Jing Zhang, Li Yang, Yongli Tang*, and Chunming Zha School of Software, Henan Polytechnic University, Jiaozuo 454000, China * Corresponding author: Yongli Tang (Email: yltang@hpu.edu.cn) Abstract: The development of cloud computing has brought many conveniences to life, its advantages of low cost and high computing power bring convenience to our life, but the main problem is how to protect user data on untrustworthy cloud servers. To solve this problem, we have proposed a new private set intersection protocol, denoted as. The protocol uses a representation of sets with polynomial point-value pairs. All elements should be transmitted and computed in the protocol as ciphertext by introducing random polynomials to re-randomize the encryption elements. To reduce the computational burden of each party. The parties send the processed polynomials to the cloud server, which calculates the intersection. In addition, our protocol achieves fairness in the case of collusion between parties. Finally, the security of the protocol is demonstrated under the UC model. Comparing the performance of this protocol with other related protocols show that the protocol is better than the other associated protocols in terms of low computational overhead. Keywords: Private set intersection; Secure multi-party computation; Fair computation; Oblivious Linear Function Evaluation. 1. Introduction 1.1. Background Private Set Intersection (PSI) is an important branch of secure multi-party computation that allows parties to jointly compute the common information of their sets without revealing any additional privacy information. At the end of the PSI protocol, if the PSI protocol outputs the results to all parties, we say it's fair. Since Freedman proposed PSI in [1], PSI has not only become an important research problem in privacy, but also has specific applications in many scenarios. For example, in the process of genetic similarity testing, the participants only want to get the same gene fragment of both for themselves, while the rest of the gene fragments should be kept strictly confidential. Another typical example is private contact discovery, where WeChat makes friend account recommendations based on the cell phone address book. At the same time, the emergence of cloud server provides more convenient conditions for PSI[2,3]. The PSI protocol combined with cloud computing technology is also widely utilized, such as online advertising[4], genetic testing[5], contact tracing for infection detection[6,7]. PSI based on cloud outsourcing brings us a lot of convenience, but there are still some problems that we need to solve. protocols based on public-key cryptosystems often require additional management of keys which is too expensive. In addition, the cloud server it may not perform the computation honestly, so one of the basic requirements of outsourcing the computation is to ensure the correctness of the results. In other words, the user should have a way to verify the correctness of the cloud server output with absolute probability. Although the cloud server is not trusted, inappropriate behavior can occur on the client side. For instance, a malicious user may intentionally claim that the cloud server's outputs are incorrect, even though the cloud server performed the calculations honestly. Therefore, the results are best disclosed to all parties at the same time. These problems are also of concern to us. 1.2. Our Contributions A new protocol MPSI is proposed which is implemented by combining cloud servers and Oblivious Linear Function Evaluation (OLE). The protocol achieves fairness in multi- party PSI while protecting the privacy of all parties. The main contributions of this paper can be summarized in the following three aspects: (a)The MPSI protocol uses polynomials to improve the pre-processing of set elements by introducing common sets. Using OLE to blind the polynomials of the parties involved, only the polynomials need to be compared. The computation overhead of the entire protocol is reduced by reducing the number of times to determine whether the elements are equal. (b)The MPSI protocol further reduces the computational burden on all parties by shifting the computation of intersections to the server. In addition, multiple parties are able to run the MPSI protocol in parallel with each other. In addition, the protocol ends with each party knowing the result of the intersection, achieving fairness of the MPSI protocol. (c)The MPSI protocol resists collusion between the cloud server and 1n − parties. The MPSI protocol also ensures that each party can check the integrity and correctness of the results to counteract malicious behavior of the cloud server. 2. Related work Scholars have studied PSI extensively, and in this section, we present further related work. Generally speaking, these works could be categorized into the 3 types. 2.1. Public-key technology The PSI protocol was proposed in [1] based on polynomial evaluation, where a polynomial is constructed from the elements in the set, the coefficients of the polynomial are found by interpolation, and the polynomial coefficients are 69 sent to the server in ciphertext. In this protocol, a larger number of polynomials will cause the higher computational costs in the homomorphic encryption process. In [8], authors constructed the oblivious pseudo-random function (OPRF) based on the inadvertent transmission expansion protocol to efficiently complete the privacy equivalence test and propose a PSI protocol. In [9] , authors introduced the cuckoo hash mapping technique based on [8] and proposes an efficient PSI protocol. In [10] a new PSI protocol with lower complexity is given. Based on this, [11] proposed an unbalanced PSI protocol is made resistant to malicious attacks by using OPRF in the initialization part of this protocol. In [12] , authors used a new inadvertent transfer expansion protocol based on the [9] for constructing inadvertent pseudo-random functions as well as PSI schemes. The most common technique is homomorphic encryption. The authors of [13] improved computational efficiency by using ElGamal encryption and reduced computational complexity by using the Cuckoo Hash technique [14]. Abadi proposed a point-value pair-based d- polynomial representation of the set method, which is accomplished by the Paillier encryption scheme, reducing the multiplicative complexity from ( )2O d to ( )O d [15]. The PSI protocols based on public-key technology are generally suitable for models with high computational power, but communication bandwidth and time complexity are a big obstacle for practical applications. 2.2. Oblivious transfer technology Traditional OT protocols limit the security and efficiency of PSI protocols due to the large number of OTs that need to be used, but this bottleneck can be effectively solved by OT extension technology (OTE). Phase hashing and permutation hashing methods were applied to reduce computational effort and memory in [16]. A protocol based on OT extensions that gives a lightweight protocol for security and communication networks was proposed in[17]. In [18], Pinkas analyzed the existing PSI protocols and constructed a new PSI protocol using hashing techniques and OPRF to optimize the PSI protocol. In [19], a PSI protocol based on string detection with Paxos (Paxos) data structure was proposed that not only has linear communi-cation and computational complexity, but also resistant to malicious attacks Dong cons-tructed a semi- honest PSI protocol based on IKNP03-OT [20] and Bloom filters [21]. Later, Pinkas introduced ALSZ13-OT [22] based on [21], which led to a 50% reduction in the amount of communication between the parties [8]. To make the protocols more computationally efficient, most OT protocols are implemented using symmetric cryptosystems. These protocols have low communication complexity and time complexity. However, these protocols require operations such as key management. 2.3. Cloud computing. Cloud computing technology provides users with flexible and economical computing resources. Using cloud servers to assist in computing privacy set intersection is a feasible approach, however, cloud servers bring convenience to users but also raise new security issues, and untrustworthy cloud servers may violate data privacy confidentiality agreements to steal private data [23,24]. Therefore, a number of cloud server-based privacy intersection solutions have emerged. In [25], authours constructed a series of PSI protocols for cloud computing environments that allow two-party clients to use the computational power and storage space of the cloud server to assist in computing PSI of both parties without leaking private information to the cloud server, but are limited to solving the two-party privacy intersection computation problem. In [26,27], authours proposed privacy set intersection protocols supporting multiple parties respectively, but their computation and communication are done by each party, and when the party's equipment is limited, it is not possible to securely use cloud services to assist the computation. In [28], A fair two-party PSI protocol is proposed, which combines cloud servers with cuckoo hashing to achieve a fair PSI. The variation between the above protocols are shown in Table 1, and we have mainly analyzed structure and adversary model. Table 1. Variation between the above protocols. Type Reference Structure Adversary model Public Key [8] OPRF+GBF Semihonest [9] OPRF+Hash Semihonest [10] HE Semihonest [11] OPRF+HE Malicious [12] OPRF+ IKNP-OT Semihonest [13] HE+Hash Malicious [15] HE Semihonest Oblivious transfer [16] GC+OPRF Semihonest [17] OPRF+Hash Semihonest [18] OOS-OT+Hash Malicious [19] IKNP-OT Semihonest [20] BF+ IKNP-OT Malicious Cloud computing [24] Hash+ point-value polynomial Semihonest [25] OPPRF+OT Semihonest [26] KSO15-OT Malicious [28] ElGamal +Hash Semihonest 3. Preliminaries In this section, we give the representation of polynomials with sets and the related definitions. We also provide the OLE algorithm and security model used to construct our scheme. 3.1. Polynomial point-value pairs represent sets In order to achieve the conversion from set to polynomial. The representation illustrates that a random point evaluation polynomial can be used to represent the set. Definition 1. Polynomial point-value pairs represent sets. Given a set  1, , dX x x= ,we define its characteristic polynomial as ( ) ( ) ( )1 df x x x x x= −   − (1) to determine whether a set contains an element x , it is only necessary to determine whether ( ) 0f x = holds. Definition 2. Suppose X and Y are two sets of the same degree d and denoted by polynomials ( ) ( ),F x G x .We can represent the intersection ( ) ( )F x G x by finding the roots of this polynomial when it is equal to 0, ( ) ( ) ( ) ( )1 2F x H x G x H x+ (2) where ( )1H x and ( )2H x are randomly chosen d-degree polynomials. Definition 3. Let ( )0 R denote the ( ) ( )0 , 0x R R x  = . Let ( ), logd d poly . Suppose   ( ),degr x r d = is a 70 random polynomial. For all non-trivial  p x , ( )deg p d = , ( ) ( )( )  ( )0 0Pr | |r p negl     (3) 3.2. Oblivious Linear Function Evaluation. Intuitively, Oblivious Linear Function Evaluation (OLE) is a generalisation of OT to the larger domain by [29]. The ideal functionality of OLEF allows the sender and receiver to jointly compute a linear function ( )xc ax b= + . In the OLEF , the receiver inputs x and obtains ( )c x and the sender inputs ,a b and obtains nothing. The OLE guarantees that the receiver has no knowledge of ,a b other than the result ( )c x , and the sender has no knowledge of x . The ideal functionality of OLEF is shown in Figure 1. Sender Receiver a,b x ( )f x a x b + Figure 1. The ideal functionality of OLEF 3.3. Security Model. In the Universal Composability (UC) framework of [30] the MPSI protocol is proved. Let  corresponds to the protocol in the real world and F corresponds to the ideal function in the ideal world. For  protocols in the real world, there is a PPT adversary and will exist a simulator Sim in the ideal world. The protocol is secure if Equation 4 holds. ( ) ( ), ,, ,F SimReal X Y Ideal X Y  (4) where ( ), ,Real X Y is the real output, ( ), ,F SimIdeal X Y is the ideal output, the  indicates computationally indistinguishable. 4. Our Protocol In this section, we present the proposed PSI protocol. To make it easier to understand, we first introduce the overall idea of designing a protocol. 4.1. Overview The protocol has n parties ( )1iP i n  and a cloud server S are involved. iP input his private set iX and compute the intersection 1 n i i X = through S without leakage information. We have proposed a new design idea based on [29], where OLEF algorithm is run between iP and ( )( )1 , 1 modcP i n c i n  = + . iP obtains polynomial iR , after which the party iP sends the polynomial iR to S . The cloud server S computes 1 = n com i i R R =  and the set formed by the roots of the comR is the intersection of the sets iX . However, we have discrepancy with the protocol of [29]. We have analyzed three possible scenarios of untrustworthy cloud servers. (a) It can claim that all elements are not in the intersection set. (b) It can claim that all elements are in the intersection set. (c) The cloud server feeds only a portion of the intersection to the party. We need to ensure that the results returned by the cloud server S cannot be empty and cannot directly return all the information entered by the parties [31]. In order to be able to realize this, the parties work collectively to generate a set ( )( )0 0, / 2iD D d d= − and iP generates the private set ( )( ), / 2i i iD D d d= − . First, iP chooses 0 iD D+ to blind the set iX , then iP get 0i i iX X D D = + + . Second, iP expands its set iX  with  copies of all element. Prior to the start of the protocol, iP need creates his new set ( ) 1, ,j j i i iX x x = for all j i ix X  , meanwhile, define ( )i iX X  − = . However, there is still a need to consider data privacy during the interaction between the two sets of information while correctly computing the intersection. We use OLE to solve this problem. In our protocol, the parties iP holds sets ( ),i iX X d  = and constructs a polynomial ( )0 iR x based on iX  . iP randomly generates two polynomials ( )1 iR x and ( )2 iR x , where ( ) ( )1 2 / 2i iR x R x d= = . iP and ( )( )1 , 1 modcP i n c i n  = + run the OLEF algorithm twice , iP get ( ) ( ) ( ) ( )1 0 2 i c i cR x R x R x R x = + and cP get ( ) ( ) ( ) ( )1 2 c i c iR x R x R x R x = + . If ( )iR x is sent directly to the cloud server S , the polynomial ( )0 iR x of iP is compromised if cP and the cloud server S are colluded. To avoid this problem, we require the ( )1iP i n  to do another blinded operation before sending. ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) 2 0 2 0 1 2 2 2 OLEF i i i i i i c i c i R R x R x R x R x R x R x R x R x R x = − + = + + − (5) iP sends OLEF iR to the cloud server S . The cloud server S derives 1 = OLE n F com i i R R =  . After that, the cloud server send comR to the iP . 4.2. MPSI Protocol We give a detailed description of our MPSI proposed protocol in this section. we define the set iX  as    1= , , , , 1,i ij d i i i i i iX x x x j d .The new protocol MPSI is shown in Algorithm 1. Inputs: iP holds the set iX , where  1, , i ii n X d = . Let  max 1id X= + . Outputs: int 1 d Set i i X X− = = . 1. Preparation Phase. (1) All parties run a pseudo-random function generator PRFF to generate the set 0 ,D where ( )0 / 2iD d d= − . (2) iP run PRFF to generate three private sets 1 2,i iD D and 3 iD , where ( )1 / 2i iD d d= − , 2 / 2iD d= and 3 / 2iD d= . iP uses 1 0 iD D+ to blind the set iX , then 71 1 0i i iX X D D = + + . For all j i ix X  , iP creates his new set ( ) 1, ,j j i i iX x x = (3) iP generates three polynomials ( )0 iR x , ( )1 iR x and ( )2 iR x , where ( ) ( )0 , d i k k ik R x x x x X  = −  , ( ) ( ) /21 2, d i k k ik R x x x x D  = −  and ( ) ( ) /22 3, d i k k ik R x x x x D  = −  . 2. Execute OLE and Blindness. (1) iP as a receiver, inputs ( )0 iR x into OLEF . ( )( )1 , 1 modcP i n c i n  = + as a sender, inputs ( )1 cR x and ( )2 cR x into OLEF . iP get ( ) ( ) ( )0 1 2 i i c cR R x R x R x = + , cP get ⊥ . (2) cP as a receiver, inputs ( )0 cR x into OLEF . iP as a sender, inputs ( )1 iR x and ( )2 iR x into OLEF . cP get ( ) ( ) ( )0 1 2 c c i iR R x R x R x = + , iP get ⊥ . (3) ( )1iP i n  computes ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2OLEF i i c i c iR R x R x R x R x R x= + + − . 3. Set intersection. The cloud server S computes 1 = OLE n F com i i R R =  and sends comR to iP . 4. Checking and verification. (1) iP aborts the protocol if any of the following occurs: ( ) 00,comR x x D  or ( ) 0,com iR x x D=  or ( ) ( )  0, 0, , , 1,j j j com i com i i iR x R x x X    =    . (2)For ix X  , if ( ) 1 0, d com i i R x x X  = =  . Then iP calculates ( ) 1 1 d d i i i i X X   − = =  = and int 0 1 d Set i i X X D− = = − . Algorithm 1. Malicious security Multi-party PSI 4.3. Analysis of correctness Theorem 1. We say that MPSI protocol does not correctly calculate the probability of intersection as : ( ) ( ) 1 Pr | |0, n com i i X n lR x x eg =       =  (6) Proof. According to the MPSI , we get ( ) ( ) ( ) ( ) ( ) ( )2 1 0 2 2OLEF i i i c i c iR R x R x R x R x R x R x= − = + − ，then ( ) ( )( ) ( ) ( ) ( )( )( ) ( ) ( ) ( )( )( ) 1 2 1 0 1 1 1 1 0 1 1 1 = OLE n F com i i n i i i n n n R R R x R x R x R x R x R x R x R x = = = − = + + + +   (7) According to the Definition 2, equation (7) is equivalent to 1=com nR X X  (8) then iP calculates ( ) 1 1 d d i i i i X X   − = =  = , we can get ( ) ( ) ( ) ( ) 1 1 1 1 0 1 0 1 1 1 1 0 =com n n n n n R X X X D D X D D X D X D D  = + + + + = + + (9) Let ( ) ( ) ( ), , 1 i i d X k k ik R x x x x X i n= −    , ( ) ( )1 0 01Ψ iX cR R= + and ( ) ( )1 0 02Ψ cX iR R= + ( )( )1 modc i n= + . equation (9) is equivalent to ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 0 1 0 2 0 0 1 1 0 0 1 0 0 1 1 1 0 0 Ψ Ψ i c i c i c i c X c X i X c X i X X X i c X c i R R R R R R R R R R R R R R R R   =  +  + =   =     (10) By Definition 3, we have ( ) ( ) ( ) ( ) ( ) ( ) 1 0 1 0 1 1 0 Pr | | Pr | | Pr | | i c X i c X c i R R negl R R negl R R negl                   (11) Then we can get ( ) ( ) ( ) ( )00 1 0 2 1 0 1 int =Ψ Ψ n n Set X D X D X X X −  − − = =   (12) According to the above equations, we can conclude that ( ) ( ) 1 Pr | |0, n com i i X n lR x x eg =       =  , the proof is finished. 4.4. Security Analysis The formal security proof of polynomial-based protocol is given. Theorem 2. The MPSI protocol is secure in the presence of a malicious adversary if the PRFF is the pseudo- random function. Proof. This theorem is proved by taking into account the cases in which the parties are destroyed. By building a simulator in each case, only the inputs and outputs of the destroyed party are obtained and a view is generated. Further, the view must be computationally indistinguishable from the real view. Let  iM i P is malicious= and 1tM M n=  − . Let  jH j P is honest= and 1tH H=  .We will only discuss the worst-case scenario here. Namely, the 1tM M n= = − . Case 1: Cloud sever S and 1P are honest, the other parties are malicious. In this case, we construct the simulator 1Sim as follows. It is given M input set MX . 1Sim generates its own view based on the execution process of the protocol. For the OT, 1Sim generates 1P s random string ( )0 1R x , ( )1 1R x and ( )2 1R x , In order to build the view, 1Sim runs the OLEF as receiver and inputs ( )0 1R x , ( )1 1R x and ( )2 1R x and outputs 1 OLEF R . Then 1Sim sends 1 OLEF R to S . Finally 1Sim outputs M s view. Consider the following hybrid games. Game 0: M and 1P output in the real protocol. This corresponds to ( ), 1,PSI MReal X X . From the MPSI protocol, we know ( ) ( ), 1 1 int, , , ,OLE OLE PSI F F M n SetReal X X R R X −= . Game 1: Identical to Game 0, except that on 1P chooses 72 the random PRFF key. The 1Sim aborts according to the Checking and verification in Algorithm 1. If the environment can distinguish between Game 0 and Game 1, then the environment must manage to send 1 OLEF R such that ( ) ( ) ( )( ) ( ) ( )( )0 1 2 2 2 1 2 1 2 1R x R x R x R x R x+  − , while passing the check of Checking and verification in Algorithm 1 with non-negligible probability. Let ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2 1 1 2 1 2 1 OLEF R R x R x R x R x R x= + + − . Due to the fact that x is uniformly random, the probability of satisfying 1 0OLEF R = is /d . Therefore, Game 1 and Game 0 are computationally indistinguishable. Game 2: The remainder is the same as Game 1 except for 1Sim generates the ( )0 1R x , ( )1 1R x and ( )2 1R x according to the Algorithm 1 and adjustsd the output. This corresponds to ( ), 1 1,F Sim MIdeal X X . The previous Games determined that the inputs ( )0 1R x , ( )1 1R x and ( )2 1R x are extracted correctly. Note that the received intersection 1 2= OLE OLE OLEF F F com nR R R R+ + + , the adversary cannot modify the element information in the intersection unless there is a negligible probability. Further, As ( )0 1R x , ( )1 1R x and ( )2 1R x are uniform randomly over the choice , ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2 1 1 2 1 2 1 OLEF R R x R x R x R x R x= + + − is also randomly distributed. Similarly, the ( )0 1R x , ( )1 1R x and ( )2 1R x are uniform randomly over the choice, comR is also randomly distributed. Due to the degree of ( )0 1R x is d , the ( )1 2R x and ( )2 2R x are randomly. Therefore, the Game 2 and Game 1 are computationally indistinguishable. . Then we get ( ) ( ), 1 1 1 int, , , ,OLE OLEF F F Sim M n SetIdeal X X R R X −= . Combining the above, we can get that ( ) ( ), 1 , 1 1, , PSI M F Sim MReal X X Ideal X X  (13) Case 2: We assume that only 1P is honest, the cloud server S and the other parties are malicious. Also, the malicious cloud server S can conspire with 1n − malicious parties. We construct the simulator 2Sim as follows. It is given M input set MX . 2Sim generates its own view based on the execution process of the protocol. For the OT, 2Sim generates 1P s random string ( )0 1R x , ( )1 1R x and ( )2 1R x , In order to build the view, 2Sim runs the OLEF as receiver and inputs inputs ( )0 1R x , ( )1 1R x and ( )2 1R x and outputs 1 OLEF R . Then 2Sim sends 1 OLEF R to S . Finally 1Sim outputs M s view. Consider the following series of hybrid games. Game 0: ( ), 1,PSI MReal X X . M and 1P output in the real protocol. This corresponds to ( ), 1,PSI MReal X X . From the MPSI protocol, we know ( ) ( ), 1 1 int, , , ,OLE OLE PSI F F M n SetReal X X R R X −= . Game 1: Identical to Game 0, except that on 1P chooses the random PRFF key. The 1Sim aborts according to the Checking and verification in Algorithm 1. If the environment can distinguish between Game 0 and Game 1,then the environment must manage to send 1 OLEF R such that ( ) ( ) ( )( ) ( ) ( )( )0 1 2 2 2 1 2 1 2 1R x R x R x R x R x+  − , while passing the check in Checking and verification in Algorithm 1 with non-negligible probability. Let ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2 1 1 2 1 2 1 OLEF R R x R x R x R x R x= + + − . Due to the fact that x is uniformly random, the probability of satisfying 1 0OLEF R = is /d . Therefore, Game 1 and Game 0 are computationally indistinguishable. Game 2: The remainder is the same as Game 1, except that 1Sim generates the ( )0 1R x , ( )1 1R x and ( )2 1R x according to the Algorithm 1 and adjustsd the output. This corresponds to ( ), 1 1,F Sim MIdeal X X . The previous Games determined that the inputs ( )0 1R x , ( )1 1R x and ( )2 1R x are extracted correctly. Note that the received intersection 1 2= OLE OLE OLEF F F com nR R R R+ + + , the adversary cannot modify the element information in the intersection unless there is a negligible probability. Further, As ( )0 1R x , ( )1 1R x and ( )2 1R x are uniform randomly over the choice , ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2 1 1 2 1 2 1 OLEF R R x R x R x R x R x= + + − is also randomly distributed. Similarly, the ( )0 1R x , ( )1 1R x and ( )2 1R x are uniform randomly over the choice, comR is also randomly distributed. Therefore, the Game 2 and Game 1 are computationally indistinguishable. Finally, the malicious cloud server S conspire with 1n − malicious parties. Then the adversary obtains ( ) ( ) ( )( ) ( ) ( )0 1 2 2 2 1 1 2 1 2 1 OLEF R R x R x R x R x R x= + + − . To the adversary , ( )1 1R x and ( )2 1R x are random and unknown, the adversary cannot get the information about ( )0 1R x and pass the check with absolute advantage. Then we get ( ) ( ), 1 1 1 int, , , ,OLE OLEF F F Sim M n SetIdeal X X R R X −= . Combining the above, we can get that ( ) ( ), 1 , 2 1, , PSI M F Sim MReal X X Ideal X X  (14) the proof is finished. 5. Efficiency Analysis 5.1. Theoretical Evaluation The comparison between the MPSI protocol and [29,32] is given in this section. In contrast to previous work that relied on exponential operations on domains, our protocol requires only addition and multiplication for computing privacy set intersections. Our MPSI protocol requires one interaction between each party and also one interaction with the cloud server. The resulting communication complexity is ( )( )2 logO n n d k+ . iP and ( )( )1 , 1 modcP i n c i n  = + perform nd operations in the OLE algorithm and logn d operations in the encryption step. The cloud server computes PSI and no other operations are involved. The detailed analysis of the relevant PSI protocols is presented in table 2. We evaluated its performance in five aspects: total communication complexity, total computation complexity, client communication, client Computation and fairness. From 73 the Table 2, compared to literature [29] and [32], our MPSI protocol has the following advantages: (a) The total computational complexity, total communication complexity, client communication and client computation of our protocol are no greater than other protocols. The MPSI protocol uses polynomials to perform comparisons. The computational efficiency of the MPSI protocol is reduced by reducing the times of the set are compared. At the same time all parties can execute the protocol in parallel. This is why the protocol has a significantly lower computational and communication cost than other protocols. (b) Only our protocol achieves fair multi-party PSI. The MPSI protocol guaranteed that after the protocol is executed, each party can know the intersection result. Table 2. Comparison with related PSI protocols Protocal Communication Computation Fairness ( )( )2O k n nd+ ( )logO nd d No ( )( )2 logO k n nd d+ ( )logO n nd d+ No Ours ( )( )2 logO k n n d+ ( )logO nd n d+ Yes 5.2. Experimental Evaluation To more visually compare the runtime overhead of each protocol, simulation experiments and results analysis are conducted in this paper. It should be noted that the time consumed by the protocol refers to the average time consumed in 10 experiments. The experimental platform is Windows 10, Intel(R) Core(TM) i5-5200U CPU @ 2.20 GHz 2.20 GHz, 4.00 GB of RAM, and a compiled environment of Dev-C++5.11. First consider the effect of the change in the number of elements contained in the set on the running time. Suppose 20n = , 128k = , 10 12 14 16 18 202 ,2 ,2 ,2 ,2 ,2d = are selected for comparison experiments, and the relationship between the protocol running time and the number of elements contained in the set is shown in Figure 2. From Figure 2, when the number of sets increases, the execution time of all three protocols grows. However, the time of MPSI protocol increases the slowest when the fixed set cardinality is small. In addition, the MPSI protocol has the slowest time growth rate. In addition, the change in the number of partes in the protocol has an impact on the running time of the protocol. Assume that the total number of elements in the set 8 1 2 n i i d d = = = and keep the remaining parameters constant. The number of parties 3 4 5 6=10 10 10 10n ， ， ， is selected for comparison experiments, and the relations between the protocol running time and the number of parties is shown in Figure 3. 210 212 214 216 218 220 0 100 200 300 400 500 600 700 T im e (s ) Set Cardinality [29] [32] Ours Figure 2. Running time v.s. set cardinality 10 102 103 104 0 20 40 60 80 100 120 T im e ( m s) Parties [29] [32] Ours Figure 3. Running time v.s. the number of parties From Figure 3, the running time of all protocols increases gradually with the number of parties. The time overheads of the MPSI protocols are lower than those of the other protocols when n is fixed. In addition, the MPSI protocol has the slowest time growth rate. To sum up, the MPSI protocol saves the time overhead of the multi-party PSI computation to a certain extent, improves the calculation efficiency, and realizes the fair multi-party PSI computation. Therefore, the overall efficiency of the MPSI protocol is better than the compared protocols. 6. Conclusion PSI is a popular field of study and has been applied in many domains. In this paper, we design a multi-party privacy intersection computation protocol for untrustworthy cloud computing environment, so that the multi-party holding the privacy set can use the computing and communication capabilities of untrustworthy cloud servers to assist the parties to complete the privacy set intersection computation without revealing any set information. This paper has a wider range of applications than existing schemes. The next work will focus on how to safely outsource party s data for reuse of processed privacy data. Acknowledgments This work was supported by the Support Plan of Scientific and Technological Innovation Team in Universities of Henan Province (No. 20IRTSTHN013), the Youth Talent Support 74 Program of Henan Association for Science and Technology (No. 2021HYTP008), the Fundamental Research Funds for the Universities of Henan Province (No. NSFRF210312), and the Project supported by the PhD Foundation of Henan Polytechnic University (No. B2021-41). References [1] Freedman, Michael J, Kobbi Nissim, and Benny Pinkas. "Efficient Private Matching and Set Intersection". International conference on the theory and applications of cryptographic techniques. 2004. [2] Yang, Li, et al. "Achieving Privacy-Preserving Sensitive Attributes for Large Universe Based on Private Set Intersection." Information Sciences 582 pp.529-46.2022. [3] Ruan, Ou, and Jianqiang Zeng. "A Delegated Offline Private Set Intersection Protocol for Cloud Computing Environments". Proceedings of the 2022 2nd International Conference on Control and Intelligent Robotics. 2022. [4] Lv Siyi, Ye Jinhui, and Yin Sjie. "Unbalanced Private Set Intersection Cardinality Protocol with Low Communication Cost." Future Generation Computer Systems 102 pp.1054- 61.2020. [5] Yang, Yaxi, et al. "Prirange: Privacy-Preserving Range- Constrained Intersection Query over Genomic Data." IEEE Transactions on Cloud Computing.2022. [6] Singh, Priyanka, et al. "Ppcontacttracing: A Privacy-Preserving Contact Tracing Protocol for Covid-19 Pandemic." arXiv preprint arXiv:.06648 20.8 pp.6648-57.2020. [7] Duong, T., D. H. Phan, and T. Ni. "Catalic: Delegated Psi Cardinality with Applications to Contact Tracing". International Conference on the Theory and Application of Cryptology and Information Security. 2020. [8] Pinkas, Benny, Thomas Schneider, and Michael Zohner. "Faster Private Set Intersection Based on Ot Extension". 23rd USENIX Security Symposium (USENIX Security 14). 2014. [9] Kolesnikov, Vladimir, et al. "Efficient Batched Oblivious Prf with Applications to Private Set Intersection". Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016. [10] Chen, Hao, Kim Laine, and Peter Rindal. "Fast Private Set Intersection from Homomorphic Encryption." Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017. [11] Chen, Hao, et al. "Labeled Psi from Fully Homomorphic Encryption with Malicious Security". Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018. [12] Pinkas, Benny, et al. "Spot-Light: Lightweight Private Set Intersection from Sparse Ot Extension". Annual International Cryptology Conference. 2019. [13] Freedman, Michael J., et al. "Efficient Set Intersection with Simulation-Based Security." Journal of Cryptology 29.1 pp.115-55.2016. [14] Pagh, Rasmus. "On the Cell Probe Complexity of Membership and Perfect Hashing". Proceedings of the thirty-third annual ACM symposium on Theory of computing. 2001. [15] Abadi, A., S. Terzis, and C. Dong. "O-Psi: Delegated Private Set Intersection on Outsourced Datasets". IFIP International Information Security and Privacy Conference. 2015. [16] Pinkas, Benny, et al. "Phasing: Private Set Intersection Using Permutation-Based Hashing". 24th USENIX Security Symposium (USENIX Security 15). 2015. [17] Dong, C., et al. "Fair Private Set Intersection with a Semi- Trusted Arbiter". Data and Applications Security and Privacy XXVII. 2013. [18] Pinkas, Benny, Thomas Schneider, and Michael Zohner. "Scalable Private Set Intersection Based on Ot Extension." Acm Transactions on Privacy and Security (TOPS) 21.2 pp.1- 35.2018. [19] Pinkas, Benny, et al. "Psi from Paxos: Fast, Malicious Private Set Intersection". Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020. [20] Ishai, Yuval, et al. "Extending Oblivious Transfers Efficiently". Annual International Cryptology Conference. 2003. [21] Dong, Changyu, Liqun Chen, and Zikai Wen. "When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol". Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013. [22] Asharov, Gilad, et al. "More Efficient Oblivious Transfer and Extensions for Faster Secure Computation". Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security. 2013. [23] ZHANG, En, and Ganggang JIN. "Cloud Outsourcing Multiparty Private Set Intersection Protocol Based on Homomorphic Encryption and Bloom Filter." Journal of Computer Applications 38.8 pp.2256-60.2018. [24] Tajima, Arisa, Hiroki Sato, and Hayato Yamana. "Outsourced Private Set Intersection Cardinality with Fully Homomorphic Encryption". 2018 6th International Conference on Multimedia Computing and Systems (ICMCS). 2018. [25] Abadi, Aydin, et al. "Efficient Delegated Private Set Intersection on Outsourced Private Datasets." IEEE Transactions on Dependable and Secure Computing 16.4 pp.608-24.2017. [26] Kolesnikov, Vladimir, et al. "Practical Multi-Party Private Set Intersection from Symmetric-Key Techniques". Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017. [27] Zhang, En, et al. "Efficient Multi-Party Private Set Intersection against Malicious Adversaries". Proceedings of the 2019 ACM SIGSAC conference on cloud computing security workshop. 2019. [28] Zhang, Jing, et al. "Outsourced Mutual Private Set Intersection Protocol for Edge-Assisted Iot." 2021.2021. [29] Ghosh, Satrajit, and Tobias Nilges. "An Algebraic Approach to Maliciously Secure Private Set Intersection". Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2019. [30] Canetti, Ran. "Universally Composable Security: A New Paradigm for Cryptographic Protocols". Proceedings 42nd IEEE Symposium on Foundations of Computer Science. 2001. [31] Kamara, S., et al. "Scaling Private Set Intersection to Billion- Element Sets". Springer Berlin Heidelberg. 2014. [32] Hazay, Carmit, and Muthuramakrishnan Venkitasubramaniam. "Scalable Multi-Party Private Set-Intersection". IACR international workshop on public key cryptography. 2017.