# Outsourced Mutual Private Set Intersection Protocol for Edge-Assisted IoT

Authors: Jing Zhang; Rongxia Qin; Ruijie Mu; Xiaojun Wang; Yongli Tang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The development of edge computing and Internet of Things technology has brought convenience to our lives, but the sensitive and private data collected are also more vulnerable to attack. Aiming at the data privacy security problem of edge-assisted Internet of Things, an outsourced mutual Private Set Intersection protocol is proposed. The protocol uses the ElGamal threshold encryption algorithm to rerandomize the encrypted elements to ensure all the set elements are calculated in the form of ciphertext. After that, the protocol maps the set elements to the corresponding hash bin under the execution of two hash functions and calculates the intersection in a bin-to-bin manner, reducing the number of comparisons of the set elements. In addition, the introduction of edge servers reduces the computational burden of participating users and achieves the fairness of the protocol. Finally, the IND-CPA security of the protocol is proved, and the performance of the protocol is compared with other relevant schemes. The evaluation results show that this protocol is superior to other related protocols in terms of lower computational overhead.


---

## Body

## 1. Introduction

The vigorous development of fifth-generation technology (5G), Internet of Things (IoT), edge computing, and other technologies has spawned new medical and life modes such as smart medical treatment [1], smart home [2], and smart bus [3]. Intelligent IoT devices have been widely used in daily life and have brought great changes to people's life. With the assistance of proxy devices and edge servers [4], these data can be outsourced to edge storage for subsequent analysis and use. However, although data outsourcing based on edge computing reduces the storage and computing overhead on the user side, it also exposes the user's sensitive data to the risk of leakage [5]. How to protect the privacy of data stored on edge servers and share data with designated data consumers (such as service and product providers, medical professionals, and educators) has become the focus of research.Private Set Intersection (PSI), as an efficient encryption technology that allows secret sharing of data information, can ensure the security of the data stored on the edge server when making full use of the data for intersection calculation. So it has become an important research object to solve the problem of edge-assisted Internet of Things data privacy sharing. PSI protocol [6] refers to the intersection of two participants calculating their private sets. In the edge computing environment, two clients encrypt their respective data sets and outsource them to the edge server. Then the edge server effectively performs the intersection operation but cannot know any information in the set. Then one or two clients can obtain the intersection result, while their respective sets remain private. Usually, only one client obtains the intersection result is the one-way PSI protocol [7], which can be applied in situations such as contact tracing of the novel coronavirus COVID-19 [8]. At this time, the client unilaterally obtains the intersection result to determine whether it belongs to the contact. However, one-way PSI protocol cannot guarantee that both clients obtain the intersection result at the same time. Obviously, one-way PSI cannot satisfy both clients in the situation such as profile matching [9], in which both clients want to obtain the intersection results to realize the medical information sharing between patients. In this case, mutual PSI (mPSI) protocol [10] is the better choice. That is our focus.Debnath et al. [11] proposed a secure mutual oblivious pseudorandom function (mOPRF) under the malicious model based on composite order group to maintain the fairness of the mPSI protocol and use homomorphic encryption algorithm to protect data privacy. However, since the protocol is constructed based on composite order, the efficiency is lower than that based on prime order. Based on [11], Debnath et al. [12] proposed another mPSI protocol using prime order groups. The protocol also uses homomorphic encryption algorithm to ensure the security of data and uses semihonest offline arbiter to achieve fairness between two participants. However, the complexity of the protocol is still high. The mPSI protocol in [13] is also constructed based on prime order. It uses the multiplicative homomorphic encryption ElGamal and the distributed ElGamal cryptosystem to ensure the security of data and the offline semihonest arbiter to achieve fairness. But in order to ensure the security under the malicious model, the verifiable Cramer-Shoup cryptographic system used makes the protocol more complicated. Overall, although these mPSI protocols achieve data privacy and fairness, they have high computational complexity and low efficiency.In this paper, we propose an outsourced mPSI (O-mPSI) protocol in the aid of the edge server. The protocol not only protects the data privacy of parties and achieves the fairness of the results obtained by both parties, but also improves the efficiency. The main contributions are as follows:(1)
The O-mPSI protocol improves the method of preprocessing set elements in [14] by increasing the number of elements stored in each hash bin instead of using the stash. It only needs to compare the elements in the two hash tables in a bin-to-bin manner to calculate the intersection, which further reduces the number of comparisons of set elements and decreases the computational cost of the protocol. As a result, the computation and communication overhead of this protocol is lower than the existing mPSI protocol and realizes the efficiency of the O-mPSI protocol.(2)
The protocol adopts ElGamal threshold encryption algorithm to encrypt the elements in the hash table to ensure that the set elements of both parties are compared in the form of ciphertext, so that the users can correctly and safely calculate the intersection and realize the data privacy of the O-mPSI protocol.(3)
The protocol introduces a semihonest edge server as the third party, and the work of set element comparison is transferred to the server, which further reduces the computational burden of users. At the same time, it enables two users to process collection elements in parallel. This ensures that, after the implementation of the agreement, both parties can know the intersection results at the same time and realize the fairness of O-mPSI protocol.


## 2. Related Work

Since Agrawal et al. [15] proposed the concept of PSI, a series of work has been done to construct the PSI protocol. Ordinarily, they are divided into one-way PSI and mutual PSI.


### 2.1. One-Way PSI

At present, there are many types of research on the one-way PSI protocol, and the design methods are mainly based on public key encryption, garbled circuit (GC), oblivious transfer (OT), and cloud computing. Based on the design method of public key encryption system, literature [16] uses Fully Homomorphic Encryption (FHE) to construct the PSI protocol. The protocol uses bloom filters (BF) to process data, so that the complexity of the protocol has nothing to do with the size of the client set. Huang and Evans designed a PSI protocol [17] through GC that can resist semihonest adversaries, which proved to be suitable for the intersection calculation of sets of different sizes. Pinkas et al. realized the PSI protocol [18] with linear communication complexity based on GC and oblivious programmable pseudorandom functions (OPPRF). This protocol is superior to previous circuit-based PSI protocols in terms of efficiency. Literature [14] constructed oblivious pseudorandom function (OPRF) based on OT extension and then proposed a PSI protocol combined with OPRF and hash algorithm, and the security is proved under the semihonest opponent model. Kavousi et al. proposed a PSI protocol in [19], which takes the OPRF and the garbled BF as its main components, avoiding costly operations of computation and having high scalability. The protocol in [20] allows users to store their private data sets on cloud server and also entrust computing of the intersection to the server and use homomorphic encryption (HE) and oblivious polynomial evaluation (OPE) to process the data. It greatly reduces the workload of users and improves the computational efficiency of the protocol. The PSI protocol designed by Abadi et al. [21] also uses cloud storage of private data sets. It is mainly constructed by hash table and OPE without any public key encryption operation. However, all parties need to establish a secure channel in advance; otherwise it is easy for an attacker to eavesdrop on the communication between honest parties. Literature [22] proposed an improved PSI scheme based on [21]. There is no need for any secure channel in the scheme, which is superior to the scheme in [21] in terms of confidentiality and complexity.


### 2.2. Mutual PSI

The research on mutual PSI protocol began in 2005; Kissner and Song et al. proposed the first mPSI protocol [23], which is based on the mathematical properties of OPE and uses HE to calculate PSI on ciphertexts. The fairness of the protocol depends on the fairness of the threshold encryption scheme used by the protocol. Camenisch and Zaverucha proposed another mPSI authentication set protocol [24] based on Camenisch-Lysyanskaya signature (CLS) and OPE. The disadvantage of this protocol is that its computational overhead is quadratic and the computational complexity is relatively high. Fairness of the protocol in [24] is realized by a fair exchange scheme. However, if the input is not authenticated, it usually does not work. Kim et al. coupled the prime representation (PR) technology with threshold additive HE and realized an mPSI protocol [25] with linear complexity for the first time in the semihonest security model and through the nature of threshold decryption to achieve the fairness of the protocol. Dong and Chen et al. proposed a fair mPSI protocol [26] with a semihonest arbitrator based on HE and OPE. The arbitrator in the protocol can handle conflicts and cannot know the user's private input and output. The mPSI protocol in [11] is constructed by HE and mutual oblivious pseudorandom function (mOPRF). The fairness of the mOPRF ensures the fairness of the protocol. And in the standard model, it has been proven to resist the attack of malicious adversaries. In [12], an mPSI protocol with linear communication and computational overhead is constructed by using prime order group. The protocol uses a distributed ElGamal encryption algorithm and an offline semitrusted third party to achieve the fairness of the protocol and the security under the malicious adversary model. The mPSI protocol in [13] uses multiplicative HE and a distributed ElGamal cryptosystem to protect data privacy and uses an offline semihonest arbiter to achieve fairness. Under the decisional Diffie-Herman hypothesis, it is proved that the protocol is safe under the malicious adversary model.We show the differences between these protocols in Table1.Table 1
Difference between the mentioned protocols.
TypeReferenceStructureAdversary modelFairnessPublic key[12]HEMaliciousYes[13]HEMaliciousYes[16]FHE + BFSemihonestNo[23]HE + OPEMaliciousYes[24]HE + OPE + CLSMaliciousYes[25]HE + PRSemihonestYes[26]HE + OPEMaliciousYesGarbled circuit[17]GCSemihonestNo[18]GC + OPPRFSemihonestNoOblivious transfer[11]mOPRF + HEMaliciousYes[14]hash + OPRFSemihonestNo[19]OPRF + garbled BFSemihonestNoCloud computing[20]HE + OPESemihonestNo[21]Hash + OPESemihonestNo[22]Hash + OPESemihonestNo


