# Efficient Cloud-Based Private Set Intersection Protocol with Hidden Access Attribute and Integrity Verification

Authors: Jianhong Zhang; Menglong Wu
Journal: Security and Communication Networks
 (2021)

---

## Body

## 1. Introduction

With the rapid progress of the technology of wireless communication and sensor, the Internet of Things (IoT) is changing our lives. From medical devices and air quality monitoring to intelligent street lights, energy-efficient buildings, smart home, and more, the IoT is in more places than ever. As the number of the connected IoT devices increases, the amount of data generated by these devices will also exponentially increase. According to the newer forecast from International Data Corporation (IDC) [1], there will be 41.6 billion connected IoT devices in 2025, and they will generate 79.4 ZB of data. For the IoT devices with limited computation and storage resources, it is an important challenge to how to properly use and store such vast amounts of data. Cloud computing makes it possible to process and store massive amounts of data, and it also makes those data users possessing limited resources to easily access the stored data in cloud at any time and from anywhere.As a cryptographic tool that is realizing secure multiparty computation, private set intersection (PSI) can make two parties holding sets compute their intersection without revealing any information other than the intersection. Since PSI was proposed by Freedman in [2], a mass of PSI schemes [3–7] have been put forward. The powerful privacy protection of PSI makes it to be important applications in real life, such as private contact tracing [8], DNA testing and pattern matching [9], remote medical diagnostics [10], and the effectiveness assessment of online advertising [11]. Over the last few years, PSI has been further developed such that it becomes very practical with extremely fast implementations that can conduct millions of items in seconds. However, most PSI schemes require two parties possessing datasets to jointly calculate the intersection of the available datasets locally. As the commercial value of cloud computing services drives, the user might delegate cloud service provider to execute the PSI computation for the outsourced datasets in cloud.To our knowledge, in most of the existing PSI protocols, both participants jointly compute the intersection of their sets in an interactive manner, which makes that each participant must have a local copy of its dataset. It brings a heavy burden to resource-limited users. The advent of cloud computing makes the delegation of PSI computation promising since cloud servers can provide flexible and cost-effective storage space and on-demand computing power service. Recently, several cloud-based PSI protocols [6, 12, 13] are proposed. In these schemes, to achieve PSI computation, the user needs to outsource its dataset to a cloud server. However, the cloud server is not fully trusted, and it might reveal or tamper with the items in the outsourced dataset. To ensure the privacy of the outsourced dataset, they should be processed by applying cryptographic algorithms before outsourcing. However, the complicated cryptographic operations do not only incur the heavy computation burden to the resource-constrained data users but also impede access over the dataset of the data owner. To realize access control, data owners must be real-time online to execute PSI computations with the authorized data user.Recently, to avoid data owner real-time online and achieve fine-grained access control, Ali et al. proposed an attribute-based private set intersection computation protocol [14]. However, their scheme cannot ensure the integrity of the returned blinded dataset from the cloud, since when the cloud is not fully trusted, it may return the partial blinded dataset or delete some items of the outsourced dataset. Additionally, in their scheme, the access policy needs to be embedded in the blinded dataset. This kind of direct exposure of access policy can result in privacy revelation of data users since the access policy often contains some sensitive information.To solve the above issue and provide fine-grained access control, in the paper, we proposed an efficient cloud-based private set intersection computation (PSI) protocol. The main contributions in this works are summarized as follows:(i)
Fine-grained access control of PSI computation: it provides fine-grained access control for PSI computation in the cloud environment and makes access control over the outsourced dataset of data owners realized by applying attribute-based encryption.(ii)
Offline data owner: in the PSI-computation phase, data owner does not need to be online in real-time, which reduces the burdens of communication and computation of data owner.(iii)
Resisting colluding attack: the collusion between cloud server and unauthorized data users cannot obtain any information about the outsourced datasets.(iv)
Data secrecy: for data owner, an authorized data user with datasetY only learns the information of the intersection X∩Y; none of the other information about dataset X except X∩Y is obtained by data user.(v)
Integrity: it can ensure the integrity of the returned blinded dataset in order to resist the malicious behaviors of the cloud server.(vi)
Hidden access policy: to satisfy more practical privacy requirements, the proposed protocol enables that cloud server cannot derive any sensitive information about attribute from the blinded dataset.


### 1.1. Paper Organization

The remainder of the paper is organized as follows. Section2 reviews related work, and Section 3 describes some preliminaries. In Section 4, we give problem formulation of the proposed protocol. In Section 5, the proposed PSI protocol is given. In Section 6, we analyze the security of the proposed protocol. In Section 7, we evaluate the performance of the proposed protocol. Finally, the paper is summarized in Section 8.


## 1.1. Paper Organization

The remainder of the paper is organized as follows. Section2 reviews related work, and Section 3 describes some preliminaries. In Section 4, we give problem formulation of the proposed protocol. In Section 5, the proposed PSI protocol is given. In Section 6, we analyze the security of the proposed protocol. In Section 7, we evaluate the performance of the proposed protocol. Finally, the paper is summarized in Section 8.


## 2. Related Work

Meadows proposed the first secure PSI protocol [15] based on multiplicative homomorphic techniques. Due to being based on public-key cryptography, the scheme running time is unacceptable, in particular, when the size of the dataset becomes large. In [2], Freedman et al. proposed a private set intersection protocol by means of partial homomorphic encryption and point-value polynomial representation of sets. Later, Hazay and Nizim extended it to the malicious setting in [16]. In [17], Kissner and Song proposed privacy-preserving set operations. Their scheme can compute not only the intersection of the sets but also the union of the sets in a privacy-preserving way.In [18], Jarecki and Liu proposed a novel PSI protocol based on the composite residual problem. In their scheme, the user and the server obtain the intersection of the two datasets by using parallel oblivious pseudorandom function. However, it relied on a common reference model. In [19], De Cristofaro et al. proposed two PSI protocols in malicious model. However, their schemes are unable to hide the cardinality of the user’s dataset. To overcome this problem, Ateniese et al. proposed a PSI protocol [20] under the RSA assumption. But their scheme is only proven to be secure in the random oracle model. Based on the scheme in [18], De Cristofaro and Tsudik presented an efficient PSI protocol [21] by using OPRF techniques. Over the past few years, many efficient PSI protocols [3–13, 16, 17] have been successively proposed.According to cryptographic techniques used to construct PSI protocol, the existing PSI protocols are mainly classified into three different groups:(i)
Public-key-based PSI protocol: homomorphic encryption is a common cryptographic technique to design PIS protocol. In the early days, most PSI protocols were constructed based on homomorphic encryption, where the protocols in [2, 8, 10, 15, 22, 23] are the classic instances. In the type of protocols, data owner first encrypts dataset X to obtain the corresponding ciphertext C and sends C to data user, and then using homomorphic properties of homomorphic encryption, data user conducts some specific operations on the ciphertext C and its dataset Y. Finally, data owner obtains the corresponding intersection by using its private key. This type of protocol is suitable for the scenario in which both participants possess strong computing capability. In general, such protocols require a higher computation cost since public-key cryptography is included. However, it is suitable for designing some PSI protocols with a custom function.(ii)
Circuit-based PSI protocol: circuit-based generic technique of secure computation is another method to design PSI protocol. Fairplay proposed the first PSI protocol by using Yao’s garbled-circuit approach in [24]. In the subsequent works, Huang et al. presented three PSI protocols based on Yao’s generic garbled-circuit method [25]. Their schemes are competitive with the fastest public-key-based protocols. Afterwards, Pinkas et al. gave some new optimizations for circuit-based PSI in [26]. By using secure multiparty computation idea, this type of protocol can transform the specific function into garbled Boolean circuit to realize secure computation, and its key technique is symmetric cryptography. For this general circuit protocol, its advantage is that it makes the design and implementation of the protocol easier. However, due to its generalization, the garbled circuit makes the scalability of the protocol poor.(iii)
Oblivious transfer- (OT-) based PSI protocol: oblivious transfer protocol is a foundation of secure computation. To realize large-scale data processing, Dong et al. presented two efficient PSI protocols [27] based on bloom filters and OT extension protocol. Their protocols are rather efficient and highly scalable compared with some PSI protocols. To reduce the runtime, Pinkas et al. gave an optimization of PSI protocol [27] using random OT extension in [26]. The core idea of this type of protocols is to have both parties collaboratively engage in many OT protocols. In general, this type of PSI protocols had lower computation costs and communication consumption, but extra keys-related computations are demanded such as secret key agreement.From the above analysis, public-key-based PSI protocols exist as higher computation complexity, and circuit-based PSI protocol and OT-based PSI protocols have higher efficiency due to using symmetric encryption, but key agreement or secure transferring of secret keys also require additional computation costs and communication overhead.


## 3. Preliminaries

### 3.1. Composite Order Bilinear Group

