# Enhanced Dual-Policy Attribute-Based Encryption for Secure Data Sharing in the Cloud

Authors: Ti Wang; Yongbin Zhou; Hui Ma; Rui Zhang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

As a promising service paradigm, cloud computing has attracted lots of enterprises and individuals to outsource big data to public cloud. To facilitate secure data using and sharing, dual-policy attribute-based encryption (DP-ABE) is a suitable solution. It allows two access control mechanisms over encrypted data at the same time: one involves access policies over subjective attributes ascribed to user credentials, and the other involves policies over objective attributes ascribed to data. In this work, we are exploring methods to make DP-ABE more flexible, more efficient, and more secure for deployments in cloud scenes. Our proposal features the following achievements simultaneously: (1) beyond the access control mechanisms of DP-ABE, it also supports two flexible features called encryption and key generation in single-policy modes; (2) most operations of key generation, encryption, and decryption are securely outsourced to cloud servers, leaving extremely low overheads for the PKG, data owners, and users; and (3) it realizes the strongest security notion of public-key encryption schemes, namely, CCA security. We formalize the security definition and formally prove its security in the random oracle model. Moreover, we implement the proposed schemes using the Charm framework. The experiment results demonstrate that our schemes are efficient and practical.


---

## Body

## 1. Introduction

As a promising service paradigm, cloud computing has attracted great interest of the industrial world due to its powerful computation and storage capabilities. To avoid maintaining specialized data centers, a growing number of enterprises and individuals choose to outsource huge amounts of data to public cloud, based on which they can store, manage, and share the data conveniently. Since cloud servers are owned by third parties (such as Amazon S3) and not fully trusted, data should be outsourced in encrypted forms to protect security. In 2005, Sahai and Waters [1] introduced the primitive of Attribute-based encryption (ABE), which is formally refined by Goyal et al. [2]. ABE is a suited solution for secure data sharing in the cloud, since it can realize fine-grained access control over encrypted data using access policies and attribute sets among secret keys and ciphertexts. Particularly, ABE comes in two flavors, called Ciphertext-Policy ABE (CP-ABE) and Key-Policy (KP-ABE).In CP-ABE [3, 4], every participant is assigned a secret key, which contains a set of attributes based on his/her role. A data owner encrypts data associated with an access policy before uploading to the cloud, and a data user can decrypt it only if the attribute set of the secret key satisfies the access policy of the ciphertext. Take the electronic medical record (EMR) system as an example. If a nurse encrypts a record under (“Cardiology” and (“Chief Physician” or “Associate Chief Physician”)), a doctor with the secret key corresponding to {“Cardiology,” “Chief Physician”} can decrypt the ciphertext. In summary, attributes in CP-ABE are used to annotate the data users’ credentials, which are called subjects since users are to decrypt.While, in KP-ABE [2, 5], secret keys are associated with access policies and ciphertexts are associated with attribute sets. Attributes are used to annotate data, which are called objects since they are to be encrypted. For example, a secret key corresponding to ((“Male” or “Female”) and “Blood Pressure”) can decrypt a record encrypted under {“Male,” “Blood Pressure”}.As pointed by Attrapadung and Imai [6], a drawback of the above two types of ABE is that we must choose whether attributes will be used as subjects or objects, and after setup we must also stick with such a condition throughout the entire application. This is pretty inconvenient, since if we are using KP-ABE, the encrypted record can only be ascribed by objective attributes. Thus, the nurse station, as the encryptor, could not directly specify subjective access policies of doctors, i.e., who can or cannot decrypt. The same inconvenience happens also for CP-ABE, complimentarily.To solve this, Dual-Policy ABE (DP-ABE) is proposed [6]. Basically, DP-ABE is a conjunctively combined scheme between CP-ABE and KP-ABE, where the CP-ABE (resp. KP-ABE) component deals with subjective (resp. objective) attribute universe. The decryption can be done if and only if the subjective (resp. objective) attribute set satisfies the subjective (resp. objective) access policy, respectively, at the same time. Due to its flexible access control abilities, DP-ABE can be useful in general-purpose applications.In this paper, we advance the state of the art on secure data sharing by providing more flexible, more efficient, and more secure dual-policy attribute-based encryption schemes. To the best of our knowledge, our proposal is the first structured DP-ABE scheme that achieves flexibility enhanced access control mechanisms, fully outsourced computation, and the security against chosen ciphertext attack (CCA), simultaneously. Our techniques may help develop other practical encryption schemes for secure data sharing in cloud scenes.


### 1.1. Related Work

#### 1.1.1. Dual-Policy ABE

The first DP-ABE scheme was proposed by Attrapadung and Imai [6] in 2009. Since this scheme was constructed based on the underlying KP-ABE [2] and CP-ABE [7], it supported monotone LSSS access structures and selective security. To reduce the size of ciphertext of Ref. [6], Miyaji and Tran [8] proposed a DP-ABE scheme with short ciphertext where access structures were expressed as all AND gates type. However, Rao and Dutta [9] pointed out there was a mistake in the decryption algorithm of Ref. [8], so they proposed a new DP-ABE scheme in which the size of ciphertext was only related to subjective attributes.Okamoto and Takashima [10] proposed a fully secure dual-policy functional encryption for general relations using the concept of dual pairing vector spaces [11]. By extending the pair encodings primitive [12], Attrapadung and Yamada [13] provided a generic conversion that converts ABE into its dual-policy variant, and obtained the first realizations of fully secure DP-ABE for formulae, unbounded DP-ABE for formulae, and DP-ABE for regular languages. Attrapadung [14] proposed a prime-order version of Ref. [12], and constructed an efficient DP-ABE with large universe in prime-order groups. Recently, Xu et al. [15] presented a generic construction of DP-ABE by introducing the El-Gamal type cryptosystem. They also gave an instantiation of DP-ABE based on CP-ABE [16] and KP-ABE [2]. Han et al. [17] applied DP-ABE in blockchain scenarios.


#### 1.1.2. ABE with Outsourced Computation

In most of the ABE schemes, the size of ciphertext and operations of decryption are linear with the number of attributes in the access policy. In 2011, Green et al. [18] introduced the technique of outsourced decryption for attribute-based encryption. A proxy can use the transformation key to convert any original ABE ciphertext to a short ciphertext. However, the proxy can learn nothing about the plaintext during the operation. Finally, to recover the plaintext, the data user only needs to conduct one exponentiation easily.Hohenberger and Waters [19] developed new “connect and correct” techniques for ABE that split the computation for key generation and encryption into two phases: a preparation phase that does the vast majority of the work to generate a secret key or encrypt a message, and a second phase can then rapidly assemble an ABE secret key or ciphertext when the specifics become known. Subsequently, based on this concept, Ma et al. proposed an online/offline ABE with cryptographic reverse firewalls [20], a ciphertext-policy attribute-based proxy re-encryption (CP-AB-PRE) [21], and efficient CP-ABE [22, 23] with outsourced computation for various applications.


#### 1.1.3. CCA Secure ABE

CCA is the strongest notion for a public-key encryption, while the security against chosen plaintext attacks (CPA) can only provide basic data confidentiality. Goyal et al. [2] proposed a generic conversion making a CPA-secure KP-ABE CCA-secure. Yamada et al. [24] presented CCA conversions for KP-ABE and CP-ABE.The attribute-based encryption with outsourced decryption (OD-ABE) schemes [18] could achieve replayable CCA security [25]. Zuo et al. [26] and Wang et al. [27] proposed constructions of selectively and fully CCA-secure OD-ABE, respectively. Liang et al. [28] proposed a CCA-secure CP-AB-PRE scheme for cloud data sharing. To the best of our knowledge, Ref. [10] is the only scheme in the dual-policy setting that achieves CCA security in the literature.


### 1.2. Our Contribution

In this work, we are exploring methods to make DP-ABE more flexible, more efficient, and more secure for secure data sharing in the cloud. Specially, our contribution is fourfold:(1)
Flexibility-Enhanced Access Control Mechanisms. Firstly, a monotone LSSS-realizable large-universe DP-ABE scheme is proposed based on prime-order asymmetric pairing groups. In order to support more flexible access control functionalities in real-world deployments, we further design two practical features for our scheme, called encryption and key generation in single-policy modes. The scheme is proven selectively CPA-secure under two modifiedq-type assumptions.(2)
Low Computation Cost. Secondly, by utilizing the outsourced computation technique [23], we construct a more computationally efficient scheme, called fully outsourced dual-policy attribute-based encryption (FO-DP-ABE). The scheme securely outsources almost all expensive computation during key generation, encryption, and decryption to cloud servers, leaving extremely low overheads for the PKG, data owners, and users.(3)
High-Level Security. Thirdly, to realize the strongest security notion of public-key encryption schemes, we make our FO-DP-ABE scheme CCA-secure by applying the Canetti-Halevi-Katz [31] and the Fujisaki-Okamoto [32] transformations without efficiency compromise. We formalize the security definition and formally prove its security in the random oracle model.(4)
Thorough Performance Evaluations. Finally, we give detailed theoretical comparisons with several practical DP-ABE schemes. Also, we implement our DP-ABE and FO-DP-ABE schemes using a rapidly prototyping tool calledCharm [33], and conduct extensive experiments to evaluate performance. The results show that our schemes are sufficiently efficient to be applied for limited-resource devices.Table1 compares the functions in our proposed schemes with those in some related work. Our schemes are more suitable from the practicality and security aspects.Table 1
Function comparison with some related work of DP-ABE.
SchemesPairing group∗Objective/subjective attribute†Single-policy mode(s)‡Outsourced computationSecurity modelDP-ABE [6]Prime-orderSmall/small universeEncryption×IND-CPADP-ABE [10]Prime-orderSmall/small universe××IND-CCADP-ABE [9]Prime-orderSmall/small universe××IND-CPADP-ABE [13]Composite-orderLarge/large universe××IND-CPADP-ABE [14]Prime-orderLarge/large universe××IND-CPADP-ABE [15]Prime-orderSmall/large universe××IND-CPAOur DP-ABEPrime-orderLarge/large universeEncryption/KeyGen✔IND-CPAOur FO-DP-ABEPrime-orderLarge/large universeEncryption/KeyGen✔IND-CCA∗Regarding time performances, Guillevic [29] reported that for the same 128 bit security, pairings are 254 times slower in composite-order than in prime-order groups, and exponentiations are also about 1014 times slower. Moreover, composite-order group elements are about 12 times larger than prime-order group elements. Although there exist techniques [30] to convert pairing-based schemes from composite-order groups to prime-order groups, there is still a significant performance degradation due to the required size of the special vectors [16]. †In small universe constructions, the size of the attribute space is polynomially bounded in the security parameter and the attributes are fixed at setup. Moreover, the size of the public parameters grew linearly with the number of attributes. In large universe constructions, on the other hand, the size of the attribute universe can be exponentially large, which is a desirable feature [16]. ‡Encryption and key generation in single-policy modes are pretty flexible features. When a DP-ABE scheme has been already set up, it can also be used in KP-ABE or/and CP-ABE settings. If one ignores subjective (resp. objective) attributes, the DP-ABE scheme becomes KP-ABE (resp. CP-ABE). This flexibility provides great convenience since the same ciphertext (or/and the same secret key) can be used for all three variants of ABE.


### 1.3. Paper Organization

The rest of this paper is arranged as follows. In Section2, we introduce the necessary background knowledge. In Section 3, we give the formal definition and security model of DP-ABE, and present a basic CPA-secure construction. In Section 4, we describe the single-policy modes of our DP-ABE. In Section 5, we propose our FO-DP-ABE scheme, and give the details of security proof in the proposed security model. In Section 6, we make detailed performance evaluations. Section 7 presents a brief conclusion.


## 1.1. Related Work

### 1.1.1. Dual-Policy ABE

The first DP-ABE scheme was proposed by Attrapadung and Imai [6] in 2009. Since this scheme was constructed based on the underlying KP-ABE [2] and CP-ABE [7], it supported monotone LSSS access structures and selective security. To reduce the size of ciphertext of Ref. [6], Miyaji and Tran [8] proposed a DP-ABE scheme with short ciphertext where access structures were expressed as all AND gates type. However, Rao and Dutta [9] pointed out there was a mistake in the decryption algorithm of Ref. [8], so they proposed a new DP-ABE scheme in which the size of ciphertext was only related to subjective attributes.Okamoto and Takashima [10] proposed a fully secure dual-policy functional encryption for general relations using the concept of dual pairing vector spaces [11]. By extending the pair encodings primitive [12], Attrapadung and Yamada [13] provided a generic conversion that converts ABE into its dual-policy variant, and obtained the first realizations of fully secure DP-ABE for formulae, unbounded DP-ABE for formulae, and DP-ABE for regular languages. Attrapadung [14] proposed a prime-order version of Ref. [12], and constructed an efficient DP-ABE with large universe in prime-order groups. Recently, Xu et al. [15] presented a generic construction of DP-ABE by introducing the El-Gamal type cryptosystem. They also gave an instantiation of DP-ABE based on CP-ABE [16] and KP-ABE [2]. Han et al. [17] applied DP-ABE in blockchain scenarios.


### 1.1.2. ABE with Outsourced Computation

In most of the ABE schemes, the size of ciphertext and operations of decryption are linear with the number of attributes in the access policy. In 2011, Green et al. [18] introduced the technique of outsourced decryption for attribute-based encryption. A proxy can use the transformation key to convert any original ABE ciphertext to a short ciphertext. However, the proxy can learn nothing about the plaintext during the operation. Finally, to recover the plaintext, the data user only needs to conduct one exponentiation easily.Hohenberger and Waters [19] developed new “connect and correct” techniques for ABE that split the computation for key generation and encryption into two phases: a preparation phase that does the vast majority of the work to generate a secret key or encrypt a message, and a second phase can then rapidly assemble an ABE secret key or ciphertext when the specifics become known. Subsequently, based on this concept, Ma et al. proposed an online/offline ABE with cryptographic reverse firewalls [20], a ciphertext-policy attribute-based proxy re-encryption (CP-AB-PRE) [21], and efficient CP-ABE [22, 23] with outsourced computation for various applications.


### 1.1.3. CCA Secure ABE

CCA is the strongest notion for a public-key encryption, while the security against chosen plaintext attacks (CPA) can only provide basic data confidentiality. Goyal et al. [2] proposed a generic conversion making a CPA-secure KP-ABE CCA-secure. Yamada et al. [24] presented CCA conversions for KP-ABE and CP-ABE.The attribute-based encryption with outsourced decryption (OD-ABE) schemes [18] could achieve replayable CCA security [25]. Zuo et al. [26] and Wang et al. [27] proposed constructions of selectively and fully CCA-secure OD-ABE, respectively. Liang et al. [28] proposed a CCA-secure CP-AB-PRE scheme for cloud data sharing. To the best of our knowledge, Ref. [10] is the only scheme in the dual-policy setting that achieves CCA security in the literature.


## 1.1.1. Dual-Policy ABE

The first DP-ABE scheme was proposed by Attrapadung and Imai [6] in 2009. Since this scheme was constructed based on the underlying KP-ABE [2] and CP-ABE [7], it supported monotone LSSS access structures and selective security. To reduce the size of ciphertext of Ref. [6], Miyaji and Tran [8] proposed a DP-ABE scheme with short ciphertext where access structures were expressed as all AND gates type. However, Rao and Dutta [9] pointed out there was a mistake in the decryption algorithm of Ref. [8], so they proposed a new DP-ABE scheme in which the size of ciphertext was only related to subjective attributes.Okamoto and Takashima [10] proposed a fully secure dual-policy functional encryption for general relations using the concept of dual pairing vector spaces [11]. By extending the pair encodings primitive [12], Attrapadung and Yamada [13] provided a generic conversion that converts ABE into its dual-policy variant, and obtained the first realizations of fully secure DP-ABE for formulae, unbounded DP-ABE for formulae, and DP-ABE for regular languages. Attrapadung [14] proposed a prime-order version of Ref. [12], and constructed an efficient DP-ABE with large universe in prime-order groups. Recently, Xu et al. [15] presented a generic construction of DP-ABE by introducing the El-Gamal type cryptosystem. They also gave an instantiation of DP-ABE based on CP-ABE [16] and KP-ABE [2]. Han et al. [17] applied DP-ABE in blockchain scenarios.


## 1.1.2. ABE with Outsourced Computation

In most of the ABE schemes, the size of ciphertext and operations of decryption are linear with the number of attributes in the access policy. In 2011, Green et al. [18] introduced the technique of outsourced decryption for attribute-based encryption. A proxy can use the transformation key to convert any original ABE ciphertext to a short ciphertext. However, the proxy can learn nothing about the plaintext during the operation. Finally, to recover the plaintext, the data user only needs to conduct one exponentiation easily.Hohenberger and Waters [19] developed new “connect and correct” techniques for ABE that split the computation for key generation and encryption into two phases: a preparation phase that does the vast majority of the work to generate a secret key or encrypt a message, and a second phase can then rapidly assemble an ABE secret key or ciphertext when the specifics become known. Subsequently, based on this concept, Ma et al. proposed an online/offline ABE with cryptographic reverse firewalls [20], a ciphertext-policy attribute-based proxy re-encryption (CP-AB-PRE) [21], and efficient CP-ABE [22, 23] with outsourced computation for various applications.


## 1.1.3. CCA Secure ABE

CCA is the strongest notion for a public-key encryption, while the security against chosen plaintext attacks (CPA) can only provide basic data confidentiality. Goyal et al. [2] proposed a generic conversion making a CPA-secure KP-ABE CCA-secure. Yamada et al. [24] presented CCA conversions for KP-ABE and CP-ABE.The attribute-based encryption with outsourced decryption (OD-ABE) schemes [18] could achieve replayable CCA security [25]. Zuo et al. [26] and Wang et al. [27] proposed constructions of selectively and fully CCA-secure OD-ABE, respectively. Liang et al. [28] proposed a CCA-secure CP-AB-PRE scheme for cloud data sharing. To the best of our knowledge, Ref. [10] is the only scheme in the dual-policy setting that achieves CCA security in the literature.