## 2.1. One-Way PSI

At present, there are many types of research on the one-way PSI protocol, and the design methods are mainly based on public key encryption, garbled circuit (GC), oblivious transfer (OT), and cloud computing. Based on the design method of public key encryption system, literature [16] uses Fully Homomorphic Encryption (FHE) to construct the PSI protocol. The protocol uses bloom filters (BF) to process data, so that the complexity of the protocol has nothing to do with the size of the client set. Huang and Evans designed a PSI protocol [17] through GC that can resist semihonest adversaries, which proved to be suitable for the intersection calculation of sets of different sizes. Pinkas et al. realized the PSI protocol [18] with linear communication complexity based on GC and oblivious programmable pseudorandom functions (OPPRF). This protocol is superior to previous circuit-based PSI protocols in terms of efficiency. Literature [14] constructed oblivious pseudorandom function (OPRF) based on OT extension and then proposed a PSI protocol combined with OPRF and hash algorithm, and the security is proved under the semihonest opponent model. Kavousi et al. proposed a PSI protocol in [19], which takes the OPRF and the garbled BF as its main components, avoiding costly operations of computation and having high scalability. The protocol in [20] allows users to store their private data sets on cloud server and also entrust computing of the intersection to the server and use homomorphic encryption (HE) and oblivious polynomial evaluation (OPE) to process the data. It greatly reduces the workload of users and improves the computational efficiency of the protocol. The PSI protocol designed by Abadi et al. [21] also uses cloud storage of private data sets. It is mainly constructed by hash table and OPE without any public key encryption operation. However, all parties need to establish a secure channel in advance; otherwise it is easy for an attacker to eavesdrop on the communication between honest parties. Literature [22] proposed an improved PSI scheme based on [21]. There is no need for any secure channel in the scheme, which is superior to the scheme in [21] in terms of confidentiality and complexity.


## 2.2. Mutual PSI

The research on mutual PSI protocol began in 2005; Kissner and Song et al. proposed the first mPSI protocol [23], which is based on the mathematical properties of OPE and uses HE to calculate PSI on ciphertexts. The fairness of the protocol depends on the fairness of the threshold encryption scheme used by the protocol. Camenisch and Zaverucha proposed another mPSI authentication set protocol [24] based on Camenisch-Lysyanskaya signature (CLS) and OPE. The disadvantage of this protocol is that its computational overhead is quadratic and the computational complexity is relatively high. Fairness of the protocol in [24] is realized by a fair exchange scheme. However, if the input is not authenticated, it usually does not work. Kim et al. coupled the prime representation (PR) technology with threshold additive HE and realized an mPSI protocol [25] with linear complexity for the first time in the semihonest security model and through the nature of threshold decryption to achieve the fairness of the protocol. Dong and Chen et al. proposed a fair mPSI protocol [26] with a semihonest arbitrator based on HE and OPE. The arbitrator in the protocol can handle conflicts and cannot know the user's private input and output. The mPSI protocol in [11] is constructed by HE and mutual oblivious pseudorandom function (mOPRF). The fairness of the mOPRF ensures the fairness of the protocol. And in the standard model, it has been proven to resist the attack of malicious adversaries. In [12], an mPSI protocol with linear communication and computational overhead is constructed by using prime order group. The protocol uses a distributed ElGamal encryption algorithm and an offline semitrusted third party to achieve the fairness of the protocol and the security under the malicious adversary model. The mPSI protocol in [13] uses multiplicative HE and a distributed ElGamal cryptosystem to protect data privacy and uses an offline semihonest arbiter to achieve fairness. Under the decisional Diffie-Herman hypothesis, it is proved that the protocol is safe under the malicious adversary model.We show the differences between these protocols in Table1.Table 1
Difference between the mentioned protocols.
TypeReferenceStructureAdversary modelFairnessPublic key[12]HEMaliciousYes[13]HEMaliciousYes[16]FHE + BFSemihonestNo[23]HE + OPEMaliciousYes[24]HE + OPE + CLSMaliciousYes[25]HE + PRSemihonestYes[26]HE + OPEMaliciousYesGarbled circuit[17]GCSemihonestNo[18]GC + OPPRFSemihonestNoOblivious transfer[11]mOPRF + HEMaliciousYes[14]hash + OPRFSemihonestNo[19]OPRF + garbled BFSemihonestNoCloud computing[20]HE + OPESemihonestNo[21]Hash + OPESemihonestNo[22]Hash + OPESemihonestNo


## 3. Preliminaries

### 3.1. Decisional Diffie-Hellman Assumption

Definition 1.
LetG be a cyclic group of prime order p, g is the generator of G, and a,b←ZRp. For the following two four-tuple distributions: R=g,ga,gb,gc∈G4, D=g,ga,gb,gab∈G4, and for any probability polynomial time (PPT) adversary A when distinguishing between R and D, its advantage AdvADDHλ=PrAR=1−PrAD=1 is negligible with security parameter λ, where R is a random four-tuple and D is a Diffie-Hellman four-tuple.


### 3.2. Security Model

#### 3.2.1. Adversary Model

We consider the environment where a PPT adversaryA exists; the definition and model follow [27]. In this setting, the adversary A can eavesdrop on the messages transmitted through the communication channel and allow A to corrupt participant to obtain private key. The capabilities of the adversary A are shown in Table 2.Table 2
Capabilities of the adversary.
TypesDescriptionsC1A can learn the messages transmitted in the communication channel.C2A can corrupt one of the two participants to obtain its secret data and private key.C3A can collude with dishonest edge server S to obtain the information stored in the server.


#### 3.2.2. Formal Security Model

We mainly describe the formal security model of the O-mPSI protocol in this section. It is based on the model in [28] and we made some modifications according to the specific requirements of the O-mPSI protocol.Initialization. In a two-party set intersection scheme O-mPSI, three entities are involved, that is, two participants P1,P2∈User and an edge server S∈Server. Each of them may have several instances called oracle, which involve different, concurrent executions of O-mPSI. We denote user instances as P1i,P2ii∈Z, server instances as Si, and any kind of instance as U∈User∪Server. In addition, P1 holds key pair pk1,sk1, P2 has key pair pk2,sk2, and pk is the system public key.Queries. The adversary A only interacts with the participants of the protocol through oracle queries, which simulates the capabilities of adversary A in a real attack. And all possible oracle queries are shown below:(1)
Execute (P1i,P2i,Si): The adversary’s eavesdropping attack is simulated in this oracle query (see C1 in Table 2), and the messages exchanged during the actual implementation of the O-mPSI protocol are returned.(2)
Send (U,m): A sends a message to instance U in this query; then the response generated by U processing m based on O-mPSI protocol is returned.(3)
Corrupt (U,a): The corruption ability of the adversary is simulated in this query (see C2 in Table 2). A can only corrupt one of the two users, not both.Ifa=1, it returns the private key sk1 and data set X of P1.Ifa=2, it returns the private key sk2 and data set Y of P2.(4)
Collude (S): The collusion ability of adversary A is simulated in this query (i.e., C3 in Table 2). Any information stored on the server is returned.(5)
Reveal (U): The system private key shared by the instances P1i and P2i is returned to the adversary in this query. But instances P1i, P2i and their partner Si must not have been queried by corrupt-query and test-query; otherwise it returns ⊥.(6)
Challenge (U,m0,m1): In this query, A selects two messages m0 and m1 of equal length and sends them to instance U. The instance U selects b←R0,1 randomly, then encrypts mb, and returns the ciphertext c. Among them, P1i, P2i, and Si in U have not been inquired by corrupt-query and reveal-query; otherwise it returns ⊥. And this query is called only once during execution.(7)
Test (U): After querying the oracle, if the guessed bit b′=b, return 1; otherwise return 0. This query can only point to the instance in the challenge-query and is called only once during execution.IND-CPA security. During the execution of the O-mPSI protocol, A can require polynomial degree to execute, send, corrupt, collude, and reveal queries. A can also send a challenge-query and a test-query to an instance that has not been queried. At the end of the game execution, for the bit b in the challenge-query, A outputs a guess bit b′ in the test-query. If b′=b, it means that A wins and it is recorded as Succ. The advantage that the adversary A can destroy the IND-CPA security of O-mPSI protocol is defined as(1)AdvO−mPSIIND−CPAA=PrSuccA−12=Prb′=b−12.Definition 2.
For any PPT adversaryA, if there is a negligible function ε⋅ such that AdvO−mPSIIND−CPAAPrSuccA−1/2≤ελ, then the O-mPSI protocol is IND-CPA secure.


