# Delegated Key-Policy Attribute-Based Set Intersection over Outsourced Encrypted Data Sets for CloudIoT

Authors: Yanfeng Shi; Shuo Qiu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Private set intersection (PSI) is a fundamental cryptographic primitive, allowing two parties to calculate the intersection of their data sets without exposing additional private information. In cloud-based IoT system, IoT-enabled devices would like to outsource their data sets in their encrypted form to the cloud. In this scenario, how to delegate the set intersection computation over outsourced encrypted data sets to the cloud and how to achieve the fine-grained access control for PSI without divulging any additional information to the cloud are still open problems. With that in mind, in this work, we combine key-policy attribute-based encryption (KP-ABE) and PSI to introduce such a novel concept, calleddelegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI), to solve this problem. Then we propose a first concrete KP-ABSI scheme and analyze its efficiency.


---

## Body

## 1. Introduction

Internet of Things (IoT) is enabling Smart City initiatives all over the world. Recently, IoT-based applications have been widely developed, such as smart grid and smart healthcare [1, 2]. With the growth of IoT, enormous amount of data is generated by IoT-enabled devices. They need to be stored, processed, and accessed. Thus, Alessio et al. firstly merged cloud and IoT to introduce a new paradigm named CloudIoT to solve the issues [3]. For cloud-based IoT, the research on the security and privacy for the big data of IoT is a hot spot.Private set intersection (PSI), firstly proposed by [4], is a special case of secure multiparty computation. It enables two parties to calculate the set intersection of their data sets under the condition of privacy preservation. It is applied to many practical scenarios, such as IoT and internet-based personal health record (PHR) systems. In traditional PSI solutions, the data users hold their own data sets. However, in CloudIoT computing, data users (i.e., IoT-enabled devices) with limited computing power and storage resources would like to outsource their data sets to the cloud. For confidentiality and privacy, data sets should be encrypted before outsourcing. Cloud service providers provide flexible services to fulfill cloud users’ demand.Based on this, we research on PSI over outsourced encrypted data sets in the CloudIoT system. In this scenario, the data users (i.e., the IoT-enabled devices) will encrypt and outsource their data sets to the cloud and then delegate the cloud to perform the set intersection. It has been studied by some works [5–7]. But it indeed raises a concern on how to enforce fine-grained access control for limiting the cloud’s capability on computing set intersection. For this, Mohammad Ali et. al combined ciphertext-policy attribute-based encryption and private set intersection to propose an attribute-based private set intersection [8]. However, in their solution, the data user, who requests the set intersection operation, should hold the data sets in plaintext form. It does not really focus on outsourced encrypted data sets. Besides, there is still no solution for key-policy setting.In this paper, we firstly combined key-policy attribute-based encryption and private set intersection to introduce a novel concept calleddelegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI). KP-ABSI focuses on the problem of set intersection over outsourced data sets in the cloud paradigm. It allows data owners to specify some attributes set on his/her data set and encrypt it before outsourcing, respectively. A data user with proper access control policy (satisfied by the attribute set specified by the data owner and himself/herself) can generate a token to delegate the cloud sever to perform the set intersection over his/her and the data owner’s outsourced encrypted data sets. We formally give the definition and security notion for KP-ABSI and propose a concrete construction.Our KP-ABSI scheme has three distinctive properties: (1) Our solution realizes fine-grained authorization for set intersection over encrypted outsourced data sets by combining KP-ABE and PSI. (2) The cloud server cannot obtain any information about the plaintexts beyond the result of set intersection, which is also with the form of ciphertexts. (3) Compared with existing PSI schemes, our schemes do not require interaction with the data owner or the trusted authority.


## 2. Related Work

Although the scholars have carried out extensive research on PSI, the existing solutions cannot solve the problems considered in this paper. In the following part, we will briefly introduce the related works. In general, they can be divided into three categories as follows.Two-Party Private Set Intersection. The traditional PSI has two participants, a data owner and a data user. Both of them hold their own data sets and interactively compute the set intersection [9, 10]. However, two-party PSI does not apply to cloud computing because two parties must hold their data sets by themselves.Three-Party Private Set Intersection. Typically, three-party PSI involves three participants: a data owner, a data user, and the cloud server. The data user and the data owner would like to outsource their data sets to the cloud and delegate set intersection computation to the cloud. [5, 7, 11]. Moreover, public key encryption with equality test [12–15] can also be used to attain this goal. However, in these solutions, there is not any authorization mechanism and the data owner online is required to authorize the data user. So, they are not practical in the cloud computing.Attribute-Based Encryption. ABE, which is introduced by Sahai and Waters, achieves fine-grained access control for outsourced data [16]. There are two variants of ABE: key-policy attribute-based encryption (KP-ABE) where the decryption key is associated with the access control policy (e.g., [17–19]) and ciphertext-policy attribute-based encryption (CP-ABE) where the ciphertext is associated with the access control policy (e.g., [20–22]). In 2017, Zhu et al. presented a key-policy attribute-based encryption with equality test, which can be utilized to do the set intersection over outsourced encrypted data set of one element. After that, Wang et al. proposed the first ciphertext-policy attribute-based encryption with equality test scheme [23, 24]. Later, Cui et al. improved its efficiency [25]. However, attribute-based encryption with equality test is only for one element. For this, in 2020, Mohammad Ali et. al firstly combined CP-ABE and PSI to propose an attribute-based set intersection scheme [8]. It achieves fine-grained access control for set intersection computation. Unfortunately, their solution requires the data user to hold his/her data set in the plaintext form. It did not really focus on outsourced encrypted data sets in the cloud computing. Moreover, there are no key-policy setting solutions for attribute-based set intersection.Thus, in this paper, we combine KP-ABE with PSI to introduce a novel primitive-delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI). For fairness, we summarize the properties of KP-ABSI scheme in Table1.Table 1
Property summary for PSI solutions in the literature and KP-ABSI in this paper. PSI delegation means that the data owners can delegate set intersection operations to the cloud. Outsourced encrypted data set means it can do PSI over outsourced encrypted data sets in the cloud. Fine-grained authorization means that it supports attribute-based access control policy.
SchemesPSI delegationOutsourced encrypted data setsFine-grained authorizationTwo-party PSI [9, 10]✕✕✕Three-party PSI [5, 12]✓✓✕AB-PSI [8]✓✕✓KP-ABSI✓✓✓


## 3. Problem Formulation

### 3.1. System Model

The system model for KP-ABSI is shown in Figure1. There are three participants: the trusted attribute authority, the cloud users (e.g., data owner Alice, authorized data user Bob, and unauthorized data user Carlos), and the cloud server. The trusted attribute authority primarily initiates the public parameters and issues private keys for data users according to their access control polices. Cloud server provides powerful storage and computing services for cloud users. The cloud users outsource their private data sets to the cloud server. Specifically, a cloud user, Alice, outsources her data set to the cloud in encrypted form, where the encryption is conducted according to some attribute set UAttA. An authorized user, Bob, whose access control policy is satisfied by the attribute set UAttA, can delegate to the cloud the computation of set intersection between Alice’s outsourced encrypted sets and his own outsourced encrypted sets (Bob naturally has the private key to decrypt his own outsourced encrypted data). Meanwhile, any unauthorized user, Carlos, is neither able to decrypt Alice’s outsourced encrypted data sets nor able to delegate the cloud to perform the set intersection operation.Figure 1
System model of delegated key-policy attribute-based set intersection over outsourced encrypted data sets.In this model, we assume that the cloud is semitrusted (i.e., honest-but-curious), which means that the cloud honestly executes the protocol for two honest users, but tries to learn useful information beyond the ciphertexts through set intersection operations. Cloud users may be malicious and may collude with each other. We even allow a malicious user, say Bob, to collude with the semitrusted cloud. However, in this case, we cannot require that the cloud be not able to decrypt the honest user’s, say Alice, ciphertext data set when the malicious and colluding user, Bob, has the private key for decrypting Alice’s data set (e.g., Bob can simply give his private key to the cloud).


### 3.2. Functional Definition