## 1.2. Our Contribution

In this work, we are exploring methods to make DP-ABE more flexible, more efficient, and more secure for secure data sharing in the cloud. Specially, our contribution is fourfold:(1)
Flexibility-Enhanced Access Control Mechanisms. Firstly, a monotone LSSS-realizable large-universe DP-ABE scheme is proposed based on prime-order asymmetric pairing groups. In order to support more flexible access control functionalities in real-world deployments, we further design two practical features for our scheme, called encryption and key generation in single-policy modes. The scheme is proven selectively CPA-secure under two modifiedq-type assumptions.(2)
Low Computation Cost. Secondly, by utilizing the outsourced computation technique [23], we construct a more computationally efficient scheme, called fully outsourced dual-policy attribute-based encryption (FO-DP-ABE). The scheme securely outsources almost all expensive computation during key generation, encryption, and decryption to cloud servers, leaving extremely low overheads for the PKG, data owners, and users.(3)
High-Level Security. Thirdly, to realize the strongest security notion of public-key encryption schemes, we make our FO-DP-ABE scheme CCA-secure by applying the Canetti-Halevi-Katz [31] and the Fujisaki-Okamoto [32] transformations without efficiency compromise. We formalize the security definition and formally prove its security in the random oracle model.(4)
Thorough Performance Evaluations. Finally, we give detailed theoretical comparisons with several practical DP-ABE schemes. Also, we implement our DP-ABE and FO-DP-ABE schemes using a rapidly prototyping tool calledCharm [33], and conduct extensive experiments to evaluate performance. The results show that our schemes are sufficiently efficient to be applied for limited-resource devices.Table1 compares the functions in our proposed schemes with those in some related work. Our schemes are more suitable from the practicality and security aspects.Table 1
Function comparison with some related work of DP-ABE.
SchemesPairing group∗Objective/subjective attribute†Single-policy mode(s)‡Outsourced computationSecurity modelDP-ABE [6]Prime-orderSmall/small universeEncryption×IND-CPADP-ABE [10]Prime-orderSmall/small universe××IND-CCADP-ABE [9]Prime-orderSmall/small universe××IND-CPADP-ABE [13]Composite-orderLarge/large universe××IND-CPADP-ABE [14]Prime-orderLarge/large universe××IND-CPADP-ABE [15]Prime-orderSmall/large universe××IND-CPAOur DP-ABEPrime-orderLarge/large universeEncryption/KeyGen✔IND-CPAOur FO-DP-ABEPrime-orderLarge/large universeEncryption/KeyGen✔IND-CCA∗Regarding time performances, Guillevic [29] reported that for the same 128 bit security, pairings are 254 times slower in composite-order than in prime-order groups, and exponentiations are also about 1014 times slower. Moreover, composite-order group elements are about 12 times larger than prime-order group elements. Although there exist techniques [30] to convert pairing-based schemes from composite-order groups to prime-order groups, there is still a significant performance degradation due to the required size of the special vectors [16]. †In small universe constructions, the size of the attribute space is polynomially bounded in the security parameter and the attributes are fixed at setup. Moreover, the size of the public parameters grew linearly with the number of attributes. In large universe constructions, on the other hand, the size of the attribute universe can be exponentially large, which is a desirable feature [16]. ‡Encryption and key generation in single-policy modes are pretty flexible features. When a DP-ABE scheme has been already set up, it can also be used in KP-ABE or/and CP-ABE settings. If one ignores subjective (resp. objective) attributes, the DP-ABE scheme becomes KP-ABE (resp. CP-ABE). This flexibility provides great convenience since the same ciphertext (or/and the same secret key) can be used for all three variants of ABE.


## 1.3. Paper Organization

The rest of this paper is arranged as follows. In Section2, we introduce the necessary background knowledge. In Section 3, we give the formal definition and security model of DP-ABE, and present a basic CPA-secure construction. In Section 4, we describe the single-policy modes of our DP-ABE. In Section 5, we propose our FO-DP-ABE scheme, and give the details of security proof in the proposed security model. In Section 6, we make detailed performance evaluations. Section 7 presents a brief conclusion.


## 2. Preliminary

In this section, we review some notations and definitions.


### 2.1. Notations

Algx,y,…⟶z denotes that z is obtained by running an algorithm Alg on inputs x,y,…. For n∈ℕ, n=1,2,…,n. We denote S the size of a set S, and s←$S the operation of choosing an element s uniformly at random from S. Mi denotes the i th row of a matrix M, and Mi,j denotes the i,j th element of M. neglλ denotes a negligible function, i.e., ∀n>0, ∃λ0∈ℕ, s.t., λ>λ0, neglλ<1/λn.The acronyms used in this paper are given in Table2.Table 2
Acronyms used in this paper.
AcronymDescriptionPKGPrivate key generatorPKPublic parametersMSKMaster secret keyIKIntermediate keySKSecret keyTKTransformation keyRKRetrieval keyITIntermediate ciphertextCTCiphertextTCTTransformed ciphertextSkpObjective attribute setAkpObjective access structureScpSubjective attribute setAcpSubjective access structure


### 2.2. Definitions

Definition 1 (Bilinear Maps).
LetGroupGen be a probabilistic polynomial-time (PPT) algorithm that takes as input a security parameter λ and outputs a tuple par=p,G1,G2,GT,e,g1,g2, where G1, G2, and GT are cyclic groups of the same prime-order p∈Θ2λ, g1,g2 are generators of G1,G2, respectively, and e:G1×G2⟶GT is a bilinear map satisfying that:(1)
Bilinearity:∀g1∈G1,g2∈G2, and ∀a,b∈ℤp∗, we have eg1a,g2b=eg1,g2ab.(2)
Nondegeneracy:eg1,g2≠1, whenever g1,g2 are not identities of G1,G2, respectively.(3)
Computability:∀g1∈G1,g2∈G2, there is an efficient algorithm to compute eg1,g2.
Following the standard terminology, we refer toe as pairing. Pairings fall into three basic types:(i)
Type-I:G1=G2;(ii)
Type-II:G1≠G2 but there is an efficiently computable isomorphism ψ:G2⟶G1;(iii)
Type-III:G1≠G2 and there is no efficiently computable isomorphism between G1 and G2.
As summarized in Ref. [34], Type-I is “symmetric,” since it is simpler and the complexity assumptions can be weaker. Type-I groups have serious security issues [35]. Type-II and Type-III are “asymmetric,” in which Type-III is typically the most efficient choice for implementation [36]. We use only Type-III throughout the paper.Definition 2 (Access Structure [37]).
LetP1,…,Pn be a set of parties. A collection A is monotone for ∀B and C, if B∈A and B⊆C, then C∈A. An access structure is a collection of nonempty subsets of P1,…,Pn, i.e., A⊆2P1,…,Pn∖∅. The sets in A are called the authorized sets, and the sets not in A are called unauthorized sets.Definition 3 (Linear Secret Sharing Schemes (LSSS) [37]).
Letp be a prime. A secret sharing scheme Π with domain of secrets ℤp realizing access structures on the attribute universe U is linear over ℤp if:(1)
The shares of the parties form a vector overℤp;(2)
For each access structureA on U, there exists a matrix M∈ℤpl×n, called the share-generating matrix, and a function ρ, that labels the rows of M with attributes from U. During the generation of the shares, we consider the column vector v⟶=s,r2,…,rn⊤, where r2,…,rn←$ℤp. Then, the vector of l shares of the secret s according to Π is equal to Mv⟶∈ℤpl×1. The share Mv⟶i belongs to attribute ρi.
Lewko and Waters [38] gave a method to transform any monotone access structure into an LSSS M,ρ. Specially, each entry in M is 0, 1 or −1, and we can choose coefficients that are 0 or 1 for the resulting M,ρ.


### 2.3. Assumptions

The KP-ABE and CP-ABE schemes [16] are secure under two q-type assumptions on prime-order asymmetric pairing groups. To construct our DP-ABE in single-policy modes, we will use the following modified q-type assumptions.Definition 4 (Modifiedq-1 Assumption).
An asymmetric pairing group generatorGroupGen satisfies the modified q-1 assumption if for all adversaries A, there exists negl such that:(1)PrAλ,par,D,R1=1−PrAλ,par,D,R2=1≤neglλ,where par=p,G1,G2,GT,e,g1,g2←GroupGenλ, R1=eg1,g2saq+1, R2←$GT, a,s,b1,…,bq←$ℤp∗, w1←$G1, and D contains the following terms:(2)g2s,w1,w1sg1ai,g2ai,g1bj,g2bj,g1sbj,g1aibj,g1ai/bj2∀i,j∈q,qg1aibj/bj′2∀i,j,j′∈2q,q,qwithj≠j′g1ai/bj∀i,j∈2q,qwithi≠q+1g1saibj/bj′,g1saibj/bj′2∀i,j,j′∈q,q,qwithj≠j′.Definition 5.
(Modifiedq-2 Assumption). An asymmetric pairing group generator GroupGen satisfies the modified q-2 assumption if for all adversaries A, there exists negl such that:(3)PrAλ,par,D,R1=1−PrAλ,par,D,R2=1≤neglλ,where par=p,G1,G2,GT,e,g1,g2←GroupGenλ, R1=eg1,g2xyz, R2←$GT, x,y,z,b1,…,bq←$ℤp∗, w2←$G1, and D contains the following terms:(4)g1x,g1y,g2y,g2z,g1xz2,w2,w2zg1bi,g2bi,g1xzbi,g2xzbi,g1xz/bi,g1x2zbi,g1y/bi2,g1y2/bi2∀i∈qg1xzbi/bj,g1ybi/bj2,g1xyzbi/bj,g1xz2bi/bj∀i,j∈q,qwithi≠j.
Compared with the original assumption [16], the modified q-1 assumption is slightly stronger, since adversaries can obtain two additional elements w1,w1s. Nevertheless, it is trivially secure in the generic group model [39]. Since w1 is randomly chosen from G1, adversaries with the help of w1s would have no additional advantage to distinguish R1 or R2. Similarly, the modified q-2 assumption is secure.


## 2.1. Notations

Algx,y,…⟶z denotes that z is obtained by running an algorithm Alg on inputs x,y,…. For n∈ℕ, n=1,2,…,n. We denote S the size of a set S, and s←$S the operation of choosing an element s uniformly at random from S. Mi denotes the i th row of a matrix M, and Mi,j denotes the i,j th element of M. neglλ denotes a negligible function, i.e., ∀n>0, ∃λ0∈ℕ, s.t., λ>λ0, neglλ<1/λn.The acronyms used in this paper are given in Table2.Table 2
Acronyms used in this paper.
AcronymDescriptionPKGPrivate key generatorPKPublic parametersMSKMaster secret keyIKIntermediate keySKSecret keyTKTransformation keyRKRetrieval keyITIntermediate ciphertextCTCiphertextTCTTransformed ciphertextSkpObjective attribute setAkpObjective access structureScpSubjective attribute setAcpSubjective access structure


## 2.2. Definitions

Definition 1 (Bilinear Maps).
LetGroupGen be a probabilistic polynomial-time (PPT) algorithm that takes as input a security parameter λ and outputs a tuple par=p,G1,G2,GT,e,g1,g2, where G1, G2, and GT are cyclic groups of the same prime-order p∈Θ2λ, g1,g2 are generators of G1,G2, respectively, and e:G1×G2⟶GT is a bilinear map satisfying that:(1)
Bilinearity:∀g1∈G1,g2∈G2, and ∀a,b∈ℤp∗, we have eg1a,g2b=eg1,g2ab.(2)
Nondegeneracy:eg1,g2≠1, whenever g1,g2 are not identities of G1,G2, respectively.(3)
Computability:∀g1∈G1,g2∈G2, there is an efficient algorithm to compute eg1,g2.
Following the standard terminology, we refer toe as pairing. Pairings fall into three basic types:(i)
Type-I:G1=G2;(ii)
Type-II:G1≠G2 but there is an efficiently computable isomorphism ψ:G2⟶G1;(iii)
Type-III:G1≠G2 and there is no efficiently computable isomorphism between G1 and G2.
As summarized in Ref. [34], Type-I is “symmetric,” since it is simpler and the complexity assumptions can be weaker. Type-I groups have serious security issues [35]. Type-II and Type-III are “asymmetric,” in which Type-III is typically the most efficient choice for implementation [36]. We use only Type-III throughout the paper.Definition 2 (Access Structure [37]).
LetP1,…,Pn be a set of parties. A collection A is monotone for ∀B and C, if B∈A and B⊆C, then C∈A. An access structure is a collection of nonempty subsets of P1,…,Pn, i.e., A⊆2P1,…,Pn∖∅. The sets in A are called the authorized sets, and the sets not in A are called unauthorized sets.Definition 3 (Linear Secret Sharing Schemes (LSSS) [37]).
Letp be a prime. A secret sharing scheme Π with domain of secrets ℤp realizing access structures on the attribute universe U is linear over ℤp if:(1)
The shares of the parties form a vector overℤp;(2)
For each access structureA on U, there exists a matrix M∈ℤpl×n, called the share-generating matrix, and a function ρ, that labels the rows of M with attributes from U. During the generation of the shares, we consider the column vector v⟶=s,r2,…,rn⊤, where r2,…,rn←$ℤp. Then, the vector of l shares of the secret s according to Π is equal to Mv⟶∈ℤpl×1. The share Mv⟶i belongs to attribute ρi.
Lewko and Waters [38] gave a method to transform any monotone access structure into an LSSS M,ρ. Specially, each entry in M is 0, 1 or −1, and we can choose coefficients that are 0 or 1 for the resulting M,ρ.


## 2.3. Assumptions

The KP-ABE and CP-ABE schemes [16] are secure under two q-type assumptions on prime-order asymmetric pairing groups. To construct our DP-ABE in single-policy modes, we will use the following modified q-type assumptions.Definition 4 (Modifiedq-1 Assumption).
An asymmetric pairing group generatorGroupGen satisfies the modified q-1 assumption if for all adversaries A, there exists negl such that:(1)PrAλ,par,D,R1=1−PrAλ,par,D,R2=1≤neglλ,where par=p,G1,G2,GT,e,g1,g2←GroupGenλ, R1=eg1,g2saq+1, R2←$GT, a,s,b1,…,bq←$ℤp∗, w1←$G1, and D contains the following terms:(2)g2s,w1,w1sg1ai,g2ai,g1bj,g2bj,g1sbj,g1aibj,g1ai/bj2∀i,j∈q,qg1aibj/bj′2∀i,j,j′∈2q,q,qwithj≠j′g1ai/bj∀i,j∈2q,qwithi≠q+1g1saibj/bj′,g1saibj/bj′2∀i,j,j′∈q,q,qwithj≠j′.Definition 5.
(Modifiedq-2 Assumption). An asymmetric pairing group generator GroupGen satisfies the modified q-2 assumption if for all adversaries A, there exists negl such that:(3)PrAλ,par,D,R1=1−PrAλ,par,D,R2=1≤neglλ,where par=p,G1,G2,GT,e,g1,g2←GroupGenλ, R1=eg1,g2xyz, R2←$GT, x,y,z,b1,…,bq←$ℤp∗, w2←$G1, and D contains the following terms:(4)g1x,g1y,g2y,g2z,g1xz2,w2,w2zg1bi,g2bi,g1xzbi,g2xzbi,g1xz/bi,g1x2zbi,g1y/bi2,g1y2/bi2∀i∈qg1xzbi/bj,g1ybi/bj2,g1xyzbi/bj,g1xz2bi/bj∀i,j∈q,qwithi≠j.
Compared with the original assumption [16], the modified q-1 assumption is slightly stronger, since adversaries can obtain two additional elements w1,w1s. Nevertheless, it is trivially secure in the generic group model [39]. Since w1 is randomly chosen from G1, adversaries with the help of w1s would have no additional advantage to distinguish R1 or R2. Similarly, the modified q-2 assumption is secure.


## 3. Dual-Policy Attribute-Based Encryption

In this section, we propose our dual-policy attribute-based encryption (DP-ABE) scheme.


### 3.1. Syntax

Define the functionfS,A=1 if the attribute set S satisfies the access structure A. A dual-policy attribute-based encryption (DP-ABE) for access structure space G contains the following algorithms:(i)
Setupλ,U⟶PK,MSK. The setup algorithm takes a security parameter λ and a universe description U as input, and outputs the public parameters PK and the master secret key MSK.(ii)
KeyGenPK,MSK,Akp,Scp⟶SK. The key generation algorithm takes the public parameters PK, the master secret key MSK, an objective access structure Akp, and a subjective attribute set Scp as input, and outputs a secret key SK corresponding to Akp,Scp.(iii)
EncryptPK,msg,Skp,Acp⟶CT. The encryption algorithm takes the public parameters PK, a message msg from the message space ℳ, an objective attribute set Skp, and a subjective access structure Acp as input, and outputs a ciphertext CT encrypted under Skp,Acp.(iv)
DecryptPK,SK,CT⟶msg or ⊥. The decryption algorithm takes the public parameters PK, a secret key SK corresponding to Akp,Scp, and a ciphertext CT encrypted under Skp,Acp as input, and outputs the decryption result msg if it holds that the objective attribute set Skp satisfies the objective access structure Akp, i.e., fSkp,Akp=1, and that the subjective attribute set Scp satisfies the subjective access structure Acp, i.e., fScp,Acp=1. Otherwise, it outputs ⊥.Correctness. It requires that for allSkp⊆U, all Scp⊆U, all Akp∈G, all Acp∈G, all msg∈ℳ, all PK,MSK∈Setupλ,U, all SK∈KeyGenPK,MSK,Akp,Scp, and all CT∈EncryptPK,msg,Skp,Acp:(5)IffSkp,Akp=1andfScp,Acp=1,thenDecryptPK,SK,CT=msg.


### 3.2. Security Model