### 3.3. Hash Algorithm

Cuckoo hashing. Cuckoo hashing [29] is a method to solve hash conflict, which is widely used in PSI protocols. In this hashing technique, two hash functions h1,h2:0,1∗⟶1,…,m are used to map n elements into m bins, where each bin has at most b elements. When storing an element x in the cuckoo hash table, calculate the two bin positions h1x and h2x corresponding to x. If both bins are not full, insert x into either of them; if one of the two bins is full and the other is not full, then insert x into the bin that is not full; if both bins are full, then randomly select a position to kick out one of the elements y and then insert x into it; the kicked y is reinserted into the cuckoo table using the same algorithm. This process is called relocation, and the relocation process is executed recursively until all elements are stored in the cuckoo hash table.Simple hashing. This hashing technique is similar to cuckoo hashing. Two hash functions h1,h2:0,1∗⟶1,…,m are used to map n elements into m bins, and each bin also has at most b elements. However, in simple hash mapping, when the element x is mapped to its corresponding two positions h1x and h2x, the elements are stored in both h1x and h2x.


### 3.4. ElGamal Threshold Encryption Algorithm

The ElGamal threshold encryption algorithm [30] is implemented according to the additive homomorphism of the ElGamal encryption algorithm, which is composed of KeyGen, Encrypt, Decrypt, and Rerandomize four algorithms. The specific algorithm is as follows:KeyGen. Given a cyclic group G of order p and its generator g, the security parameter is λ. Parties P1 and P2 randomly select ski←Ζpi=1,2 and then compute pki=gskimodp, where ski is their respective private key, and pki is their respective public key. Then the public key of the threshold encryption scheme is pk=pk1⋅pk2.Encrypt. For a message m, map m to Hm using the hash function H⋅, where H⋅ is defined as 0,1∗⟶G. Then select a random number r1, and compute the ciphertext of the message m as ct=gm⋅pkr1modp.Decrypt. For a ciphertext ct, P1 half-decrypts it as ct′=gm⋅pkr1/gr1sk1modp; then P2 fully decrypts ct′ as gm=ct′/gr1sk2modp.Rerandomize. For the given ciphertext ct, select a random number r2 to rerandomize it to ct∗=gm⋅pkr1⋅pkr2=gm⋅pkr1+r2.


## 3.1. Decisional Diffie-Hellman Assumption

Definition 1.
LetG be a cyclic group of prime order p, g is the generator of G, and a,b←ZRp. For the following two four-tuple distributions: R=g,ga,gb,gc∈G4, D=g,ga,gb,gab∈G4, and for any probability polynomial time (PPT) adversary A when distinguishing between R and D, its advantage AdvADDHλ=PrAR=1−PrAD=1 is negligible with security parameter λ, where R is a random four-tuple and D is a Diffie-Hellman four-tuple.


## 3.2. Security Model

### 3.2.1. Adversary Model

We consider the environment where a PPT adversaryA exists; the definition and model follow [27]. In this setting, the adversary A can eavesdrop on the messages transmitted through the communication channel and allow A to corrupt participant to obtain private key. The capabilities of the adversary A are shown in Table 2.Table 2
Capabilities of the adversary.
TypesDescriptionsC1A can learn the messages transmitted in the communication channel.C2A can corrupt one of the two participants to obtain its secret data and private key.C3A can collude with dishonest edge server S to obtain the information stored in the server.


### 3.2.2. Formal Security Model

We mainly describe the formal security model of the O-mPSI protocol in this section. It is based on the model in [28] and we made some modifications according to the specific requirements of the O-mPSI protocol.Initialization. In a two-party set intersection scheme O-mPSI, three entities are involved, that is, two participants P1,P2∈User and an edge server S∈Server. Each of them may have several instances called oracle, which involve different, concurrent executions of O-mPSI. We denote user instances as P1i,P2ii∈Z, server instances as Si, and any kind of instance as U∈User∪Server. In addition, P1 holds key pair pk1,sk1, P2 has key pair pk2,sk2, and pk is the system public key.Queries. The adversary A only interacts with the participants of the protocol through oracle queries, which simulates the capabilities of adversary A in a real attack. And all possible oracle queries are shown below:(1)
Execute (P1i,P2i,Si): The adversary’s eavesdropping attack is simulated in this oracle query (see C1 in Table 2), and the messages exchanged during the actual implementation of the O-mPSI protocol are returned.(2)
Send (U,m): A sends a message to instance U in this query; then the response generated by U processing m based on O-mPSI protocol is returned.(3)
Corrupt (U,a): The corruption ability of the adversary is simulated in this query (see C2 in Table 2). A can only corrupt one of the two users, not both.Ifa=1, it returns the private key sk1 and data set X of P1.Ifa=2, it returns the private key sk2 and data set Y of P2.(4)
Collude (S): The collusion ability of adversary A is simulated in this query (i.e., C3 in Table 2). Any information stored on the server is returned.(5)
Reveal (U): The system private key shared by the instances P1i and P2i is returned to the adversary in this query. But instances P1i, P2i and their partner Si must not have been queried by corrupt-query and test-query; otherwise it returns ⊥.(6)
Challenge (U,m0,m1): In this query, A selects two messages m0 and m1 of equal length and sends them to instance U. The instance U selects b←R0,1 randomly, then encrypts mb, and returns the ciphertext c. Among them, P1i, P2i, and Si in U have not been inquired by corrupt-query and reveal-query; otherwise it returns ⊥. And this query is called only once during execution.(7)
Test (U): After querying the oracle, if the guessed bit b′=b, return 1; otherwise return 0. This query can only point to the instance in the challenge-query and is called only once during execution.IND-CPA security. During the execution of the O-mPSI protocol, A can require polynomial degree to execute, send, corrupt, collude, and reveal queries. A can also send a challenge-query and a test-query to an instance that has not been queried. At the end of the game execution, for the bit b in the challenge-query, A outputs a guess bit b′ in the test-query. If b′=b, it means that A wins and it is recorded as Succ. The advantage that the adversary A can destroy the IND-CPA security of O-mPSI protocol is defined as(1)AdvO−mPSIIND−CPAA=PrSuccA−12=Prb′=b−12.Definition 2.
For any PPT adversaryA, if there is a negligible function ε⋅ such that AdvO−mPSIIND−CPAAPrSuccA−1/2≤ελ, then the O-mPSI protocol is IND-CPA secure.


## 3.2.1. Adversary Model

We consider the environment where a PPT adversaryA exists; the definition and model follow [27]. In this setting, the adversary A can eavesdrop on the messages transmitted through the communication channel and allow A to corrupt participant to obtain private key. The capabilities of the adversary A are shown in Table 2.Table 2
Capabilities of the adversary.
TypesDescriptionsC1A can learn the messages transmitted in the communication channel.C2A can corrupt one of the two participants to obtain its secret data and private key.C3A can collude with dishonest edge server S to obtain the information stored in the server.


## 3.2.2. Formal Security Model

We mainly describe the formal security model of the O-mPSI protocol in this section. It is based on the model in [28] and we made some modifications according to the specific requirements of the O-mPSI protocol.Initialization. In a two-party set intersection scheme O-mPSI, three entities are involved, that is, two participants P1,P2∈User and an edge server S∈Server. Each of them may have several instances called oracle, which involve different, concurrent executions of O-mPSI. We denote user instances as P1i,P2ii∈Z, server instances as Si, and any kind of instance as U∈User∪Server. In addition, P1 holds key pair pk1,sk1, P2 has key pair pk2,sk2, and pk is the system public key.Queries. The adversary A only interacts with the participants of the protocol through oracle queries, which simulates the capabilities of adversary A in a real attack. And all possible oracle queries are shown below:(1)
Execute (P1i,P2i,Si): The adversary’s eavesdropping attack is simulated in this oracle query (see C1 in Table 2), and the messages exchanged during the actual implementation of the O-mPSI protocol are returned.(2)
Send (U,m): A sends a message to instance U in this query; then the response generated by U processing m based on O-mPSI protocol is returned.(3)
Corrupt (U,a): The corruption ability of the adversary is simulated in this query (see C2 in Table 2). A can only corrupt one of the two users, not both.Ifa=1, it returns the private key sk1 and data set X of P1.Ifa=2, it returns the private key sk2 and data set Y of P2.(4)
Collude (S): The collusion ability of adversary A is simulated in this query (i.e., C3 in Table 2). Any information stored on the server is returned.(5)
Reveal (U): The system private key shared by the instances P1i and P2i is returned to the adversary in this query. But instances P1i, P2i and their partner Si must not have been queried by corrupt-query and test-query; otherwise it returns ⊥.(6)
Challenge (U,m0,m1): In this query, A selects two messages m0 and m1 of equal length and sends them to instance U. The instance U selects b←R0,1 randomly, then encrypts mb, and returns the ciphertext c. Among them, P1i, P2i, and Si in U have not been inquired by corrupt-query and reveal-query; otherwise it returns ⊥. And this query is called only once during execution.(7)
Test (U): After querying the oracle, if the guessed bit b′=b, return 1; otherwise return 0. This query can only point to the instance in the challenge-query and is called only once during execution.IND-CPA security. During the execution of the O-mPSI protocol, A can require polynomial degree to execute, send, corrupt, collude, and reveal queries. A can also send a challenge-query and a test-query to an instance that has not been queried. At the end of the game execution, for the bit b in the challenge-query, A outputs a guess bit b′ in the test-query. If b′=b, it means that A wins and it is recorded as Succ. The advantage that the adversary A can destroy the IND-CPA security of O-mPSI protocol is defined as(1)AdvO−mPSIIND−CPAA=PrSuccA−12=Prb′=b−12.Definition 2.
For any PPT adversaryA, if there is a negligible function ε⋅ such that AdvO−mPSIIND−CPAAPrSuccA−1/2≤ελ, then the O-mPSI protocol is IND-CPA secure.