In this part, we introduce the formal definition for delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI), where private keys are associated with access control policies. For convenience, we denote byUAtt an attribute set and by T an access policy in KP-ABSI. Let FUAtt,T=1 if and only if UAtt satisfies T in KP-ABSI.Definition 1.
Delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI) includes five algorithms as follows:pk,mk⟵Setup1ℓ: Given a security parameter ℓ as input, the trusted attribute authority initializes the system public parameters pk and the master secret key mk.sk⟵KeyGenmk,T: Given the master secret key mk and an access control policy T, the trusted attribute authority issues private keys sk for a data user.cph⟵EncD,UAtt: Given an attribute set UAtt, a data user encrypts his/her private data set D to the ciphertext cph. The resulting ciphertexts will be outsourced to the cloud.tkn⟵TokenGensk: With his/her private key sk, the data user generates a token tkn and delegates the set intersection computation to the cloud.rslt⟵SItkn,cph,cph′: The cloud utilizes tkn to compute, on behalf of two data users, the set intersection rslt only if the access control policy T corresponding to tkn satisfies both FUAtt,T=1 and FUAtt′,T=1, where the attribute sets UAtt and UAtt′ are, respectively, specified by cph and cph′. We say that a KP-ABSI scheme is correct if the following holds: Given pk,mk⟵Setup1ℓ, sk⟵KeyGenmk,T, tkn⟵TokenGensk, and cph⟵EncD,UAtt for set D and cph′⟵EncD′,IEnc′ for set D′, if FUAtt,T=1 and UAtt′,T=1, then rslt is the encrypted form of set intersection D∩D′, where rslt⟵SIcph,cph′,tkn.


### 3.3. Security Definitions

The security for KP-ABSI can be expressed by the three properties as follows.


#### 3.3.1. Selective Security against Chosen-Plaintext Attack

It indicates that a probabilistic polynomial-time (PPT) adversaryA, without being given the corresponding tokens, is not able to obtain any useful information about the encrypted data sets. Notice that “selective” means that adversary A should choose a target attribute set UAtt∗ which it wants to challenge before the public parameters are generated. The security definition for selective security against chosen-plaintext attack can be formalized via the following game between an adversary A and a challenger.Setup:A selects a target attribute set UAtt∗ and sends it to the challenger. The challenger runs Setup algorithm to initialize pk and mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles:OKeyGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger returns sk⟵KeyGenmk,pk,T to A.OTokenGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge: The adversaryA randomly gives two data sets D0 and D1, where D0=D1 but D0≠D1, to the challenger. Then, the challenger picks σ⟵R0,1 at random, builds the challenge ciphertext cph∗=EncDσ,UAtt∗, and sends cph∗ to A.Phase 2: Same as Phase 1.Guess:A eventually outputs a guess σ′ of σ. If σ=σ′, we say that A wins the game.Definition 2.
We say that a KP-ABSI scheme is selective secure against chosen-plaintext attack, if any PPT adversaryA wins the above game with a negligible advantage, where the advantage can be described as Prσ′=σ−1/2.


#### 3.3.2. One-Way Security against Chosen-Plaintext Attack

It says that a PPT adversaryA, even given an appropriate token, cannot obtain the plaintexts corresponding to the ciphertexts. Note that the term “appropriate” means that the access control policy that generates the token is satisfied by the attribute set associated with the target ciphertext. Of course, A can choose a plaintext data set of its choice, encrypt it with public keys, and then utilize the token to check whether or not the target ciphertext is equal to the ciphertext of his choice. In other words, this type of brute-force attack is inherent to the set intersection problem and we can only demand that A cannot have any attack strategy significantly better than the brute-force attack, as captured by this property via the following game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles. Meanwhile, the challenger maintains a list LT, which is initially empty.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge:A gives a target attribute set UAtt∗ to the challenger, where, ∀T∈LT, FUAtt∗,T=0. The challenger selects an access control T∗ such that FUAtt∗,T∗=1, picks D∗ uniformly at random, runs cph∗⟵EncD∗,UAtt∗ and tkn∗⟵TokenGenKeyGenT∗, and returns cph∗,tkn∗ to A.Phase 2:A executes the same as in Phase 1, except that FUAtt∗,T=0 when querying OKeyGenT.Guess:A outputs a guess d. If d∈D∗, we say that A wins the game.Definition 3.
We say that a KP-ABSI scheme achieves one-way security against chosen-plaintext attack if, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage is defined as Prd∈D∗−mD∗/Msg, where m is the number of guess/brute-force attacks A makes, and Msg is the message space of set elements.


#### 3.3.3. Fine-Grained Authorization Security

This property says that the cloud is unable to utilize the given tokens to conduct set intersection over ciphertexts if no access control policy (associated with the data user’s private key) that generates the tokens is satisfied by both of the attribute sets associated with the two ciphertexts. More specifically, consider the tokentkn1 that can be used to conduct set intersection over ciphertexts cph1 and cph2 and the token tkn2 that can be used to conduct set intersection over ciphertexts cph2 and cph3. If the access control policy that is used to generate tkn1 is not satisfied by the attribute set associated with ciphertext cph3, and the access control policy that is used to generate tkn2 is not satisfied by the attribute set associated with ciphertext cph1; then the cloud cannot do the set intersection computation over ciphertexts cph1 and cph3 by using tkn1 and/or tkn2. The definition for fine-grained authorization security can be described via a game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master secret key.Phase 1: The adversaryA makes polynomial queries for the following oracles. Meanwhile, the challenger maintains two lists LT and Ltkn, which are empty initially.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger runs sk⟵KeyGenmk,T and tkn⟵TokenGensk, returns tkn back to A, and records T to Ltkn.Challenge:A gives two target attribute sets UAtt1∗ and UAtt2∗ to the challenger. Then the challenger chooses two data sets D0,D1, picks a bit σ⟵R0,1 randomly, runs cph1∗⟵EncD0,UAtt1∗ and cph2∗⟵EncDσ,UAtt2∗, and returns cph1∗,cph2∗ to A. Here, we require that∀T∈LT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously;∀T∈Ltkn, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Phase 2:A executes the same as in Phase 1, except for the following:When queryingOKeyGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.When queryingOTokenGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Guess: The adversaryA eventually outputs a guess σ′. If σ=σ′, we say that A wins the game.Definition 4.
If, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage can be expressed as Prσ′=σ−1/2, we say that a KP-ABSI scheme achieves fine-grained authorization security.


## 3.1. System Model

The system model for KP-ABSI is shown in Figure1. There are three participants: the trusted attribute authority, the cloud users (e.g., data owner Alice, authorized data user Bob, and unauthorized data user Carlos), and the cloud server. The trusted attribute authority primarily initiates the public parameters and issues private keys for data users according to their access control polices. Cloud server provides powerful storage and computing services for cloud users. The cloud users outsource their private data sets to the cloud server. Specifically, a cloud user, Alice, outsources her data set to the cloud in encrypted form, where the encryption is conducted according to some attribute set UAttA. An authorized user, Bob, whose access control policy is satisfied by the attribute set UAttA, can delegate to the cloud the computation of set intersection between Alice’s outsourced encrypted sets and his own outsourced encrypted sets (Bob naturally has the private key to decrypt his own outsourced encrypted data). Meanwhile, any unauthorized user, Carlos, is neither able to decrypt Alice’s outsourced encrypted data sets nor able to delegate the cloud to perform the set intersection operation.Figure 1
System model of delegated key-policy attribute-based set intersection over outsourced encrypted data sets.In this model, we assume that the cloud is semitrusted (i.e., honest-but-curious), which means that the cloud honestly executes the protocol for two honest users, but tries to learn useful information beyond the ciphertexts through set intersection operations. Cloud users may be malicious and may collude with each other. We even allow a malicious user, say Bob, to collude with the semitrusted cloud. However, in this case, we cannot require that the cloud be not able to decrypt the honest user’s, say Alice, ciphertext data set when the malicious and colluding user, Bob, has the private key for decrypting Alice’s data set (e.g., Bob can simply give his private key to the cloud).


## 3.2. Functional Definition

In this part, we introduce the formal definition for delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI), where private keys are associated with access control policies. For convenience, we denote byUAtt an attribute set and by T an access policy in KP-ABSI. Let FUAtt,T=1 if and only if UAtt satisfies T in KP-ABSI.Definition 1.
Delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI) includes five algorithms as follows:pk,mk⟵Setup1ℓ: Given a security parameter ℓ as input, the trusted attribute authority initializes the system public parameters pk and the master secret key mk.sk⟵KeyGenmk,T: Given the master secret key mk and an access control policy T, the trusted attribute authority issues private keys sk for a data user.cph⟵EncD,UAtt: Given an attribute set UAtt, a data user encrypts his/her private data set D to the ciphertext cph. The resulting ciphertexts will be outsourced to the cloud.tkn⟵TokenGensk: With his/her private key sk, the data user generates a token tkn and delegates the set intersection computation to the cloud.rslt⟵SItkn,cph,cph′: The cloud utilizes tkn to compute, on behalf of two data users, the set intersection rslt only if the access control policy T corresponding to tkn satisfies both FUAtt,T=1 and FUAtt′,T=1, where the attribute sets UAtt and UAtt′ are, respectively, specified by cph and cph′. We say that a KP-ABSI scheme is correct if the following holds: Given pk,mk⟵Setup1ℓ, sk⟵KeyGenmk,T, tkn⟵TokenGensk, and cph⟵EncD,UAtt for set D and cph′⟵EncD′,IEnc′ for set D′, if FUAtt,T=1 and UAtt′,T=1, then rslt is the encrypted form of set intersection D∩D′, where rslt⟵SIcph,cph′,tkn.