We use the security model in Ref. [6]. Let ΠDP−ABE=Setup,KeyGen,Encrypt,Decrypt be a DP-ABE scheme for access structure space G, and consider the following experiment for an adversary A.The DP-ABE experimentExpA,ΠDP−ABECPAλ,U:Init.A declares the challenge objective attribute set Skp∗ and the challenge subjective access structure Acp∗.Setup. The challengerC runs Setupλ,U to obtain PK,MSK and sends PK to A.Phase 1.A can adaptively ask for secret keys for pairs of objective access structure and subjective attribute set Akp,Scp such that fSkp∗,Akp=0 or fScp,Acp∗=0. C sends SK=KeyGenPK,MSK,Akp,Scp to A.Challenge.A submits two equal length messages msg0∗ and msg1∗ as the challenge. C picks b←$0,1 and sends CT∗=EncryptPK,msgb∗,Skp∗,Acp∗ to A.Phase 2. Phase 1 is repeated.Guess.A outputs a guess b′ of b. The output of the experiment is 1 if b′=b.Definition 6.
A DP-ABE is selectively IND-CPA secure if for all adversariesA, there exists negl such that:(6)PrExpA,ΠDP−ABEIND−CPAλ,U=1−12≤neglλ.


### 3.3. Construction

(i)
Setupλ,U. Call GroupGenλ to obtain par=p,G1,G2,GT,e,g1,g2. The attribute universe is U=ℤp. Choose u1,u2,h1,h2,w1,w2,v←$G1 and α←$ℤp. Output PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α and MSK=α.(ii)
KeyGenPK,MSK,Akp,Scp. Let Akp=M,ρ be an LSSS access structure with M∈ℤpk×m and ρ:k⟶ℤp. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(7)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.LetScp=A1,A2,…,Ad⊆ℤp be an attribute set. Choose r←$ℤp and compute K0=g1α−βw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(8)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.OutputSK=SKkp,SKcp.(iii)
EncryptPK,msg∈GT,Skp,Acp. Choose s←$ℤp and compute C0=g2s,Cm=eg1,g2αs⋅msg.LetSkp=B1,B2,…,Bc⊆ℤp be an attribute set. For i∈c choose σi←$ℤp and compute(9)Ci,1=g2σi,Ci,2=u1Bih1σiw1−s.SetCTkp=Skp,Ci,1,Ci,2i∈c.LetAcp=N,π be an LSSS access structure with N∈ℤpl×n and π:l⟶ℤp. Choose η⟶=s,η2,…,ηn⊤ where η2,…,ηn←$ℤp. The vector of the shares of s is δ⟶=δ1,…,δl⊤=Nη⟶. For j∈l choose tj←$ℤp and compute(10)Cj,1=w2δjvtj,Cj,2=u2πjh2−tj,Cj,3=g2tj.SetCTcp=Acp,Cj,1,Cj,2,Cj,3j∈l.OutputCT=C0,Cm,CTkp,CTcp.(iv)
DecryptPK,SK,CT. Parse the key and ciphertext:(11)SKkp=Akp,Ki,0,Ki,1,Ki,2i∈k,CTkp=Skp,Ci,1,Ci,2i∈c.IffSkp,Akp=1, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Compute(12)Ekp=e∏i∈IKi,0φi,C0∏i∈IeKi,1φi,Cεi,1eCεi,2φi,Ki,2.Parse the key and ciphertext:(13)SKcp=Scp,K0,K1,Kj,2,Kj,3j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3j∈l.IffScp,Acp=1, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Compute(14)Ecp=eK0,C0e∏j∈JCj,1ϕj,K1∏j∈JeCj,2ϕj,Kεj,2eKεj,3ϕj,Cj,3.Outputmsg=Cm/Ekp⋅Ecp.Correctness: IffSkp,Akp=1 and fScp,Acp=1, we have that ∑i∈Iφiμi=β, ∑j∈Jϕjδj=s. Therefore:(15)Ekp=∏i∈IeKi,0,C0eKi,1,C∈i,1eC∈i,2,Ki,2φi=∏i∈Ieg1,g2sφiμiew1,g2sφiτieu1ρih1,g2−σ∈iφiτieu1ρih1,g2σ∈iφiτiew1,g2−sφiτi=eg1,g2s∑i∈Iφiμi=eg1,g2βs,Ecp=eK0,C0∏j∈JeCj,1,K1eCj,2,Kεj,2eKεj,3,Cj,3ϕj=eg1,g2α−βsew2,g2rs∏j∈Jew2,g2rϕjδjev,g2rϕjtjeu2πjh2,g2−rεjϕjtj⋅1∏j∈Jeu2πjh2,g2rεjϕjtjev,g2−rϕjtj=eg1,g2α−βsew2,g2rsew,g2r∑j∈Jϕjδj=eg1,g2α−βs.


### 3.4. Security Analysis

Theorem 1.
Suppose that the KP-ABE and CP-ABE schemes [16] are selectively IND-CPA secure, then the proposed DP-ABE scheme is selectively IND-CPA secure.Proof.
Our DP-ABE scheme is a generic construction according to El-Gamal type schemes [15]. Suppose there is an adversary A that can attack the proposed DP-ABE scheme. We can construct an algorithm ℬ to break the KP-ABE and CP-ABE schemes [16].
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗ is of size c, and Acp∗ is of size l×n. ℬ passes on Skp∗ to the challenger Ckp of the KP-ABE scheme, and passes on Acp∗ to the challenger Ckp of the CP-ABE scheme.
Setup.ℬ receives PKkp=par,u1,h1,w1,eg1,g2MSKkp from Ckp, and PKcp=par,u2,h2,w2,v,eg1,g2MSKcp from Ccp. By the definition of El-Gamal type schemes, we have
(16)MSKkp=MSKcp=α.
ℬ returns PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α to A.
Phase 1.A queries the secret key corresponding to the pair Akp,Scp where Akp is of size k×m, and Scp is of size d. ℬ acts as follows:
(i)
IffSkp∗,Akp=1, then we must have fScp,Acp∗=0. Let Akp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(17)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.
SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.
LetScp=A1,A2,…,Ad. Call the key generation oracle of Ccp on Scp to obtain(18)SKcp′=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.
SetSKcp=Scp,K0′⋅g1−β,K1′,Kj,2′,Kj,3′j∈d.
ReturnSK=SKkp,SKcp.(ii)
Else,fSkp∗,Akp=0. Call the key generation oracle of Ckp on Akp to obtain(19)SKkp′=Akp,Ki,0′,Ki,1′,Ki,2′i∈k.
LetAkp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶.
SetSKkp=Akp,Ki,0′⋅g1−μi,Ki,1′,Ki,2′i∈k.
LetScp=A1,A2,…,Ad. Choose r←$ℤp and compute K0=g1βw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(20)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.
SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.
ReturnSK=SKkp,SKcp.
Challenge.A submits two messages msg0∗,msg1∗ from the message space GT. ℬ passes msg0∗,msg1∗,Skp∗ on to Ckp to obtain Ckp,0,Ckp,m,CTkp, and passes msg0∗,msg1∗,Acp∗ on to Ccp to obtain Ccp,0,Ccp,m,CTcp.
By the definition of El-Gamal type schemes, we have(21)Ckp,0=Ccp,0=g2s,Ckp,m=Ccp,m=eg1,g2αs⋅msgb∗.
ℬ returns CT=g2s,eg1,g2αs⋅msgb∗,CTkp,CTcp to A.
Phase 2. Phase 1 is repeated.
Guess.A outputs a bit b′. ℬ outputs b′ as its guess.
It is clear that from the view ofA, the simulation is indistinguishable from the real experiment. Therefore, we obtain the theorem.


## 3.1. Syntax

Define the functionfS,A=1 if the attribute set S satisfies the access structure A. A dual-policy attribute-based encryption (DP-ABE) for access structure space G contains the following algorithms:(i)
Setupλ,U⟶PK,MSK. The setup algorithm takes a security parameter λ and a universe description U as input, and outputs the public parameters PK and the master secret key MSK.(ii)
KeyGenPK,MSK,Akp,Scp⟶SK. The key generation algorithm takes the public parameters PK, the master secret key MSK, an objective access structure Akp, and a subjective attribute set Scp as input, and outputs a secret key SK corresponding to Akp,Scp.(iii)
EncryptPK,msg,Skp,Acp⟶CT. The encryption algorithm takes the public parameters PK, a message msg from the message space ℳ, an objective attribute set Skp, and a subjective access structure Acp as input, and outputs a ciphertext CT encrypted under Skp,Acp.(iv)
DecryptPK,SK,CT⟶msg or ⊥. The decryption algorithm takes the public parameters PK, a secret key SK corresponding to Akp,Scp, and a ciphertext CT encrypted under Skp,Acp as input, and outputs the decryption result msg if it holds that the objective attribute set Skp satisfies the objective access structure Akp, i.e., fSkp,Akp=1, and that the subjective attribute set Scp satisfies the subjective access structure Acp, i.e., fScp,Acp=1. Otherwise, it outputs ⊥.Correctness. It requires that for allSkp⊆U, all Scp⊆U, all Akp∈G, all Acp∈G, all msg∈ℳ, all PK,MSK∈Setupλ,U, all SK∈KeyGenPK,MSK,Akp,Scp, and all CT∈EncryptPK,msg,Skp,Acp:(5)IffSkp,Akp=1andfScp,Acp=1,thenDecryptPK,SK,CT=msg.


## 3.2. Security Model

We use the security model in Ref. [6]. Let ΠDP−ABE=Setup,KeyGen,Encrypt,Decrypt be a DP-ABE scheme for access structure space G, and consider the following experiment for an adversary A.The DP-ABE experimentExpA,ΠDP−ABECPAλ,U:Init.A declares the challenge objective attribute set Skp∗ and the challenge subjective access structure Acp∗.Setup. The challengerC runs Setupλ,U to obtain PK,MSK and sends PK to A.Phase 1.A can adaptively ask for secret keys for pairs of objective access structure and subjective attribute set Akp,Scp such that fSkp∗,Akp=0 or fScp,Acp∗=0. C sends SK=KeyGenPK,MSK,Akp,Scp to A.Challenge.A submits two equal length messages msg0∗ and msg1∗ as the challenge. C picks b←$0,1 and sends CT∗=EncryptPK,msgb∗,Skp∗,Acp∗ to A.Phase 2. Phase 1 is repeated.Guess.A outputs a guess b′ of b. The output of the experiment is 1 if b′=b.Definition 6.
A DP-ABE is selectively IND-CPA secure if for all adversariesA, there exists negl such that:(6)PrExpA,ΠDP−ABEIND−CPAλ,U=1−12≤neglλ.


## 3.3. Construction

(i)
Setupλ,U. Call GroupGenλ to obtain par=p,G1,G2,GT,e,g1,g2. The attribute universe is U=ℤp. Choose u1,u2,h1,h2,w1,w2,v←$G1 and α←$ℤp. Output PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α and MSK=α.(ii)
KeyGenPK,MSK,Akp,Scp. Let Akp=M,ρ be an LSSS access structure with M∈ℤpk×m and ρ:k⟶ℤp. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(7)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.LetScp=A1,A2,…,Ad⊆ℤp be an attribute set. Choose r←$ℤp and compute K0=g1α−βw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(8)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.OutputSK=SKkp,SKcp.(iii)
EncryptPK,msg∈GT,Skp,Acp. Choose s←$ℤp and compute C0=g2s,Cm=eg1,g2αs⋅msg.LetSkp=B1,B2,…,Bc⊆ℤp be an attribute set. For i∈c choose σi←$ℤp and compute(9)Ci,1=g2σi,Ci,2=u1Bih1σiw1−s.SetCTkp=Skp,Ci,1,Ci,2i∈c.LetAcp=N,π be an LSSS access structure with N∈ℤpl×n and π:l⟶ℤp. Choose η⟶=s,η2,…,ηn⊤ where η2,…,ηn←$ℤp. The vector of the shares of s is δ⟶=δ1,…,δl⊤=Nη⟶. For j∈l choose tj←$ℤp and compute(10)Cj,1=w2δjvtj,Cj,2=u2πjh2−tj,Cj,3=g2tj.SetCTcp=Acp,Cj,1,Cj,2,Cj,3j∈l.OutputCT=C0,Cm,CTkp,CTcp.(iv)
DecryptPK,SK,CT. Parse the key and ciphertext:(11)SKkp=Akp,Ki,0,Ki,1,Ki,2i∈k,CTkp=Skp,Ci,1,Ci,2i∈c.IffSkp,Akp=1, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Compute(12)Ekp=e∏i∈IKi,0φi,C0∏i∈IeKi,1φi,Cεi,1eCεi,2φi,Ki,2.Parse the key and ciphertext:(13)SKcp=Scp,K0,K1,Kj,2,Kj,3j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3j∈l.IffScp,Acp=1, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Compute(14)Ecp=eK0,C0e∏j∈JCj,1ϕj,K1∏j∈JeCj,2ϕj,Kεj,2eKεj,3ϕj,Cj,3.Outputmsg=Cm/Ekp⋅Ecp.Correctness: IffSkp,Akp=1 and fScp,Acp=1, we have that ∑i∈Iφiμi=β, ∑j∈Jϕjδj=s. Therefore:(15)Ekp=∏i∈IeKi,0,C0eKi,1,C∈i,1eC∈i,2,Ki,2φi=∏i∈Ieg1,g2sφiμiew1,g2sφiτieu1ρih1,g2−σ∈iφiτieu1ρih1,g2σ∈iφiτiew1,g2−sφiτi=eg1,g2s∑i∈Iφiμi=eg1,g2βs,Ecp=eK0,C0∏j∈JeCj,1,K1eCj,2,Kεj,2eKεj,3,Cj,3ϕj=eg1,g2α−βsew2,g2rs∏j∈Jew2,g2rϕjδjev,g2rϕjtjeu2πjh2,g2−rεjϕjtj⋅1∏j∈Jeu2πjh2,g2rεjϕjtjev,g2−rϕjtj=eg1,g2α−βsew2,g2rsew,g2r∑j∈Jϕjδj=eg1,g2α−βs.


## 3.4. Security Analysis

Theorem 1.
Suppose that the KP-ABE and CP-ABE schemes [16] are selectively IND-CPA secure, then the proposed DP-ABE scheme is selectively IND-CPA secure.Proof.
Our DP-ABE scheme is a generic construction according to El-Gamal type schemes [15]. Suppose there is an adversary A that can attack the proposed DP-ABE scheme. We can construct an algorithm ℬ to break the KP-ABE and CP-ABE schemes [16].
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗ is of size c, and Acp∗ is of size l×n. ℬ passes on Skp∗ to the challenger Ckp of the KP-ABE scheme, and passes on Acp∗ to the challenger Ckp of the CP-ABE scheme.
Setup.ℬ receives PKkp=par,u1,h1,w1,eg1,g2MSKkp from Ckp, and PKcp=par,u2,h2,w2,v,eg1,g2MSKcp from Ccp. By the definition of El-Gamal type schemes, we have
(16)MSKkp=MSKcp=α.
ℬ returns PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α to A.
Phase 1.A queries the secret key corresponding to the pair Akp,Scp where Akp is of size k×m, and Scp is of size d. ℬ acts as follows:
(i)
IffSkp∗,Akp=1, then we must have fScp,Acp∗=0. Let Akp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(17)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.
SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.
LetScp=A1,A2,…,Ad. Call the key generation oracle of Ccp on Scp to obtain(18)SKcp′=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.
SetSKcp=Scp,K0′⋅g1−β,K1′,Kj,2′,Kj,3′j∈d.
ReturnSK=SKkp,SKcp.(ii)
Else,fSkp∗,Akp=0. Call the key generation oracle of Ckp on Akp to obtain(19)SKkp′=Akp,Ki,0′,Ki,1′,Ki,2′i∈k.
LetAkp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶.
SetSKkp=Akp,Ki,0′⋅g1−μi,Ki,1′,Ki,2′i∈k.
LetScp=A1,A2,…,Ad. Choose r←$ℤp and compute K0=g1βw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(20)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.
SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.
ReturnSK=SKkp,SKcp.
Challenge.A submits two messages msg0∗,msg1∗ from the message space GT. ℬ passes msg0∗,msg1∗,Skp∗ on to Ckp to obtain Ckp,0,Ckp,m,CTkp, and passes msg0∗,msg1∗,Acp∗ on to Ccp to obtain Ccp,0,Ccp,m,CTcp.
By the definition of El-Gamal type schemes, we have(21)Ckp,0=Ccp,0=g2s,Ckp,m=Ccp,m=eg1,g2αs⋅msgb∗.
ℬ returns CT=g2s,eg1,g2αs⋅msgb∗,CTkp,CTcp to A.
Phase 2. Phase 1 is repeated.
Guess.A outputs a bit b′. ℬ outputs b′ as its guess.
It is clear that from the view ofA, the simulation is indistinguishable from the real experiment. Therefore, we obtain the theorem.


## 4. Single-Policy Modes of DP-ABE

In this section, we describe two features of our DP-ABE called encryption in single-policy modes and key generation in single-policy modes.Suppose that a DP-ABE scheme has been setup already, which means that the the public parameters PK is chosen and published. The single-policy encryption modes allow a data owner to still encrypt messages as if it were a KP-ABE or CP-ABE on-the-fly, and the single-policy key generation modes allow the PKG to still generate secret keys as if it were a KP-ABE or CP-ABE on-the-fly.To describe single-policy modes, we define two special symbolsSany and Aany, where fSany,A=1 for ∀A⊆G, and fS,Aany=1 for ∀S⊆U.


### 4.1. Encryption in Single-Policy Modes