## 3.3. Hash Algorithm

Cuckoo hashing. Cuckoo hashing [29] is a method to solve hash conflict, which is widely used in PSI protocols. In this hashing technique, two hash functions h1,h2:0,1∗⟶1,…,m are used to map n elements into m bins, where each bin has at most b elements. When storing an element x in the cuckoo hash table, calculate the two bin positions h1x and h2x corresponding to x. If both bins are not full, insert x into either of them; if one of the two bins is full and the other is not full, then insert x into the bin that is not full; if both bins are full, then randomly select a position to kick out one of the elements y and then insert x into it; the kicked y is reinserted into the cuckoo table using the same algorithm. This process is called relocation, and the relocation process is executed recursively until all elements are stored in the cuckoo hash table.Simple hashing. This hashing technique is similar to cuckoo hashing. Two hash functions h1,h2:0,1∗⟶1,…,m are used to map n elements into m bins, and each bin also has at most b elements. However, in simple hash mapping, when the element x is mapped to its corresponding two positions h1x and h2x, the elements are stored in both h1x and h2x.


## 3.4. ElGamal Threshold Encryption Algorithm

The ElGamal threshold encryption algorithm [30] is implemented according to the additive homomorphism of the ElGamal encryption algorithm, which is composed of KeyGen, Encrypt, Decrypt, and Rerandomize four algorithms. The specific algorithm is as follows:KeyGen. Given a cyclic group G of order p and its generator g, the security parameter is λ. Parties P1 and P2 randomly select ski←Ζpi=1,2 and then compute pki=gskimodp, where ski is their respective private key, and pki is their respective public key. Then the public key of the threshold encryption scheme is pk=pk1⋅pk2.Encrypt. For a message m, map m to Hm using the hash function H⋅, where H⋅ is defined as 0,1∗⟶G. Then select a random number r1, and compute the ciphertext of the message m as ct=gm⋅pkr1modp.Decrypt. For a ciphertext ct, P1 half-decrypts it as ct′=gm⋅pkr1/gr1sk1modp; then P2 fully decrypts ct′ as gm=ct′/gr1sk2modp.Rerandomize. For the given ciphertext ct, select a random number r2 to rerandomize it to ct∗=gm⋅pkr1⋅pkr2=gm⋅pkr1+r2.


## 4. Outsourced Mutual PSI Protocol

### 4.1. Overview

The system model of O-mPSI protocol is shown in Figure1. There are three entities involved, two participating users P1,P2 and a semihonest edge server S. Among them, P1 has private data set X=x1,…xn1 and user P2 has private data set Y=y1,…,yn2. They hope to calculate the intersection X∩Y of X and Y through the server S without revealing their own set information.Figure 1
System model of O-mPSI protocol.The design idea of our protocol is based on [14], where P1 and P2 select three hash functions h1,h2,h3:0,1∗⟶1,…,m to generate three hash bin positions corresponding to the set elements in the hash table. P1 uses the cuckoo hashing to select one of the three bins to map each element in the set X to hash table T1, each bin stores one element, and the remaining elements are stored in the stash ST. P2 uses simple hashing to map each element in set Y to the corresponding three bins in hash table T2, and each bin stores b elements. Then, the elements in the hash bin of T1 are compared with the elements in the corresponding hash bin of T2. And each element in the stash ST is compared to all elements in set Y. In this way, the comparison times of elements are reduced from On2 to On, and the intersection X∩Y is all the equal elements obtained by comparison.But we diverge from the protocol of [14] in the method. In our protocol, parties P1 and P2 agree on two hash functions h1,h2:0,1∗⟶1,…,m to generate the two hash bin positions corresponding to the set elements in the hash table. In this way, the elements in the set Y of P2 only need to be stored twice, which saves storage space and reduces the subsequent computational burden. Moreover, our protocol sets the size of each bin of hash table T1 to b. This avoids that the elements cannot be stored in the hash table T1 due to too many relocations when hash conflicts occur, so there is no need to increase the stash to store the elements. Therefore, it is only necessary to compare the elements in the bin of T1 with the elements in the corresponding bin of T2 to obtain the intersection. This further decreases the number of comparisons and reduces the complexity of the protocol.However, there is still a problem of how to protect the privacy of user set information while calculating the intersection correctly. We use the ElGamal threshold encryption algorithm to solve this problem, as shown in Section4.2.1. Participant Paa=1,2 uses the public key pk to encrypt the elements in the hash table Ta and then sends it to the other party to rerandomize. Combined with the hash algorithm, we can see that, for ∀xi∈X in the hash bin of T1, if the same element yj∈Y in T2 is stored in the corresponding hash bin, there must be E∗xi=E∗yj in the two hash bins with the same bin number. Therefore, the use of ElGamal threshold encryption algorithm enables the comparison operation of elements to be performed in the form of ciphertext and ensures that the encrypted results of equal elements on both sides are the same. It creates conditions for the smooth implementation of intersection calculation.In addition, in order to decrease the computational burden of both parties, the element comparison work is handed over to the edge server. Specifically,Paa=1,2 sends the hash table encrypted by the ElGamal encryption algorithm to the server. Then the server compares the elements in the two hash tables in a bin-to-bin manner in the form of ciphertext. That is, it compares the elements in the hash bin of T1 with the elements in the corresponding hash bin of T2. In this way, all the equal ciphertext elements in the m bins are the intersection X∩Y in the ciphertext form. Then P1 and P2 cooperate to decrypt the intersection in the form of ciphertext in parallel, and the plaintext intersection X∩Y can be obtained at the same time. Among them, the comparison work of m bins can be performed in parallel, which reduces the time overhead of O-mPSI protocol.


### 4.2. O-mPSI Protocol

In this section, we introduce the proposed O-mPSI protocol. For easier understanding, we divide the protocol into two parts: the data encryption part and the set intersection computation part, which are introduced in the following two subsections, respectively.


#### 4.2.1. ElGamal Threshold Encryption Protocol

In this section, we describe how ElGamal threshold encryption algorithm works in the protocol, and the details are shown in Algorithm1.Algorithm 1: ElGamal threshold encryption protocol.
Inputs:P1: The cuckoo hash table T1P2: The hash table T2Output: the encrypted cuckoo hash tablectT1∗ and ctT2∗.Key generation phaseP1 and P2 calculate as below:1. Determine a hash functionH:0,1∗⟶G.2. Run theKeyGen algorithm in ElGamal threshold encryption to generate the key pairs pki,ski,i=1,2.3. Publish the public keyspkii=1,2 and keep the private key skii=1,2.4. Each party computespk=pk1⋅pk2.Encryption phase1.P1 encrypts the cuckoo hash table T1 by bins, for all k∈m, P1 computes as follows:(1) choose a random numberr1k, for all items xiki=1,…,b in the kth cuckoo hash table T1k, using ElGamal threshold encryption algorithm to encrypt them: ctT1k=Exik=gr1k,gHxik⋅pkr1k(2) sendsctT1=ctT11,…,ctT1m to P2 in shuffled order.2.P2 encrypts the hash table T2 by bins, for all k∈m, P2 computes as follows:(1) choose a random numberr2k, for all items yiki=1,…,b in the kth hash table T2k, using ElGamal threshold encryption algorithm to encrypt them: ctT2k=Eyik=gr2k,gHyik⋅pkr2k(2) sendsctT2=ctT21,…,ctT2m to P1 in shuffled order.3.P1 re-randomizes the received ctT2 by bins. For all k∈m and ∀i∈b , P1 computes as follows: ctT2k∗=E∗yik=gr1k+r2k,gHyik⋅pkr1k+r2k.ThenctT2∗=ctT21∗,…,ctT2m∗.4.P2 re-randomizes the received ctT1 by bins. For all k∈m and ∀i∈b, P2 computes as follows: ctT1k∗=E∗xik=gr1k+r2k,gHxik⋅pkr1k+r2kThenctT1∗=ctT11∗,…,ctT1m∗.Remark 1.
In the key generation phase, partiesP1 and P2 jointly generate the public key pk so that both parties can use the same public key for encryption in the subsequent encryption phase.Remark 2.
In the encryption phase, after encrypting the hash table, each partyPii=1,2 needs to send ctTi to the other party for rerandomization. Because each party privately chose a random number for encryption, two equal elements are encrypted differently by the two parties. In addition, to calculate the set intersection correctly, adding the rerandomization operation performed by the other party to make the encryption results of equal elements the same is necessary.