## 3.3. Security Definitions

The security for KP-ABSI can be expressed by the three properties as follows.


### 3.3.1. Selective Security against Chosen-Plaintext Attack

It indicates that a probabilistic polynomial-time (PPT) adversaryA, without being given the corresponding tokens, is not able to obtain any useful information about the encrypted data sets. Notice that “selective” means that adversary A should choose a target attribute set UAtt∗ which it wants to challenge before the public parameters are generated. The security definition for selective security against chosen-plaintext attack can be formalized via the following game between an adversary A and a challenger.Setup:A selects a target attribute set UAtt∗ and sends it to the challenger. The challenger runs Setup algorithm to initialize pk and mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles:OKeyGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger returns sk⟵KeyGenmk,pk,T to A.OTokenGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge: The adversaryA randomly gives two data sets D0 and D1, where D0=D1 but D0≠D1, to the challenger. Then, the challenger picks σ⟵R0,1 at random, builds the challenge ciphertext cph∗=EncDσ,UAtt∗, and sends cph∗ to A.Phase 2: Same as Phase 1.Guess:A eventually outputs a guess σ′ of σ. If σ=σ′, we say that A wins the game.Definition 2.
We say that a KP-ABSI scheme is selective secure against chosen-plaintext attack, if any PPT adversaryA wins the above game with a negligible advantage, where the advantage can be described as Prσ′=σ−1/2.


### 3.3.2. One-Way Security against Chosen-Plaintext Attack

It says that a PPT adversaryA, even given an appropriate token, cannot obtain the plaintexts corresponding to the ciphertexts. Note that the term “appropriate” means that the access control policy that generates the token is satisfied by the attribute set associated with the target ciphertext. Of course, A can choose a plaintext data set of its choice, encrypt it with public keys, and then utilize the token to check whether or not the target ciphertext is equal to the ciphertext of his choice. In other words, this type of brute-force attack is inherent to the set intersection problem and we can only demand that A cannot have any attack strategy significantly better than the brute-force attack, as captured by this property via the following game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles. Meanwhile, the challenger maintains a list LT, which is initially empty.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge:A gives a target attribute set UAtt∗ to the challenger, where, ∀T∈LT, FUAtt∗,T=0. The challenger selects an access control T∗ such that FUAtt∗,T∗=1, picks D∗ uniformly at random, runs cph∗⟵EncD∗,UAtt∗ and tkn∗⟵TokenGenKeyGenT∗, and returns cph∗,tkn∗ to A.Phase 2:A executes the same as in Phase 1, except that FUAtt∗,T=0 when querying OKeyGenT.Guess:A outputs a guess d. If d∈D∗, we say that A wins the game.Definition 3.
We say that a KP-ABSI scheme achieves one-way security against chosen-plaintext attack if, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage is defined as Prd∈D∗−mD∗/Msg, where m is the number of guess/brute-force attacks A makes, and Msg is the message space of set elements.


### 3.3.3. Fine-Grained Authorization Security

This property says that the cloud is unable to utilize the given tokens to conduct set intersection over ciphertexts if no access control policy (associated with the data user’s private key) that generates the tokens is satisfied by both of the attribute sets associated with the two ciphertexts. More specifically, consider the tokentkn1 that can be used to conduct set intersection over ciphertexts cph1 and cph2 and the token tkn2 that can be used to conduct set intersection over ciphertexts cph2 and cph3. If the access control policy that is used to generate tkn1 is not satisfied by the attribute set associated with ciphertext cph3, and the access control policy that is used to generate tkn2 is not satisfied by the attribute set associated with ciphertext cph1; then the cloud cannot do the set intersection computation over ciphertexts cph1 and cph3 by using tkn1 and/or tkn2. The definition for fine-grained authorization security can be described via a game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master secret key.Phase 1: The adversaryA makes polynomial queries for the following oracles. Meanwhile, the challenger maintains two lists LT and Ltkn, which are empty initially.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger runs sk⟵KeyGenmk,T and tkn⟵TokenGensk, returns tkn back to A, and records T to Ltkn.Challenge:A gives two target attribute sets UAtt1∗ and UAtt2∗ to the challenger. Then the challenger chooses two data sets D0,D1, picks a bit σ⟵R0,1 randomly, runs cph1∗⟵EncD0,UAtt1∗ and cph2∗⟵EncDσ,UAtt2∗, and returns cph1∗,cph2∗ to A. Here, we require that∀T∈LT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously;∀T∈Ltkn, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Phase 2:A executes the same as in Phase 1, except for the following:When queryingOKeyGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.When queryingOTokenGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Guess: The adversaryA eventually outputs a guess σ′. If σ=σ′, we say that A wins the game.Definition 4.
If, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage can be expressed as Prσ′=σ−1/2, we say that a KP-ABSI scheme achieves fine-grained authorization security.


## 3.3.1. Selective Security against Chosen-Plaintext Attack

It indicates that a probabilistic polynomial-time (PPT) adversaryA, without being given the corresponding tokens, is not able to obtain any useful information about the encrypted data sets. Notice that “selective” means that adversary A should choose a target attribute set UAtt∗ which it wants to challenge before the public parameters are generated. The security definition for selective security against chosen-plaintext attack can be formalized via the following game between an adversary A and a challenger.Setup:A selects a target attribute set UAtt∗ and sends it to the challenger. The challenger runs Setup algorithm to initialize pk and mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles:OKeyGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger returns sk⟵KeyGenmk,pk,T to A.OTokenGenT: If FUAtt∗,T=1, the challenger aborts; otherwise, the challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge: The adversaryA randomly gives two data sets D0 and D1, where D0=D1 but D0≠D1, to the challenger. Then, the challenger picks σ⟵R0,1 at random, builds the challenge ciphertext cph∗=EncDσ,UAtt∗, and sends cph∗ to A.Phase 2: Same as Phase 1.Guess:A eventually outputs a guess σ′ of σ. If σ=σ′, we say that A wins the game.Definition 2.
We say that a KP-ABSI scheme is selective secure against chosen-plaintext attack, if any PPT adversaryA wins the above game with a negligible advantage, where the advantage can be described as Prσ′=σ−1/2.


## 3.3.2. One-Way Security against Chosen-Plaintext Attack

It says that a PPT adversaryA, even given an appropriate token, cannot obtain the plaintexts corresponding to the ciphertexts. Note that the term “appropriate” means that the access control policy that generates the token is satisfied by the attribute set associated with the target ciphertext. Of course, A can choose a plaintext data set of its choice, encrypt it with public keys, and then utilize the token to check whether or not the target ciphertext is equal to the ciphertext of his choice. In other words, this type of brute-force attack is inherent to the set intersection problem and we can only demand that A cannot have any attack strategy significantly better than the brute-force attack, as captured by this property via the following game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master private key.Phase 1: The adversaryA can make polynomial queries for the following oracles. Meanwhile, the challenger maintains a list LT, which is initially empty.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger calculates sk⟵KeyGenmk,T and returns tkn⟵TokenGensk to A.Challenge:A gives a target attribute set UAtt∗ to the challenger, where, ∀T∈LT, FUAtt∗,T=0. The challenger selects an access control T∗ such that FUAtt∗,T∗=1, picks D∗ uniformly at random, runs cph∗⟵EncD∗,UAtt∗ and tkn∗⟵TokenGenKeyGenT∗, and returns cph∗,tkn∗ to A.Phase 2:A executes the same as in Phase 1, except that FUAtt∗,T=0 when querying OKeyGenT.Guess:A outputs a guess d. If d∈D∗, we say that A wins the game.Definition 3.
We say that a KP-ABSI scheme achieves one-way security against chosen-plaintext attack if, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage is defined as Prd∈D∗−mD∗/Msg, where m is the number of guess/brute-force attacks A makes, and Msg is the message space of set elements.


## 3.3.3. Fine-Grained Authorization Security