Throughout the paper, we only consider composite order bilinear groups since our scheme is based on such construction. In the following, we review some concepts of such bilinear pair:(1)
G1 and GT are two cyclic groups with the same composite order N=pq where p,q are two distinct primes, and it is deemed to be hard for solving the discrete logarithm problem in group Gi,i∈1,T.(2)
Lete^:G1×G1⟶GT denote a computable bilinear map which satisfies the following criteria:(i)
Bilinearity: for arbitrarya,b∈ZN and all Q,F∈G1, we have e^Qa,Fb=e^Q,Fab.(ii)
Nondegeneracy:∃g,h∈G1 such that eg,h has the order N in GT.(iii)
Orthogonal property: letGp and Gq denote two subgroups of G1 with the order p and q, respectively. For ∀hp∈Gp and ∀hq∈Gq, then ehp,hq=1.


#### 3.1.1. The Decisional Bilinear Diffie–Hellman Assumption inG

Letg,ga,gb,gc,T∈G14 and GT be a random 5-tuple where a,b,c∈Zp, there does not exist an efficient PPT algorithm A which can distinguish T=?eg,gabc. A’s advantage of breaking the decisional Diffie–Hellman problem in G1 is defined as(1)ε=Preg,gabc=T←Ag,ga,gc,gb.We think that the DBDH problem is againstA if the algorithm A is capable of distinguishing eg,gabc and T in a nonnegligible probability ε.


### 3.2. Access Tree

Access trees can make the representation of access control policies easier to understand. In what follows, we explain the access trees used in our constructions.Access treeT is a tree-like access structure, and each leaf node is associated with an attribute value, and an inner-node l is represented with a threshold gate numl,kl, where numl is the children number of inner-node l and kl is its threshold value satisfying 0<kl≤numl. Specifically, when kl=1 and kl=numl, it means that the corresponding threshold gate is the OR-gate and the AND-gate, respectively. For each leaf node l, its threshold value is kl=1.For the sake of presentation, the children of each nodel are ordering from 1 to numl. At the same time, we define that function parentl is the parent of node l, indexl is the number associated with node l, and then function attl is an attribute associated with the leaf node l.Assume thatR is the root of an access tree T, then we use TR to represent this tree, and Tx is denoted by a subtree of T rooted at node x if node x is an inner node of T. For an attribute set S, if it satisfies the subtree Tx, then it is represented as TxS=1. The satisfied conditions are divided into the following two cases:(1)
Whenx is a leaf node, TxS=1 is returned if and only if attx∈S;(2)
Whenx is a nonleaf node, TxS can be computed recursively. For all children z of node x, if at least kx children satisfy TzS=1, then TxS=1 is returned.


## 3.1. Composite Order Bilinear Group

Throughout the paper, we only consider composite order bilinear groups since our scheme is based on such construction. In the following, we review some concepts of such bilinear pair:(1)
G1 and GT are two cyclic groups with the same composite order N=pq where p,q are two distinct primes, and it is deemed to be hard for solving the discrete logarithm problem in group Gi,i∈1,T.(2)
Lete^:G1×G1⟶GT denote a computable bilinear map which satisfies the following criteria:(i)
Bilinearity: for arbitrarya,b∈ZN and all Q,F∈G1, we have e^Qa,Fb=e^Q,Fab.(ii)
Nondegeneracy:∃g,h∈G1 such that eg,h has the order N in GT.(iii)
Orthogonal property: letGp and Gq denote two subgroups of G1 with the order p and q, respectively. For ∀hp∈Gp and ∀hq∈Gq, then ehp,hq=1.


### 3.1.1. The Decisional Bilinear Diffie–Hellman Assumption inG

Letg,ga,gb,gc,T∈G14 and GT be a random 5-tuple where a,b,c∈Zp, there does not exist an efficient PPT algorithm A which can distinguish T=?eg,gabc. A’s advantage of breaking the decisional Diffie–Hellman problem in G1 is defined as(1)ε=Preg,gabc=T←Ag,ga,gc,gb.We think that the DBDH problem is againstA if the algorithm A is capable of distinguishing eg,gabc and T in a nonnegligible probability ε.


## 3.1.1. The Decisional Bilinear Diffie–Hellman Assumption inG

Letg,ga,gb,gc,T∈G14 and GT be a random 5-tuple where a,b,c∈Zp, there does not exist an efficient PPT algorithm A which can distinguish T=?eg,gabc. A’s advantage of breaking the decisional Diffie–Hellman problem in G1 is defined as(1)ε=Preg,gabc=T←Ag,ga,gc,gb.We think that the DBDH problem is againstA if the algorithm A is capable of distinguishing eg,gabc and T in a nonnegligible probability ε.


## 3.2. Access Tree

Access trees can make the representation of access control policies easier to understand. In what follows, we explain the access trees used in our constructions.Access treeT is a tree-like access structure, and each leaf node is associated with an attribute value, and an inner-node l is represented with a threshold gate numl,kl, where numl is the children number of inner-node l and kl is its threshold value satisfying 0<kl≤numl. Specifically, when kl=1 and kl=numl, it means that the corresponding threshold gate is the OR-gate and the AND-gate, respectively. For each leaf node l, its threshold value is kl=1.For the sake of presentation, the children of each nodel are ordering from 1 to numl. At the same time, we define that function parentl is the parent of node l, indexl is the number associated with node l, and then function attl is an attribute associated with the leaf node l.Assume thatR is the root of an access tree T, then we use TR to represent this tree, and Tx is denoted by a subtree of T rooted at node x if node x is an inner node of T. For an attribute set S, if it satisfies the subtree Tx, then it is represented as TxS=1. The satisfied conditions are divided into the following two cases:(1)
Whenx is a leaf node, TxS=1 is returned if and only if attx∈S;(2)
Whenx is a nonleaf node, TxS can be computed recursively. For all children z of node x, if at least kx children satisfy TzS=1, then TxS=1 is returned.


## 4. Problem Formulation

In this section, to better understand the motivation of the proposed scheme, we will give the system model and threat model that correspond to our protocol.


### 4.1. System Model

For a cloud-based PSI computation protocol with fine-grained access control and integrity verification, its system model is shown in Figure1. The system model consists of four entities: key generation center (KGC), cloud service provider (CSP), data owners, and data users. The roles of these entities are described as follows.Figure 1
The system model of the proposed scheme.


#### 4.1.1. Key Generation Center

It is responsible for establishing system parameters and generating the secret keys of the attributes for data users. In addition, it also generates a public-private key pair for the data owners’ signature algorithm.


#### 4.1.2. Cloud Service Provider

It has abundant storage space and powerful computing capability, and it can provide storage services of the outsourced dataset for data owners and PSI computation services for data users.


#### 4.1.3. Data Owner

It is the owner of a datasetX. To achieve fine-grained access control, data owner needs to define an access control policy before outsourcing the dataset; and then it blinds the dataset based the defined access policy.


#### 4.1.4. Data User

It also possesses a datasetY and can request the CSP to generate a token in order to compute private set intersection X∩Y. It is worth noting that only data user whose attributes satisfy access policy defined by data owner can obtain the returned PSI token by the CSP.


### 4.2. Threat Model

In our proposed protocol, the CSP is not a fully trusted entity, like [6, 11, 14, 17], it may attempt to tamper or delete the items in the outsourced dataset, and it also might try to extract sensitive information from the outsourced dataset by colluding some unauthorized data users. For data user, it is identified as a malicious entity. It may collude the CSP to obtain more information beyond the intersections. Additionally, an unauthorized data user also may attempt to obtain the qualification of the PSI computation. The KGC is assumed to be a trusted entity. It is responsible for generating secret keys for data user’s attribute set and public/private key pairs for data owners. Data owner is assumed to be a trusted entity. It honestly encrypts its dataset and outsources them to the CSP. They never reveal the elements of their private datasets.


### 4.3. Security Goals

For the proposed protocol, its goals are given as follows:(1)
It achieves fine-grained access control and makes that only data users satisfying the defined access policy by data owner can conduct PSI computation.(2)
The authorized data users learn nothing, except the intersection of datasets, this is to say, it achieves data secrecy.(3)
The CSP does not learn any information about the protocol results and the outsourced dataset, this is to say, it is adaptively secure against chosen dataset attack.(4)
It must ensure the integrity of the blinded dataset returned by the cloud server to the data user.


## 4.1. System Model

For a cloud-based PSI computation protocol with fine-grained access control and integrity verification, its system model is shown in Figure1. The system model consists of four entities: key generation center (KGC), cloud service provider (CSP), data owners, and data users. The roles of these entities are described as follows.Figure 1
The system model of the proposed scheme.


### 4.1.1. Key Generation Center

It is responsible for establishing system parameters and generating the secret keys of the attributes for data users. In addition, it also generates a public-private key pair for the data owners’ signature algorithm.


### 4.1.2. Cloud Service Provider

It has abundant storage space and powerful computing capability, and it can provide storage services of the outsourced dataset for data owners and PSI computation services for data users.


### 4.1.3. Data Owner

It is the owner of a datasetX. To achieve fine-grained access control, data owner needs to define an access control policy before outsourcing the dataset; and then it blinds the dataset based the defined access policy.


### 4.1.4. Data User

It also possesses a datasetY and can request the CSP to generate a token in order to compute private set intersection X∩Y. It is worth noting that only data user whose attributes satisfy access policy defined by data owner can obtain the returned PSI token by the CSP.