#### 4.2.2. Outsourced Two-Party Set Intersection Protocol

In this section, we will explain the intersection calculation part of the O-mPSI protocol. Detailed description can be seen in Algorithm2.Algorithm 2: Outsourced two-party set intersection protocol.
Inputs:P1: Set X=x1,…,xn1P2: Set Y=y1,…,yn2Output: The intersection setI, where I=X∩Y.Data storage phase:1.P1 and P2 determine the number m of bins, the size b of bins and the two hash functions h1,h2:0,1∗⟶1,…,m.2. Forxi∈X, i∈n1, P1 computes the two bin positions h1xi and h2xi corresponding to xi, and inserts xi into one of them. P1 fills the bin with less than b elements with dummy elements, then generates the cuckoo hash table T1.3. Foryj∈Y, j∈n2, P2 computes the bin positions h1yj and h2yj corresponding to yj, and inserts yj into both of them. P2 fills the bin with less than b elements with dummy elements, then generates the hash table T2.Data encryption phase:1.P1 calls the ElGamal threshold encryption protocol to compute the encrypted hash table ctT2∗, and then sends ctT2∗ to the server in shuffled order.2.P2 calls the ElGamal threshold encryption protocol to compute the encrypted cuckoo hash table ctT1∗, and then sends ctT1∗ to the server in shuffled order.Intersection calculation phase:1. After thectT1∗ and ctT2∗ are received, the server proceeds as follows:(1) computes the encrypted set intersection by bins: fork∈m, computes ctIk=ctT1k∗∩ctT2k∗.(2) then the final encrypted intersectionctI=ctI1∪ctI2∪⋯∪ctIm.(3) publishingctI=X∩Y..2. After receivingctI, the users P1, P2 and the server proceed as follows:(1) each partyPii=1,2 half-decrypts ctI to ctIi′ using its private key, and then sends ctIi′ to the server.(2) then the server sendsctI2′ to P1 and sends ctI1′ to P2.Each party fully decrypts the received other party half-decrypted intersection, and gets the plaintext intersection setI=z1,…,zw.Remark 3.
In the data storage phase,P1 hashes all its elements into one of its two corresponding bins, and each element is stored in only one bin. P2 hashes all its elements into both of its two corresponding bins, and each element is stored in both bins. In this case, suppose that there is xi=yj (xi∈X and yj∈Y); the two bin positions h1xi and h2xi corresponding to x are the same as the two bin positions h1yj and h2yj corresponding to y. Then no matter which bin(h1xi or h2xi) x is stored in, the corresponding element y can be found in the two bins h1yj and h2yj. Therefore, it can be known that storing all elements in set Y in both bins can avoid missing intersection elements when computing the set intersection.Remark 4.
In the data encryption phase, partiesP1 and P2 use the ElGamal threshold encryption algorithm in Section 4.2.1 to encrypt the elements in their hash table and at the same time add a permutation sequence, so that both parties cannot know the specific location of the element. After hash tables T1 and T2 undergo the same permutation process, their bin numbers still correspond, so the intersection can be calculated correctly by the bins.Remark 5.
In the intersection calculation phase, if the server continues to calculate on the encrypted intersection according to the addition homomorphism of ElGamal homomorphism encryption algorithm, the encrypted intersection sum can be obtained. Then continuing step 2, the plaintext intersection sum will be obtained by bothP1 and P2.


## 4.1. Overview

The system model of O-mPSI protocol is shown in Figure1. There are three entities involved, two participating users P1,P2 and a semihonest edge server S. Among them, P1 has private data set X=x1,…xn1 and user P2 has private data set Y=y1,…,yn2. They hope to calculate the intersection X∩Y of X and Y through the server S without revealing their own set information.Figure 1
System model of O-mPSI protocol.The design idea of our protocol is based on [14], where P1 and P2 select three hash functions h1,h2,h3:0,1∗⟶1,…,m to generate three hash bin positions corresponding to the set elements in the hash table. P1 uses the cuckoo hashing to select one of the three bins to map each element in the set X to hash table T1, each bin stores one element, and the remaining elements are stored in the stash ST. P2 uses simple hashing to map each element in set Y to the corresponding three bins in hash table T2, and each bin stores b elements. Then, the elements in the hash bin of T1 are compared with the elements in the corresponding hash bin of T2. And each element in the stash ST is compared to all elements in set Y. In this way, the comparison times of elements are reduced from On2 to On, and the intersection X∩Y is all the equal elements obtained by comparison.But we diverge from the protocol of [14] in the method. In our protocol, parties P1 and P2 agree on two hash functions h1,h2:0,1∗⟶1,…,m to generate the two hash bin positions corresponding to the set elements in the hash table. In this way, the elements in the set Y of P2 only need to be stored twice, which saves storage space and reduces the subsequent computational burden. Moreover, our protocol sets the size of each bin of hash table T1 to b. This avoids that the elements cannot be stored in the hash table T1 due to too many relocations when hash conflicts occur, so there is no need to increase the stash to store the elements. Therefore, it is only necessary to compare the elements in the bin of T1 with the elements in the corresponding bin of T2 to obtain the intersection. This further decreases the number of comparisons and reduces the complexity of the protocol.However, there is still a problem of how to protect the privacy of user set information while calculating the intersection correctly. We use the ElGamal threshold encryption algorithm to solve this problem, as shown in Section4.2.1. Participant Paa=1,2 uses the public key pk to encrypt the elements in the hash table Ta and then sends it to the other party to rerandomize. Combined with the hash algorithm, we can see that, for ∀xi∈X in the hash bin of T1, if the same element yj∈Y in T2 is stored in the corresponding hash bin, there must be E∗xi=E∗yj in the two hash bins with the same bin number. Therefore, the use of ElGamal threshold encryption algorithm enables the comparison operation of elements to be performed in the form of ciphertext and ensures that the encrypted results of equal elements on both sides are the same. It creates conditions for the smooth implementation of intersection calculation.In addition, in order to decrease the computational burden of both parties, the element comparison work is handed over to the edge server. Specifically,Paa=1,2 sends the hash table encrypted by the ElGamal encryption algorithm to the server. Then the server compares the elements in the two hash tables in a bin-to-bin manner in the form of ciphertext. That is, it compares the elements in the hash bin of T1 with the elements in the corresponding hash bin of T2. In this way, all the equal ciphertext elements in the m bins are the intersection X∩Y in the ciphertext form. Then P1 and P2 cooperate to decrypt the intersection in the form of ciphertext in parallel, and the plaintext intersection X∩Y can be obtained at the same time. Among them, the comparison work of m bins can be performed in parallel, which reduces the time overhead of O-mPSI protocol.


## 4.2. O-mPSI Protocol

In this section, we introduce the proposed O-mPSI protocol. For easier understanding, we divide the protocol into two parts: the data encryption part and the set intersection computation part, which are introduced in the following two subsections, respectively.


### 4.2.1. ElGamal Threshold Encryption Protocol

In this section, we describe how ElGamal threshold encryption algorithm works in the protocol, and the details are shown in Algorithm1.Algorithm 1: ElGamal threshold encryption protocol.
Inputs:P1: The cuckoo hash table T1P2: The hash table T2Output: the encrypted cuckoo hash tablectT1∗ and ctT2∗.Key generation phaseP1 and P2 calculate as below:1. Determine a hash functionH:0,1∗⟶G.2. Run theKeyGen algorithm in ElGamal threshold encryption to generate the key pairs pki,ski,i=1,2.3. Publish the public keyspkii=1,2 and keep the private key skii=1,2.4. Each party computespk=pk1⋅pk2.Encryption phase1.P1 encrypts the cuckoo hash table T1 by bins, for all k∈m, P1 computes as follows:(1) choose a random numberr1k, for all items xiki=1,…,b in the kth cuckoo hash table T1k, using ElGamal threshold encryption algorithm to encrypt them: ctT1k=Exik=gr1k,gHxik⋅pkr1k(2) sendsctT1=ctT11,…,ctT1m to P2 in shuffled order.2.P2 encrypts the hash table T2 by bins, for all k∈m, P2 computes as follows:(1) choose a random numberr2k, for all items yiki=1,…,b in the kth hash table T2k, using ElGamal threshold encryption algorithm to encrypt them: ctT2k=Eyik=gr2k,gHyik⋅pkr2k(2) sendsctT2=ctT21,…,ctT2m to P1 in shuffled order.3.P1 re-randomizes the received ctT2 by bins. For all k∈m and ∀i∈b , P1 computes as follows: ctT2k∗=E∗yik=gr1k+r2k,gHyik⋅pkr1k+r2k.ThenctT2∗=ctT21∗,…,ctT2m∗.4.P2 re-randomizes the received ctT1 by bins. For all k∈m and ∀i∈b, P2 computes as follows: ctT1k∗=E∗xik=gr1k+r2k,gHxik⋅pkr1k+r2kThenctT1∗=ctT11∗,…,ctT1m∗.Remark 1.
In the key generation phase, partiesP1 and P2 jointly generate the public key pk so that both parties can use the same public key for encryption in the subsequent encryption phase.Remark 2.
In the encryption phase, after encrypting the hash table, each partyPii=1,2 needs to send ctTi to the other party for rerandomization. Because each party privately chose a random number for encryption, two equal elements are encrypted differently by the two parties. In addition, to calculate the set intersection correctly, adding the rerandomization operation performed by the other party to make the encryption results of equal elements the same is necessary.