This property says that the cloud is unable to utilize the given tokens to conduct set intersection over ciphertexts if no access control policy (associated with the data user’s private key) that generates the tokens is satisfied by both of the attribute sets associated with the two ciphertexts. More specifically, consider the tokentkn1 that can be used to conduct set intersection over ciphertexts cph1 and cph2 and the token tkn2 that can be used to conduct set intersection over ciphertexts cph2 and cph3. If the access control policy that is used to generate tkn1 is not satisfied by the attribute set associated with ciphertext cph3, and the access control policy that is used to generate tkn2 is not satisfied by the attribute set associated with ciphertext cph1; then the cloud cannot do the set intersection computation over ciphertexts cph1 and cph3 by using tkn1 and/or tkn2. The definition for fine-grained authorization security can be described via a game between an adversary A and a challenger.Setup: The challenger runsSetup to initialize pk,mk, sends pk to A, and sets mk as the master secret key.Phase 1: The adversaryA makes polynomial queries for the following oracles. Meanwhile, the challenger maintains two lists LT and Ltkn, which are empty initially.OKeyGenT: The challenger returns sk⟵KeyGenmk,T to A and records T to LT.OTokenGenT: The challenger runs sk⟵KeyGenmk,T and tkn⟵TokenGensk, returns tkn back to A, and records T to Ltkn.Challenge:A gives two target attribute sets UAtt1∗ and UAtt2∗ to the challenger. Then the challenger chooses two data sets D0,D1, picks a bit σ⟵R0,1 randomly, runs cph1∗⟵EncD0,UAtt1∗ and cph2∗⟵EncDσ,UAtt2∗, and returns cph1∗,cph2∗ to A. Here, we require that∀T∈LT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously;∀T∈Ltkn, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Phase 2:A executes the same as in Phase 1, except for the following:When queryingOKeyGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.When queryingOTokenGenT, FUAtt1∗,T and FUAtt2∗,T do not output 1 simultaneously.Guess: The adversaryA eventually outputs a guess σ′. If σ=σ′, we say that A wins the game.Definition 4.
If, for any PPT adversaryA, the advantage of A winning the game is negligible, where the advantage can be expressed as Prσ′=σ−1/2, we say that a KP-ABSI scheme achieves fine-grained authorization security.


## 4. Scheme Construction

### 4.1. Basic Idea

To illustrate the idea, let a data user’s private key begat,gbt, which can be generated by running qv0|v∈lvsT⟵ShareT,abt for some random t and setting gqv0H1attvtv,gtv, where tv is a random number with respect to leaf v∈lvsT. A set element d is encrypted into two parts:The first part is related tod; namely,(1)gbr1,gar1+r2H2d,gr2,whereg is a generator of G, r1 and r2 are two random numbers, H1,H2 are two hash functions, and a,b are private keys.The second part is related to the attribute set corresponding to the access control policy in question, namely,H1atir2 for ati∈UAtt.A data user can generate the token asgatk,gbtk,gqv0kH1attvktv,gktv, by which the cloud is able to translate the ciphertext into an intermediate form eH2d,gbtk once the attribute set UAtt satisfies the access control policy T.


### 4.2. KP-ABSI Construction

Setup(1ℓ): Given the security parameter ℓ as input, the public parameters and the master secret key can be generated as follows:Lete,q,g,gT,G,GT⟵BMapGen1ℓ.LetH1:0,1∗⟶G and H2:0,1∗⟶G be two secure hash functions that are modeled as random oracles.Selecta,b⟵Rℤp and set the public parameters and the master secret key as(2)pk=e,G,GT,g,ga,gb,H1,H2,mk=a,b.KeyGenmk,T: Given access tree T, this algorithm selects t⟵Rℤp, computes X1=gat and X2=gbt, and runs qv0|v∈lvsT⟵ShareT,abt. Then, for each leaf v∈lvsT, the algorithm selects tv⟵Rℤp and sets Yv=gqv0H1attvtv and Zv=gtv. The secret key is(3)sk=T,X1,X2,Yv,Zv|v∈lvsT.EncD,UAtt: Given set for outsourcing, D=d0,…,dn, this algorithm encrypts the set as follows: for each dj, it selects r1,r2⟵Rℤp , sets A1=gbr1, A2=gar1+r2H2dj, and A3=gr2, and computes Bi=H1atir2 for each ati∈UAtt. The ciphertext of dj is(4)cphj=UAtt,A1,A2,A3,Bi|ati∈UAtt.The set of ciphertexts iscph=cph0,…,cphn.TokenGensk: Given secret key sk, this algorithm selects k⟵Rℤp, sets X^1=X1k=gatk and X^2=X2k=gbtk, and computes Y^v=Yvk and Z^v=Zvk for leaf v∈lvsT. The token is(5)tkn=T,X^1,X^2,Y^v,Z^v|v∈lvsT.SItkn,cph,cph′: Given cph=cph0,…,cphn, cph′=cph0′,…,cphm′, and tkn, this algorithm is executed as follows:Givencphj∈cph, it selects an attribute set S∈UAtt satisfying T. If S does not exist, it returns 0. Otherwise, it computes(6)Ev=eY^v,A3eZ^v,Bi=eg,gqv0kr2,for allv∈lvsT with attv=ati, computes(7)Eroot=eg,gabtkr2⟵CombineT,Ev|attv∈S,E1=eA1,X^1=eg,gabtkr1,E2j=eA2,X^2ErootE1=eH2dj,gbtk,and setsE=E20,…,E2n.Givencphj′∈cph′, it selects an attribute set S′∈UAtt′ satisfying T. If S′ does not exist, it returns 0. Otherwise, it computes Ev′=eY^v,A3′/eZ^v,Bi=eg,gqv0kr2′ for all v∈lvsT with attv=ati, computes(8)Eroot′=eg,gabtkr2′⟵CombineT,Ev′|attv∈S′,E1′=eA1′,X^1=eg,gabtkr1′,E2j′=eA2,X^2Eroot′E1′=eH2dj′,gbtk,and setsE′=E20′,…,E2m′.Output the set intersectionrslt=cphj|cphj∈cph,E2j∈E∩E′.The correctness of the above KP-ABSI scheme can be verified by following the protocol. In what follows, we analyze its security.


### 4.3. Security Analysis