## 4.1.1. Key Generation Center

It is responsible for establishing system parameters and generating the secret keys of the attributes for data users. In addition, it also generates a public-private key pair for the data owners’ signature algorithm.


## 4.1.2. Cloud Service Provider

It has abundant storage space and powerful computing capability, and it can provide storage services of the outsourced dataset for data owners and PSI computation services for data users.


## 4.1.3. Data Owner

It is the owner of a datasetX. To achieve fine-grained access control, data owner needs to define an access control policy before outsourcing the dataset; and then it blinds the dataset based the defined access policy.


## 4.1.4. Data User

It also possesses a datasetY and can request the CSP to generate a token in order to compute private set intersection X∩Y. It is worth noting that only data user whose attributes satisfy access policy defined by data owner can obtain the returned PSI token by the CSP.


## 4.2. Threat Model

In our proposed protocol, the CSP is not a fully trusted entity, like [6, 11, 14, 17], it may attempt to tamper or delete the items in the outsourced dataset, and it also might try to extract sensitive information from the outsourced dataset by colluding some unauthorized data users. For data user, it is identified as a malicious entity. It may collude the CSP to obtain more information beyond the intersections. Additionally, an unauthorized data user also may attempt to obtain the qualification of the PSI computation. The KGC is assumed to be a trusted entity. It is responsible for generating secret keys for data user’s attribute set and public/private key pairs for data owners. Data owner is assumed to be a trusted entity. It honestly encrypts its dataset and outsources them to the CSP. They never reveal the elements of their private datasets.


## 4.3. Security Goals

For the proposed protocol, its goals are given as follows:(1)
It achieves fine-grained access control and makes that only data users satisfying the defined access policy by data owner can conduct PSI computation.(2)
The authorized data users learn nothing, except the intersection of datasets, this is to say, it achieves data secrecy.(3)
The CSP does not learn any information about the protocol results and the outsourced dataset, this is to say, it is adaptively secure against chosen dataset attack.(4)
It must ensure the integrity of the blinded dataset returned by the cloud server to the data user.


## 5. Our Concrete Construction

In this section, we present a concrete construction of the cloud-based PSI protocol with fine-grained access and integrity verification. The protocol consists of the following three stages, the detailed descriptions are given as follows.


### 5.1. System Initiation

In this stage, key generation center (KGC) is responsible for initializing system parameters and producing secret key of the data user with attribute setAtt. To do it, it needs to execute the following two algorithms: Setup and KeyGen.


#### 5.1.1. Setupλ,U

Taking a security parameterλ and the universal attribute set U as inputs, it outputs G1,GT,N=p⋅q,e←Gen1λ, where G1 and GT are cyclic groups of order N and p,q are two distinct 512-bit primes. Let Gp and Gq denote two subgroups of group G1 with the order p and q, respectively, and gp and gq are the generators of Gp and Gq, respectively. e:G1×G1⟶GT is a bilinear pairing map.For the universal attribute setU=w1,…,wn, where n is the maximum number of attributes, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(2)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l. Finally, public parameters Param are published as follows:(3)Param=G1,GT,N,e,H,H0,e,gp,Px,Py,Ti1≤i≤n,and master secret keys α,ti,1≤i≤n are securely stored. Note that each Ti corresponds to each attribute wi.


#### 5.1.2. KeyGenAtt,α,a,β

For a data user with an attribute setAtt=w1,…,wt, if it wants to register to the system, it sends its attribute set Att to KGC, and then KGC makes use of its secret key to generate the secret key for the data owner with attribute set Att.(1)
First of all, KGC randomly chooses a numberr∈Zp to compute(4)sk0=gpα−r,(2)
and then for each attributewj in Att, it computes skj=gpr⋅tj−1.(3)
The resultant secret keyskAtt=sk0,skiwi∈Att.In addition, for data owner, it randomly choosessko∈Zp to compute its public key pko=gpsko. This public-private key pair pko,sko is used to generate digital signature.


### 5.2. Blinding of Dataset

For a data owner, if it wants to outsource the datasetX=xii∈I to cloud server, to ensure the security of the dataset, it needs to blind the dataset before outsourcing. To achieve the confidentiality and fine-grained access control of data, it needs to execute the following Blind algorithms.


#### 5.2.1. Blind (Param,T, X)

For a datasetX and an access structure T, the algorithm takes X and T as inputs and outputs the blinded data. The detailed process is given as follows.(1)
First of all, it picks a numbert∈Zp and R0′∈Gq at random to compute(5)C0=Pxt⋅R0′,C=Pyt,Cix=H0HCpk0⊕H0xii∈I,whereI=X is the size of the dataset X and ‖ is a concatenate operator.(2)
Then, it generates a signatureδs=δ1,δ2 on C1x‖⋯‖CIx by randomly choosing r0∈ZN, where δ1=gpr0 and δ2=r0−sko⋅H1C1x‖⋯‖CIx,δ1modN.(3)
To facilitate the expression of access structure, we adopt access treeT. For each node v in T, the algorithm randomly allocates a kv−1 degree polynomial fv in the top-down manner, where kv is the children number of node v. Especially for root RT of access tree T, the allocated polynomial fRx should satisfy fR0=t; for the other node v, it should satisfy fv0=fparentvindexv, where indexv denotes an index value of node v in the children of its parent node, and parentv is the parent node of node v. Finally, for each leaf node i of access tree T corresponding to an attribute wi, the blinded data is computed(6)Ci=Tifi0Ri′,whereRi′ is a random element in group Gq. Note that Ti corresponds to the attribute wi.(4)
At last, the blinded dataset ofX is BT=T,δs,C0,Cixi∈I,Cjj∈T, and data owner uploads them to cloud server.


### 5.3. PSI Computation

To obtain private set intersection of a blinded datasetBT of dataset X uploaded by a special data owner, the stage is divided into three parts: Token1 generation, Token2 generation, and set intersection computation. Firstly, a data user with dataset Y needs to run TokenGen1 algorithm to produce a PSI-token 1 for cloud server, and then cloud server runs TokenGen2 algorithm to produce a PSI-token 2 by using PSI-token 1. Finally, data user computes the intersection X∩Y of the two datasets X and Y by using the PSI-token 2 produced by cloud server. The detailed processes are given as follows.


#### 5.3.1. TokenGen1Param,skAtt

Taking system parametersParam and secret key of data user skAtt, this algorithm randomly selects a number μ∈Zp to compute a PSI-token 1:(7)ToK1=sk1μ,…,sk2μ,…,skAttμ,sk0μ.


#### 5.3.2. TokenGen2Param,ToK1,BT

Taking the PSI-token 1ToK1 and the blinded dataset BT, this algorithm firstly verifies whether Att satisfies the access tree T correlating to the blinded dataset BT. If it does not, then it outputs ⊥ and aborts it.For the sake of illustration, we define a recursive algorithmTok2⋅ that takes as input an access tree T, an attribute set Att, the blinded dataset BT, and a node from T.For each node inT, cloud server executes a recursive algorithm Tok2⋅ as follows:(1)
Ifθi∈T is a leaf node and attθi∈Att, where wi=attθi is an attribute corresponding to leaf node θi, then it computes(8)Tok2T,Att,BT,θi=eCi,skiμ=egptifi0,gprti−1μeRifi0⋅Ri′,gprti−1μ=egptifi0,gpμrti−1=egp,gprμfi0,whereskiμ is the i-th element in PSI-token 1 ToK1 and Ci is the i-th in Cjj∈T.(2)
Ifθi∈T is a nonleaf node, the recursive algorithm runs as follows: for all child node childθi of node θi, it calls Tok2T,Att,BT,indexj,childθi for j=1,…,ω and stores them, where childθi denotes all children of θi and indexj,childθi denotes the j-th child node of θi. The algorithm is run until children nodes of a node are leaf nodes, and then we compute(9)Tok2T,Att,BT,θi=∏k=1ωTok2T,Att,BT,indexk,childθiΔω,k0,wherechildθi is the child node of node θi and w is threshold value of parent node parentθi, and for θi, its Lagrange coefficient is(10)Δω,kx=∏j∈1,ω,j≠kx−jk−j.Through recursively runningTok2T,Att,BT,θi in the bottom-to-top manner in access tree T, we can obtain the PSI–token 2,(11)Tok2=egp,gprtμ.In the end, the algorithm returns the PSI-token 2Tok2, Cixi∈I and the signature δs of Cixi∈I.


#### 5.3.3. PSI ComputationParam,ToK2,Cixi∈IY=yjj∈1,…,Y,δs