### 4.2.2. Outsourced Two-Party Set Intersection Protocol

In this section, we will explain the intersection calculation part of the O-mPSI protocol. Detailed description can be seen in Algorithm2.Algorithm 2: Outsourced two-party set intersection protocol.
Inputs:P1: Set X=x1,…,xn1P2: Set Y=y1,…,yn2Output: The intersection setI, where I=X∩Y.Data storage phase:1.P1 and P2 determine the number m of bins, the size b of bins and the two hash functions h1,h2:0,1∗⟶1,…,m.2. Forxi∈X, i∈n1, P1 computes the two bin positions h1xi and h2xi corresponding to xi, and inserts xi into one of them. P1 fills the bin with less than b elements with dummy elements, then generates the cuckoo hash table T1.3. Foryj∈Y, j∈n2, P2 computes the bin positions h1yj and h2yj corresponding to yj, and inserts yj into both of them. P2 fills the bin with less than b elements with dummy elements, then generates the hash table T2.Data encryption phase:1.P1 calls the ElGamal threshold encryption protocol to compute the encrypted hash table ctT2∗, and then sends ctT2∗ to the server in shuffled order.2.P2 calls the ElGamal threshold encryption protocol to compute the encrypted cuckoo hash table ctT1∗, and then sends ctT1∗ to the server in shuffled order.Intersection calculation phase:1. After thectT1∗ and ctT2∗ are received, the server proceeds as follows:(1) computes the encrypted set intersection by bins: fork∈m, computes ctIk=ctT1k∗∩ctT2k∗.(2) then the final encrypted intersectionctI=ctI1∪ctI2∪⋯∪ctIm.(3) publishingctI=X∩Y..2. After receivingctI, the users P1, P2 and the server proceed as follows:(1) each partyPii=1,2 half-decrypts ctI to ctIi′ using its private key, and then sends ctIi′ to the server.(2) then the server sendsctI2′ to P1 and sends ctI1′ to P2.Each party fully decrypts the received other party half-decrypted intersection, and gets the plaintext intersection setI=z1,…,zw.Remark 3.
In the data storage phase,P1 hashes all its elements into one of its two corresponding bins, and each element is stored in only one bin. P2 hashes all its elements into both of its two corresponding bins, and each element is stored in both bins. In this case, suppose that there is xi=yj (xi∈X and yj∈Y); the two bin positions h1xi and h2xi corresponding to x are the same as the two bin positions h1yj and h2yj corresponding to y. Then no matter which bin(h1xi or h2xi) x is stored in, the corresponding element y can be found in the two bins h1yj and h2yj. Therefore, it can be known that storing all elements in set Y in both bins can avoid missing intersection elements when computing the set intersection.Remark 4.
In the data encryption phase, partiesP1 and P2 use the ElGamal threshold encryption algorithm in Section 4.2.1 to encrypt the elements in their hash table and at the same time add a permutation sequence, so that both parties cannot know the specific location of the element. After hash tables T1 and T2 undergo the same permutation process, their bin numbers still correspond, so the intersection can be calculated correctly by the bins.Remark 5.
In the intersection calculation phase, if the server continues to calculate on the encrypted intersection according to the addition homomorphism of ElGamal homomorphism encryption algorithm, the encrypted intersection sum can be obtained. Then continuing step 2, the plaintext intersection sum will be obtained by bothP1 and P2.


## 4.2.1. ElGamal Threshold Encryption Protocol

In this section, we describe how ElGamal threshold encryption algorithm works in the protocol, and the details are shown in Algorithm1.Algorithm 1: ElGamal threshold encryption protocol.
Inputs:P1: The cuckoo hash table T1P2: The hash table T2Output: the encrypted cuckoo hash tablectT1∗ and ctT2∗.Key generation phaseP1 and P2 calculate as below:1. Determine a hash functionH:0,1∗⟶G.2. Run theKeyGen algorithm in ElGamal threshold encryption to generate the key pairs pki,ski,i=1,2.3. Publish the public keyspkii=1,2 and keep the private key skii=1,2.4. Each party computespk=pk1⋅pk2.Encryption phase1.P1 encrypts the cuckoo hash table T1 by bins, for all k∈m, P1 computes as follows:(1) choose a random numberr1k, for all items xiki=1,…,b in the kth cuckoo hash table T1k, using ElGamal threshold encryption algorithm to encrypt them: ctT1k=Exik=gr1k,gHxik⋅pkr1k(2) sendsctT1=ctT11,…,ctT1m to P2 in shuffled order.2.P2 encrypts the hash table T2 by bins, for all k∈m, P2 computes as follows:(1) choose a random numberr2k, for all items yiki=1,…,b in the kth hash table T2k, using ElGamal threshold encryption algorithm to encrypt them: ctT2k=Eyik=gr2k,gHyik⋅pkr2k(2) sendsctT2=ctT21,…,ctT2m to P1 in shuffled order.3.P1 re-randomizes the received ctT2 by bins. For all k∈m and ∀i∈b , P1 computes as follows: ctT2k∗=E∗yik=gr1k+r2k,gHyik⋅pkr1k+r2k.ThenctT2∗=ctT21∗,…,ctT2m∗.4.P2 re-randomizes the received ctT1 by bins. For all k∈m and ∀i∈b, P2 computes as follows: ctT1k∗=E∗xik=gr1k+r2k,gHxik⋅pkr1k+r2kThenctT1∗=ctT11∗,…,ctT1m∗.Remark 1.
In the key generation phase, partiesP1 and P2 jointly generate the public key pk so that both parties can use the same public key for encryption in the subsequent encryption phase.Remark 2.
In the encryption phase, after encrypting the hash table, each partyPii=1,2 needs to send ctTi to the other party for rerandomization. Because each party privately chose a random number for encryption, two equal elements are encrypted differently by the two parties. In addition, to calculate the set intersection correctly, adding the rerandomization operation performed by the other party to make the encryption results of equal elements the same is necessary.


## 4.2.2. Outsourced Two-Party Set Intersection Protocol

In this section, we will explain the intersection calculation part of the O-mPSI protocol. Detailed description can be seen in Algorithm2.Algorithm 2: Outsourced two-party set intersection protocol.
Inputs:P1: Set X=x1,…,xn1P2: Set Y=y1,…,yn2Output: The intersection setI, where I=X∩Y.Data storage phase:1.P1 and P2 determine the number m of bins, the size b of bins and the two hash functions h1,h2:0,1∗⟶1,…,m.2. Forxi∈X, i∈n1, P1 computes the two bin positions h1xi and h2xi corresponding to xi, and inserts xi into one of them. P1 fills the bin with less than b elements with dummy elements, then generates the cuckoo hash table T1.3. Foryj∈Y, j∈n2, P2 computes the bin positions h1yj and h2yj corresponding to yj, and inserts yj into both of them. P2 fills the bin with less than b elements with dummy elements, then generates the hash table T2.Data encryption phase:1.P1 calls the ElGamal threshold encryption protocol to compute the encrypted hash table ctT2∗, and then sends ctT2∗ to the server in shuffled order.2.P2 calls the ElGamal threshold encryption protocol to compute the encrypted cuckoo hash table ctT1∗, and then sends ctT1∗ to the server in shuffled order.Intersection calculation phase:1. After thectT1∗ and ctT2∗ are received, the server proceeds as follows:(1) computes the encrypted set intersection by bins: fork∈m, computes ctIk=ctT1k∗∩ctT2k∗.(2) then the final encrypted intersectionctI=ctI1∪ctI2∪⋯∪ctIm.(3) publishingctI=X∩Y..2. After receivingctI, the users P1, P2 and the server proceed as follows:(1) each partyPii=1,2 half-decrypts ctI to ctIi′ using its private key, and then sends ctIi′ to the server.(2) then the server sendsctI2′ to P1 and sends ctI1′ to P2.Each party fully decrypts the received other party half-decrypted intersection, and gets the plaintext intersection setI=z1,…,zw.Remark 3.
In the data storage phase,P1 hashes all its elements into one of its two corresponding bins, and each element is stored in only one bin. P2 hashes all its elements into both of its two corresponding bins, and each element is stored in both bins. In this case, suppose that there is xi=yj (xi∈X and yj∈Y); the two bin positions h1xi and h2xi corresponding to x are the same as the two bin positions h1yj and h2yj corresponding to y. Then no matter which bin(h1xi or h2xi) x is stored in, the corresponding element y can be found in the two bins h1yj and h2yj. Therefore, it can be known that storing all elements in set Y in both bins can avoid missing intersection elements when computing the set intersection.Remark 4.
In the data encryption phase, partiesP1 and P2 use the ElGamal threshold encryption algorithm in Section 4.2.1 to encrypt the elements in their hash table and at the same time add a permutation sequence, so that both parties cannot know the specific location of the element. After hash tables T1 and T2 undergo the same permutation process, their bin numbers still correspond, so the intersection can be calculated correctly by the bins.Remark 5.
In the intersection calculation phase, if the server continues to calculate on the encrypted intersection according to the addition homomorphism of ElGamal homomorphism encryption algorithm, the encrypted intersection sum can be obtained. Then continuing step 2, the plaintext intersection sum will be obtained by bothP1 and P2.