Theorem 1.
Under the DLN assumption, the above KP-ABSI scheme achieves the selective security against chosen-plaintext attacks in the random oracle as specified in Definition2.Firstly, we prove that our scheme achieves the security goal whenD=1 (i.e., the message space has a single element) and then extends the proof to the case D>1.Proof.
We show that if there is a PPT adversaryA that wins the selective security game with a nonnegligible advantage μ, then a challenger that can solve the DLN problem with the advantage at least μ/2 can be constructed. Specifically, given a DLN instance g,h,f,fr1,gr2,Q, where g,f,h,Q⟵RG and r1,r2⟵Rℤp are unknown, the game is simulated by the challenger as follows.Setup: The adversaryA gives an attribute set UAtt∗ to the challenger. Then the challenger produces the bilinear map e:G×G⟶GT, constructs gb=f and ga=h with a and b unknown, and sets pk=e,g,f,h,G,GT. The challenger sends pk to A. The challenger maintains two lists ListH1ati,αi,βi and ListH2d,γ, which are initially empty. A can query OH1 and OH2 polynomially many times as follows:OH1ati: Given attribute ati, the challenger responds as follows:The caseati was queried before: it retrieves αi,βi from ListH1 and returns fαigβi to A.The caseati was not queried before: if ati∈UAtt∗, it selects βi⟵Rℤp, adds ati,αi=0,βi to ListH1, and returns gβi to A; otherwise, it selects αi,βi⟵Rℤp, adds ati,αi,βi to ListH1, and returns fαigβi to A.OH2d: Given a message d as input, if d was queried before, it retrieves γ from ListH2 and returns gγ to A; otherwise, it picks γ⟵Rℤp randomly, records d,γ to ListH2, and returns gγ to A.Phase 1: The adversaryA makes polynomial queries for the following oracles as follows:OKeyGenT: If FUAtt∗,T=1, the simulation is aborted; otherwise, the challenger produces sk according to the two following procedures:PolySatTv,UAtt∗,λv: Given a secret value λv, this procedure builds the polynomial for each node of subtree Tv, where FUAtt∗,Tv=1. Suppose that the threshold value of node v is kv; it lets qv0=λv and chooses kv−1 coefficients uniformly at random to uniquely determine the polynomial qv. Then it recursively runs PolySatTv′,UAtt∗,λv′ to build the polynomial for each child node v′ of v, by letting λv′=qvindexv′.PolyUnsatTv,UAtt∗,gλv: Given an element gλv∈G, where λv is unknown to the challenger, this procedure is to build the polynomial for each node of subtree Tv, where FUAtt∗,Tv=0. Assume that the threshold value of node v is kv and V is the set of children of node v such that, ∀v′∈V,FUAtt∗,Tv′=1. Since FUAtt∗,Tv=0, we have V<kv. For each v′∈V, it selects λv′⟵Rℤp and sets λv′=qvindexv′. It then determines the other kv−V points of polynomial qv such that gqv0=gλv. For each child node v′ of node v, it executes the following:(i)
Ifv′ is a node with Fat∗,Tv′=1, it runs PolySatTv′,UAtt∗,qvindexv′, where qvindexv′ is known.(ii)
Ifv′ is a node with Fat∗,Tv′=0, it runs PolySatTv′,UAtt∗,gλv′, where gλv′=gqvindexv′ is known.Based on the two procedures above, the challenger executesPolyUnsatT,UAtt∗,ga by implicitly defining qroot0=a. Note that, for each v∈lvsT, the challenger knows qv0 if attv∈UAtt∗ and knows gqv0 otherwise. Therefore, it generates credentials as follows by selecting t⟵Rℤp and setting X1=ht and X2=ft (while noting that btqv0 is the secret share of abt):Ifattv=atj for some atj∈UAtt∗, it selects tv⟵Rℤp and sets Yv=ftqv0gβjtv=gbtqv0H1attvtv and Zv=gtv.Ifattv∉UAtt∗, where attv=atj for some j, it selects tv′⟵Rℤp and sets Yv=fttv′αjgqv0−βj/αjgtv′βj and Zv=g−qv0/αjgtv′. Note that Yv,Zv is valid because the challenger implicitly sets tv=−qv0/αj+tv′ and the following:(9)Yv=fttv′αjgqv0−βj/αjgtv′βj=ftqv0fαjgβj−qv0/αj+tv′=ftqv0H1atjtv,Zv=g−qv0/αjgtv′=gtv.OtknT: The challenger queries OKeyGenT to obtain sk and returns tkn⟵TokenGensk to A.Challenge: The adversaryA gives two messages D0=d0 and D1=d1 of equal length to the challenger. Then the challenger randomly picks σ⟵R0,1, encrypts dσ to cph∗=UAtt∗,fr1,QH2dσ,gr2,gr2βj|atj∈UAtt∗, and sends cph∗ to A.Phase 2:A executes the same as in the above Phase1.Guess: The adversaryA will eventually output a guess σ′ of σ. If σ′=σ, the challenger outputs Q=hr1+r2; otherwise, it outputs Q≠hr1+r2.
The simulation is completed. In Challenge phase, ifQ=hr1+r2, then cph∗ is indeed a valid ciphertext of Dσ and the probability that A outputs σ′=σ is 1/2+μ. Otherwise, if Q is a random element from G, then cph∗ is a random group element and the probability that A outputs σ′=σ is 1/2. In conclusion, the probability that the challenger correctly guesses Q=?hr1+r2 is 1/21/2+1/2+μ=1/2+μ/2. That is, if A wins the game with the advantage μ, then the challenger solves the DLN problem with the advantage μ/2.
So far, we have shown that our KP-ABSI scheme is selective secure against chosen-plaintext attack whenD=1. In what follows, we prove that our KP-ABSI scheme achieves the selective security against chosen-plaintext attack for the general case of D>1.
Suppose thatA gives two sets D0=d0,…,dn and D1=d0′,…,dn′. Denote by cphi the encryption of d0,…,di,di+1′,…,dn′, meaning that cphn is the encryption of D0 and cph−1 is the encryption of D1. The Challenge phase is extended to accommodate an additional adversary A′ as follows:A′ picks a random index i⟵R0,n and presents di,di′ to the challenger. Then the challenger sends back cphi to A′ by encrypting di if σ=0 or returns di′ if σ=1.A′ encrypts d0,…,di−1 and di+1′,…,dn′ and returns cph0,…,cphn to A. A′ outputs A’s output σ′.
Note thatA′ sends to A the ciphertext cphi if σ=0 and the ciphertext cphi−1 if σ=1. Denote by Acphi the guess of A with ciphertexts cphi. Then we show the probability that A′ wins the game. Note that(10)PrA′outputs0|σ=0=∑j=0n1n+1PrAcphj=0,PrA′outputs0|σ=1=∑j=0n1n+1PrAcphj−1=1.
Therefore, the probability thatA′ wins the game is(11)12PrA′cph=0|σ=0+12PrA′cph=1|σ=1=∑j=0n12n+1PrAcphj=0+∑j=0n12n+1PrAcphj−1=1=n2n+1+12n+1PrAcphn=0+12n+1PrAcph−1=1=n2n+1+1n+112PrAcphn=0+12PrAcph−1=1≤12+ε,where ε is negligible because the advantage that A′ wins the game is negligible. Thus, the probability that A distinguishes cph−1 from cphn is(12)12PrAcphn=0+12PrAcph−1=1≤12+n+1ε.
That is, the advantage ofA distinguishing cph−1 from cphn is at most n+1ε. Therefore, the scheme achieves the selective security against chosen-plaintext attack when D≥1.Theorem 2.
Given one-way hash functionH2, the above KP-ABSI scheme achieves the one-way security against chosen-plaintext attack as specified in Definition 3.Proof.
We prove this theorem by showing that if there is a PPT adversaryA winning the one-way security game against chosen-plaintext attack with a nonnegligible advantage μ, then a challenger breaking the one-way hash function H2 can be simulated.
GivenH2d∗=y∗, the challenger can simulate the one-way security game as follows:Setup: The challenger randomly picksa,b⟵Rℤp, produces pk=e,G,GT,g,p,ga,gb,mk=a,b, and sends pk to A.Phase 1: The challenger maintains a listLT, which is empty initially. A makes polynomial queries for the following oracles:OKeyGenT: Given an access control policy T, it returns sk⟵KeyGenmk,pk,T to A and adds T to LT.OtknT: Given an access control policy T, it runs tkn⟵TokenGenKeyGenmk,pk,T,pk and returns tkn to A.Challenge:A gives an attribute set UAtt∗ to the challenger, where, ∀T∈LT, FUAtt∗,T=0. The challenger picks j⟵Rℤp and sets a data set D∗=d0,d1,…,d|D∗|−1, where d0,…,dj−1,dj+1,…,dD∗−1 are randomly chosen from the message space Msg and dj is implicitly set as dj=d∗ and generates the ciphertext cph=cphkk∈0,D∗−1 as follows:Ifk≠j, cphk is generated the same as in the real construction.Ifk=j,(13)cphk=UAtt∗,A1=gbr1,A2=gar1+r2y∗,A3=gr2,Bi=H1atir2|ati∈UAtt∗,by randomly choosingr1,r2⟵Rℤp and implicitly setting dj=d∗.The challenger chooses an access treeT∗ satisfying FUAtt∗,T∗=1, runs tkn∗⟵TokenGenKeyGenmk,pk,T∗,pk, and returns cph∗=cph,tkn∗ to the adversary A.Phase 2: The adversaryA executes the same as in Phase 1 while complying with the necessary requirements defined by the game.Guess:A will eventually output a guess d to the challenger. The challenger wins if d=d∗.
The simulation is completed. If the probability thatA outputs d∈D∗ is Prd∈D∗−mD∗/Msg=μ, then Prd∈D∗=mD∗/Msg+μ. Since the data set size is D∗, Prd:d=d∗≥Prd∈D∗/D∗=1/D∗mD∗/Msg+μ. Therefore, if A wins the one-way security game against chosen-plaintext attack with a nonnegligible advantage μ, the one-way hash function H2 can be broken by the challenger with a nonnegligible probability at least 1/D∗mD∗/Msg+μ. □Theorem 3.
The KP-ABSI achieves fine-grained authorization security in the generic bilinear group model as specified in Definition4.Proof.
Similar to the proof for Theorem1, firstly, we prove that our KP-ABSI scheme achieves fine-grained authorization when the challenge size D0=D1=1 and then extend the proof to the case of challenge size D0=D1>1.Setup: The challenger randomly picksa,b⟵Rℤp, produces pk=e,G,GT,g,p,ga,gb, and sends pk to A. The challenger maintains two lists ListH1atj,αj and ListH2d,β, which are empty initially. A can make polynomial queries for the following OH1 and OH2.OH1atj: Given an attribute atj, if atj was queried before, the challenger returns gαj by retrieving αj from ListH1; otherwise, the challenger picks αj⟵Rℤp, records atj,αj to ListH1, and returns gαj to A.OH2d: Given a message d, if d was queried before, the challenger returns gβ; otherwise, the challenger picks β⟵Rℤp, records d,β to ListH2, and returns gβ to A.Phase 1: The challenger keeps the two lists,LT and Ltkn, which are initially empty. A can make polynomial queries for the following oracles.OKeyGenT: The challenger selects tu⟵Rℤp and runs qv0u|v∈lvsT⟵ShareT,abtu. For each node v∈lvsT, the challenger chooses tvu⟵Rℤp and sets(14)sk=T,X1=gatu,X2=gbtu,Yv=gqv0u+αjtvu,Zv=gtvu|v∈lvsT,whereattv=atj. The challenger sends sk to A and records T to LT.OtknT: The challenger runs OKeyGenT, selects ku⟵Rℤp, and sets(15)tkn=T,Y^v=Yvku=gqv0uku+αjtvuku,Z^v=Zvku=gtvuku|v∈lvsT,X^1=X1ku=gatuku,X^2=X2ku=gbtuku,whereattv=atj. It returns tkn to A and adds T to Ltkn.Challenge:A chooses two attribute sets UAtt1∗ and UAtt2∗ with the following restrictions: (1) ∀T∈LT, FUAtt1∗,T and FUAtt2∗,T cannot output 1 at the same time, and, (2) ∀T∈Ltkn, FUAtt1∗,T and FUAtt2∗,T cannot output 1 at the same time. Then, A sends UAtt1∗ and UAtt2∗ to the challenger. The challenger chooses two sets D0=d0,D1=d1 of equal length. For d0, the challenger selects r1,r2⟵RZp and computes(16)cph1∗=A1=gbr1,A2=gar1+r2+β0,A3=gr2,Bj=gαjr2|atj∈UAtt1∗.The challenger randomly picksσ⟵R0,1 and r3,r4⟵RZp for dσ and sets(17)cph2∗=A1′=gbr3,A2′=gar3+r4+βσ,A3′=gr4,Bj′=gαjr4|atj∈UAtt2∗.Phase 2: Same as Phase 1.Guess: Finally,A will eventually output a guess σ′ of σ.
IfA can determine whether d0 is equal to dσ or not, A also can determine whether gβσ is equal to gβ0 or not. The only way for A to achieve this is to construct a query Γ2β0−βσ for some Γ2. To prove Theorem 3, we will show that A can never construct a query for Γ2β0−βσ.
Table2 shows all the possible queries of G by means of the bilinear map and group elements given to the adversary. Note that β0,βσ only incurs in terms ar1+r2+β0 and ar3+r4+βσ, respectively. Thus, A must construct gΓ2ar1+r2−r3−r4 for obtaining gΓ2β0−βσ. Moreover, since r1,r2 and r3,r4 are independent, A must construct gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2. Then we show that adversary A can never build gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2.
To constructΓ2ar1+r2 for A, as r1 only appears in the term br1, we let Γ2=Γ2′b for some Γ2′. That is, A needs to construct the term Γ2′abr2. In order to get that, the only way of constructing Γ2′abr2 is to apply tkn1 in Table 2 with Bj=gαjr2|atj∈UAtt1∗ of cph1∗, which will result in eg,gabtkr2, meaning that A can construct the query abtkr2. That is, Γ2 can be written as Γ2=Γ2′b=Γ2′′tkb for a known constant Γ2′′. Similarly, we can show that Γ2 can be written as Γ2=Γ2′b=Γ2′′t′kb for a known constant Γ2′′ to build Γ2ar3+r4. Since t and t′ are unknown to A, then Γ2′ cannot be constructed, since A cannot find a known constant Γ2′′ that is the product of t and t′.
In conclusion,A is able to construct gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2 with a negligible probability and get a negligible advantage in the fine-grained authorization game.
Similar to the proof in Theorem1, an adversary A′ can be simulated and it can be proved that if A can break the fine-grained authorization security for D0=D1>1, then A′ can break the fined-grained authorization security for D0=D1=1. This completes the proof.Table 2
tkn1 and tkn2 that can be obtained by A, where FUAtt1∗,T1=1 and FUAtt2∗,T2=1.
tkn1=T1,X1=gatk,X2=gbtk,Yv=gkqv0+αjtv,Zv=gktv|v∈lvsT1tkn2=T2,X1′=gat′k,X2′=gbt′k,Yv′=gkqv′0+αjtv′,Zv=gktv′|v∈lvsT2