When a message is encrypted in KP-ABE mode (we will refer to both the ciphertext as well as the encryption mode by KP-CT) with the objective attribute setSkp and the subjective access policy Acp=Aany, any data user can decrypt it with a secret key corresponding to Akp,Scp if fSkp,Akp=1. Analogously, when a message is encrypted in CP-ABE mode (denoted by CP-CT) with the subjective access policy Acp and the objective attribute set Skp=Sany, any data user can decrypt it with a secret key corresponding to Akp,Scp if fScp,Acp=1.Generic Construction. Attrapadung and Imai [6] proposed a simple generic conversion from any DP-ABE scheme Π to a new DP-ABE scheme Π′ that admits single-policy encryption modes. The idea is to use dummy attributes: one for objective and one for subjective attribute.Specially,Π′.Setup is the same as Π.Setup except that it additionally chooses a special objective attribute Act,o and a special subjective attribute Act,s, and adds them into the public parameters PK. Both Act,o,Act,s will not be used as attributes in Π′. Next we define(22)Π′.KeyGenPK,MSK,Akp,Scp=Π.KeyGenPK,MSK,Akp∪Act,o,Scp∪Act,s,In KP−ABEmode,Π′.EncryptPK,Skp,Aany=Π.EncryptPK,Skp,Act,s,In CP−ABEmode,Π′.EncryptPK,Sany,Acp=Π.EncryptPK,Act,o,Acp.Direct Construction. When applying the above generic conversion to our proposed DP-ABE, the resulting scheme involves using the dummy attributes in all secret keys. Thus, we present a direct construction as follows.To encrypt a message in KP-ABE mode, we remove all elements involving attributes in the ciphertextCTcp, such that any secret key SKcp can decrypt it. Set CTcp=Aany,Cw=w2−s, and remain C0,Cm,CTkp exactly the same as in the DP-ABE.Similarly, to encrypt a message in CP-ABE mode, we remove all elements involving attributes in the ciphertextCTkp, such that any secret key SKkp can decrypt it. Set CTkp=Sany,Cw=w1−s, and remain C0,Cm,CTcp exactly the same as in the DP-ABE.


### 4.2. Key Generation in Single-Policy Modes

When a secret key is generated in KP-ABE mode (denoted by KP-SK) with the objective access policyAkp and the subjective attribute set Scp=Sany, a data user with it can decrypt any ciphertext encrypted under Skp,Acp if fSkp,Akp=1. Analogously, when a secret key is generated in the CP-ABE mode (denoted by CP-SK) with the subjective attribute set Scp and the objective access policy Akp=Aany, a data user with it can decrypt any ciphertext encrypted under Skp,Acp if fScp,Acp=1.Generic Construction. We can also use the idea of dummy attributes to convert from any DP-ABE schemeΠ to a new DP-ABE scheme Π″ that admits single-policy key generation modes.Specially,Π″.Setup is the same as Π.Setup except that it additionally chooses a special objective attribute Ask,o and a special subjective attribute Ask,s, and adds them into the public parameters PK. Both Ask,o,Ask,s will not be used as attributes in Π″. Next we define(23)Π″.EncryptPK,Skp,Acp=Π.EncryptPK,Skp∪Ask,o,Acp∪Ask,s,In KP−ABEmode,Π″.KeyGenPK,MSK,Akp,Sany=Π.KeyGenPK,MSK,Akp,Ask,s,In CP−ABEmode,Π″.KeyGenPK,MSK,Aany,Scp=Π.KeyGenPK,MSK,Ask,o,Scp.Direct Construction. When applying the above generic conversion to our proposed DP-ABE, the resulting scheme involves using the dummy attributes in all ciphertexts. Thus, we present a direct construction as follows.To generate a secret key in KP-ABE mode, we setSKcp=Sany, and directly use the master secret key MSK=α to generate SKkp. Specially, choose ν⟶=α,ν2,…,νm⊤ where ν2,…,νm←$ℤp. The vector of the shares of is αμ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(24)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.To generate a secret key in CP-ABE mode, we setSKkp=Aany, and directly use the master secret key MSK=α to generate SKcp. Specially, choose r←$ℤp and compute K0=g1αw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(25)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.


### 4.3. Decryption Cases and Security Analysis

Encryption and key generation in single-policy modes are orthogonal from the functional aspect, so they can be used simultaneously in the whole system, which leads to three kinds of ciphertexts and three kinds of secret keys, namely, in KP/CP/DP-ABE modes, respectively.For the generic constructions, dummy attributes are introduced in the attribute set and access policy, which do not change the structures of ciphertexts or secret keys, so the decryption can be done exactly in the same way as in the dual-policy setting. While, for the direct constructions, the decryption algorithms are different. We discuss 9 kinds of decryption cases in Table3.Table 3
Decryption cases of DP-ABE in single-policy modes.
SKCTKP-ABE modeSkp,AanyCP-ABE modeSany,AcpDP-ABE modeSkp,AcpKP-ABE modeAkp,SanyIffSkp,Akp=1, then Ekp=eg1,g2αsSincefSany,Akp=1 and fSany,Acp=1, we always have Ekp=e∏i∈IKi,0φi,C0eCw,∏i∈IKi,2φi=eg1,g2αsIffSkp,Akp=1, then Ekp=eg1,g2αsCP-ABE modeAany,ScpSincefSkp,Aany=1 and fScp,Aany=1, we always have Ecp=eK0,C0eCw,K1=eg1,g2αsIffScp,Acp=1, then Ecp=eg1,g2αsIffScp,Acp=1, then Ecp=eg1,g2αsDP-ABE modeAkp,ScpIffSkp,Akp=1, then Ekp=eg1,g2αs, Ecp=eK0,C0eCw,K1=eg1,g2α−βsIffScp,Acp=1, then Ecp=eg1,g2α−βs, Ekp=e∏i∈IKi,0φi,C0eCw,∏i∈IKi,2φi=eg1,g2βsIffSkp,Akp=1 and fScp,Acp=1, then Ecp=eg1,g2αs, Ecp=eg1,g2α−βsTheorem 2.
Suppose that the modifiedq−1 (resp. q−2) assumption holds, then the proposed DP-ABE scheme with encryption in CP-ABE (resp. KP-ABE) mode is selectively IND-CPA secure against all adversaries with a challenge access policy of size l×n, where l,n≤q (resp. attribute set of size c, where c≤q).Proof.
Here we prove the security of CP-CT. The proof of KP-CT is similar.
Suppose there is an adversaryA that can attack the DP-ABE scheme with encryption in CP-ABE mode. We can construct an algorithm ℬ to attack the modified q−1 assumption.
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗=Sany, and Acp∗ is of size l×n, where l,n≤q.
Setup. According to the strategy in the proof of CP-ABE scheme [16], ℬ uses the modified q−1 assumption instance to generate PKcp=par,u2,h2,w2,v,eg1,g2α, and implicitly sets MSK=α. Then, it chooses u1,h1,w1←$G1, and returns PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α to A.
Phase 1.A queries the secret key corresponding to the pair Akp,Scp where Akp is of size k×m, and Scp is of size d. Since Skp∗=Sany, we have fScp,Acp∗=0. ℬ acts as follows:
LetAkp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(26)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.
SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.
LetScp=A1,A2,…,Ad. According to the strategy in the proof of CP-ABE scheme [16], use the modified q−1 assumption instance to generate(27)SKcp′=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.
SetSKcp=Scp,K0′⋅g1−β,K1′,Kj,2′,Kj,3′j∈d.
ReturnSK=SKkp,SKcp.Challenge.A submits two messages msg0∗,msg1∗ from the message space GT. According to the strategy in the proof of CP-ABE scheme [16], ℬ uses the modified q−1 assumption instance to generate Ccp,0=g2s,Ccp,m=eg1,g2αs⋅msgb∗,CTcp and CTkp=Sany,Cw=w1−s. Finally, it returns CT∗=g2s,eg1,g2αs⋅msgb∗,CTkp,CTcp to A.Phase 2. Phase 1 is repeated.Guess.A outputs a bit b′. ℬ outputs b′ as its guess.
From the view ofA, the simulation is indistinguishable from the real experiment. Also note that in a secret key SK=SKkp,SKcp, SKkp can be used to recover Ekp=eg1,g2βs from CTkp, and the distribution of SKcp is the same as that of a secret key generated by using MSK′=α−β in CP-ABE scheme [16]. Therefore, the challenge ciphertext is actually g2s,eg1,g2α−βs⋅msgb∗,CTcp, which is the same as in CP-ABE scheme [16]. We obtain the theorem.Theorem 3.
Suppose that the KP-ABE and CP-ABE schemes [16] are selectively IND-CPA secure, then the proposed DP-ABE scheme with key generation in CP-ABE (or KP-ABE) mode is selectively IND-CPA secure.Proof.
We present the security sketch of key generation in CP-ABE mode. The security in KP-ABE mode is similar.
We use the strategy in the proof of Theorem1. The only difference is that, A is also allowed to ask for any secret key corresponding to Akp∗,Scp where Akp∗=Aany, and fScp,Acp∗=0. For this kind of query, ℬ can directly call the key generation oracle of Ccp on Scp to obtain SKcp, set SKkp=Aany, and return SK=SKkp,SKcp to A.


## 4.1. Encryption in Single-Policy Modes

When a message is encrypted in KP-ABE mode (we will refer to both the ciphertext as well as the encryption mode by KP-CT) with the objective attribute setSkp and the subjective access policy Acp=Aany, any data user can decrypt it with a secret key corresponding to Akp,Scp if fSkp,Akp=1. Analogously, when a message is encrypted in CP-ABE mode (denoted by CP-CT) with the subjective access policy Acp and the objective attribute set Skp=Sany, any data user can decrypt it with a secret key corresponding to Akp,Scp if fScp,Acp=1.Generic Construction. Attrapadung and Imai [6] proposed a simple generic conversion from any DP-ABE scheme Π to a new DP-ABE scheme Π′ that admits single-policy encryption modes. The idea is to use dummy attributes: one for objective and one for subjective attribute.Specially,Π′.Setup is the same as Π.Setup except that it additionally chooses a special objective attribute Act,o and a special subjective attribute Act,s, and adds them into the public parameters PK. Both Act,o,Act,s will not be used as attributes in Π′. Next we define(22)Π′.KeyGenPK,MSK,Akp,Scp=Π.KeyGenPK,MSK,Akp∪Act,o,Scp∪Act,s,In KP−ABEmode,Π′.EncryptPK,Skp,Aany=Π.EncryptPK,Skp,Act,s,In CP−ABEmode,Π′.EncryptPK,Sany,Acp=Π.EncryptPK,Act,o,Acp.Direct Construction. When applying the above generic conversion to our proposed DP-ABE, the resulting scheme involves using the dummy attributes in all secret keys. Thus, we present a direct construction as follows.To encrypt a message in KP-ABE mode, we remove all elements involving attributes in the ciphertextCTcp, such that any secret key SKcp can decrypt it. Set CTcp=Aany,Cw=w2−s, and remain C0,Cm,CTkp exactly the same as in the DP-ABE.Similarly, to encrypt a message in CP-ABE mode, we remove all elements involving attributes in the ciphertextCTkp, such that any secret key SKkp can decrypt it. Set CTkp=Sany,Cw=w1−s, and remain C0,Cm,CTcp exactly the same as in the DP-ABE.


## 4.2. Key Generation in Single-Policy Modes

When a secret key is generated in KP-ABE mode (denoted by KP-SK) with the objective access policyAkp and the subjective attribute set Scp=Sany, a data user with it can decrypt any ciphertext encrypted under Skp,Acp if fSkp,Akp=1. Analogously, when a secret key is generated in the CP-ABE mode (denoted by CP-SK) with the subjective attribute set Scp and the objective access policy Akp=Aany, a data user with it can decrypt any ciphertext encrypted under Skp,Acp if fScp,Acp=1.Generic Construction. We can also use the idea of dummy attributes to convert from any DP-ABE schemeΠ to a new DP-ABE scheme Π″ that admits single-policy key generation modes.Specially,Π″.Setup is the same as Π.Setup except that it additionally chooses a special objective attribute Ask,o and a special subjective attribute Ask,s, and adds them into the public parameters PK. Both Ask,o,Ask,s will not be used as attributes in Π″. Next we define(23)Π″.EncryptPK,Skp,Acp=Π.EncryptPK,Skp∪Ask,o,Acp∪Ask,s,In KP−ABEmode,Π″.KeyGenPK,MSK,Akp,Sany=Π.KeyGenPK,MSK,Akp,Ask,s,In CP−ABEmode,Π″.KeyGenPK,MSK,Aany,Scp=Π.KeyGenPK,MSK,Ask,o,Scp.Direct Construction. When applying the above generic conversion to our proposed DP-ABE, the resulting scheme involves using the dummy attributes in all ciphertexts. Thus, we present a direct construction as follows.To generate a secret key in KP-ABE mode, we setSKcp=Sany, and directly use the master secret key MSK=α to generate SKkp. Specially, choose ν⟶=α,ν2,…,νm⊤ where ν2,…,νm←$ℤp. The vector of the shares of is αμ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(24)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.To generate a secret key in CP-ABE mode, we setSKkp=Aany, and directly use the master secret key MSK=α to generate SKcp. Specially, choose r←$ℤp and compute K0=g1αw2r, K1=g2r. For j∈d choose rj←$ℤp and compute(25)Kj,2=g2rj,Kj,3=u2Ajh2rjv−r.SetSKcp=Scp,K0,K1,Kj,2,Kj,3j∈d.


## 4.3. Decryption Cases and Security Analysis

Encryption and key generation in single-policy modes are orthogonal from the functional aspect, so they can be used simultaneously in the whole system, which leads to three kinds of ciphertexts and three kinds of secret keys, namely, in KP/CP/DP-ABE modes, respectively.For the generic constructions, dummy attributes are introduced in the attribute set and access policy, which do not change the structures of ciphertexts or secret keys, so the decryption can be done exactly in the same way as in the dual-policy setting. While, for the direct constructions, the decryption algorithms are different. We discuss 9 kinds of decryption cases in Table3.Table 3
Decryption cases of DP-ABE in single-policy modes.
SKCTKP-ABE modeSkp,AanyCP-ABE modeSany,AcpDP-ABE modeSkp,AcpKP-ABE modeAkp,SanyIffSkp,Akp=1, then Ekp=eg1,g2αsSincefSany,Akp=1 and fSany,Acp=1, we always have Ekp=e∏i∈IKi,0φi,C0eCw,∏i∈IKi,2φi=eg1,g2αsIffSkp,Akp=1, then Ekp=eg1,g2αsCP-ABE modeAany,ScpSincefSkp,Aany=1 and fScp,Aany=1, we always have Ecp=eK0,C0eCw,K1=eg1,g2αsIffScp,Acp=1, then Ecp=eg1,g2αsIffScp,Acp=1, then Ecp=eg1,g2αsDP-ABE modeAkp,ScpIffSkp,Akp=1, then Ekp=eg1,g2αs, Ecp=eK0,C0eCw,K1=eg1,g2α−βsIffScp,Acp=1, then Ecp=eg1,g2α−βs, Ekp=e∏i∈IKi,0φi,C0eCw,∏i∈IKi,2φi=eg1,g2βsIffSkp,Akp=1 and fScp,Acp=1, then Ecp=eg1,g2αs, Ecp=eg1,g2α−βsTheorem 2.
Suppose that the modifiedq−1 (resp. q−2) assumption holds, then the proposed DP-ABE scheme with encryption in CP-ABE (resp. KP-ABE) mode is selectively IND-CPA secure against all adversaries with a challenge access policy of size l×n, where l,n≤q (resp. attribute set of size c, where c≤q).Proof.
Here we prove the security of CP-CT. The proof of KP-CT is similar.
Suppose there is an adversaryA that can attack the DP-ABE scheme with encryption in CP-ABE mode. We can construct an algorithm ℬ to attack the modified q−1 assumption.
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗=Sany, and Acp∗ is of size l×n, where l,n≤q.
Setup. According to the strategy in the proof of CP-ABE scheme [16], ℬ uses the modified q−1 assumption instance to generate PKcp=par,u2,h2,w2,v,eg1,g2α, and implicitly sets MSK=α. Then, it chooses u1,h1,w1←$G1, and returns PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α to A.
Phase 1.A queries the secret key corresponding to the pair Akp,Scp where Akp is of size k×m, and Scp is of size d. Since Skp∗=Sany, we have fScp,Acp∗=0. ℬ acts as follows:
LetAkp=M,ρ. Choose ν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k choose τi←$ℤp and compute(26)Ki,0=g1μiw1τi,Ki,1=u1ρih1−τi,Ki,2=g2τi.
SetSKkp=Akp,Ki,0,Ki,1,Ki,2i∈k.
LetScp=A1,A2,…,Ad. According to the strategy in the proof of CP-ABE scheme [16], use the modified q−1 assumption instance to generate(27)SKcp′=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.
SetSKcp=Scp,K0′⋅g1−β,K1′,Kj,2′,Kj,3′j∈d.
ReturnSK=SKkp,SKcp.Challenge.A submits two messages msg0∗,msg1∗ from the message space GT. According to the strategy in the proof of CP-ABE scheme [16], ℬ uses the modified q−1 assumption instance to generate Ccp,0=g2s,Ccp,m=eg1,g2αs⋅msgb∗,CTcp and CTkp=Sany,Cw=w1−s. Finally, it returns CT∗=g2s,eg1,g2αs⋅msgb∗,CTkp,CTcp to A.Phase 2. Phase 1 is repeated.Guess.A outputs a bit b′. ℬ outputs b′ as its guess.
From the view ofA, the simulation is indistinguishable from the real experiment. Also note that in a secret key SK=SKkp,SKcp, SKkp can be used to recover Ekp=eg1,g2βs from CTkp, and the distribution of SKcp is the same as that of a secret key generated by using MSK′=α−β in CP-ABE scheme [16]. Therefore, the challenge ciphertext is actually g2s,eg1,g2α−βs⋅msgb∗,CTcp, which is the same as in CP-ABE scheme [16]. We obtain the theorem.Theorem 3.
Suppose that the KP-ABE and CP-ABE schemes [16] are selectively IND-CPA secure, then the proposed DP-ABE scheme with key generation in CP-ABE (or KP-ABE) mode is selectively IND-CPA secure.Proof.
We present the security sketch of key generation in CP-ABE mode. The security in KP-ABE mode is similar.
We use the strategy in the proof of Theorem1. The only difference is that, A is also allowed to ask for any secret key corresponding to Akp∗,Scp where Akp∗=Aany, and fScp,Acp∗=0. For this kind of query, ℬ can directly call the key generation oracle of Ccp on Scp to obtain SKcp, set SKkp=Aany, and return SK=SKkp,SKcp to A.