## 5. Security Analysis

The security proof of the O-mPSI protocol based on decisional Diffie-Hellman (DDH) assumption is shown in this section.Theorem 1.
LetGbe a represented group of orderp. LetAbe a PPT adversary against the IND-CPA security within a time limitt, andAcan sendqsendsend-queries,qexeexecute-queries, andqhrandom oracle queries at most. Then we can get(2)AdvO−mPSIIND−CPAA≤qhAdvADDHt+1/3⋅qsend+qexe+1p2+qh2+1/3⋅qsend+qexe22p.Proof.
LetA be the adversary against the IND-CPA security of O-mPSI protocol. Then construct PPT adversaries to attack the DDH assumption through A. If A can break the IND-CPA security, then at least one PPT adversary has successfully broken the DDH assumption. We utilize hybrid games to prove Theorem 1. The game starts from the real attack and ends when the adversary does not have any advantage. An event Succn is defined for each game Gn0≤n≤4, which indicates that A guesses the bit b in the test-query correctly.(1)
GameG0: The game G0 corresponds to a real attack in the random oracle model. According to Definition 2, we can get(3)AdvO−mPSIIND−CPAA=PrSucc0−12.(2)
GameG1: We simulate the random oracle H:0,1∗⟶G (and there is also a random oracle H′ that will appear in G3) in G1 by maintaining hash list L (and L′) as usual. Besides, Send, Execute, Corrupt, Collude, Reveal, Challenge, and Test oracles will be simulated as in the real attack (see Table 3). It is easy to know that G1 is completely indistinguishable from the real attack, so that(4)PrSucc1−PrSucc0=0.(3)
GameG2: Like G1, we simulate all oracles in G2, except for games where some collisions occur: Hx and Hy. Because x or y is simulated, they are randomly and uniformly selected. Therefore, from the birthday paradox, we know that(5)PrSucc2−PrSucc1≤qh2+1/3⋅qsend+qexe22p.(4)
GameG3: In G3, we use the private oracles H′ instead of the oracle H to calculate sctT1 and sctT2, which are completely independent of ctT1 and ctT2. The games G3 and G2 are indistinguishable unless the event AskH3 occurs: A queries the hash function H for ctT1 or ctT2. In addition, no matter what bit b in challenge-query is, the answer is random. Therefore, it can be see that(6)PrSucc3−PrSucc2≤PrAskH3PrSucc3=12.(5)
GameG4: In G4 , we simulate the executions through the random self-reducibility of the Diffie-Hellman problem, and given one DDH instance A=gx,B=gy, we randomly select α,β∈Zp and let Ex=Aα, Ey=Bβ, so we can get a quadruple DDHg,A,B,DDHEx,Ey. Then we have(7)DDHEx,Ey=DDHAα,Bβ=DDHA,Bαβ.
Moreover,AskH4 means that the adversary A had queried the random oracle H on Ex or Ey. Then we get(8)PrAskH3=PrAskH4PrAskH4≤qhAdvADDHt+1/3⋅qsend+qexe+1p2.
According to the above equations, we can conclude that(9)AdvO−mPSIIND−CPAA≤qhAdvADDHt+1/3⋅qsend+qexe+1p2+qh2+1/3⋅qsend+qexe22p.
The simulation queries involved in the protocol are as follows.Table 3
Simulation of the queries in O-mPSI protocol.
NumberQueries(1)HashHm (or H′m): If there is a record m,r existing in list L, return r. Otherwise, select a random number r∈G to return, and add the record m,r to the list L (or list L′).(2)Send (Pi, a, start): For each of the m hash bins, if a=1, choose a random number r1kk∈m, compute Exk=gHxk⋅pkr1k, and then return ctT1=ctT11,…,ctT1m; if a=2, choose a random number r2k, compute Eyk=gHyk⋅pkr2k, and then return ctT2=ctT21,…,ctT2m.(3)Send (Pi,a,ctTa): For k∈m, if a=1, compute E∗yk=gHyk⋅pkr1k+r2k, and then return ctT2∗=ctT21∗,…,ctT2m∗; if a=2, compute E∗xk=gHxk⋅pkr1k+r2k, and then return ctT1∗=ctT11∗,…,ctT1m∗.(4)Send (Si, (ctT1∗, ctT2∗)): For each of the m hash bins, compute ctIk=ctT1k∗∩ctT2k∗ and ctI=ctI1∪ctI2∪⋯∪ctIm. Then return ctI.(5)Execute (P1i,P2i,Si): According to the successive simulations of the send-queries, return ctT1← send-query (P1i, start), ctT2← send-query (P2i, start), ctT2∗← send-query (P1i, ctT2), ctT1∗← send-query (P2i, ctT1), and ctI← send-query (Si, (ctT1∗, ctT2∗)).(6)Corrupt (Ui,a): Return sk1 and X if a=1; return sk2 and Y if a=2.(7)Collude (Si): Return ctT1∗, ctT2∗, and ctI of Si.(8)Reveal (Ui): Compute sk=sk1+sk2 and return the private key sk of P1i and P2i.(9)Challenge (Ui,m0,m1): The instance Ui randomly selects b←R0,1, then computes Emb=gr,gHmb⋅pkr, and returns the Emb.(10)Test-query (Ui): According to the Emb obtained from challenge-query, A outputs a guess bit b′. If b′=b, return 1; otherwise return 0.


## 6. Performance Evaluation

### 6.1. Theoretical Evaluation

In this section, regarding the complexity of calculation and communication, we compare the O-mPSI protocol with the protocols in [11, 12, 20]. We choose these three protocols because both parties of the protocols in [11, 12] can know the intersection, and the protocol in [20] supports outsourcing. These protocols are very similar to our protocol. The comparison results are shown in Table 4.Table 4
Comparison of the properties of O-mPSI protocol and related protocols.
ProtocolComp. CostComm. CostFairnessUserServerDebnath’s mPSI1 [11]48n—103nYesDebnath’s mPSI2 [12]23n+7—12n+4YesAbadi’s PSI [20]10n+1510n+1516n+24NoOur O-mPSI6.5n06nYesComputation complexity. Our O-mPSI protocol uses a cuckoo hash table to store data, and the ElGamal threshold encryption algorithm to encrypt data. We use the number of modular exponential operations to evaluate the computational overhead of O-mPSI protocol. Party P1 and party P2 each performs 2m+mb exponential operations when encrypting the hash tables T1 and T2 and performs w exponential operations in the decryption phase. The server only performs the intersection calculation which does not involve any exponential operations, where m represents how many bins are in the hash table, b is the size of the bin, and w is the intersection-cardinality. Therefore, the protocol O-mPSI has performed 22m+mb+w modular exponential operations in total. We define n=n1≫n2, b=4, mb=1.5n, where nii=1,2 is the cardinality of the private set of party Pi. The possible values of intersection w are in the range [0, n], where we take its maximum value n. Therefore, the computational complexity is 6.5n in the O-mPSI protocol.The protocol in [11] is based on the two-way oblivious pseudorandom function mOPRF, without the participation of a third-party server, and its computation complexity is 48n. The protocol in [12] also does not involve the third-party server; its computation complexity is 23n+7. In the verifiable delegated PSI protocol of [20], the user performs 10n+15 exponential operations and the server performs 10n+15 exponential operations, so the overall computation complexity of [20] is 20n+30.From the analysis above, it is clear that our O-mPSI protocol has much lower computational complexity than the other three protocols.Communication complexity. Our O-mPSI protocol uses the number of transmitted ciphertexts to express the complexity of communication. Party P1 sends mb encrypted elements Exik and mb rerandomized elements E∗yik, for 1≤i≤b and 1≤k≤m, to P2. Party P2 sends mb encrypted elements Eyik and mb rerandomized elements E∗xik, for 1≤i≤b and 1≤k≤m, to P1. Thus, the O-mPSI protocol generates a total of 4mb ciphertexts transmissions. The communication complexity of the protocol O-mPSI is 6n, due to mb=1.5n.In [11], the protocol generates 103n ciphertexts interactions, the protocol in [12] generates 12n+4 ciphertexts interactions, and the protocol in [20] generates 16n+24 ciphertexts interactions.To sum up, we can see that our O-mPSI protocol is superior to the other three protocols in terms of the communication complexity.