### 4.4. Efficiency Analysis

Now we evaluate the efficiency of the schemes in terms of the asymptotic computational complexity. The asymptotic complexity is measured in terms of operations:H denotes the operation of mapping a bit-string to an element of G, E denotes the group exponentiation operation in G, ET denotes the group exponentiation operation in GT, and P denotes the pairing operation. We ignore the multiplication operations because they are much more efficient than the operations mentioned above (Table 3).Table 3
N is the number of attributes involved in the access tree in question, S is the number of a data user’s attributes, and n is the size of sets (here we assume that both sets have the same size n).
SchemeKP-ABSIKeyGen3N+2E+NHEncS+3nE+S+1nHTokenGen2N+2ESI2S+2⋅2nP+S⋅2nETWe can see that TokenGen incurs small cost when compared with SI. This implies that the data user should use the token to outsource the set intersection operations to the cloud.


## 4.1. Basic Idea

To illustrate the idea, let a data user’s private key begat,gbt, which can be generated by running qv0|v∈lvsT⟵ShareT,abt for some random t and setting gqv0H1attvtv,gtv, where tv is a random number with respect to leaf v∈lvsT. A set element d is encrypted into two parts:The first part is related tod; namely,(1)gbr1,gar1+r2H2d,gr2,whereg is a generator of G, r1 and r2 are two random numbers, H1,H2 are two hash functions, and a,b are private keys.The second part is related to the attribute set corresponding to the access control policy in question, namely,H1atir2 for ati∈UAtt.A data user can generate the token asgatk,gbtk,gqv0kH1attvktv,gktv, by which the cloud is able to translate the ciphertext into an intermediate form eH2d,gbtk once the attribute set UAtt satisfies the access control policy T.


## 4.2. KP-ABSI Construction

Setup(1ℓ): Given the security parameter ℓ as input, the public parameters and the master secret key can be generated as follows:Lete,q,g,gT,G,GT⟵BMapGen1ℓ.LetH1:0,1∗⟶G and H2:0,1∗⟶G be two secure hash functions that are modeled as random oracles.Selecta,b⟵Rℤp and set the public parameters and the master secret key as(2)pk=e,G,GT,g,ga,gb,H1,H2,mk=a,b.KeyGenmk,T: Given access tree T, this algorithm selects t⟵Rℤp, computes X1=gat and X2=gbt, and runs qv0|v∈lvsT⟵ShareT,abt. Then, for each leaf v∈lvsT, the algorithm selects tv⟵Rℤp and sets Yv=gqv0H1attvtv and Zv=gtv. The secret key is(3)sk=T,X1,X2,Yv,Zv|v∈lvsT.EncD,UAtt: Given set for outsourcing, D=d0,…,dn, this algorithm encrypts the set as follows: for each dj, it selects r1,r2⟵Rℤp , sets A1=gbr1, A2=gar1+r2H2dj, and A3=gr2, and computes Bi=H1atir2 for each ati∈UAtt. The ciphertext of dj is(4)cphj=UAtt,A1,A2,A3,Bi|ati∈UAtt.The set of ciphertexts iscph=cph0,…,cphn.TokenGensk: Given secret key sk, this algorithm selects k⟵Rℤp, sets X^1=X1k=gatk and X^2=X2k=gbtk, and computes Y^v=Yvk and Z^v=Zvk for leaf v∈lvsT. The token is(5)tkn=T,X^1,X^2,Y^v,Z^v|v∈lvsT.SItkn,cph,cph′: Given cph=cph0,…,cphn, cph′=cph0′,…,cphm′, and tkn, this algorithm is executed as follows:Givencphj∈cph, it selects an attribute set S∈UAtt satisfying T. If S does not exist, it returns 0. Otherwise, it computes(6)Ev=eY^v,A3eZ^v,Bi=eg,gqv0kr2,for allv∈lvsT with attv=ati, computes(7)Eroot=eg,gabtkr2⟵CombineT,Ev|attv∈S,E1=eA1,X^1=eg,gabtkr1,E2j=eA2,X^2ErootE1=eH2dj,gbtk,and setsE=E20,…,E2n.Givencphj′∈cph′, it selects an attribute set S′∈UAtt′ satisfying T. If S′ does not exist, it returns 0. Otherwise, it computes Ev′=eY^v,A3′/eZ^v,Bi=eg,gqv0kr2′ for all v∈lvsT with attv=ati, computes(8)Eroot′=eg,gabtkr2′⟵CombineT,Ev′|attv∈S′,E1′=eA1′,X^1=eg,gabtkr1′,E2j′=eA2,X^2Eroot′E1′=eH2dj′,gbtk,and setsE′=E20′,…,E2m′.Output the set intersectionrslt=cphj|cphj∈cph,E2j∈E∩E′.The correctness of the above KP-ABSI scheme can be verified by following the protocol. In what follows, we analyze its security.