## 5. Fully Outsourced DP-ABE

In this section, we propose our fully outsourced dual-policy attribute-based encryption (FO-DP-ABE) scheme.


### 5.1. System Model

As illustrated in Figure1, five entities are involved in system, namely, the private key generator (PKG), data owner (DO), data user (DU), cloud server 1 (CS1), and cloud server 2 (CS2). A data owner can also be a data user in the system, and vice versa. Specifically.(i)
Private Key Generator is responsible to setup the system parameters and to distribute all cryptographic keys to other entities.(ii)
Data Owner encrypts data and uploads ciphertext to the cloud.(iii)
Data User downloads ciphertext from the cloud and decrypts it to recover data.(iv)
Cloud Server 1 is deployed to provide outsourced computation (key generation, encryption, and decryption) service and data storage service.(v)
Cloud Server 2 is deployed to provide outsourced computation (key generation and encryption) service.Figure 1
System model of FO-DP-ABE.As shown in Figure2, the system process is as follows:(1)
System Initialization. The PKG generates the public parameters PK and the master secret key MSK, broadcasts PK to all entities, and keeps MSK locally.(2)
User Registration. The PKG continuously requests intermediate keys IKs from two cloud servers. For each data user, the PKG assigns an objective access structureAkp and a subjective attribute set Scp, and uses IK1, IK2 to generate a transformation key TK and a retrieval key RK. TK is sent to the cloud server 1 and RK is send to the user.(3)
Data Encryption. The data owner continuously requests intermediate ciphertext ITs from two cloud servers. To encrypt the messagemsg, the owner uses IT1, IT2 to generate a ciphertext CT under an objective attribute set Skp and a subjective access structure Acp. CT is uploaded to the cloud server 1.(4)
Data Decryption. The cloud server 1 executes outsourced decryption on CT with TK to generate a transformed ciphertext TCT. The user downloads TCT and decrypts it with RK to recover the messagemsg.Figure 2
Flow chart of FO-DP-ABE.The channels that transmit TK, RK, IKs, ITs should be secure, because the secret keys are always distributed privately, and the intermediate computation results cannot be accessed by outsiders.


### 5.2. Syntax

An FO-DP-ABE for access structure spaceG contains the following algorithms:(i)
Setupλ,U⟶PK,MSK. The setup algorithm takes a security parameter λ and a universe description U as input, and outputs the public parameters PK and the master secret key MSK.(ii)
KeyGen.outPK⟶IK. The outsourced key generation algorithm takes the public parameters PK as input, and outputs an intermediate key IK.(iii)
KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2⟶TK,RK. The local key generation algorithm takes the public parameters PK, the master secret key MSK, an objective access structure Akp, a subjective attribute set Scp, and two intermediate keys IK1,IK2 as input, and outputs a transformation key TK and a retrieval key RK corresponding to Akp,Scp.(iv)
Encrypt.outPK⟶IT. The outsourced encryption algorithm takes the public parameters PK as input, and outputs an intermediate ciphertext IT.(v)
Encrypt.ownerPK,msg,Skp,Acp,IT1,IT2⟶CT. The local encryption algorithm takes the public parameters PK, a message msg from the message space ℳ, an objective attribute set Skp, a subjective access structure Acp, and two intermediate ciphertexts IT1,IT2 as input, and outputs a ciphertext CT encrypted under Skp,Acp.(vi)
Decrypt.outPK,TK,CT⟶TCT or ⊥. The outsourced decryption algorithm takes the public parameters PK, a transformation key TK corresponding to Akp,Scp, and a ciphertext CT encrypted under Skp,Acp as input, and outputs a transformed ciphertext TCT if it holds that the objective attribute set Skp satisfies the objective access structure Akp, i.e., fSkp,Akp=1, and that the subjective attribute set Scp satisfies the subjective access structure Acp, i.e., fScp,Acp=1. Otherwise, it outputs ⊥.(vii)
Decrypt.userPK,RK,TCT⟶msg. The local decryption algorithm takes the public parameters PK, a retrieval key RK, and a transformed ciphertext TCT as input, and outputs the decryption result msg.Correctness. It requires that for allSkp⊆U, all Scp⊆U, all Akp∈G, all Acp∈G, all msg∈ℳ, all PK,MSK∈Setupλ,U, all IK1,IK2∈KeyGen.outPK, all TK,RK∈KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2, all IT1,IT2∈Encrypt.outPK , and all CT∈Encrypt.ownerPK,msg,Skp,Acp,IT1,IT2:(28)IffSkp,Akp=1,fScp,Acp=1,thenDecrypt.outPK,TK,CT=TCT,Decrypt.userPK,RK,TCT=msg.


### 5.3. Security Model

LetΠFO−DP−ABE=Setup,KeyGen.out,KeyGen.pkg,Encrypt.out,Encrypt.owner,Decrypt.out,Decrypt.user be an FO-DP-ABE scheme for access structure space G, and consider the following experiments for an adversary A.The FO-DP-ABE experiment against the Type-1 adversaryExpA,ΠFO−DP−ABEIND−CCA1λ,U:Init.A declares the challenge objective attribute set Skp∗ and the challenge subjective access structure Acp∗.Setup. The challengerC runs Setupλ,U to obtain PK,MSK and sends PK to A.Phase 1.C initializes an empty table T and an integer ctr=0. Proceeding adaptively, A can repeatedly make any of the following queries:(i)
CreateAkp,Scp: C sets ctr=ctr+1. It runs KeyGen.outPK twice to obtain IK1,IK2, runs KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2 to obtain TK,RK and stores the entry ctr,Akp,Scp,TK,RK in table T.(ii)
Corrupt.TKκ: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns TK to A.(iii)
Corrupt.RKκ: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns RK to A. Note that the κ th entry does not satisfy fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(iv)
Corrupt.IK1: C runs KeyGen.outPK to obtain IK1 and returns IK1 to A.(v)
Corrupt.IT1: C runs Encrypt.outPK to obtain IT1 and returns IT1 to A.(vi)
Decrypt.CTκ,CT: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns the output of Decrypt.userPK,RK,Decrypt.outPK,TK,CT to A.(vii)
Decrypt.TCTκ,TCT: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns the output of Decrypt.userPK,RK,TCT to A. Note that it simply returns ⊥ if TCT is not generated from Decrypt.outPK,TK,⋅.Challenge.A submits two equal length messages msg0∗ and msg1∗ as the challenge. C picks b←$0,1, runs Encrypt.outPK twice to obtain IT1,IT2, runs Encrypt.ownerPK,msgb∗,Skp∗,Acp∗,IT1,IT2 to obtain CT∗, and returns CT∗ to A.Phase 2. Phase 1 is repeated with the restrictions that the adversary cannot query:(i)
Corrupt.RKκ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(ii)
Decrypt.CTκ,CT∗ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(iii)
Decrypt.TCTκ,TCT∗ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously, and TCT∗=Decrypt.outPK,TK,CT∗, where TK is of the κ th entry in table T.Guess.A outputs a guess b′ of b. The output of the experiment is 1 iff b′=b.The FO-DP-ABE experiment against the Type-2 adversaryExpA,ΠFO−DP−ABEIND−CCA2λ,U:Same as the above experiment, except thatA cannot query Corrupt.TK. Besides, the query Corrupt.IK1 is replaced by Corrupt.IK2, and the query Corrupt.IT1 is replaced by Corrupt.IT2.Definition 7.
An FO-DP-ABE is selectively IND-CCA secure if for all adversariesA, there exists negl such that:(29)PrExpA,ΠFO−DP−ABEIND−CCA1,2λ,U=1−12≤neglλ.Remark.
The security model covers the situations of encryption and key generation in single-policy modes. If the challenge objective attribute set isSany∗, or the challenge subjective access structure is Aany∗, the adversary cannot make queries which may trivially break the security of CT∗.


### 5.4. Construction

First, we present some intuitions of the construction. We apply the outsourced computation technique [23] on the proposed DP-ABE, and transform it to be secure against the chosen ciphertext attack. (1) The key generation and encryption are split into two phases: an outsourced computation phase in which two cloud servers create intermediate keys or ciphertexts offline, and the second phase in which the PKG or the data owner can rapidly compute the “correction factors” and assemble a key or ciphertext online. (2) To make the scheme CCA-secure, the Canetti-Halevi-Katz transformation [31] is applied to make CT non-malleable. The data owner generates a one-time signature of the ciphertext, which allows the cloud server (we explicitly compute the randomness r=r′+r″γ, which is used to demonstrate that K0,K1 and, Kj,3 are well-formed. In a real system, the PKG does not need to correct r locally. Thus, the attribute key module IKcp,main would not contain r′. We consider this in the performance evaluations (Section 6)). Publicly verify it before the outsourced decryption. Then, the data user can verify TCT according to the Fujisaki-Okamoto transformation [32].The constructions of single-policy modes of FO-DP-ABE are omitted, which can be achieved in a manner similar to that given in Section4.TheSetup algorithm is similar as our DP-ABE scheme, except that the public parameters PK includes a key derivation function ℱ:GT⟶0,1L and three hash functions ℋ1:GT×0,1L⟶ℤp∗, ℋ2:GT×0,1L⟶ℤp∗, ℋ3:0,1∗⟶G1. Other algorithms are as follows:(i)
KeyGen.outPK. Choose μi′,τi′,xi′←$ℤp and compute(30)Ki,0′=g1μi′w1τi′,Ki,1′=u1xi′h1−τi′,Ki,2′=g2τi′.SetIKkp=μi′,τi′,xi′,Ki,0′,Ki,1′,Ki,2′.Chooseα′,r′←$ℤp and compute(31)K0′=g1α′w2r′,K1′=g2r′,Kv′=v−r′.Chooserj′,aj′←$ℤp and compute(32)Kj,2′=g2rj′,Kj,3′=u2aj′h2rj′.SetIKcp,main=α′,r′,K0′,K1′,Kv′, IKcp,attr=rj′,aj′,Kj,2′,Kj,3′.OutputIK=IKkp,IKcp,main,IKcp,attr.(ii)
KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2. Choose γ←$ℤp. Let Akp=M,ρ be an LSSS access structure with M∈ℤpk×m and ρ:k⟶ℤp. Select and assemble(33)IK1kp=μi′,τi′,xi′,Ki,0′,Ki,1′,Ki,2′i∈k,IK2kp=μi″,τi″,xi″,Ki,0″,Ki,1″,Ki,2″i∈k.Fori∈k compute(34)μ˜i=μi′+μi″γ,τi=τi′+τi″γ,xi=xi′τi′+xi″τi″γτi,Ki,0=Ki,0′⋅Ki,0″=g1μ˜iw1τi1/γ,Ki,1=Ki,1′⋅Ki,1″=u1xih1−τi/γ,Ki,2=Ki,2′⋅Ki,2″=g2τi/γ.Chooseν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k compute(35)Ki,3=μi−μ˜iγ,Ki,4=xi−ρiτiγ.SetTKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k.LetScp=A1,A2,…,Ad⊆ℤp be an attribute set. Select and assemble(36)IK1cp=α′,r′,K0′,K1′,Kv′,rj′,aj′,Kj,2′,Kj,3′j∈d,IK2cp=α″,r″,K0″,K1″,Kv″,rj″,aj″,Kj,2″,Kj,3″j∈d.Compute (we explicitly compute the randomnessr=r′+r″γ, which is used to demonstrate that K0,K1 and, Kj,3 are well-formed. In a real system, the PKG does not need to correct r locally. Thus, the attribute key module IKcp,main would not contain r′. We consider this in the performance evaluations (Section 6)).(37)α˜=α′+α″γ,r=r′+r″γ,K0=K0′⋅K0″=g1α˜w2r1/γ,K1=K1′⋅K1″=g2r/γ,K4=α−α˜−βγ.Forj∈d compute(38)rj=rj′+rj″γ,aj=aj′rj′+aj′′rj′′γrj,Kj,2=Kj,2′⋅Kj,2′′=g2rj/γ,Kj,3=Kj,3′⋅Kj,3′′⋅Kv′⋅Kv′′=u2ajh2rj/γv−r/γ,Kj,5=Aj−ajrjγ.SetTKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d.OutputTK=TKkp,TKcp, RK=γ.(iii)
Encrypt.outPK. Choose s′,z′←$ℤp and compute(39)C0′=g2s′,Cv′=g2z′,Cr′=eg1,g2αs′.SetITcmn=s′,z′,C0′,Cv′,Cr′.Chooseθ′←$ℤp and compute Cw′=w1−θ′.Chooseσi′,bi′←$ℤp and compute(40)Ci,1′=g2σi′,Ci,2′=u1bi′h1σi′.SetITkp,main=θ′,Cw′, ITkp,attr=σi′,bi′,Ci,1′,Ci,2′.Chooseδj′,tj′,yj′←$ℤp and compute(41)Cj,1′=w2δj′vtj′,Cj,2′=u2yj′h2−tj′,Cj,3′=g2tj′.SetITcp=δj′,tj′,yj′,Cj,1′,Cj,2′,Cj,3′.OutputIT=ITcmn,ITkp,main,ITkp,attr,ITcp.(iv)
Encrypt.ownerPK,msg∈0,1L,Skp,Acp,IT1,IT2. Select and assemble(42)IT1cmn=s′,z′,C0′,Cv′,Cr′,IT2cmn=s″,z″,C0″,Cv″,Cr″.Chooseran←$GT and compute(43)s=ℋ1msg,ran,s˜=s′+s″,Cs=s−s˜,z=ℋ2msg,ran,z˜=z′+z″,Cz=z−z˜,C0=C0′⋅C0″=g2s˜,Cv=Cv′⋅Cv″=g2z˜,Cr=Cr′⋅Cr″⋅ran=eg1,g2αs˜⋅ran,Cm=ℱran⊕msg.SetCTcmn=Cs,Cz,C0,Cv,Cr,Cm.LetSkp=B1,B2,…,Bc⊆ℤp be an attribute set. Select and assemble(44)IT1kp=θ′,Cw′,σi′,bi′,Ci,1′,Ci,2′i∈c,IT2kp=θ″,Cw″,σi″,bi″,Ci,1″,Ci,2″i∈c.Compute(45)θ=θ′+θ″,Cθ=s−θ.Fori∈c compute(46)σi=σi′+σi″,bi=bi′σi′+bi″σi″σi,Ci,1=Ci,1′⋅Ci,1″=g2σi,Ci,2=Ci,2′⋅Ci,2″⋅Cw′⋅Cw″=u1bih1σiw1−θ,Ci,3=Bi−biσi.SetCTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.LetAcp=N,π be an LSSS access structure with N∈ℤpl×n and π:l⟶ℤp. Select and assemble(47)IT1cp=δj′,tj′,yj′,Cj,1′,Cj,2′,Cj,3′j∈l,IT2cp=δj″,tj″,yj″,Cj,1″,Cj,2″,Cj,3″j∈l.Forj∈l compute(48)δ˜j=δj′+δj″,tj=tj′+tj″,yj=yj′tj′+yj″tj″tj,Cj,1=Cj,1′⋅Cj,1″=w2δ˜jvtj,Cj,2=Cj,2′⋅Cj,2″=u2yjh2−tj,Cj,3=Cj,3′⋅Cj,3″=g2tj.Chooseη⟶=s,η2,…,ηn⊤ where η2,…,ηn←$ℤp. The vector of the shares of s is δ⟶=δ1,…,δl⊤=Nη⟶. For j∈l compute(49)Cj,4=δj−δ˜j,Cj,5=yj−πjtj.SetCTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.Compute(50)sig=ℋ3CTcmn,CTkp,CTcpz.OutputCT=sig,CTcmn,CTkp,CTcp.(v)
Decrypt.outPK,TK,CT (we give the details about how to verify the correctness of CT, and how to outsource decrypt it with TK. Actually, the cloud server 1 can execute the verification and precalculation on CT just after receiving it. Thus, the complexity of Decrypt.out is the same as that of Decrypt in our DP-ABE. We consider this in the performance evaluations (Section 6)). Compute T0=Cv⋅g2Cz.ParseCT=sig,CTcmn,CTkp,CTcp. Output ⊥ if(51)esig,g2≠eℋ3CTcmn,CTkp,CTcp,T0.ParseCTcmn=Cs,Cz,C0,Cv,Cr,Cm.Parse the key and ciphertext:(52)TKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k,CTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.IffSkp,Akp≠1, output ⊥. Otherwise, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Output ⊥ if ∃i∈I that(53)eCεi,2⋅u1Cεi,3w1−Cθ,g2≠eu1Bih1,Cεi,1ew1−1,C0⋅g2Cs.Otherwise, compute(54)Ekp=eg1∑i∈IφiKi,3⋅∏i∈IKi,0φi,C0⋅g2Cs⋅∏i∈IeKi,1⋅u1Ki,4,C∈i,1C∈i,2⋅u1C∈i,3w1−Cθ,Ki,2φi.Parse the key and ciphertext:(55)TKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.IffScp,Acp≠1, output ⊥. Otherwise, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Output ⊥ if(56)ew2∑j∈JϕjCj,4⋅∏j∈JCj,1ϕj,g2≠ew2,C0⋅g2Csev,∏j∈JCj,3ϕj,or∃j∈J that(57)eCj,2⋅u2Cj,5,g2≠eu2πjh2,Cj,3−1.Otherwise, compute(58)Ecp=eK0⋅g1K4,C0⋅g2Csew2∑j∈JϕjCj,4⋅∏j∈JCj,1ϕj,K1⋅1∏j∈JeCj,2⋅u2Cj,5,Kεj,2eKεj,3⋅u2Kεj,5,Cj,3ϕj.ComputeT1=Ekp⋅Ecp=eg1,g2βs/γ+α−βs/γ=eg1,g2αs/γ, T2=Cr⋅eg1,g2αCs=eg1,g2αs⋅ran. Output TCT=T0,T1,T2,Cm.(vi)
Decrypt.userPK,RK,TCT. Parse RK=γ and TCT=T0,T1,T2,Cm. Compute(59)ran=T2T1γ,msg=ℱran⊕Cm,s=ℋ1msg,ran,z=ℋ2msg,ran.IfT0=g2z, T1=eg1,g2αs/γ and T2=eg1,g2αs⋅ran, output msg. Otherwise, ⊥.Correctness: Can be easily verified.