Upon receivingToK2 and Cixi∈I, the algorithm takes ToK2,Cixi∈I, Y, and δs as inputs and executes Algorithm 1. In this algorithm, lines 1–3 are used to check the validity of the signature δs, which can achieve the integrity checking of the returned dataset by cloud server. Lines 7–17 are used to seek the intersection of two datasets. If Cix==τj holds, then the element of the intersection is found.Algorithm 1:PSI computation.
Input: Param,δs,μ,pk0,ToK2,Cixi∈I,Y=yjj∈1,…,YOutput: the intersection X∩Y of dataset X and dataset Y(1)
ifδ1!=g1δ2⋅pkoH1C1x‖⋯‖CIx,δ1, then(2)
printf (“the returned dataset is not intact”);(3)
exit (0);(4)
end(5)
ComputeTmp=Tok2μ−1eC0,sk0;(6)
Sety=Y;(7)
fori=1:Ido(8)
forj=1:ydo(9)
Computeτj=H0HTmp‖pk0⊕H0yj;(10)
ifCix==τj, then(11)
printf (“%d,” yj);(12)
else(13)
j++;(14)
end(15)
end(16)
i++;(17)
end


### 5.4. Correctness

In the subsection, we show that the proposed scheme is correct, because in the blinding stage, the datasetX=xii∈I is blinded into BT, and each Cix in BT has the following format Cix=H0HC‖pk0⊕H0xi.In addition, in the stage of intersection computation, data user can use PSI-token 2 to obtain the following relation:(12)Tmp=Tok2μ−1⋅eC0,sk0=egp,gprtePxt⋅R0′,gpα−r=egp,gprtegpt,gpα−r=egp,gpαt=Pyt.Thus, it can obtainX∩Y by running Algorithm 1 in PSI computation phase. It means that the proposed scheme is correct.


## 5.1. System Initiation

In this stage, key generation center (KGC) is responsible for initializing system parameters and producing secret key of the data user with attribute setAtt. To do it, it needs to execute the following two algorithms: Setup and KeyGen.


### 5.1.1. Setupλ,U

Taking a security parameterλ and the universal attribute set U as inputs, it outputs G1,GT,N=p⋅q,e←Gen1λ, where G1 and GT are cyclic groups of order N and p,q are two distinct 512-bit primes. Let Gp and Gq denote two subgroups of group G1 with the order p and q, respectively, and gp and gq are the generators of Gp and Gq, respectively. e:G1×G1⟶GT is a bilinear pairing map.For the universal attribute setU=w1,…,wn, where n is the maximum number of attributes, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(2)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l. Finally, public parameters Param are published as follows:(3)Param=G1,GT,N,e,H,H0,e,gp,Px,Py,Ti1≤i≤n,and master secret keys α,ti,1≤i≤n are securely stored. Note that each Ti corresponds to each attribute wi.


### 5.1.2. KeyGenAtt,α,a,β

For a data user with an attribute setAtt=w1,…,wt, if it wants to register to the system, it sends its attribute set Att to KGC, and then KGC makes use of its secret key to generate the secret key for the data owner with attribute set Att.(1)
First of all, KGC randomly chooses a numberr∈Zp to compute(4)sk0=gpα−r,(2)
and then for each attributewj in Att, it computes skj=gpr⋅tj−1.(3)
The resultant secret keyskAtt=sk0,skiwi∈Att.In addition, for data owner, it randomly choosessko∈Zp to compute its public key pko=gpsko. This public-private key pair pko,sko is used to generate digital signature.


## 5.1.1. Setupλ,U

Taking a security parameterλ and the universal attribute set U as inputs, it outputs G1,GT,N=p⋅q,e←Gen1λ, where G1 and GT are cyclic groups of order N and p,q are two distinct 512-bit primes. Let Gp and Gq denote two subgroups of group G1 with the order p and q, respectively, and gp and gq are the generators of Gp and Gq, respectively. e:G1×G1⟶GT is a bilinear pairing map.For the universal attribute setU=w1,…,wn, where n is the maximum number of attributes, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(2)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l. Finally, public parameters Param are published as follows:(3)Param=G1,GT,N,e,H,H0,e,gp,Px,Py,Ti1≤i≤n,and master secret keys α,ti,1≤i≤n are securely stored. Note that each Ti corresponds to each attribute wi.


## 5.1.2. KeyGenAtt,α,a,β

For a data user with an attribute setAtt=w1,…,wt, if it wants to register to the system, it sends its attribute set Att to KGC, and then KGC makes use of its secret key to generate the secret key for the data owner with attribute set Att.(1)
First of all, KGC randomly chooses a numberr∈Zp to compute(4)sk0=gpα−r,(2)
and then for each attributewj in Att, it computes skj=gpr⋅tj−1.(3)
The resultant secret keyskAtt=sk0,skiwi∈Att.In addition, for data owner, it randomly choosessko∈Zp to compute its public key pko=gpsko. This public-private key pair pko,sko is used to generate digital signature.


## 5.2. Blinding of Dataset

For a data owner, if it wants to outsource the datasetX=xii∈I to cloud server, to ensure the security of the dataset, it needs to blind the dataset before outsourcing. To achieve the confidentiality and fine-grained access control of data, it needs to execute the following Blind algorithms.


### 5.2.1. Blind (Param,T, X)

For a datasetX and an access structure T, the algorithm takes X and T as inputs and outputs the blinded data. The detailed process is given as follows.(1)
First of all, it picks a numbert∈Zp and R0′∈Gq at random to compute(5)C0=Pxt⋅R0′,C=Pyt,Cix=H0HCpk0⊕H0xii∈I,whereI=X is the size of the dataset X and ‖ is a concatenate operator.(2)
Then, it generates a signatureδs=δ1,δ2 on C1x‖⋯‖CIx by randomly choosing r0∈ZN, where δ1=gpr0 and δ2=r0−sko⋅H1C1x‖⋯‖CIx,δ1modN.(3)
To facilitate the expression of access structure, we adopt access treeT. For each node v in T, the algorithm randomly allocates a kv−1 degree polynomial fv in the top-down manner, where kv is the children number of node v. Especially for root RT of access tree T, the allocated polynomial fRx should satisfy fR0=t; for the other node v, it should satisfy fv0=fparentvindexv, where indexv denotes an index value of node v in the children of its parent node, and parentv is the parent node of node v. Finally, for each leaf node i of access tree T corresponding to an attribute wi, the blinded data is computed(6)Ci=Tifi0Ri′,whereRi′ is a random element in group Gq. Note that Ti corresponds to the attribute wi.(4)
At last, the blinded dataset ofX is BT=T,δs,C0,Cixi∈I,Cjj∈T, and data owner uploads them to cloud server.


## 5.2.1. Blind (Param,T, X)

For a datasetX and an access structure T, the algorithm takes X and T as inputs and outputs the blinded data. The detailed process is given as follows.(1)
First of all, it picks a numbert∈Zp and R0′∈Gq at random to compute(5)C0=Pxt⋅R0′,C=Pyt,Cix=H0HCpk0⊕H0xii∈I,whereI=X is the size of the dataset X and ‖ is a concatenate operator.(2)
Then, it generates a signatureδs=δ1,δ2 on C1x‖⋯‖CIx by randomly choosing r0∈ZN, where δ1=gpr0 and δ2=r0−sko⋅H1C1x‖⋯‖CIx,δ1modN.(3)
To facilitate the expression of access structure, we adopt access treeT. For each node v in T, the algorithm randomly allocates a kv−1 degree polynomial fv in the top-down manner, where kv is the children number of node v. Especially for root RT of access tree T, the allocated polynomial fRx should satisfy fR0=t; for the other node v, it should satisfy fv0=fparentvindexv, where indexv denotes an index value of node v in the children of its parent node, and parentv is the parent node of node v. Finally, for each leaf node i of access tree T corresponding to an attribute wi, the blinded data is computed(6)Ci=Tifi0Ri′,whereRi′ is a random element in group Gq. Note that Ti corresponds to the attribute wi.(4)
At last, the blinded dataset ofX is BT=T,δs,C0,Cixi∈I,Cjj∈T, and data owner uploads them to cloud server.


## 5.3. PSI Computation

To obtain private set intersection of a blinded datasetBT of dataset X uploaded by a special data owner, the stage is divided into three parts: Token1 generation, Token2 generation, and set intersection computation. Firstly, a data user with dataset Y needs to run TokenGen1 algorithm to produce a PSI-token 1 for cloud server, and then cloud server runs TokenGen2 algorithm to produce a PSI-token 2 by using PSI-token 1. Finally, data user computes the intersection X∩Y of the two datasets X and Y by using the PSI-token 2 produced by cloud server. The detailed processes are given as follows.


### 5.3.1. TokenGen1Param,skAtt

Taking system parametersParam and secret key of data user skAtt, this algorithm randomly selects a number μ∈Zp to compute a PSI-token 1:(7)ToK1=sk1μ,…,sk2μ,…,skAttμ,sk0μ.


### 5.3.2. TokenGen2Param,ToK1,BT