## 4.3. Security Analysis

Theorem 1.
Under the DLN assumption, the above KP-ABSI scheme achieves the selective security against chosen-plaintext attacks in the random oracle as specified in Definition2.Firstly, we prove that our scheme achieves the security goal whenD=1 (i.e., the message space has a single element) and then extends the proof to the case D>1.Proof.
We show that if there is a PPT adversaryA that wins the selective security game with a nonnegligible advantage μ, then a challenger that can solve the DLN problem with the advantage at least μ/2 can be constructed. Specifically, given a DLN instance g,h,f,fr1,gr2,Q, where g,f,h,Q⟵RG and r1,r2⟵Rℤp are unknown, the game is simulated by the challenger as follows.Setup: The adversaryA gives an attribute set UAtt∗ to the challenger. Then the challenger produces the bilinear map e:G×G⟶GT, constructs gb=f and ga=h with a and b unknown, and sets pk=e,g,f,h,G,GT. The challenger sends pk to A. The challenger maintains two lists ListH1ati,αi,βi and ListH2d,γ, which are initially empty. A can query OH1 and OH2 polynomially many times as follows:OH1ati: Given attribute ati, the challenger responds as follows:The caseati was queried before: it retrieves αi,βi from ListH1 and returns fαigβi to A.The caseati was not queried before: if ati∈UAtt∗, it selects βi⟵Rℤp, adds ati,αi=0,βi to ListH1, and returns gβi to A; otherwise, it selects αi,βi⟵Rℤp, adds ati,αi,βi to ListH1, and returns fαigβi to A.OH2d: Given a message d as input, if d was queried before, it retrieves γ from ListH2 and returns gγ to A; otherwise, it picks γ⟵Rℤp randomly, records d,γ to ListH2, and returns gγ to A.Phase 1: The adversaryA makes polynomial queries for the following oracles as follows:OKeyGenT: If FUAtt∗,T=1, the simulation is aborted; otherwise, the challenger produces sk according to the two following procedures:PolySatTv,UAtt∗,λv: Given a secret value λv, this procedure builds the polynomial for each node of subtree Tv, where FUAtt∗,Tv=1. Suppose that the threshold value of node v is kv; it lets qv0=λv and chooses kv−1 coefficients uniformly at random to uniquely determine the polynomial qv. Then it recursively runs PolySatTv′,UAtt∗,λv′ to build the polynomial for each child node v′ of v, by letting λv′=qvindexv′.PolyUnsatTv,UAtt∗,gλv: Given an element gλv∈G, where λv is unknown to the challenger, this procedure is to build the polynomial for each node of subtree Tv, where FUAtt∗,Tv=0. Assume that the threshold value of node v is kv and V is the set of children of node v such that, ∀v′∈V,FUAtt∗,Tv′=1. Since FUAtt∗,Tv=0, we have V<kv. For each v′∈V, it selects λv′⟵Rℤp and sets λv′=qvindexv′. It then determines the other kv−V points of polynomial qv such that gqv0=gλv. For each child node v′ of node v, it executes the following:(i)
Ifv′ is a node with Fat∗,Tv′=1, it runs PolySatTv′,UAtt∗,qvindexv′, where qvindexv′ is known.(ii)
Ifv′ is a node with Fat∗,Tv′=0, it runs PolySatTv′,UAtt∗,gλv′, where gλv′=gqvindexv′ is known.Based on the two procedures above, the challenger executesPolyUnsatT,UAtt∗,ga by implicitly defining qroot0=a. Note that, for each v∈lvsT, the challenger knows qv0 if attv∈UAtt∗ and knows gqv0 otherwise. Therefore, it generates credentials as follows by selecting t⟵Rℤp and setting X1=ht and X2=ft (while noting that btqv0 is the secret share of abt):Ifattv=atj for some atj∈UAtt∗, it selects tv⟵Rℤp and sets Yv=ftqv0gβjtv=gbtqv0H1attvtv and Zv=gtv.Ifattv∉UAtt∗, where attv=atj for some j, it selects tv′⟵Rℤp and sets Yv=fttv′αjgqv0−βj/αjgtv′βj and Zv=g−qv0/αjgtv′. Note that Yv,Zv is valid because the challenger implicitly sets tv=−qv0/αj+tv′ and the following:(9)Yv=fttv′αjgqv0−βj/αjgtv′βj=ftqv0fαjgβj−qv0/αj+tv′=ftqv0H1atjtv,Zv=g−qv0/αjgtv′=gtv.OtknT: The challenger queries OKeyGenT to obtain sk and returns tkn⟵TokenGensk to A.Challenge: The adversaryA gives two messages D0=d0 and D1=d1 of equal length to the challenger. Then the challenger randomly picks σ⟵R0,1, encrypts dσ to cph∗=UAtt∗,fr1,QH2dσ,gr2,gr2βj|atj∈UAtt∗, and sends cph∗ to A.Phase 2:A executes the same as in the above Phase1.Guess: The adversaryA will eventually output a guess σ′ of σ. If σ′=σ, the challenger outputs Q=hr1+r2; otherwise, it outputs Q≠hr1+r2.
The simulation is completed. In Challenge phase, ifQ=hr1+r2, then cph∗ is indeed a valid ciphertext of Dσ and the probability that A outputs σ′=σ is 1/2+μ. Otherwise, if Q is a random element from G, then cph∗ is a random group element and the probability that A outputs σ′=σ is 1/2. In conclusion, the probability that the challenger correctly guesses Q=?hr1+r2 is 1/21/2+1/2+μ=1/2+μ/2. That is, if A wins the game with the advantage μ, then the challenger solves the DLN problem with the advantage μ/2.
So far, we have shown that our KP-ABSI scheme is selective secure against chosen-plaintext attack whenD=1. In what follows, we prove that our KP-ABSI scheme achieves the selective security against chosen-plaintext attack for the general case of D>1.
Suppose thatA gives two sets D0=d0,…,dn and D1=d0′,…,dn′. Denote by cphi the encryption of d0,…,di,di+1′,…,dn′, meaning that cphn is the encryption of D0 and cph−1 is the encryption of D1. The Challenge phase is extended to accommodate an additional adversary A′ as follows:A′ picks a random index i⟵R0,n and presents di,di′ to the challenger. Then the challenger sends back cphi to A′ by encrypting di if σ=0 or returns di′ if σ=1.A′ encrypts d0,…,di−1 and di+1′,…,dn′ and returns cph0,…,cphn to A. A′ outputs A’s output σ′.
Note thatA′ sends to A the ciphertext cphi if σ=0 and the ciphertext cphi−1 if σ=1. Denote by Acphi the guess of A with ciphertexts cphi. Then we show the probability that A′ wins the game. Note that(10)PrA′outputs0|σ=0=∑j=0n1n+1PrAcphj=0,PrA′outputs0|σ=1=∑j=0n1n+1PrAcphj−1=1.
Therefore, the probability thatA′ wins the game is(11)12PrA′cph=0|σ=0+12PrA′cph=1|σ=1=∑j=0n12n+1PrAcphj=0+∑j=0n12n+1PrAcphj−1=1=n2n+1+12n+1PrAcphn=0+12n+1PrAcph−1=1=n2n+1+1n+112PrAcphn=0+12PrAcph−1=1≤12+ε,where ε is negligible because the advantage that A′ wins the game is negligible. Thus, the probability that A distinguishes cph−1 from cphn is(12)12PrAcphn=0+12PrAcph−1=1≤12+n+1ε.
That is, the advantage ofA distinguishing cph−1 from cphn is at most n+1ε. Therefore, the scheme achieves the selective security against chosen-plaintext attack when D≥1.Theorem 2.
Given one-way hash functionH2, the above KP-ABSI scheme achieves the one-way security against chosen-plaintext attack as specified in Definition 3.Proof.
We prove this theorem by showing that if there is a PPT adversaryA winning the one-way security game against chosen-plaintext attack with a nonnegligible advantage μ, then a challenger breaking the one-way hash function H2 can be simulated.
GivenH2d∗=y∗, the challenger can simulate the one-way security game as follows:Setup: The challenger randomly picksa,b⟵Rℤp, produces pk=e,G,GT,g,p,ga,gb,mk=a,b, and sends pk to A.Phase 1: The challenger maintains a listLT, which is empty initially. A makes polynomial queries for the following oracles:OKeyGenT: Given an access control policy T, it returns sk⟵KeyGenmk,pk,T to A and adds T to LT.OtknT: Given an access control policy T, it runs tkn⟵TokenGenKeyGenmk,pk,T,pk and returns tkn to A.Challenge:A gives an attribute set UAtt∗ to the challenger, where, ∀T∈LT, FUAtt∗,T=0. The challenger picks j⟵Rℤp and sets a data set D∗=d0,d1,…,d|D∗|−1, where d0,…,dj−1,dj+1,…,dD∗−1 are randomly chosen from the message space Msg and dj is implicitly set as dj=d∗ and generates the ciphertext cph=cphkk∈0,D∗−1 as follows:Ifk≠j, cphk is generated the same as in the real construction.Ifk=j,(13)cphk=UAtt∗,A1=gbr1,A2=gar1+r2y∗,A3=gr2,Bi=H1atir2|ati∈UAtt∗,by randomly choosingr1,r2⟵Rℤp and implicitly setting dj=d∗.The challenger chooses an access treeT∗ satisfying FUAtt∗,T∗=1, runs tkn∗⟵TokenGenKeyGenmk,pk,T∗,pk, and returns cph∗=cph,tkn∗ to the adversary A.Phase 2: The adversaryA executes the same as in Phase 1 while complying with the necessary requirements defined by the game.Guess:A will eventually output a guess d to the challenger. The challenger wins if d=d∗.
The simulation is completed. If the probability thatA outputs d∈D∗ is Prd∈D∗−mD∗/Msg=μ, then Prd∈D∗=mD∗/Msg+μ. Since the data set size is D∗, Prd:d=d∗≥Prd∈D∗/D∗=1/D∗mD∗/Msg+μ. Therefore, if A wins the one-way security game against chosen-plaintext attack with a nonnegligible advantage μ, the one-way hash function H2 can be broken by the challenger with a nonnegligible probability at least 1/D∗mD∗/Msg+μ. □Theorem 3.
The KP-ABSI achieves fine-grained authorization security in the generic bilinear group model as specified in Definition4.Proof.
Similar to the proof for Theorem1, firstly, we prove that our KP-ABSI scheme achieves fine-grained authorization when the challenge size D0=D1=1 and then extend the proof to the case of challenge size D0=D1>1.Setup: The challenger randomly picksa,b⟵Rℤp, produces pk=e,G,GT,g,p,ga,gb, and sends pk to A. The challenger maintains two lists ListH1atj,αj and ListH2d,β, which are empty initially. A can make polynomial queries for the following OH1 and OH2.OH1atj: Given an attribute atj, if atj was queried before, the challenger returns gαj by retrieving αj from ListH1; otherwise, the challenger picks αj⟵Rℤp, records atj,αj to ListH1, and returns gαj to A.OH2d: Given a message d, if d was queried before, the challenger returns gβ; otherwise, the challenger picks β⟵Rℤp, records d,β to ListH2, and returns gβ to A.Phase 1: The challenger keeps the two lists,LT and Ltkn, which are initially empty. A can make polynomial queries for the following oracles.OKeyGenT: The challenger selects tu⟵Rℤp and runs qv0u|v∈lvsT⟵ShareT,abtu. For each node v∈lvsT, the challenger chooses tvu⟵Rℤp and sets(14)sk=T,X1=gatu,X2=gbtu,Yv=gqv0u+αjtvu,Zv=gtvu|v∈lvsT,whereattv=atj. The challenger sends sk to A and records T to LT.OtknT: The challenger runs OKeyGenT, selects ku⟵Rℤp, and sets(15)tkn=T,Y^v=Yvku=gqv0uku+αjtvuku,Z^v=Zvku=gtvuku|v∈lvsT,X^1=X1ku=gatuku,X^2=X2ku=gbtuku,whereattv=atj. It returns tkn to A and adds T to Ltkn.Challenge:A chooses two attribute sets UAtt1∗ and UAtt2∗ with the following restrictions: (1) ∀T∈LT, FUAtt1∗,T and FUAtt2∗,T cannot output 1 at the same time, and, (2) ∀T∈Ltkn, FUAtt1∗,T and FUAtt2∗,T cannot output 1 at the same time. Then, A sends UAtt1∗ and UAtt2∗ to the challenger. The challenger chooses two sets D0=d0,D1=d1 of equal length. For d0, the challenger selects r1,r2⟵RZp and computes(16)cph1∗=A1=gbr1,A2=gar1+r2+β0,A3=gr2,Bj=gαjr2|atj∈UAtt1∗.The challenger randomly picksσ⟵R0,1 and r3,r4⟵RZp for dσ and sets(17)cph2∗=A1′=gbr3,A2′=gar3+r4+βσ,A3′=gr4,Bj′=gαjr4|atj∈UAtt2∗.Phase 2: Same as Phase 1.Guess: Finally,A will eventually output a guess σ′ of σ.
IfA can determine whether d0 is equal to dσ or not, A also can determine whether gβσ is equal to gβ0 or not. The only way for A to achieve this is to construct a query Γ2β0−βσ for some Γ2. To prove Theorem 3, we will show that A can never construct a query for Γ2β0−βσ.
Table2 shows all the possible queries of G by means of the bilinear map and group elements given to the adversary. Note that β0,βσ only incurs in terms ar1+r2+β0 and ar3+r4+βσ, respectively. Thus, A must construct gΓ2ar1+r2−r3−r4 for obtaining gΓ2β0−βσ. Moreover, since r1,r2 and r3,r4 are independent, A must construct gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2. Then we show that adversary A can never build gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2.
To constructΓ2ar1+r2 for A, as r1 only appears in the term br1, we let Γ2=Γ2′b for some Γ2′. That is, A needs to construct the term Γ2′abr2. In order to get that, the only way of constructing Γ2′abr2 is to apply tkn1 in Table 2 with Bj=gαjr2|atj∈UAtt1∗ of cph1∗, which will result in eg,gabtkr2, meaning that A can construct the query abtkr2. That is, Γ2 can be written as Γ2=Γ2′b=Γ2′′tkb for a known constant Γ2′′. Similarly, we can show that Γ2 can be written as Γ2=Γ2′b=Γ2′′t′kb for a known constant Γ2′′ to build Γ2ar3+r4. Since t and t′ are unknown to A, then Γ2′ cannot be constructed, since A cannot find a known constant Γ2′′ that is the product of t and t′.
In conclusion,A is able to construct gΓ2ar1+r2 and gΓ2ar3+r4 for the same Γ2 with a negligible probability and get a negligible advantage in the fine-grained authorization game.
Similar to the proof in Theorem1, an adversary A′ can be simulated and it can be proved that if A can break the fine-grained authorization security for D0=D1>1, then A′ can break the fined-grained authorization security for D0=D1=1. This completes the proof.Table 2
tkn1 and tkn2 that can be obtained by A, where FUAtt1∗,T1=1 and FUAtt2∗,T2=1.
tkn1=T1,X1=gatk,X2=gbtk,Yv=gkqv0+αjtv,Zv=gktv|v∈lvsT1tkn2=T2,X1′=gat′k,X2′=gbt′k,Yv′=gkqv′0+αjtv′,Zv=gktv′|v∈lvsT2