### 5.5. Security Analysis

Theorem 4.
Suppose that the proposed DP-ABE is selectively IND-CPA secure, then the proposed FO-DP-ABE scheme is selectively IND-CCA secure in the random oracle model.Proof.
In the security model, the Type-1 adversary gets more information (i.e., all transformation keys) than the Type-2 adversary, so we only prove the security against the former.
Suppose there is an adversaryA that can attack the proposed FO-DP-ABE in the selective CCA security model. We can construct an algorithm ℬ to break the proposed DP-ABE in the selective CPA security model.
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗ is of size c, and Acp∗ is of size l×n. ℬ passes on them to the challenger C of the DP-ABE scheme.
Setup.ℬ receives the public parameters PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α from C, and returns them to A.
Phase 1.ℬ initializes an empty table T, an integer ctr=0, and three empty lists ℒ1,ℒ2,ℒ3. It answers the queries from A as follows:(i)
Random Oracleℋ1msg,ran: If there is an entry msg,ran,s in ℒ1, return s. Otherwise, choose s←$ℤp∗, record msg,ran,s in ℒ1, and return s.(ii)
Random Oracleℋ2msg,ran: If there is an entry msg,ran,z in ℒ2, return z. Otherwise, choose z←$ℤp∗, record msg,ran,z in ℒ2, and return z.(iii)
Random Oracleℱran: If there is an entry ran,str in ℒ3, return str. Otherwise, choose str←$0,1L, record ran,str in ℒ3, and return str.(iv)
CreateAkp,Scp: Suppose Akp is of size k×m, and Scp is of size d. Set ctr=ctr+1 and act as follows:(1)
IffSkp∗,Akp=1 and fScp,Acp∗=1, then choose MSK′=γ←$ℤp, run KeyGen.outPK twice to obtain IK1,IK2, and run KeyGen.pkgPK,MSK′,Akp,Scp,IK1,IK2 to obtain TK′,RK′.SetTK=TK′, RK=γ,RK′.Otherwise,fSkp∗,Akp=0 or fScp,Acp∗=0. Call the key generation oracle of C on Akp,Scp to obtain SK=SKkp,SKcp, where(60)SKkp=Akp,Ki,0′,Ki,1′,Ki,2′i∈k,SKcp=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.Chooseγ←$ℤp.Fori∈k choose μ˜i,xi←$ℤp and compute(61)Ki,0=Ki,0′⋅g1−μ˜i1/γ,Ki,1=Ki,1′⋅u1−xi1/γ,Ki,2=Ki,2′1/γ,Ki,3=μ˜iγ,Ki,4=xiγ.SetTKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k.Chooseα˜←$ℤp and compute(62)K0=K0′⋅g1−α˜1/γ,K1=K1′1/γ,K4=α˜γ.Forj∈d choose aj←$ℤp and compute(63)Kj,2=Kj,2′1/γ,Kj,3=Kj,3′⋅u2−aj1/γ,Kj,5=ajγ.SetTKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d.SetTK=TKkp,TKcp,RK=γ.(2)
Storectr,Akp,Scp,TK,RK in T.(v)
Corrupt.TKκ: Retrieve the κ th entry κ,Akp,Scp,TK,RK in T and return TK.(vi)
Corrupt.RKκ: Retrieve the κ th entry κ,Akp,Scp,TK,RK in T and return RK.(vii)
Decrypt.CTκ,CT: Parse CT=sig,CTcmn,CTkp,CTcp and act as follows:(1)
Retrieve theκ th entry κ,Akp,Scp,TK,RK in T.(2)
ParseCTcmn=Cs,Cz,C0,Cv,Cr,Cm. Output ⊥ if(64)esig,g2≠eℋ3CTcmn,CTkp,CTcp,Cv⋅g2Cz.Parse the key and ciphertext:(65)TKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k,CTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.IffSkp,Akp≠1, output ⊥. Otherwise, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Output ⊥ if ∃i∈I that(66)eCεi,2⋅u1Cεi,3w1−Cθ,g2≠eu1Bih1,Cεi,1ew1−1,C0⋅g2Cs.Parse the key and ciphertext:(67)TKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.IffScp,Acp≠1, output ⊥. Otherwise, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Output ⊥ if(68)e∏j∈JCj,1ϕj⋅w2∑j∈JϕjCj,4,g2≠ew2,C0⋅g2Csev,∏j∈JCj,3ϕj,or∃j∈J that(69)eCj,2⋅u2Cj,5,g2≠eu2πjh2,Cj,3−1.(3)
Search the pairsmsg,ran,s in ℒ1, msg,ran,z in ℒ2 and ran,str in ℒ3. These pairs should satisfy(70)sig=ℋ3CTcmn,CTkp,CTcpz,C0=g2s−Cs,Cv=g2z−Cz,Cr=eg1,g2αs−Cs⋅ran,Cm=str⊕msg.(4)
If zero matches are found, return⊥. If more than one matches are found, abort the simulation. Otherwise, return msg.(viii)
Decrypt.TCTκ,TCT: Parse TCT=T0,T1,T2,Cm and act as follows:(1)
Retrieve theκ th entry κ,Akp,Scp,TK,RK in T.(2)
Search the pairsmsg,ran,s in ℒ1, msg,ran,z in ℒ2 and ran,str in ℒ3.
IffSkp∗,Akp=1 and fScp,Acp∗=1, then RK=γ,RK′. These pairs should satisfy(71)T0=g2z,T1=eg1,g2γs,T2=eg1,g2αs⋅ran,Cm=str⊕msg.
Otherwise,fSkp∗,Akp=0 or fScp,Acp∗=0, then RK=γ. These pairs should satisfy
(72)T0=g2z,T1=eg1,g2αs/γ,T2=eg1,g2αs⋅ran,Cm=str⊕msg.(3)
If zero matches are found, return⊥. If more than one matches are found, abort the simulation. Otherwise, return msg.
Challenge.A submits two messages msg0∗,msg1∗ from the message space 0,1L. ℬ acts as follows:(1)
Choose random “messages”ran0,ran1←$GT and pass ran0,ran1,A∗ on to C to obtain CT=C0′,Cr′,CTkp′,CTcp′, where(73)CTkp′=Skp∗,Ci,1′,Ci,2′i∈c,CTcp′=Acp∗,Cj,1′,Cj,2′,Cj,3′j∈l.(2)
Choosez,Cs,Cz←$ℤp and Cm←$0,1L. Compute(74)C0=C0′⋅g2−Cs,Cv=g2z−Cz,Cr=Cr′⋅eg1,g2−αCs.SetCTcmn=Cs,Cz,C0,Cv,Cr,Cm.ChooseCθ←$ℤp. For i∈c choose bi←$ℤp and compute(75)Ci,1=Ci,1′,Ci,2=Ci,2′⋅u1−biw1Cθ,Ci,3=bi.SetCTkp=Skp∗,Cθ,Ci,1,Ci,2,Ci,3i∈c.Forj∈l choose δ˜j,yj←$ℤp∗ and compute(76)Cj,1=Cj,1′⋅w2−δ˜j,Cj,2=Cj,2′⋅u2−yj,Cj,3=Cj,3′,Cj,4=δ˜j,Cj,5=yj.SetCTcp=Acp∗,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.Compute(77)sig=ℋ3CTcmn,CTkp,CTcpz.(3)
ReturnCT∗=sig,CTcmn,CTkp,CTcp.
Phase 2. Almost the same as Phase 1, but with the specified restrictions.
Guess. Eventually,A must either output a bit or abort, either way ℬ ignores it. Next, ℬ searches through lists ℒ1, ℒ2 , and ℒ3 to see if the values ran0 or ran1 appear as the first element of any entry, i.e., that A issued a query of the form ℋ1ranb,⋅, ℋ2ranb,⋅, or ℱranb. If neither or both values appear, ℬ outputs a random bit as its guess. If only value ranb appears, ℬ outputs b as its guess.
It is clear that from the view ofA, the simulation is indistinguishable from the real experiment. According to the analysis in Ref. [32], the simulation will abort with a negligible probability. The above is the security proof of FO-DP-ABE in dual-policy mode. In single-policy modes, the proof can be conducted similarly. The algorithm ℬ obtains secret keys and ciphertexts from the challenger C (running in single-policy modes), and re-randomizes them with correction factors. Therefore, we obtain the theorem.


## 5.1. System Model

As illustrated in Figure1, five entities are involved in system, namely, the private key generator (PKG), data owner (DO), data user (DU), cloud server 1 (CS1), and cloud server 2 (CS2). A data owner can also be a data user in the system, and vice versa. Specifically.(i)
Private Key Generator is responsible to setup the system parameters and to distribute all cryptographic keys to other entities.(ii)
Data Owner encrypts data and uploads ciphertext to the cloud.(iii)
Data User downloads ciphertext from the cloud and decrypts it to recover data.(iv)
Cloud Server 1 is deployed to provide outsourced computation (key generation, encryption, and decryption) service and data storage service.(v)
Cloud Server 2 is deployed to provide outsourced computation (key generation and encryption) service.Figure 1
System model of FO-DP-ABE.As shown in Figure2, the system process is as follows:(1)
System Initialization. The PKG generates the public parameters PK and the master secret key MSK, broadcasts PK to all entities, and keeps MSK locally.(2)
User Registration. The PKG continuously requests intermediate keys IKs from two cloud servers. For each data user, the PKG assigns an objective access structureAkp and a subjective attribute set Scp, and uses IK1, IK2 to generate a transformation key TK and a retrieval key RK. TK is sent to the cloud server 1 and RK is send to the user.(3)
Data Encryption. The data owner continuously requests intermediate ciphertext ITs from two cloud servers. To encrypt the messagemsg, the owner uses IT1, IT2 to generate a ciphertext CT under an objective attribute set Skp and a subjective access structure Acp. CT is uploaded to the cloud server 1.(4)
Data Decryption. The cloud server 1 executes outsourced decryption on CT with TK to generate a transformed ciphertext TCT. The user downloads TCT and decrypts it with RK to recover the messagemsg.Figure 2
Flow chart of FO-DP-ABE.The channels that transmit TK, RK, IKs, ITs should be secure, because the secret keys are always distributed privately, and the intermediate computation results cannot be accessed by outsiders.


## 5.2. Syntax

An FO-DP-ABE for access structure spaceG contains the following algorithms:(i)
Setupλ,U⟶PK,MSK. The setup algorithm takes a security parameter λ and a universe description U as input, and outputs the public parameters PK and the master secret key MSK.(ii)
KeyGen.outPK⟶IK. The outsourced key generation algorithm takes the public parameters PK as input, and outputs an intermediate key IK.(iii)
KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2⟶TK,RK. The local key generation algorithm takes the public parameters PK, the master secret key MSK, an objective access structure Akp, a subjective attribute set Scp, and two intermediate keys IK1,IK2 as input, and outputs a transformation key TK and a retrieval key RK corresponding to Akp,Scp.(iv)
Encrypt.outPK⟶IT. The outsourced encryption algorithm takes the public parameters PK as input, and outputs an intermediate ciphertext IT.(v)
Encrypt.ownerPK,msg,Skp,Acp,IT1,IT2⟶CT. The local encryption algorithm takes the public parameters PK, a message msg from the message space ℳ, an objective attribute set Skp, a subjective access structure Acp, and two intermediate ciphertexts IT1,IT2 as input, and outputs a ciphertext CT encrypted under Skp,Acp.(vi)
Decrypt.outPK,TK,CT⟶TCT or ⊥. The outsourced decryption algorithm takes the public parameters PK, a transformation key TK corresponding to Akp,Scp, and a ciphertext CT encrypted under Skp,Acp as input, and outputs a transformed ciphertext TCT if it holds that the objective attribute set Skp satisfies the objective access structure Akp, i.e., fSkp,Akp=1, and that the subjective attribute set Scp satisfies the subjective access structure Acp, i.e., fScp,Acp=1. Otherwise, it outputs ⊥.(vii)
Decrypt.userPK,RK,TCT⟶msg. The local decryption algorithm takes the public parameters PK, a retrieval key RK, and a transformed ciphertext TCT as input, and outputs the decryption result msg.Correctness. It requires that for allSkp⊆U, all Scp⊆U, all Akp∈G, all Acp∈G, all msg∈ℳ, all PK,MSK∈Setupλ,U, all IK1,IK2∈KeyGen.outPK, all TK,RK∈KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2, all IT1,IT2∈Encrypt.outPK , and all CT∈Encrypt.ownerPK,msg,Skp,Acp,IT1,IT2:(28)IffSkp,Akp=1,fScp,Acp=1,thenDecrypt.outPK,TK,CT=TCT,Decrypt.userPK,RK,TCT=msg.


## 5.3. Security Model

LetΠFO−DP−ABE=Setup,KeyGen.out,KeyGen.pkg,Encrypt.out,Encrypt.owner,Decrypt.out,Decrypt.user be an FO-DP-ABE scheme for access structure space G, and consider the following experiments for an adversary A.The FO-DP-ABE experiment against the Type-1 adversaryExpA,ΠFO−DP−ABEIND−CCA1λ,U:Init.A declares the challenge objective attribute set Skp∗ and the challenge subjective access structure Acp∗.Setup. The challengerC runs Setupλ,U to obtain PK,MSK and sends PK to A.Phase 1.C initializes an empty table T and an integer ctr=0. Proceeding adaptively, A can repeatedly make any of the following queries:(i)
CreateAkp,Scp: C sets ctr=ctr+1. It runs KeyGen.outPK twice to obtain IK1,IK2, runs KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2 to obtain TK,RK and stores the entry ctr,Akp,Scp,TK,RK in table T.(ii)
Corrupt.TKκ: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns TK to A.(iii)
Corrupt.RKκ: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns RK to A. Note that the κ th entry does not satisfy fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(iv)
Corrupt.IK1: C runs KeyGen.outPK to obtain IK1 and returns IK1 to A.(v)
Corrupt.IT1: C runs Encrypt.outPK to obtain IT1 and returns IT1 to A.(vi)
Decrypt.CTκ,CT: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns the output of Decrypt.userPK,RK,Decrypt.outPK,TK,CT to A.(vii)
Decrypt.TCTκ,TCT: C retrieves the κ th entry κ,Akp,Scp,TK,RK in table T and returns the output of Decrypt.userPK,RK,TCT to A. Note that it simply returns ⊥ if TCT is not generated from Decrypt.outPK,TK,⋅.Challenge.A submits two equal length messages msg0∗ and msg1∗ as the challenge. C picks b←$0,1, runs Encrypt.outPK twice to obtain IT1,IT2, runs Encrypt.ownerPK,msgb∗,Skp∗,Acp∗,IT1,IT2 to obtain CT∗, and returns CT∗ to A.Phase 2. Phase 1 is repeated with the restrictions that the adversary cannot query:(i)
Corrupt.RKκ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(ii)
Decrypt.CTκ,CT∗ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously.(iii)
Decrypt.TCTκ,TCT∗ that the κ th entry in table T satisfies fSkp∗,Akp=1 and fScp,Acp∗=1 simultaneously, and TCT∗=Decrypt.outPK,TK,CT∗, where TK is of the κ th entry in table T.Guess.A outputs a guess b′ of b. The output of the experiment is 1 iff b′=b.The FO-DP-ABE experiment against the Type-2 adversaryExpA,ΠFO−DP−ABEIND−CCA2λ,U:Same as the above experiment, except thatA cannot query Corrupt.TK. Besides, the query Corrupt.IK1 is replaced by Corrupt.IK2, and the query Corrupt.IT1 is replaced by Corrupt.IT2.Definition 7.
An FO-DP-ABE is selectively IND-CCA secure if for all adversariesA, there exists negl such that:(29)PrExpA,ΠFO−DP−ABEIND−CCA1,2λ,U=1−12≤neglλ.Remark.
The security model covers the situations of encryption and key generation in single-policy modes. If the challenge objective attribute set isSany∗, or the challenge subjective access structure is Aany∗, the adversary cannot make queries which may trivially break the security of CT∗.


## 5.4. Construction