Taking the PSI-token 1ToK1 and the blinded dataset BT, this algorithm firstly verifies whether Att satisfies the access tree T correlating to the blinded dataset BT. If it does not, then it outputs ⊥ and aborts it.For the sake of illustration, we define a recursive algorithmTok2⋅ that takes as input an access tree T, an attribute set Att, the blinded dataset BT, and a node from T.For each node inT, cloud server executes a recursive algorithm Tok2⋅ as follows:(1)
Ifθi∈T is a leaf node and attθi∈Att, where wi=attθi is an attribute corresponding to leaf node θi, then it computes(8)Tok2T,Att,BT,θi=eCi,skiμ=egptifi0,gprti−1μeRifi0⋅Ri′,gprti−1μ=egptifi0,gpμrti−1=egp,gprμfi0,whereskiμ is the i-th element in PSI-token 1 ToK1 and Ci is the i-th in Cjj∈T.(2)
Ifθi∈T is a nonleaf node, the recursive algorithm runs as follows: for all child node childθi of node θi, it calls Tok2T,Att,BT,indexj,childθi for j=1,…,ω and stores them, where childθi denotes all children of θi and indexj,childθi denotes the j-th child node of θi. The algorithm is run until children nodes of a node are leaf nodes, and then we compute(9)Tok2T,Att,BT,θi=∏k=1ωTok2T,Att,BT,indexk,childθiΔω,k0,wherechildθi is the child node of node θi and w is threshold value of parent node parentθi, and for θi, its Lagrange coefficient is(10)Δω,kx=∏j∈1,ω,j≠kx−jk−j.Through recursively runningTok2T,Att,BT,θi in the bottom-to-top manner in access tree T, we can obtain the PSI–token 2,(11)Tok2=egp,gprtμ.In the end, the algorithm returns the PSI-token 2Tok2, Cixi∈I and the signature δs of Cixi∈I.


### 5.3.3. PSI ComputationParam,ToK2,Cixi∈IY=yjj∈1,…,Y,δs

Upon receivingToK2 and Cixi∈I, the algorithm takes ToK2,Cixi∈I, Y, and δs as inputs and executes Algorithm 1. In this algorithm, lines 1–3 are used to check the validity of the signature δs, which can achieve the integrity checking of the returned dataset by cloud server. Lines 7–17 are used to seek the intersection of two datasets. If Cix==τj holds, then the element of the intersection is found.Algorithm 1:PSI computation.
Input: Param,δs,μ,pk0,ToK2,Cixi∈I,Y=yjj∈1,…,YOutput: the intersection X∩Y of dataset X and dataset Y(1)
ifδ1!=g1δ2⋅pkoH1C1x‖⋯‖CIx,δ1, then(2)
printf (“the returned dataset is not intact”);(3)
exit (0);(4)
end(5)
ComputeTmp=Tok2μ−1eC0,sk0;(6)
Sety=Y;(7)
fori=1:Ido(8)
forj=1:ydo(9)
Computeτj=H0HTmp‖pk0⊕H0yj;(10)
ifCix==τj, then(11)
printf (“%d,” yj);(12)
else(13)
j++;(14)
end(15)
end(16)
i++;(17)
end


## 5.3.1. TokenGen1Param,skAtt

Taking system parametersParam and secret key of data user skAtt, this algorithm randomly selects a number μ∈Zp to compute a PSI-token 1:(7)ToK1=sk1μ,…,sk2μ,…,skAttμ,sk0μ.


## 5.3.2. TokenGen2Param,ToK1,BT

Taking the PSI-token 1ToK1 and the blinded dataset BT, this algorithm firstly verifies whether Att satisfies the access tree T correlating to the blinded dataset BT. If it does not, then it outputs ⊥ and aborts it.For the sake of illustration, we define a recursive algorithmTok2⋅ that takes as input an access tree T, an attribute set Att, the blinded dataset BT, and a node from T.For each node inT, cloud server executes a recursive algorithm Tok2⋅ as follows:(1)
Ifθi∈T is a leaf node and attθi∈Att, where wi=attθi is an attribute corresponding to leaf node θi, then it computes(8)Tok2T,Att,BT,θi=eCi,skiμ=egptifi0,gprti−1μeRifi0⋅Ri′,gprti−1μ=egptifi0,gpμrti−1=egp,gprμfi0,whereskiμ is the i-th element in PSI-token 1 ToK1 and Ci is the i-th in Cjj∈T.(2)
Ifθi∈T is a nonleaf node, the recursive algorithm runs as follows: for all child node childθi of node θi, it calls Tok2T,Att,BT,indexj,childθi for j=1,…,ω and stores them, where childθi denotes all children of θi and indexj,childθi denotes the j-th child node of θi. The algorithm is run until children nodes of a node are leaf nodes, and then we compute(9)Tok2T,Att,BT,θi=∏k=1ωTok2T,Att,BT,indexk,childθiΔω,k0,wherechildθi is the child node of node θi and w is threshold value of parent node parentθi, and for θi, its Lagrange coefficient is(10)Δω,kx=∏j∈1,ω,j≠kx−jk−j.Through recursively runningTok2T,Att,BT,θi in the bottom-to-top manner in access tree T, we can obtain the PSI–token 2,(11)Tok2=egp,gprtμ.In the end, the algorithm returns the PSI-token 2Tok2, Cixi∈I and the signature δs of Cixi∈I.


## 5.3.3. PSI ComputationParam,ToK2,Cixi∈IY=yjj∈1,…,Y,δs

Upon receivingToK2 and Cixi∈I, the algorithm takes ToK2,Cixi∈I, Y, and δs as inputs and executes Algorithm 1. In this algorithm, lines 1–3 are used to check the validity of the signature δs, which can achieve the integrity checking of the returned dataset by cloud server. Lines 7–17 are used to seek the intersection of two datasets. If Cix==τj holds, then the element of the intersection is found.Algorithm 1:PSI computation.
Input: Param,δs,μ,pk0,ToK2,Cixi∈I,Y=yjj∈1,…,YOutput: the intersection X∩Y of dataset X and dataset Y(1)
ifδ1!=g1δ2⋅pkoH1C1x‖⋯‖CIx,δ1, then(2)
printf (“the returned dataset is not intact”);(3)
exit (0);(4)
end(5)
ComputeTmp=Tok2μ−1eC0,sk0;(6)
Sety=Y;(7)
fori=1:Ido(8)
forj=1:ydo(9)
Computeτj=H0HTmp‖pk0⊕H0yj;(10)
ifCix==τj, then(11)
printf (“%d,” yj);(12)
else(13)
j++;(14)
end(15)
end(16)
i++;(17)
end


## 5.4. Correctness

In the subsection, we show that the proposed scheme is correct, because in the blinding stage, the datasetX=xii∈I is blinded into BT, and each Cix in BT has the following format Cix=H0HC‖pk0⊕H0xi.In addition, in the stage of intersection computation, data user can use PSI-token 2 to obtain the following relation:(12)Tmp=Tok2μ−1⋅eC0,sk0=egp,gprtePxt⋅R0′,gpα−r=egp,gprtegpt,gpα−r=egp,gpαt=Pyt.Thus, it can obtainX∩Y by running Algorithm 1 in PSI computation phase. It means that the proposed scheme is correct.


## 6. Security Analysis

In this section, we show that the proposed PSI scheme satisfies data secrecy and resists the adaptively chosen-dataset attack.Theorem 1.
Supposed that the decisional bilinear Diffie-Hellman problem (DBDHP) inG1 is difficult to solve, then the proposed PSI scheme is adaptively secure against chosen-dataset attack in the standard model.Proof.
LetA be a (probabilistic polynomial time) PPT adversary who launches an attack on the proposed PSI scheme. If it breaks the proposed PSI scheme in a nonnegligible probability ϵ, then we are able to construct a challenger Cℋ which solves the DBDHP problem.
First of all, let us recall the DBDHP problem in subgroupGp of group G. Assume that Y⟶=gp,gpa,gpb,gpc,Z is an instance of the BDHP problem, where a,b,c are random numbers and Z∈RGT, its goal is to determine whether the case egp,gpabc=?Z holds. In the following interactive game, Cℋ attempts to solve the BDHP problem by invoking A as a subroutine.


### 6.1. Init Phase

In this phase, the adversaryA randomly selects the challenged access structure T∗ and an attribute set U and sends them to the challenger.


### 6.2. Setup

In this phase,Cℋ initializes system parameters based on the instance of the DBDH problem. Firstly, it chooses α′∈ZN to compute(13)Py=egpa,gpbegp,gpα′.It impliesα=ab+α′.Also, fori=1 to n, it randomly chooses ti∈Zp, R0∈Gq, and Ri∈Gq to compute(14)∀wi∈U:Ti=gpb/ti⋅Ri,textwi∉T∗,gpti⋅Ri,textwi∈T∗,1≤i≤n.Additionally, it also setsPx=gp⋅R0 and chooses sko∈Zp to set data owner’s public key as pko=gpsko. Finally, it sends Px,Py,T1,…,Tn to the adversary A.


### 6.3. Phase 1