## 4.4. Efficiency Analysis

Now we evaluate the efficiency of the schemes in terms of the asymptotic computational complexity. The asymptotic complexity is measured in terms of operations:H denotes the operation of mapping a bit-string to an element of G, E denotes the group exponentiation operation in G, ET denotes the group exponentiation operation in GT, and P denotes the pairing operation. We ignore the multiplication operations because they are much more efficient than the operations mentioned above (Table 3).Table 3
N is the number of attributes involved in the access tree in question, S is the number of a data user’s attributes, and n is the size of sets (here we assume that both sets have the same size n).
SchemeKP-ABSIKeyGen3N+2E+NHEncS+3nE+S+1nHTokenGen2N+2ESI2S+2⋅2nP+S⋅2nETWe can see that TokenGen incurs small cost when compared with SI. This implies that the data user should use the token to outsource the set intersection operations to the cloud.


## 5. Conclusions

In this paper, we present a novel cryptographic primitive: delegated key-policy attribute-based set intersection over outsourced encrypted data sets (KP-ABSI). It simultaneously achieves the following: (1) Each data owner outsources his/her data set in encrypted form to a cloud, where the outsourced data set is associated with an attribute set. (2) A data user is associated with an access control policy that is satisfied by the attribute sets of two encrypted data sets (owned by two data owners, respectively) and can delegate to the cloud the set intersection computation over the two data owners’ outsourced encrypted data sets. (3) The cloud can conduct the set intersection operation on behalf of the data user without being able to obtain any useful information about the data owners’ plaintext data set.Thus, our scheme can solve the PSI problem in CloudIoT system. Of course, in our solution, the cloud is semihonest. How to build a construction in the malicious model is still an open problem.



---

*Source: 5595243-2021-03-18.xml*