First, we present some intuitions of the construction. We apply the outsourced computation technique [23] on the proposed DP-ABE, and transform it to be secure against the chosen ciphertext attack. (1) The key generation and encryption are split into two phases: an outsourced computation phase in which two cloud servers create intermediate keys or ciphertexts offline, and the second phase in which the PKG or the data owner can rapidly compute the “correction factors” and assemble a key or ciphertext online. (2) To make the scheme CCA-secure, the Canetti-Halevi-Katz transformation [31] is applied to make CT non-malleable. The data owner generates a one-time signature of the ciphertext, which allows the cloud server (we explicitly compute the randomness r=r′+r″γ, which is used to demonstrate that K0,K1 and, Kj,3 are well-formed. In a real system, the PKG does not need to correct r locally. Thus, the attribute key module IKcp,main would not contain r′. We consider this in the performance evaluations (Section 6)). Publicly verify it before the outsourced decryption. Then, the data user can verify TCT according to the Fujisaki-Okamoto transformation [32].The constructions of single-policy modes of FO-DP-ABE are omitted, which can be achieved in a manner similar to that given in Section4.TheSetup algorithm is similar as our DP-ABE scheme, except that the public parameters PK includes a key derivation function ℱ:GT⟶0,1L and three hash functions ℋ1:GT×0,1L⟶ℤp∗, ℋ2:GT×0,1L⟶ℤp∗, ℋ3:0,1∗⟶G1. Other algorithms are as follows:(i)
KeyGen.outPK. Choose μi′,τi′,xi′←$ℤp and compute(30)Ki,0′=g1μi′w1τi′,Ki,1′=u1xi′h1−τi′,Ki,2′=g2τi′.SetIKkp=μi′,τi′,xi′,Ki,0′,Ki,1′,Ki,2′.Chooseα′,r′←$ℤp and compute(31)K0′=g1α′w2r′,K1′=g2r′,Kv′=v−r′.Chooserj′,aj′←$ℤp and compute(32)Kj,2′=g2rj′,Kj,3′=u2aj′h2rj′.SetIKcp,main=α′,r′,K0′,K1′,Kv′, IKcp,attr=rj′,aj′,Kj,2′,Kj,3′.OutputIK=IKkp,IKcp,main,IKcp,attr.(ii)
KeyGen.pkgPK,MSK,Akp,Scp,IK1,IK2. Choose γ←$ℤp. Let Akp=M,ρ be an LSSS access structure with M∈ℤpk×m and ρ:k⟶ℤp. Select and assemble(33)IK1kp=μi′,τi′,xi′,Ki,0′,Ki,1′,Ki,2′i∈k,IK2kp=μi″,τi″,xi″,Ki,0″,Ki,1″,Ki,2″i∈k.Fori∈k compute(34)μ˜i=μi′+μi″γ,τi=τi′+τi″γ,xi=xi′τi′+xi″τi″γτi,Ki,0=Ki,0′⋅Ki,0″=g1μ˜iw1τi1/γ,Ki,1=Ki,1′⋅Ki,1″=u1xih1−τi/γ,Ki,2=Ki,2′⋅Ki,2″=g2τi/γ.Chooseν⟶=β,ν2,…,νm⊤ where β,ν2,…,νm←$ℤp. The vector of the shares of β is μ⟶=μ1,…,μk⊤=Mν⟶. For i∈k compute(35)Ki,3=μi−μ˜iγ,Ki,4=xi−ρiτiγ.SetTKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k.LetScp=A1,A2,…,Ad⊆ℤp be an attribute set. Select and assemble(36)IK1cp=α′,r′,K0′,K1′,Kv′,rj′,aj′,Kj,2′,Kj,3′j∈d,IK2cp=α″,r″,K0″,K1″,Kv″,rj″,aj″,Kj,2″,Kj,3″j∈d.Compute (we explicitly compute the randomnessr=r′+r″γ, which is used to demonstrate that K0,K1 and, Kj,3 are well-formed. In a real system, the PKG does not need to correct r locally. Thus, the attribute key module IKcp,main would not contain r′. We consider this in the performance evaluations (Section 6)).(37)α˜=α′+α″γ,r=r′+r″γ,K0=K0′⋅K0″=g1α˜w2r1/γ,K1=K1′⋅K1″=g2r/γ,K4=α−α˜−βγ.Forj∈d compute(38)rj=rj′+rj″γ,aj=aj′rj′+aj′′rj′′γrj,Kj,2=Kj,2′⋅Kj,2′′=g2rj/γ,Kj,3=Kj,3′⋅Kj,3′′⋅Kv′⋅Kv′′=u2ajh2rj/γv−r/γ,Kj,5=Aj−ajrjγ.SetTKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d.OutputTK=TKkp,TKcp, RK=γ.(iii)
Encrypt.outPK. Choose s′,z′←$ℤp and compute(39)C0′=g2s′,Cv′=g2z′,Cr′=eg1,g2αs′.SetITcmn=s′,z′,C0′,Cv′,Cr′.Chooseθ′←$ℤp and compute Cw′=w1−θ′.Chooseσi′,bi′←$ℤp and compute(40)Ci,1′=g2σi′,Ci,2′=u1bi′h1σi′.SetITkp,main=θ′,Cw′, ITkp,attr=σi′,bi′,Ci,1′,Ci,2′.Chooseδj′,tj′,yj′←$ℤp and compute(41)Cj,1′=w2δj′vtj′,Cj,2′=u2yj′h2−tj′,Cj,3′=g2tj′.SetITcp=δj′,tj′,yj′,Cj,1′,Cj,2′,Cj,3′.OutputIT=ITcmn,ITkp,main,ITkp,attr,ITcp.(iv)
Encrypt.ownerPK,msg∈0,1L,Skp,Acp,IT1,IT2. Select and assemble(42)IT1cmn=s′,z′,C0′,Cv′,Cr′,IT2cmn=s″,z″,C0″,Cv″,Cr″.Chooseran←$GT and compute(43)s=ℋ1msg,ran,s˜=s′+s″,Cs=s−s˜,z=ℋ2msg,ran,z˜=z′+z″,Cz=z−z˜,C0=C0′⋅C0″=g2s˜,Cv=Cv′⋅Cv″=g2z˜,Cr=Cr′⋅Cr″⋅ran=eg1,g2αs˜⋅ran,Cm=ℱran⊕msg.SetCTcmn=Cs,Cz,C0,Cv,Cr,Cm.LetSkp=B1,B2,…,Bc⊆ℤp be an attribute set. Select and assemble(44)IT1kp=θ′,Cw′,σi′,bi′,Ci,1′,Ci,2′i∈c,IT2kp=θ″,Cw″,σi″,bi″,Ci,1″,Ci,2″i∈c.Compute(45)θ=θ′+θ″,Cθ=s−θ.Fori∈c compute(46)σi=σi′+σi″,bi=bi′σi′+bi″σi″σi,Ci,1=Ci,1′⋅Ci,1″=g2σi,Ci,2=Ci,2′⋅Ci,2″⋅Cw′⋅Cw″=u1bih1σiw1−θ,Ci,3=Bi−biσi.SetCTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.LetAcp=N,π be an LSSS access structure with N∈ℤpl×n and π:l⟶ℤp. Select and assemble(47)IT1cp=δj′,tj′,yj′,Cj,1′,Cj,2′,Cj,3′j∈l,IT2cp=δj″,tj″,yj″,Cj,1″,Cj,2″,Cj,3″j∈l.Forj∈l compute(48)δ˜j=δj′+δj″,tj=tj′+tj″,yj=yj′tj′+yj″tj″tj,Cj,1=Cj,1′⋅Cj,1″=w2δ˜jvtj,Cj,2=Cj,2′⋅Cj,2″=u2yjh2−tj,Cj,3=Cj,3′⋅Cj,3″=g2tj.Chooseη⟶=s,η2,…,ηn⊤ where η2,…,ηn←$ℤp. The vector of the shares of s is δ⟶=δ1,…,δl⊤=Nη⟶. For j∈l compute(49)Cj,4=δj−δ˜j,Cj,5=yj−πjtj.SetCTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.Compute(50)sig=ℋ3CTcmn,CTkp,CTcpz.OutputCT=sig,CTcmn,CTkp,CTcp.(v)
Decrypt.outPK,TK,CT (we give the details about how to verify the correctness of CT, and how to outsource decrypt it with TK. Actually, the cloud server 1 can execute the verification and precalculation on CT just after receiving it. Thus, the complexity of Decrypt.out is the same as that of Decrypt in our DP-ABE. We consider this in the performance evaluations (Section 6)). Compute T0=Cv⋅g2Cz.ParseCT=sig,CTcmn,CTkp,CTcp. Output ⊥ if(51)esig,g2≠eℋ3CTcmn,CTkp,CTcp,T0.ParseCTcmn=Cs,Cz,C0,Cv,Cr,Cm.Parse the key and ciphertext:(52)TKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k,CTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.IffSkp,Akp≠1, output ⊥. Otherwise, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Output ⊥ if ∃i∈I that(53)eCεi,2⋅u1Cεi,3w1−Cθ,g2≠eu1Bih1,Cεi,1ew1−1,C0⋅g2Cs.Otherwise, compute(54)Ekp=eg1∑i∈IφiKi,3⋅∏i∈IKi,0φi,C0⋅g2Cs⋅∏i∈IeKi,1⋅u1Ki,4,C∈i,1C∈i,2⋅u1C∈i,3w1−Cθ,Ki,2φi.Parse the key and ciphertext:(55)TKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.IffScp,Acp≠1, output ⊥. Otherwise, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Output ⊥ if(56)ew2∑j∈JϕjCj,4⋅∏j∈JCj,1ϕj,g2≠ew2,C0⋅g2Csev,∏j∈JCj,3ϕj,or∃j∈J that(57)eCj,2⋅u2Cj,5,g2≠eu2πjh2,Cj,3−1.Otherwise, compute(58)Ecp=eK0⋅g1K4,C0⋅g2Csew2∑j∈JϕjCj,4⋅∏j∈JCj,1ϕj,K1⋅1∏j∈JeCj,2⋅u2Cj,5,Kεj,2eKεj,3⋅u2Kεj,5,Cj,3ϕj.ComputeT1=Ekp⋅Ecp=eg1,g2βs/γ+α−βs/γ=eg1,g2αs/γ, T2=Cr⋅eg1,g2αCs=eg1,g2αs⋅ran. Output TCT=T0,T1,T2,Cm.(vi)
Decrypt.userPK,RK,TCT. Parse RK=γ and TCT=T0,T1,T2,Cm. Compute(59)ran=T2T1γ,msg=ℱran⊕Cm,s=ℋ1msg,ran,z=ℋ2msg,ran.IfT0=g2z, T1=eg1,g2αs/γ and T2=eg1,g2αs⋅ran, output msg. Otherwise, ⊥.Correctness: Can be easily verified.


## 5.5. Security Analysis

Theorem 4.
Suppose that the proposed DP-ABE is selectively IND-CPA secure, then the proposed FO-DP-ABE scheme is selectively IND-CCA secure in the random oracle model.Proof.
In the security model, the Type-1 adversary gets more information (i.e., all transformation keys) than the Type-2 adversary, so we only prove the security against the former.
Suppose there is an adversaryA that can attack the proposed FO-DP-ABE in the selective CCA security model. We can construct an algorithm ℬ to break the proposed DP-ABE in the selective CPA security model.
Init.ℬ runs A, who chooses the challenge pair Skp∗,Acp∗ where Skp∗ is of size c, and Acp∗ is of size l×n. ℬ passes on them to the challenger C of the DP-ABE scheme.
Setup.ℬ receives the public parameters PK=par,u1,u2,h1,h2,w1,w2,v,eg1,g2α from C, and returns them to A.
Phase 1.ℬ initializes an empty table T, an integer ctr=0, and three empty lists ℒ1,ℒ2,ℒ3. It answers the queries from A as follows:(i)
Random Oracleℋ1msg,ran: If there is an entry msg,ran,s in ℒ1, return s. Otherwise, choose s←$ℤp∗, record msg,ran,s in ℒ1, and return s.(ii)
Random Oracleℋ2msg,ran: If there is an entry msg,ran,z in ℒ2, return z. Otherwise, choose z←$ℤp∗, record msg,ran,z in ℒ2, and return z.(iii)
Random Oracleℱran: If there is an entry ran,str in ℒ3, return str. Otherwise, choose str←$0,1L, record ran,str in ℒ3, and return str.(iv)
CreateAkp,Scp: Suppose Akp is of size k×m, and Scp is of size d. Set ctr=ctr+1 and act as follows:(1)
IffSkp∗,Akp=1 and fScp,Acp∗=1, then choose MSK′=γ←$ℤp, run KeyGen.outPK twice to obtain IK1,IK2, and run KeyGen.pkgPK,MSK′,Akp,Scp,IK1,IK2 to obtain TK′,RK′.SetTK=TK′, RK=γ,RK′.Otherwise,fSkp∗,Akp=0 or fScp,Acp∗=0. Call the key generation oracle of C on Akp,Scp to obtain SK=SKkp,SKcp, where(60)SKkp=Akp,Ki,0′,Ki,1′,Ki,2′i∈k,SKcp=Scp,K0′,K1′,Kj,2′,Kj,3′j∈d.Chooseγ←$ℤp.Fori∈k choose μ˜i,xi←$ℤp and compute(61)Ki,0=Ki,0′⋅g1−μ˜i1/γ,Ki,1=Ki,1′⋅u1−xi1/γ,Ki,2=Ki,2′1/γ,Ki,3=μ˜iγ,Ki,4=xiγ.SetTKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k.Chooseα˜←$ℤp and compute(62)K0=K0′⋅g1−α˜1/γ,K1=K1′1/γ,K4=α˜γ.Forj∈d choose aj←$ℤp and compute(63)Kj,2=Kj,2′1/γ,Kj,3=Kj,3′⋅u2−aj1/γ,Kj,5=ajγ.SetTKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d.SetTK=TKkp,TKcp,RK=γ.(2)
Storectr,Akp,Scp,TK,RK in T.(v)
Corrupt.TKκ: Retrieve the κ th entry κ,Akp,Scp,TK,RK in T and return TK.(vi)
Corrupt.RKκ: Retrieve the κ th entry κ,Akp,Scp,TK,RK in T and return RK.(vii)
Decrypt.CTκ,CT: Parse CT=sig,CTcmn,CTkp,CTcp and act as follows:(1)
Retrieve theκ th entry κ,Akp,Scp,TK,RK in T.(2)
ParseCTcmn=Cs,Cz,C0,Cv,Cr,Cm. Output ⊥ if(64)esig,g2≠eℋ3CTcmn,CTkp,CTcp,Cv⋅g2Cz.Parse the key and ciphertext:(65)TKkp=Akp,Ki,0,Ki,1,Ki,2,Ki,3,Ki,4i∈k,CTkp=Skp,Cθ,Ci,1,Ci,2,Ci,3i∈c.IffSkp,Akp≠1, output ⊥. Otherwise, calculate I=i:ρi∈Skp and the constants φi∈ℤpi∈I such that ∑i∈IφiMi=1,0,…,0. Let εi denote the index of the attribute ρi in Skp. Output ⊥ if ∃i∈I that(66)eCεi,2⋅u1Cεi,3w1−Cθ,g2≠eu1Bih1,Cεi,1ew1−1,C0⋅g2Cs.Parse the key and ciphertext:(67)TKcp=Scp,K0,K1,K4,Kj,2,Kj,3,Kj,5j∈d,CTcp=Acp,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.IffScp,Acp≠1, output ⊥. Otherwise, calculate J=j:πj∈Scp and the constants ϕj∈ℤpj∈J such that ∑j∈JϕjNj=1,0,…,0. Let εj denote the index of the attribute πj in Scp. Output ⊥ if(68)e∏j∈JCj,1ϕj⋅w2∑j∈JϕjCj,4,g2≠ew2,C0⋅g2Csev,∏j∈JCj,3ϕj,or∃j∈J that(69)eCj,2⋅u2Cj,5,g2≠eu2πjh2,Cj,3−1.(3)
Search the pairsmsg,ran,s in ℒ1, msg,ran,z in ℒ2 and ran,str in ℒ3. These pairs should satisfy(70)sig=ℋ3CTcmn,CTkp,CTcpz,C0=g2s−Cs,Cv=g2z−Cz,Cr=eg1,g2αs−Cs⋅ran,Cm=str⊕msg.(4)
If zero matches are found, return⊥. If more than one matches are found, abort the simulation. Otherwise, return msg.(viii)
Decrypt.TCTκ,TCT: Parse TCT=T0,T1,T2,Cm and act as follows:(1)
Retrieve theκ th entry κ,Akp,Scp,TK,RK in T.(2)
Search the pairsmsg,ran,s in ℒ1, msg,ran,z in ℒ2 and ran,str in ℒ3.
IffSkp∗,Akp=1 and fScp,Acp∗=1, then RK=γ,RK′. These pairs should satisfy(71)T0=g2z,T1=eg1,g2γs,T2=eg1,g2αs⋅ran,Cm=str⊕msg.
Otherwise,fSkp∗,Akp=0 or fScp,Acp∗=0, then RK=γ. These pairs should satisfy
(72)T0=g2z,T1=eg1,g2αs/γ,T2=eg1,g2αs⋅ran,Cm=str⊕msg.(3)
If zero matches are found, return⊥. If more than one matches are found, abort the simulation. Otherwise, return msg.
Challenge.A submits two messages msg0∗,msg1∗ from the message space 0,1L. ℬ acts as follows:(1)
Choose random “messages”ran0,ran1←$GT and pass ran0,ran1,A∗ on to C to obtain CT=C0′,Cr′,CTkp′,CTcp′, where(73)CTkp′=Skp∗,Ci,1′,Ci,2′i∈c,CTcp′=Acp∗,Cj,1′,Cj,2′,Cj,3′j∈l.(2)
Choosez,Cs,Cz←$ℤp and Cm←$0,1L. Compute(74)C0=C0′⋅g2−Cs,Cv=g2z−Cz,Cr=Cr′⋅eg1,g2−αCs.SetCTcmn=Cs,Cz,C0,Cv,Cr,Cm.ChooseCθ←$ℤp. For i∈c choose bi←$ℤp and compute(75)Ci,1=Ci,1′,Ci,2=Ci,2′⋅u1−biw1Cθ,Ci,3=bi.SetCTkp=Skp∗,Cθ,Ci,1,Ci,2,Ci,3i∈c.Forj∈l choose δ˜j,yj←$ℤp∗ and compute(76)Cj,1=Cj,1′⋅w2−δ˜j,Cj,2=Cj,2′⋅u2−yj,Cj,3=Cj,3′,Cj,4=δ˜j,Cj,5=yj.SetCTcp=Acp∗,Cj,1,Cj,2,Cj,3,Cj,4,Cj,5j∈l.Compute(77)sig=ℋ3CTcmn,CTkp,CTcpz.(3)
ReturnCT∗=sig,CTcmn,CTkp,CTcp.
Phase 2. Almost the same as Phase 1, but with the specified restrictions.
Guess. Eventually,A must either output a bit or abort, either way ℬ ignores it. Next, ℬ searches through lists ℒ1, ℒ2 , and ℒ3 to see if the values ran0 or ran1 appear as the first element of any entry, i.e., that A issued a query of the form ℋ1ranb,⋅, ℋ2ranb,⋅, or ℱranb. If neither or both values appear, ℬ outputs a random bit as its guess. If only value ranb appears, ℬ outputs b as its guess.
It is clear that from the view ofA, the simulation is indistinguishable from the real experiment. According to the analysis in Ref. [32], the simulation will abort with a negligible probability. The above is the security proof of FO-DP-ABE in dual-policy mode. In single-policy modes, the proof can be conducted similarly. The algorithm ℬ obtains secret keys and ciphertexts from the challenger C (running in single-policy modes), and re-randomizes them with correction factors. Therefore, we obtain the theorem.