To simulate the game,A can adaptively make a series of queries in this phase.(i)
KeyGen query: while the adversaryA makes a KeyGen query with an attribute set W=w1,…,wl, where wi∈T∗, to response it, CH executes the following steps:(1)
First of all, it randomly choosesr′∈Zp to compute(15)sk0=gpα′gpb−r′=gpα′−r′b=gpα′+ab−ab+r′b=gpα−ab+r′b=gpα−r.It implicitly definesr=ab+r′b.(2)
Fori=1 to l, because all wi∉T∗, we can compute(16)ski=gpatigpr′ti=gpr⋅b/ti−1.(3)
Finally, the secret key of the corresponding attributeWskW=sk1,…,skl,sk0 is returned to the adversary A.(ii)
TokenGen1 queries: when the adversaryA issues a TokenGen1 query with attribute W, Cℋ first makes a KeyGen query with attribute W to obtain secret key skW=sk1,sk2,…,sk0, and then it chooses a random number ζ to compute a PSI-token 1:(17)ToK1=sk1ζ,sk2ζ,…,skWζ,sk0ζ,and it sendsToK1 to the adversary.(iii)
Decryption queries: for a decryption query of the ciphertextCT with attribute set W, Cℋ parses access tree T from CT and checks whether W matches the access structure T. If it matches, then Cℋ performs a KeyGen query with W to obtain skW, and then it makes use of skW to call Decryption algorithm to retrieve data M.


### 6.4. Challenge

In this stage, to produce a challenge, the adversaryA sends the challenged access tree T∗ in which l leaf nodes are involved and correspond to attributes w1,w2,…,wl and the two dataset X0 and X1 to the challenger Cℋ, where X0=xi0 and X1=xi1 are of the same size.Subsequently,Cℋ randomly flips a coin γ∈0,1 to produce the following blinded dataset:(1)
It sets(18)C0∗=gpc⋅R0⋅R0′,C∗=Z⋅egpc,gpα′,Cix=H0HC∗pko⊕H0xiγi∈I.(2)
Assume that root denotes the root node ofT∗. According to the principle from top to bottom, to compute leaf node information, we first construct a polynomial frootx satisfying gpfroot0=gpc. Although frootx is unknown, we can compute the exponential form of frootx, namely,(19)gpfrootx=gpt′⋅∏i=1πgpaixi,whereai∈Zp is the random number and π is a threshold value of root node in access tree T∗. For the children node vi of root node root, we can compute gpfvi0=gpfrooti, where fvix represents the polynomial corresponding to node vi that is the i-child of root node.According to the above method, we can obtain the following values by applying the manner from top to bottom, namely,(20)Ci∗=gpc⋅fi0ti⋅Ri,for∀wi∈T∗,wherefix denotes the polynomial of leaf node i in access tree T∗. Because Ti=gpti⋅Ri and Ri is a random element, we have(21)Ci∗=gpc⋅fi0ti⋅Ri=Ticfi0⋅Ri,(3)
and then it produces a signatureδs∗=δ1∗,δ2∗ by randomly choosing t0∗, where δ1∗=gpr0∗ and δ2∗=r0∗−sko⋅H1C1x‖⋯‖CIx.(4)
At last, the blinded datasetBT∗ is BT∗=δs∗,C0∗,Ci′∗,Cixi∈I which is returned to AI.Obviously, whenZ=egp,gpabc, we have(22)C∗=Z⋅egpc,gpα′=egp,gpabc+α′c=egp,gpab+α′c=egp,gpαc=Pyc.Thus, the produced blinded one of the datasetXγ by the above way is valid.


### 6.5. Phase 2

In this phase,A can still issue a series of new queries as in Phase 1, but the following restriction conditions must been satisfied:(1)
T∗ is not allowed to make the KeyGen queries.(2)
The blinded datasetBT∗ is not allowed to make TokenGen1 query.


### 6.6. Guess

Eventually, the adversaryA returns its guess γ′∈0,1. If γ=γ′, then it outputs true. Otherwise, false is returned.From the point of the adversaryA’s view, the simulation of Cℋ is indistinguishable from the real game. When Z is a random element of G1, the produced blinded dataset BT∗ has the same distribution as the real blinded dataset. It is independent of the choice of dataset Xγ. In this case, the probability of A guessing γ′ is(23)Prγ=γ′=12.WhenZ=egp,gpabc holds, the produced blinded dataset BT∗ is a valid one. If the adversary A breaks the proposed scheme in nonnegligible probability ε, then it means that the adversary can solve the DBDH problem in groups G1 with the following probability:(24)Prgp,gpa,gpb,gpc,egp,gpabc,Z≥12⋅12+12ε.However, due to the difficulty of solving the DBDH problem in groupsG1, thus the probability of the adversary A breaking the proposed scheme is negligible.Theorem 2.
If it is infeasible to generate a message that yields a given hash value for one-way hash functionH⋅, then our proposed PSI scheme can satisfy data secrecy in the standard model.Proof.
Suppose that there exists an adversaryAII which breaks data secrecy in the proposed scheme, then we can construct an algorithm B to solve the one-way problem of hash function. Firstly, we review the one-way problem of hash function. Given a hash value y and one-way cryptographic hash function H0, its goal is to find a number η such that it satisfies H0η=y. To break the one-way problem of hash function, the algorithm ℬ needs to initialize system parameters and plays an interactive game with the adversary Aℐℐ. The detailed processes are given as follows:(i)
Setup: the algorithmℬ takes a security parameter λ as inputs and outputs system parameters G1,GT,N=p⋅q,e,Gp,Gq,gp,gq←Gen1λ. For the universal attribute set U=w1,…,wn, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(25)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l. Finally, public parameters(26)Param=G1,GT,N,e,H,H0,e,Px,Py,Ti1≤i≤nare sent to the adversaryAII.(ii)
Phase 1: in this phase, the adversaryAII is able to adaptively issue KeyGen queries and TokenGen1 queries. When the adversary AII issues such queries, the algorithm B runs KeyGen() and TokenGen1() to response them since it has master secret key.(iii)
Challenge: to produce a challenge, the adversaryAII submits an access tree T∗ and k−1-element dataset X∗=x1∗,…,xk−1∗ to the algorithm B. The algorithm B randomly chooses a number r∈Zp to compute the blinded dataset BT∗.(1)
Fori=1 to k−1, it computes Cix∗=H0HPyr‖pk0⊕H0xi∗.(2)
Wheni=k, it sets Ckx∗=y. It means that there is a number d∗∈Zp which satisfies y=H0HPyr‖pk0⊕H0d∗.(3)
For the other components ofBT∗, they are computed by the Blind algorithm since the algorithm B possesses master secret key and the private key of data owner.(4)
Finally, it returnsBT∗=T∗,δs∗,C0∗,Cix∗i∈1,…,k,Ci∗i∈T∗ to the adversary AII.(iv)
Phase 2: in this phase, the adversaryAII is still able to issue the same queries as those in Phase 1.(v)
Guess: at last, the adversaryA outputs its guess xk∗ in the position k for the dataset X∗ in the nonnegligible probability (note that xk∗=d∗ or xk∗≠d∗). If the adversary AII wins the game, then it means that xk∗ satisfies the following relation:(27)y=H0HPyr‖pk0⊕H0xk∗.
Thus, given a hash valuey, the algorithm can find a value HPyr‖pk0⊕H0y∗ to satisfy(28)y=H0HPyrpk0⊕H0xk∗.
Obviously, it is in contradiction with the one-way property of hash function. Therefore, for two datasetsX∗ and Y∗, the adversary A can obtain nothing about Y∗\X∗∩Y∗ or X∗\X∗∩Y∗, except the intersection in X∗∩Y∗.Theorem 3.
The proposed scheme can ensure the integrity of the returned blinded dataset by the cloud assuming that the underlying Schnorr signature is unforgeable.Proof.
Suppose that there exists an adversaryAIII which breaks the integrity problem of the returned blinded dataset in the proposed scheme, then a challenger can construct an algorithm B which can break Schnorr signature; its goal is to output a new message-signature.
LetCℋ be a challenger; to break the security of Schnorr signature, the challenger Cℋ runs as follows:(i)
Setup: the algorithmℬ takes security parameter λ as input and outputs system parameters G1,GT,N=p⋅q,e,Gp,Gq,gp,gq←Gen1λ. For the universal attribute set U=w1,…,wn, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(29)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l, and it chooses a number pko∈Zp as public key. Finally, public parameters(30)Param=G1,GT,N,e,H,H0,e,Px,Py,pk0,Ti1≤i≤nare sent to the adversaryAIII, and it keeps the master private key α,ti,1≤i≤n secretly.(ii)
Blinding dataset queries: the adversaryAIII is able to adaptively issue Blinding Dataset queries with a dataset X=xii∈X and an access tree T. When receiving a query X=xii∈X,T, the challenger executes as follows:(1)
It picks a numbert∈Zp at random to compute(31)C0=Pxt⋅R0′,C=Py,tCix=H0HC‖pk0⊕H0xii∈I.(2)
Then, it sendsC1x‖⋯‖CIx to algorithm ℬ, and algorithm ℬ makes a signing query to signing oracle in the Schnorr signature security game with string C1x‖⋯‖CIx. After obtaining the returned signature δs, ℬ returns it to the challenger Cℋ.(3)
Next, the challengerCℋ computes the following values by adopting to access trees T:(32)Ci=Tifi0Ri′,whereRi′ is a random element in group Gq.(4)
Finally, it returns the blinded datasetBT=T,δs,C0,Cixi∈I,Cii∈T to the adversary AIII.(iii)
Output: eventually, the adversaryAIII outputs Tok2∗,Ci∗xi∈I,δs∗. The adversary AIII wins the game if δs is a valid signature on C1∗x‖⋯‖CX∗x and the string C1∗x‖⋯‖CX∗x is never made signing query to ℬ. If AIII wins this game, then Cℋ sets δs∗ as the output of ℬ algorithm. Because δs is a valid signature on C1∗x‖⋯‖CX∗x and never makes a signing query with string C1∗x‖⋯‖CX∗x, it means that algorithm ℬ successfully breaks the unforgeability of Schnorr signature.
Obviously, it is in contradict with the unforgeability of Schnorr signature. Thus, the proposed PSI protocol can ensure the integrity of dataset.Theorem 4.
Our proposed PSI scheme can achieve hidden access attributes.Proof.
In the proposed scheme, to achieve the attributes anonymously, we use the orthogonality property of composite order bilinear groups. In the encryption phase, the random elementsR0 and Rj are introduced into C0 and Cjj∈T in the blinded dataset. It can effectively prevent some malicious attackers from testing the access policy by a possible access structure wj′ and guessing the access structure. Thus, it achieves hidden access attributes.