### 6.2. Experimental Evaluation

To verify the theoretical analysis results in Section6.1, the computational costs of our O-mPSI protocol and the protocols in [11, 12, 20] are compared through experiments. The experimental platform is Windows 10, AMD Ryzen 5 4600H with Radeon Graphics 3.00 GHz, 16 GB RAM, and the compilation environment is MyEclipse 2017. In the experiment, we set b=4 and mb=1.5n, where m represents how many bins are in the hash table, b is the size of the bin, and n is the set cardinality.Since our O-mPSI protocol and the protocols in [11, 12, 20] all use homomorphic encryption algorithm to encrypt data, we first compare the time it takes for the four protocols to execute with different modulus lengths. In this experiment, we set n=1000; for modulus of 128 bit, 256 bit, 512 bit, and 1024 bit, the different homomorphic encryption times of the 4 protocols are shown in Figure 2.Figure 2
Time to perform homomorphic encryption of different modulus length.It can be seen from Figure2, with the increase of modulus length, the time of homomorphic encryption performed by the four protocols also increases. Among them, the time cost of the O-mPSI protocol is lower than that of Debnath’s mPSI1, mPSI2 protocol, and Abadi’s PSI protocol, and the growth trend is the slowest. The time cost in this experiment depends on how many modular exponential operations are used in the scheme. And according to Table 3, the modular exponential operation is least used in the calculation of the O-mPSI protocol. Therefore, the increase of modulus length has the least impact on O-mPSI protocol.We further compare the time it takes for the four protocols to execute at different set cardinalities. In this experiment, we fixed the modulus length to 1024 bit; for the cardinalityn of 210,212,214,216,218,220, the running time of the four protocols can be seen in Figure 3.Figure 3
Running time at different set cardinality.It can be seen from Figure3 that the execution time of the four protocols increases with the increasing size of the data set. Among them, the execution time overhead of the O-mPSI increases most slowly compared to that of Debnath’s mPSI1, mPSI2 protocol, and Abadi’s PSI protocol. This is because the O-mPSI protocol in this paper uses hash algorithm to process the set elements in advance. Therefore, as the size of the data set continues to increase, the time cost curve of O-mPSI protocol has grown slowly, while the time cost curve of the other three protocols has increased significantly.


## 6.1. Theoretical Evaluation

In this section, regarding the complexity of calculation and communication, we compare the O-mPSI protocol with the protocols in [11, 12, 20]. We choose these three protocols because both parties of the protocols in [11, 12] can know the intersection, and the protocol in [20] supports outsourcing. These protocols are very similar to our protocol. The comparison results are shown in Table 4.Table 4
Comparison of the properties of O-mPSI protocol and related protocols.
ProtocolComp. CostComm. CostFairnessUserServerDebnath’s mPSI1 [11]48n—103nYesDebnath’s mPSI2 [12]23n+7—12n+4YesAbadi’s PSI [20]10n+1510n+1516n+24NoOur O-mPSI6.5n06nYesComputation complexity. Our O-mPSI protocol uses a cuckoo hash table to store data, and the ElGamal threshold encryption algorithm to encrypt data. We use the number of modular exponential operations to evaluate the computational overhead of O-mPSI protocol. Party P1 and party P2 each performs 2m+mb exponential operations when encrypting the hash tables T1 and T2 and performs w exponential operations in the decryption phase. The server only performs the intersection calculation which does not involve any exponential operations, where m represents how many bins are in the hash table, b is the size of the bin, and w is the intersection-cardinality. Therefore, the protocol O-mPSI has performed 22m+mb+w modular exponential operations in total. We define n=n1≫n2, b=4, mb=1.5n, where nii=1,2 is the cardinality of the private set of party Pi. The possible values of intersection w are in the range [0, n], where we take its maximum value n. Therefore, the computational complexity is 6.5n in the O-mPSI protocol.The protocol in [11] is based on the two-way oblivious pseudorandom function mOPRF, without the participation of a third-party server, and its computation complexity is 48n. The protocol in [12] also does not involve the third-party server; its computation complexity is 23n+7. In the verifiable delegated PSI protocol of [20], the user performs 10n+15 exponential operations and the server performs 10n+15 exponential operations, so the overall computation complexity of [20] is 20n+30.From the analysis above, it is clear that our O-mPSI protocol has much lower computational complexity than the other three protocols.Communication complexity. Our O-mPSI protocol uses the number of transmitted ciphertexts to express the complexity of communication. Party P1 sends mb encrypted elements Exik and mb rerandomized elements E∗yik, for 1≤i≤b and 1≤k≤m, to P2. Party P2 sends mb encrypted elements Eyik and mb rerandomized elements E∗xik, for 1≤i≤b and 1≤k≤m, to P1. Thus, the O-mPSI protocol generates a total of 4mb ciphertexts transmissions. The communication complexity of the protocol O-mPSI is 6n, due to mb=1.5n.In [11], the protocol generates 103n ciphertexts interactions, the protocol in [12] generates 12n+4 ciphertexts interactions, and the protocol in [20] generates 16n+24 ciphertexts interactions.To sum up, we can see that our O-mPSI protocol is superior to the other three protocols in terms of the communication complexity.


## 6.2. Experimental Evaluation

To verify the theoretical analysis results in Section6.1, the computational costs of our O-mPSI protocol and the protocols in [11, 12, 20] are compared through experiments. The experimental platform is Windows 10, AMD Ryzen 5 4600H with Radeon Graphics 3.00 GHz, 16 GB RAM, and the compilation environment is MyEclipse 2017. In the experiment, we set b=4 and mb=1.5n, where m represents how many bins are in the hash table, b is the size of the bin, and n is the set cardinality.Since our O-mPSI protocol and the protocols in [11, 12, 20] all use homomorphic encryption algorithm to encrypt data, we first compare the time it takes for the four protocols to execute with different modulus lengths. In this experiment, we set n=1000; for modulus of 128 bit, 256 bit, 512 bit, and 1024 bit, the different homomorphic encryption times of the 4 protocols are shown in Figure 2.Figure 2
Time to perform homomorphic encryption of different modulus length.It can be seen from Figure2, with the increase of modulus length, the time of homomorphic encryption performed by the four protocols also increases. Among them, the time cost of the O-mPSI protocol is lower than that of Debnath’s mPSI1, mPSI2 protocol, and Abadi’s PSI protocol, and the growth trend is the slowest. The time cost in this experiment depends on how many modular exponential operations are used in the scheme. And according to Table 3, the modular exponential operation is least used in the calculation of the O-mPSI protocol. Therefore, the increase of modulus length has the least impact on O-mPSI protocol.We further compare the time it takes for the four protocols to execute at different set cardinalities. In this experiment, we fixed the modulus length to 1024 bit; for the cardinalityn of 210,212,214,216,218,220, the running time of the four protocols can be seen in Figure 3.Figure 3
Running time at different set cardinality.It can be seen from Figure3 that the execution time of the four protocols increases with the increasing size of the data set. Among them, the execution time overhead of the O-mPSI increases most slowly compared to that of Debnath’s mPSI1, mPSI2 protocol, and Abadi’s PSI protocol. This is because the O-mPSI protocol in this paper uses hash algorithm to process the set elements in advance. Therefore, as the size of the data set continues to increase, the time cost curve of O-mPSI protocol has grown slowly, while the time cost curve of the other three protocols has increased significantly.


## 7. Conclusions

To address the problem of data privacy and security sharing in edge-assisted IoT, we proposed a fair outsourced mPSI protocol with a lower computational cost. The proposed O-mPSI scheme uses the existing hash bin-to-bin method to calculate the intersection and improves it to further reduce the number of element comparisons. The calculation of intersection is outsourced to the edge server, which reduces the computing burden on both sides. The scheme adopts ElGamal threshold encryption algorithm to ensure data security. Only when both parties cooperate can all ciphertexts be completely decrypted. Therefore, this scheme can effectively resist the collusive attack between the server and any one of the two parties. And it proves that this scheme is IND-CPA secure under the DDH assumption. Through theoretical analysis and experimental evaluation, it is shown that the computational cost of our proposed O-mPSI protocol proposed in this paper is lower than that of other mutual PSI protocols.The combination of edge computing and IoT improves the intelligence of IoT devices and introduces intelligent devices into all aspects of life. The massive use of smart IoT devices has led to a sharp increase in the amount of data generated by users. Privacy protection and secure sharing of big data in the IoT have become the focus of current research. Therefore, research on more secure and efficient PSI technology applied to edge-assisted IoT is our future research direction.



---

*Source: 3159269-2021-12-31.xml*