## 6. Performance Evaluations

In this section, we analyze the performance our DP-ABE and FO-DP-ABE. The costs of one cloud server are evaluated in FO-DP-ABE, because the two cloud servers run in parallel.


### 6.1. Theoretical Analysis

We compare the computation and communication costs in our DP-ABE, FO-DP-ABE and those in related work [6, 15].Comparison of Computation Cost. Tables4 and 5 compare the number of modular exponentiations and pairing operations in each algorithm. In Refs. [6, 15] and our DP-ABE, the computation cost of each algorithm grows linearly with the complexity of attribute set and/or access policy. Our FO-DP-ABE outsources almost all expensive computation to cloud servers, leaving constant operations for the PKG, data owners, and users. In particular, the data owner executes one modular exponentiation in G1 to generate a one-time signature; the data user executes one modular exponentiation in GT to decrypt TCT, and one modular exponentiation in G2 and two modular exponentiations in GT to verify TCT. The signature generation and ciphertext verification are necessary to realize CCA security.Table 4
Computation cost comparison.
SchemesKey generationEncryptionDecryptionDP-ABE [6]2k+dE1+1+kE2c+2lE1+1E2+1ET2I+2JE1+2+IPDP-ABE [15]3+2k+2dE1+1+k+dE2c+4lE1+1+lE2+1ET2I+3JE1+3+I+2JPOur DP-ABE (KP mode)4kE1+kE22+2cE1+1+cE2+1ETRefer to Table5Our DP-ABE (CP mode)3+2dE1+1+dE21+4lE1+1+lE2+1ETOur DP-ABE (DP mode)3+4k+2dE1+1+k+dE21+2c+4lE1+1+c+lE2+1ETOur FO-DP-ABE (outsourced)3+4k+2dE1+1+k+dE22+2c+4lE1+1+c+lE2+1ET3I+3JE1+3+2I+2JPOur FO-DP-ABE (local)01E11E2+3ETTable 5
Computation cost comparison of decryption in our DP-ABE.
SKCTKP-ABE modeCP-ABE modeDP-ABE modeKP-ABE mode3IE1+1+2IPIE1+IE2+2P3IE1+1+2IPCP-ABE mode2P3JE1+2+2JP3JE1+2+2JPDP-ABE mode3IE1+3+2IPI+3JE1+IE2+4+2JP3I+3JE1+3+2I+2JPComparison of Communication Cost. Tables6 and 7 show the communication cost in each algorithm. In Refs. [6, 15] and our DP-ABE, the communication cost of each algorithm is linearly with the complexity of attribute set and/or access policy. While, in our FO-DP-ABE, the online communication costs of KeyGen.pkg and Encrypt.owner are almost the same as those in our DP-ABE in dual-policy mode, except that in the former several elements are transmitted for the correction of secret keys and ciphertexts. The online communication cost of Decrypt.user is reduced to constant, i.e., only one element in G2 and three elements in GT.Table 6
Communication cost comparison.
SchemesKey generationEncryptionDecryptionDP-ABE [6]k+dG1+1+kG2c+lG1+1G2+1GTc+lG1+1G2+1GTDP-ABE [15]1+k+dG1+1+k+dG2c+2lG1+1+lG2+1GTc+2lG1+1+lG2+1GTOur DP-ABE (KP mode)2kG1+kG21+cG1+1+cG2+1GTRefer to Table7Our DP-ABE (CP mode)1+dG1+1+dG21+2lG1+1+lG2+1GTOur DP-ABE (DP mode)1+2k+dG1+1+k+dG2c+2lG1+1+c+lG2+1GTOur FO-DP-ABE (offline)2+3k+2dℤp+2+2k+dG1+1+k+dG23+2c+3lℤp+1+c+2lG1+2+c+lG2+GT0Our FO-DP-ABE (online)2+2k+dℤp+1+2k+dG1+1+k+dG23+c+2lℤp+1+c+2lG1+2+c+lG2+2GT1G2+3GTTable 7
Communication cost comparison of decryption in our DP-ABE.
SKCTKP-ABE modeCP-ABE modeDP-ABE modeKP-ABE modeI‖G1+1+IG2+1GT1G1+1G2+1GTI‖G1+1+|I|G2+1GTCP-ABE mode1G1+1|G2+1GT2J‖G1+1+JG2+1GT2J‖G1+1+|J|G2+1GTDP-ABE mode1+IG1+1+IG2+1GT1+2JG1+1+JG21GTI+2JG1+1+I+JG2+1GT


### 6.2. Experimental Analysis

We choose the BN254 elliptic curve in theCharm [33] to evaluate the performance of DP-ABE and FO-DP-ABE. We use a MacBook Pro laptop with an Intel i5 CPU @2.3 GHz and 8 GB RAM running Python 3.7.4.Experiment Setting. (1) In DP-ABE in single-policy modes, the overheads are linear with only one value (i.e., the number of attributes in objective/subjective access policy or objective/subjective attribute set). We use access policies of type A1andA2and…andAt and attribute sets of type A1,A2,…,At, with t increasing from 5 to 100. (2) In DP-ABE in dual-policy mode and FO-DP-ABE, the overheads are related to two values. We use the above access policies and attribute sets for subjective (resp. objective) attributes, with the sizes of access policies and attribute sets for objective (resp. subjective) attributes fixed to 5 or 100, to simulate the minimum or maximum overhead. (3) The test data to be encrypted is an element in GT. Access policies are converted into LSSS by Ref. [38]. Instances are independent to each other, and are repeated 20 times for accuracy.Execution Time. As depicted in Figures3(a)–3(j), we show the execution time of each algorithm. (1) In Figures 3(a)–3(c), the time of KeyGen in single-policy modes is about 43–925 ms, about a half of that in the dual-policy mode. Since cloud servers take the vast majority of key generation, the time of KeyGen.out in FO-DP-ABE is almost the same as the time of KeyGen in DP-ABE in dual-policy mode, which is about 84–1731 ms. The computation of the PKG is reduced to constant, which always takes less than 50 ms to execute KeyGen.pkg. (2) Similarly, in Figures 3(d)–3(f), the time of Encrypt in single-policy modes is about 59–947 ms, about a half of that in the dual-policy mode. Since cloud servers take the vast majority of encryption, the time of Encrypt.out in FO-DP-ABE is almost the same as the time of Encrypt in DP-ABE in dual-policy mode, which is about 101–1730 ms. The computation of the data owner is reduced to constant, which always takes less than 75 ms to execute Encrypt.owner. (3) In Figures 3(g) and 3(h), the time of Decrypt in single-policy modes is constant in two cases (KP-CT with CP-SK, CP-CT with KP-SK), about 144 ms. In other cases, the time is 795–14456 ms. (4) In Figures 3(i) and 3(j), since the cloud server 1 takes the vast majority of decryption, the time of Decrypt.out in FO-DP-ABE is almost the same as the time of Decrypt in DP-ABE in dual-policy mode, which is about 795–28894 ms. The computation of the data user is reduced to constant, which always takes less than 80 ms to execute the Decrypt.user.Figure 3
Experimental results.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)Transfer Size. Figures3(k)–3(t) illustrate the transfer size of each algorithm. (1) In Figures 3(k)–3(m), the sizes of SK in single-policy modes are 372–8300 bytes, about a half of those in the dual-policy mode. The sizes of IK and SK in FO-DP-ABE are larger than the sizes of SK in DP-ABE in dual-policy mode, since the former contains correction factors. (2) Similarly, in Figures 3(n)–3(p), the sizes of CT in single-policy modes are 612–8602 bytes, about a half of those in the dual-policy mode. The sizes of IT and CT in FO-DP-ABE are larger than the sizes of CT in DP-ABE in the dual-policy mode, since the former contains correction factors. (3) In Figures 3(q) and 3(r), in single-policy modes during decryption, the sizes of CT are always G1+G2+GT, 302 bytes in two cases (KP-CT with CP-SK, CP-CT with KP-SK). In other cases the sizes are 591–8602 bytes. (4) In Figures 3(s) and 3(t), in DP-ABE in the dual-policy mode, the sizes of CT during decryption are exactly the same as those during encryption. In FO-DP-ABE, the sizes of TCT are always G2+3GT, 761 bytes.E1,E2,ET,P denote a modular exponentiation in G1,G2,GT and a pairing computation, respectively. k,d,c,l indicate the number of attributes in Akp,Scp,Skp,Acp, respectively. In decryption, I and J indicate the number of objective and subjective attributes, respectively.ℤp,G1,G2,GT denote the size of an element in ℤp,G1,G2,GT, respectively. Also, refer to the acronyms of Table 4. We omit the communication overheads of access structures.


## 6.1. Theoretical Analysis

We compare the computation and communication costs in our DP-ABE, FO-DP-ABE and those in related work [6, 15].Comparison of Computation Cost. Tables4 and 5 compare the number of modular exponentiations and pairing operations in each algorithm. In Refs. [6, 15] and our DP-ABE, the computation cost of each algorithm grows linearly with the complexity of attribute set and/or access policy. Our FO-DP-ABE outsources almost all expensive computation to cloud servers, leaving constant operations for the PKG, data owners, and users. In particular, the data owner executes one modular exponentiation in G1 to generate a one-time signature; the data user executes one modular exponentiation in GT to decrypt TCT, and one modular exponentiation in G2 and two modular exponentiations in GT to verify TCT. The signature generation and ciphertext verification are necessary to realize CCA security.Table 4
Computation cost comparison.
SchemesKey generationEncryptionDecryptionDP-ABE [6]2k+dE1+1+kE2c+2lE1+1E2+1ET2I+2JE1+2+IPDP-ABE [15]3+2k+2dE1+1+k+dE2c+4lE1+1+lE2+1ET2I+3JE1+3+I+2JPOur DP-ABE (KP mode)4kE1+kE22+2cE1+1+cE2+1ETRefer to Table5Our DP-ABE (CP mode)3+2dE1+1+dE21+4lE1+1+lE2+1ETOur DP-ABE (DP mode)3+4k+2dE1+1+k+dE21+2c+4lE1+1+c+lE2+1ETOur FO-DP-ABE (outsourced)3+4k+2dE1+1+k+dE22+2c+4lE1+1+c+lE2+1ET3I+3JE1+3+2I+2JPOur FO-DP-ABE (local)01E11E2+3ETTable 5
Computation cost comparison of decryption in our DP-ABE.
SKCTKP-ABE modeCP-ABE modeDP-ABE modeKP-ABE mode3IE1+1+2IPIE1+IE2+2P3IE1+1+2IPCP-ABE mode2P3JE1+2+2JP3JE1+2+2JPDP-ABE mode3IE1+3+2IPI+3JE1+IE2+4+2JP3I+3JE1+3+2I+2JPComparison of Communication Cost. Tables6 and 7 show the communication cost in each algorithm. In Refs. [6, 15] and our DP-ABE, the communication cost of each algorithm is linearly with the complexity of attribute set and/or access policy. While, in our FO-DP-ABE, the online communication costs of KeyGen.pkg and Encrypt.owner are almost the same as those in our DP-ABE in dual-policy mode, except that in the former several elements are transmitted for the correction of secret keys and ciphertexts. The online communication cost of Decrypt.user is reduced to constant, i.e., only one element in G2 and three elements in GT.Table 6
Communication cost comparison.
SchemesKey generationEncryptionDecryptionDP-ABE [6]k+dG1+1+kG2c+lG1+1G2+1GTc+lG1+1G2+1GTDP-ABE [15]1+k+dG1+1+k+dG2c+2lG1+1+lG2+1GTc+2lG1+1+lG2+1GTOur DP-ABE (KP mode)2kG1+kG21+cG1+1+cG2+1GTRefer to Table7Our DP-ABE (CP mode)1+dG1+1+dG21+2lG1+1+lG2+1GTOur DP-ABE (DP mode)1+2k+dG1+1+k+dG2c+2lG1+1+c+lG2+1GTOur FO-DP-ABE (offline)2+3k+2dℤp+2+2k+dG1+1+k+dG23+2c+3lℤp+1+c+2lG1+2+c+lG2+GT0Our FO-DP-ABE (online)2+2k+dℤp+1+2k+dG1+1+k+dG23+c+2lℤp+1+c+2lG1+2+c+lG2+2GT1G2+3GTTable 7
Communication cost comparison of decryption in our DP-ABE.
SKCTKP-ABE modeCP-ABE modeDP-ABE modeKP-ABE modeI‖G1+1+IG2+1GT1G1+1G2+1GTI‖G1+1+|I|G2+1GTCP-ABE mode1G1+1|G2+1GT2J‖G1+1+JG2+1GT2J‖G1+1+|J|G2+1GTDP-ABE mode1+IG1+1+IG2+1GT1+2JG1+1+JG21GTI+2JG1+1+I+JG2+1GT


## 6.2. Experimental Analysis

We choose the BN254 elliptic curve in theCharm [33] to evaluate the performance of DP-ABE and FO-DP-ABE. We use a MacBook Pro laptop with an Intel i5 CPU @2.3 GHz and 8 GB RAM running Python 3.7.4.Experiment Setting. (1) In DP-ABE in single-policy modes, the overheads are linear with only one value (i.e., the number of attributes in objective/subjective access policy or objective/subjective attribute set). We use access policies of type A1andA2and…andAt and attribute sets of type A1,A2,…,At, with t increasing from 5 to 100. (2) In DP-ABE in dual-policy mode and FO-DP-ABE, the overheads are related to two values. We use the above access policies and attribute sets for subjective (resp. objective) attributes, with the sizes of access policies and attribute sets for objective (resp. subjective) attributes fixed to 5 or 100, to simulate the minimum or maximum overhead. (3) The test data to be encrypted is an element in GT. Access policies are converted into LSSS by Ref. [38]. Instances are independent to each other, and are repeated 20 times for accuracy.Execution Time. As depicted in Figures3(a)–3(j), we show the execution time of each algorithm. (1) In Figures 3(a)–3(c), the time of KeyGen in single-policy modes is about 43–925 ms, about a half of that in the dual-policy mode. Since cloud servers take the vast majority of key generation, the time of KeyGen.out in FO-DP-ABE is almost the same as the time of KeyGen in DP-ABE in dual-policy mode, which is about 84–1731 ms. The computation of the PKG is reduced to constant, which always takes less than 50 ms to execute KeyGen.pkg. (2) Similarly, in Figures 3(d)–3(f), the time of Encrypt in single-policy modes is about 59–947 ms, about a half of that in the dual-policy mode. Since cloud servers take the vast majority of encryption, the time of Encrypt.out in FO-DP-ABE is almost the same as the time of Encrypt in DP-ABE in dual-policy mode, which is about 101–1730 ms. The computation of the data owner is reduced to constant, which always takes less than 75 ms to execute Encrypt.owner. (3) In Figures 3(g) and 3(h), the time of Decrypt in single-policy modes is constant in two cases (KP-CT with CP-SK, CP-CT with KP-SK), about 144 ms. In other cases, the time is 795–14456 ms. (4) In Figures 3(i) and 3(j), since the cloud server 1 takes the vast majority of decryption, the time of Decrypt.out in FO-DP-ABE is almost the same as the time of Decrypt in DP-ABE in dual-policy mode, which is about 795–28894 ms. The computation of the data user is reduced to constant, which always takes less than 80 ms to execute the Decrypt.user.Figure 3
Experimental results.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)(p)(q)(r)(s)(t)Transfer Size. Figures3(k)–3(t) illustrate the transfer size of each algorithm. (1) In Figures 3(k)–3(m), the sizes of SK in single-policy modes are 372–8300 bytes, about a half of those in the dual-policy mode. The sizes of IK and SK in FO-DP-ABE are larger than the sizes of SK in DP-ABE in dual-policy mode, since the former contains correction factors. (2) Similarly, in Figures 3(n)–3(p), the sizes of CT in single-policy modes are 612–8602 bytes, about a half of those in the dual-policy mode. The sizes of IT and CT in FO-DP-ABE are larger than the sizes of CT in DP-ABE in the dual-policy mode, since the former contains correction factors. (3) In Figures 3(q) and 3(r), in single-policy modes during decryption, the sizes of CT are always G1+G2+GT, 302 bytes in two cases (KP-CT with CP-SK, CP-CT with KP-SK). In other cases the sizes are 591–8602 bytes. (4) In Figures 3(s) and 3(t), in DP-ABE in the dual-policy mode, the sizes of CT during decryption are exactly the same as those during encryption. In FO-DP-ABE, the sizes of TCT are always G2+3GT, 761 bytes.E1,E2,ET,P denote a modular exponentiation in G1,G2,GT and a pairing computation, respectively. k,d,c,l indicate the number of attributes in Akp,Scp,Skp,Acp, respectively. In decryption, I and J indicate the number of objective and subjective attributes, respectively.ℤp,G1,G2,GT denote the size of an element in ℤp,G1,G2,GT, respectively. Also, refer to the acronyms of Table 4. We omit the communication overheads of access structures.


## 7. Conclusion

In this work, we resisted dual-policy attribute-based encryption (DP-ABE) for secure data sharing in the cloud. In particular, we propose two monotone LSSS-realizable large-universe DP-ABE schemes based on prime-order asymmetric pairing groups. The first one is a basic CPA-secure scheme, based on which we demonstrate the two enhanced-flexible access control features, namely, encryption and key generation in single-policy modes. The second one realizes fully outsourced computation and CCA security, which is more efficient and secure for practical deployments. The experimental results show the efficiency of our schemes.



---

*Source: 1867584-2022-05-20.xml*