## 6.1. Init Phase

In this phase, the adversaryA randomly selects the challenged access structure T∗ and an attribute set U and sends them to the challenger.


## 6.2. Setup

In this phase,Cℋ initializes system parameters based on the instance of the DBDH problem. Firstly, it chooses α′∈ZN to compute(13)Py=egpa,gpbegp,gpα′.It impliesα=ab+α′.Also, fori=1 to n, it randomly chooses ti∈Zp, R0∈Gq, and Ri∈Gq to compute(14)∀wi∈U:Ti=gpb/ti⋅Ri,textwi∉T∗,gpti⋅Ri,textwi∈T∗,1≤i≤n.Additionally, it also setsPx=gp⋅R0 and chooses sko∈Zp to set data owner’s public key as pko=gpsko. Finally, it sends Px,Py,T1,…,Tn to the adversary A.


## 6.3. Phase 1

To simulate the game,A can adaptively make a series of queries in this phase.(i)
KeyGen query: while the adversaryA makes a KeyGen query with an attribute set W=w1,…,wl, where wi∈T∗, to response it, CH executes the following steps:(1)
First of all, it randomly choosesr′∈Zp to compute(15)sk0=gpα′gpb−r′=gpα′−r′b=gpα′+ab−ab+r′b=gpα−ab+r′b=gpα−r.It implicitly definesr=ab+r′b.(2)
Fori=1 to l, because all wi∉T∗, we can compute(16)ski=gpatigpr′ti=gpr⋅b/ti−1.(3)
Finally, the secret key of the corresponding attributeWskW=sk1,…,skl,sk0 is returned to the adversary A.(ii)
TokenGen1 queries: when the adversaryA issues a TokenGen1 query with attribute W, Cℋ first makes a KeyGen query with attribute W to obtain secret key skW=sk1,sk2,…,sk0, and then it chooses a random number ζ to compute a PSI-token 1:(17)ToK1=sk1ζ,sk2ζ,…,skWζ,sk0ζ,and it sendsToK1 to the adversary.(iii)
Decryption queries: for a decryption query of the ciphertextCT with attribute set W, Cℋ parses access tree T from CT and checks whether W matches the access structure T. If it matches, then Cℋ performs a KeyGen query with W to obtain skW, and then it makes use of skW to call Decryption algorithm to retrieve data M.


## 6.4. Challenge

In this stage, to produce a challenge, the adversaryA sends the challenged access tree T∗ in which l leaf nodes are involved and correspond to attributes w1,w2,…,wl and the two dataset X0 and X1 to the challenger Cℋ, where X0=xi0 and X1=xi1 are of the same size.Subsequently,Cℋ randomly flips a coin γ∈0,1 to produce the following blinded dataset:(1)
It sets(18)C0∗=gpc⋅R0⋅R0′,C∗=Z⋅egpc,gpα′,Cix=H0HC∗pko⊕H0xiγi∈I.(2)
Assume that root denotes the root node ofT∗. According to the principle from top to bottom, to compute leaf node information, we first construct a polynomial frootx satisfying gpfroot0=gpc. Although frootx is unknown, we can compute the exponential form of frootx, namely,(19)gpfrootx=gpt′⋅∏i=1πgpaixi,whereai∈Zp is the random number and π is a threshold value of root node in access tree T∗. For the children node vi of root node root, we can compute gpfvi0=gpfrooti, where fvix represents the polynomial corresponding to node vi that is the i-child of root node.According to the above method, we can obtain the following values by applying the manner from top to bottom, namely,(20)Ci∗=gpc⋅fi0ti⋅Ri,for∀wi∈T∗,wherefix denotes the polynomial of leaf node i in access tree T∗. Because Ti=gpti⋅Ri and Ri is a random element, we have(21)Ci∗=gpc⋅fi0ti⋅Ri=Ticfi0⋅Ri,(3)
and then it produces a signatureδs∗=δ1∗,δ2∗ by randomly choosing t0∗, where δ1∗=gpr0∗ and δ2∗=r0∗−sko⋅H1C1x‖⋯‖CIx.(4)
At last, the blinded datasetBT∗ is BT∗=δs∗,C0∗,Ci′∗,Cixi∈I which is returned to AI.Obviously, whenZ=egp,gpabc, we have(22)C∗=Z⋅egpc,gpα′=egp,gpabc+α′c=egp,gpab+α′c=egp,gpαc=Pyc.Thus, the produced blinded one of the datasetXγ by the above way is valid.


## 6.5. Phase 2

In this phase,A can still issue a series of new queries as in Phase 1, but the following restriction conditions must been satisfied:(1)
T∗ is not allowed to make the KeyGen queries.(2)
The blinded datasetBT∗ is not allowed to make TokenGen1 query.


## 6.6. Guess

Eventually, the adversaryA returns its guess γ′∈0,1. If γ=γ′, then it outputs true. Otherwise, false is returned.From the point of the adversaryA’s view, the simulation of Cℋ is indistinguishable from the real game. When Z is a random element of G1, the produced blinded dataset BT∗ has the same distribution as the real blinded dataset. It is independent of the choice of dataset Xγ. In this case, the probability of A guessing γ′ is(23)Prγ=γ′=12.WhenZ=egp,gpabc holds, the produced blinded dataset BT∗ is a valid one. If the adversary A breaks the proposed scheme in nonnegligible probability ε, then it means that the adversary can solve the DBDH problem in groups G1 with the following probability:(24)Prgp,gpa,gpb,gpc,egp,gpabc,Z≥12⋅12+12ε.However, due to the difficulty of solving the DBDH problem in groupsG1, thus the probability of the adversary A breaking the proposed scheme is negligible.Theorem 2.
If it is infeasible to generate a message that yields a given hash value for one-way hash functionH⋅, then our proposed PSI scheme can satisfy data secrecy in the standard model.Proof.
Suppose that there exists an adversaryAII which breaks data secrecy in the proposed scheme, then we can construct an algorithm B to solve the one-way problem of hash function. Firstly, we review the one-way problem of hash function. Given a hash value y and one-way cryptographic hash function H0, its goal is to find a number η such that it satisfies H0η=y. To break the one-way problem of hash function, the algorithm ℬ needs to initialize system parameters and plays an interactive game with the adversary Aℐℐ. The detailed processes are given as follows:(i)
Setup: the algorithmℬ takes a security parameter λ as inputs and outputs system parameters G1,GT,N=p⋅q,e,Gp,Gq,gp,gq←Gen1λ. For the universal attribute set U=w1,…,wn, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(25)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l. Finally, public parameters(26)Param=G1,GT,N,e,H,H0,e,Px,Py,Ti1≤i≤nare sent to the adversaryAII.(ii)
Phase 1: in this phase, the adversaryAII is able to adaptively issue KeyGen queries and TokenGen1 queries. When the adversary AII issues such queries, the algorithm B runs KeyGen() and TokenGen1() to response them since it has master secret key.(iii)
Challenge: to produce a challenge, the adversaryAII submits an access tree T∗ and k−1-element dataset X∗=x1∗,…,xk−1∗ to the algorithm B. The algorithm B randomly chooses a number r∈Zp to compute the blinded dataset BT∗.(1)
Fori=1 to k−1, it computes Cix∗=H0HPyr‖pk0⊕H0xi∗.(2)
Wheni=k, it sets Ckx∗=y. It means that there is a number d∗∈Zp which satisfies y=H0HPyr‖pk0⊕H0d∗.(3)
For the other components ofBT∗, they are computed by the Blind algorithm since the algorithm B possesses master secret key and the private key of data owner.(4)
Finally, it returnsBT∗=T∗,δs∗,C0∗,Cix∗i∈1,…,k,Ci∗i∈T∗ to the adversary AII.(iv)
Phase 2: in this phase, the adversaryAII is still able to issue the same queries as those in Phase 1.(v)
Guess: at last, the adversaryA outputs its guess xk∗ in the position k for the dataset X∗ in the nonnegligible probability (note that xk∗=d∗ or xk∗≠d∗). If the adversary AII wins the game, then it means that xk∗ satisfies the following relation:(27)y=H0HPyr‖pk0⊕H0xk∗.
Thus, given a hash valuey, the algorithm can find a value HPyr‖pk0⊕H0y∗ to satisfy(28)y=H0HPyrpk0⊕H0xk∗.
Obviously, it is in contradiction with the one-way property of hash function. Therefore, for two datasetsX∗ and Y∗, the adversary A can obtain nothing about Y∗\X∗∩Y∗ or X∗\X∗∩Y∗, except the intersection in X∗∩Y∗.Theorem 3.
The proposed scheme can ensure the integrity of the returned blinded dataset by the cloud assuming that the underlying Schnorr signature is unforgeable.Proof.
Suppose that there exists an adversaryAIII which breaks the integrity problem of the returned blinded dataset in the proposed scheme, then a challenger can construct an algorithm B which can break Schnorr signature; its goal is to output a new message-signature.
LetCℋ be a challenger; to break the security of Schnorr signature, the challenger Cℋ runs as follows:(i)
Setup: the algorithmℬ takes security parameter λ as input and outputs system parameters G1,GT,N=p⋅q,e,Gp,Gq,gp,gq←Gen1λ. For the universal attribute set U=w1,…,wn, randomly choose α,t1,t2,…,tn∈Zp and R0,R1,…,Rn∈Gq to compute public keys(29)Px=gp⋅R0,Py=egp,gpα,Ti=gpti⋅Ri,1≤i≤n.Additionally, KGC chooses two collision-resistant hash functionsH and H0 satisfying H:GT⟶0,1l and H0:0,1∗⟶0,1l, and it chooses a number pko∈Zp as public key. Finally, public parameters(30)Param=G1,GT,N,e,H,H0,e,Px,Py,pk0,Ti1≤i≤nare sent to the adversaryAIII, and it keeps the master private key α,ti,1≤i≤n secretly.(ii)
Blinding dataset queries: the adversaryAIII is able to adaptively issue Blinding Dataset queries with a dataset X=xii∈X and an access tree T. When receiving a query X=xii∈X,T, the challenger executes as follows:(1)
It picks a numbert∈Zp at random to compute(31)C0=Pxt⋅R0′,C=Py,tCix=H0HC‖pk0⊕H0xii∈I.(2)
Then, it sendsC1x‖⋯‖CIx to algorithm ℬ, and algorithm ℬ makes a signing query to signing oracle in the Schnorr signature security game with string C1x‖⋯‖CIx. After obtaining the returned signature δs, ℬ returns it to the challenger Cℋ.(3)
Next, the challengerCℋ computes the following values by adopting to access trees T:(32)Ci=Tifi0Ri′,whereRi′ is a random element in group Gq.(4)
Finally, it returns the blinded datasetBT=T,δs,C0,Cixi∈I,Cii∈T to the adversary AIII.(iii)
Output: eventually, the adversaryAIII outputs Tok2∗,Ci∗xi∈I,δs∗. The adversary AIII wins the game if δs is a valid signature on C1∗x‖⋯‖CX∗x and the string C1∗x‖⋯‖CX∗x is never made signing query to ℬ. If AIII wins this game, then Cℋ sets δs∗ as the output of ℬ algorithm. Because δs is a valid signature on C1∗x‖⋯‖CX∗x and never makes a signing query with string C1∗x‖⋯‖CX∗x, it means that algorithm ℬ successfully breaks the unforgeability of Schnorr signature.
Obviously, it is in contradict with the unforgeability of Schnorr signature. Thus, the proposed PSI protocol can ensure the integrity of dataset.Theorem 4.
Our proposed PSI scheme can achieve hidden access attributes.Proof.
In the proposed scheme, to achieve the attributes anonymously, we use the orthogonality property of composite order bilinear groups. In the encryption phase, the random elementsR0 and Rj are introduced into C0 and Cjj∈T in the blinded dataset. It can effectively prevent some malicious attackers from testing the access policy by a possible access structure wj′ and guessing the access structure. Thus, it achieves hidden access attributes.


## 7. Performance Analysis

In this section, we evaluate the efficiency of the proposed PSI protocol in terms of computational costs. To give a fair comparison, we abandon the comparison with the other PSI protocols. The reason is that the goals of the proposed PSI protocol support fine-grained access control with hiding attribute and ensure the integrity of the returned dataset, which differs from most of the existing PSI protocols in which their goals are to be securely against semihonest adversaries or to improve efficiency of the PSI protocol. To our knowledge, it is the first PSI protocol with supporting attribute hidden fine-grained access control and integrity verification. Additionally, experiment results also show that the proposed PSI protocol is quite efficient.To illustrate the effectiveness of the proposed PSI scheme, we also implement the experiment simulation based on an Ubuntu 18.04 laptop computer with the Intel(R) Core(TM) 4130 CPU@3.40 GHz, 4 GB RAM. All algorithms are written with C language in Linux system. Because the proposed scheme is based on composite order bilinear pairing, we adopt “Type A1 pairing” in PBC Library which provides a level of security equivalent to 1024-bit discrete logarithm problem. To be simple, we assume that access treeT only includes a root node and n leaf nodes, namely, it is in the form of (w1ANDw2AND⋯ANDwn), where wi is an attribute.In the proposed protocol, private set intersection is only computed by data user, and data owner does not need to participate in this phase. In the whole protocol, after the dataset is outsourced to cloud server, the data owner is offline. However, in many PSI protocols [6, 18, 20, 27], both of data owner and data user have to be online and have interaction with each other.Here, we show the performance of the proposed PSI protocol by evaluating the execution-time overhead of each algorithm.The setup algorithm is used to initialize system parameters; the required execution times are mainly determined by the cardinalities of the universal attribute set. Its running time increases as the cardinalities of the universal attribute set increase; the corresponding performance graphs are given in Figure2(a). For the KeyGen algorithm, its performance is shown in Figure 2(b). According to Figure 2, we can find that the running time in the two algorithms is greatly affected by the size of the data user’s attribute set. Thus, they are two slashes that increase monotonically. When the number of attributes is 60, these two algorithm’s running time is approximately 1.2 seconds. It is acceptable. For Blind algorithm, its running time is mainly from generation of fine-grained access structure and linear to the size of attribute set. However, the size of cardinality of the dataset has little influence on the runtime of algorithm after access attributes are fixed, the reason is that we blind the dataset by adopting XOR operation in the blinding process, and XOR operation’s runtime is negligible. Their performance graphs are shown in Figures 3(a) and 3(b). From Figure 3(b), we can know when attribute number is 20 and the cardinality of dataset is 220; the runtime of algorithm is only about 371.578 ms. For TokenGen1 algorithm and TokenGen2 algorithm, their runtime is linear to the size of the data user’s attribute set, the reason is that the two algorithms correspond to decryption process of attribute-based encryption scheme. Their performance graphs are shown in Figures 4(a) and 4(b). For PSI Computation algorithm, the runtime of algorithm is only related to the cardinality of dataset; it is shown in Figure 5, and we can know that for the cardinality of dataset, from 210 to 218, the runtime of algorithm hardly changes since only 3 exponentiation in G1, 1 pairing operator, Y hash operators, and Y XOR operators are needed in this algorithm. However, XOR operator and hash operator are two kinds of lightweight operations that take almost no time. When the cardinality of dataset is 220, PSI computation runtime is 296.369 ms. Thus, it is very suitable for the resource-limited data user.Figure 2
(a) Computational costs of system initialization. (b) Computational costs of KeyGen algorithm.
(a)(b)Figure 3
(a) The impact of the size of attributes on runtime in the Blind algorithm. (b) The impact of the cardinality of datasets on runtime in the Blind algorithm.
(a)(b)Figure 4
(a) The impact of the size of data user’s attributes on runtime in the TokenGen1 algorithm. (b) The impact of the size of data user’s attributes on runtime in the TokenGen2 algorithm.
(a)(b)Figure 5
The impact of the cardinality of dataset on runtime in the PSI Computation algorithm.


## 8. Conclusion

In this work, we presented the first private set intersection (PSI) computation with supporting hidden attribute fine-grained access control and integrity verification based on attribute encryption. The main goal of the proposed scheme is to realize customized function to cater to practical application. Compared to most of the existing schemes, the proposed scheme has the following merits: (i) for data owner, it achieves dataset’s access control by defining an access policy before the dataset is outsourced. (ii) It makes data owners to be offline during the whole PSI protocol. (iii) It ensures the integrity of the returned dataset from the cloud. (iv) The main PSI computation burden is transferred to the cloud. (v) It supports one-to-many PSI computations, that is to say, after the blinded dataset is outsourced to the cloud, data user can implement PSI computations with the cloud for arbitrary times. In addition, after giving the corresponding security analysis, we evaluate each algorithm of the proposed scheme by experiment simulation; the results show that the performance of the proposed scheme is efficient and practical. To reduce computational cost of the whole scheme, we will study fine-grained access control PSI scheme with constant computation in the future work.



---

*Source: 3963037-2021-09-02.xml*