# Efficient Ciphertext-Policy Attribute-Based Encryption Constructions with Outsourced Encryption and Decryption

Authors: Hassan El Gafif; Ahmed Toumanari
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The invention of the Ciphertext-Policy Attribute-Based Encryption scheme opened a new perspective for realizing attribute-based access control systems without being forced to trust the storage service provider, which is the case in traditional systems where data are sent to the storage service provider in clear and the storage service provider is the party that controls the access to these data. In the Ciphertext-Policy Attribute-Based Encryption model, the data owner encrypts data using an attribute-based access structure before sending them to the storage service, and only users with authorized sets of attributes can successfully decrypt the generated ciphertext. However, Ciphertext-Policy Attribute-Based Encryption schemes employ expensive operations (i.e., bilinear pairings and modular exponentiations) and generate long ciphertexts and secret keys, which makes them hard to implement in real-life applications especially for resource-constrained devices. In this paper, we propose two Ciphertext-Policy Attribute-Based Encryption Key Encapsulation Mechanisms that can be provided as services in the cloud, minimizing the user’s encryption and decryption costs without exposing any sensitive information to the public cloud provider. In the first scheme, the ABE Service Provider is considered fully untrusted. On the other hand, the second scheme requires the ABE Service Provider to be semi-trusted (Honest-but-Curious) and does not collude with illegitimate users. Both schemes are proved to be selectively CPA-secure in the random oracle. The theoretical and experimental performance results show that both our first and second schemes are more efficient than the reviewed outsourced CP-ABE schemes in terms of user-side computation, communication, and storage costs.


---

## Body

## 1. Introduction

In the past, businesses were suffering from the overheads of dealing with their IT infrastructure installation and management. Nowadays, they can easily minimize these costs by externalizing their activities to one of the existing cloud solutions and paying only the amount of resources they consumed. This new paradigm is beneficial for both users and cloud providers, and this is what makes cloud services continue to attract more enterprises and individual users, helping them to start or improve their businesses easily. Cloud Storage is one of the services offered by cloud providers to help companies and individuals store, manage, and share data efficiently. Nevertheless, when outsourcing data, data owners are also outsourcing the control over their data. Therefore, this creates data security and confidentiality challenges against a third party who comprised the cloud server to steal data or even against a curious cloud provider [1]. Hence, data owners should encrypt data before outsourcing them to make sure that only authorized users can decrypt and gain access to the data.Cryptosystems in traditional public cryptography are one-to-one ciphers, meaning that the data owner should retrieve the public key of all the authorized users and encrypt a copy of his data for each user with the corresponding public key. For example, if a data owner wants to share a document with 100 users, he must create 100 copies of the document, retrieve 100 public keys, and encrypt each copy with the public key of the corresponding user. Thus, this solution is not practical since it produces huge computation, storage, and communication overheads.In 2005, Sahai and Waters [2] proposed a Fuzzy Identity-Based Encryption (FIBE) scheme with a new model that is not based on users’ public keys or identities (as in Identity-Based Encryption schemes), but instead, their model is using attributes to encrypt data and to generate secret keys. In this model, a Trusted Authority (TA) generates users’ secret keys based on their sets of attributes, and data owners specify a set of attributes and a threshold (which is the minimum number of attributes in the encryption set of attributes that should exist in the user’s set of attributes) and encrypt data using this set of attributes and threshold. Only users with a number of attributes existing in the encryption set of attributes that is greater than the threshold will be able to decrypt the ciphertext using their secret keys.Later on, two main variants of FIBE were proposed. Goyal et al. proposed the Key-Policy Attribute-Based Encryption (KP-ABE) scheme [3] where the data owner encrypts data with a set of attributes and users’ secret keys are generated based on an access policy that is associated with them. Bethencourt et al. presented the Ciphertext-Policy Attribute-Based Encryption (CP-ABE) scheme [4] where the data owner encrypts data with an access policy and users’ secret keys are generated based on their sets of attributes.The computation overhead in ABE schemes is the most challenging part that makes them hard to be adopted in real-life applications. This is due to the number of expensive modular exponentiations and pairing operations that increases linearly with the size of the access policy.Many contributions were proposed to optimize this computation overhead. Some of these contributions used different techniques to minimize the number of these operations in the encryption and decryption phases [5, 6] or to split them into two phases: in the first phase, most of the expensive operations are performed offline before knowing the message, and the second phase rapidly assembles the ciphertext [7, 8]. Others replaced the expensive modular exponentiations and pairing operations with the lightweight elliptic curve additions and point-scalar multiplications [9–11]. However, these solutions are still hard to be implemented in the applications where devices are resource-constrained such as the Internet of Things (IoT) and Wireless Sensor Networks (WSN). Computation outsourcing is another direction that achieved better results. In this solution, a big part of the encryption and decryption computation is outsourced to the cloud without revealing any sensitive information to the cloud providers that can help them reveal the plaintexts.


### 1.1. Our Contribution

Based on [4], we propose two CP-ABE with Outsourced Encryption and Decryption (CP-ABE-OED) Key Encapsulation Mechanisms (KEM) where the public ABE Service Provider performs all the encryption and decryption expensive operations leaving only one modular exponentiation and simple multiplications to be executed by the user when encrypting or decrypting data. The first scheme is suitable for the applications that consider the cloud service provider untrusted. On the other hand, the second scheme requires that the ABE Service Provider is a semi-trusted party that cannot collude with unauthorized users. Both schemes achieve provable CPA-security selectively in the random oracle.


### 1.2. Organization

The rest of our paper will be organized as follows. In Section2, we will discuss the related work. Next, we define the preliminaries in Section 3. Later on, we present our 1st and 2nd CP-ABE-OED KEMs and their security analysis in Section 4. Section 5 is dedicated to showing and analysing the performance results. Finally, we conclude our paper in Section 6.


## 1.1. Our Contribution

Based on [4], we propose two CP-ABE with Outsourced Encryption and Decryption (CP-ABE-OED) Key Encapsulation Mechanisms (KEM) where the public ABE Service Provider performs all the encryption and decryption expensive operations leaving only one modular exponentiation and simple multiplications to be executed by the user when encrypting or decrypting data. The first scheme is suitable for the applications that consider the cloud service provider untrusted. On the other hand, the second scheme requires that the ABE Service Provider is a semi-trusted party that cannot collude with unauthorized users. Both schemes achieve provable CPA-security selectively in the random oracle.


## 1.2. Organization

The rest of our paper will be organized as follows. In Section2, we will discuss the related work. Next, we define the preliminaries in Section 3. Later on, we present our 1st and 2nd CP-ABE-OED KEMs and their security analysis in Section 4. Section 5 is dedicated to showing and analysing the performance results. Finally, we conclude our paper in Section 6.


## 2. Related Work

In 2011, Green et al. [12] proposed the first outsourced CP-ABE scheme, which is selectively CPA-secure. They outsourced a big part of the expensive decryption operations in Waters’s large universe construction [13] to a decryption proxy (e.g., Cloud Server), leaving only one modular exponentiation to be executed by the user. In the registration phase, the Trusted Authority (TA) generates a public transformation key TK and a secret decryption key z for each user. To decrypt a ciphertext CT, the user sends his TK to the decryption proxy which transforms CT to a short ElGamal-style [14] ciphertext. Then, using the decryption key z, the user decrypts the transformed ciphertext. To decrypt an ABE ciphertext containing 100 attributes, it takes nearly 30 seconds of sustained computation on a 412 MHz ARM-based iPhone 3G with 128 MB of RAM using the original CP-ABE scheme [13], while it requires only 60 milliseconds using Green et al.‘s scheme [12]. Besides, thousands of lines of code, dedicated to determining how a key satisfies the access policy, were removed from the user’s side. For instance, in libfenc [15], about 3000 lines are dedicated to access policy handling, excluding dependencies. An improved scheme is also provided in [12] that is selectively secure in the Replayable Chosen-Ciphertext Attack (RCCA) security model using Fujisaki and Okamoto techniques [16].Afterward, many contributions added the notion of verifiability (i.e., the ability to verify the correctness of the transformation performed by a proxy) to the mechanism of decryption outsourcing [17–21]. In 2016, Mao et al. [21] proposed a generic construction that transforms any (selectively) CPA-secure ABE scheme with outsourced decryption (e.g., Green et al. [12]) into a (selectively) CPA-secure ABE scheme with verifiable outsourced decryption. In contrast with [17] that separately encrypts an extra random message (which is used to commit to the true message), [21] is encrypting the true message and a random message together. It then commits the random value to the message using a commitment scheme that satisfies the hiding and binding properties (at least computationally). In the decryption phase, the user receives the partially decrypted ciphertext from the decryption proxy and the commitment from the storage server and runs the revealing algorithm of the commitment scheme to verify the correctness of the transformation. The authors showed that the instantiation of this construction in the standard model using Green et al.‘s small-universe, backward-compatible, and selectively CPA-secure CP-ABE scheme with outsourced decryption [12] and Pedersen Commitment [22] as the underlying commitment scheme is more efficient than Lai et al.‘s scheme [17]. They also proposed a second generic construction to transform any (selectively) CPA-secure ABE scheme with outsourced decryption, that has ciphertext verifiability (i.e., the possibility to verify whether a normal ciphertext will be recovered into the same plaintext under two different decryption keys with two specific attributes) or delegatability (i.e., the capability to use a key to derive another inferior key), into a (selectively) RCCA-secure ABE scheme with verifiable outsourced decryption. They claimed that this is the first RCCA-secure construction that does not rely on a random oracle. In this construction, they combined a secure encapsulation scheme, a strong one-time message authentication code, and a secure commitment scheme.Obviously, the previous schemes are not suitable for IoT applications where lightweight devices encrypt data and not only decrypt them (e.g., Wireless Sensor Networks) because the encryption cost produced in these schemes is still high. Accordingly, outsourcing the encryption operations in addition to the decryption operations became a new direction [23–27].Based on [4], Zhou et al. proposed a CP-ABE scheme with outsourced encryption and decryption [23]. They outsourced a big part of the encryption operations by subdividing the access policy T into two parts: TDO (data owner’s access tree) and TESP (Encryption Service Provider’s access tree) such that T=TESPANDTDO. The data owner generates a random number s∈Zp and a random 1-degree polynomial qRx, where qR0=s, qR1=s1 and qR2=s2 and computes ℂ=M.eg,gα.s and C=gβ.s. Then, he generates the ciphertext components Cy and Cy′ for his sub-tree TDO in the same way as CP-ABE [4] using s2 as the shared key and sends ℂ,C,Cy,Cy′y∈YDO,TDO,TESP,s1 to the Encryption Service Provider (ESP). Similarly, ESP computes the ciphertext components Cy and Cy′ for TESP using s1 as the shared key. The final ciphertext is CT=T=TESP∧TDO,ℂ,C,Cy,Cy′y∈YESP∪YDO. The decryption outsourcing is achieved using almost the same key-blinding technique of Green et al. [12]. However, an untrusted ESP can reveal the encrypted data by colluding with unauthorized users with sets of attributes that satisfy TDO. Therefore, this solution is suitable only for applications where the ESP is at least semi-trusted.In 2014, Asim et al. [25] proposed a new CP-ABE scheme where they outsourced a part of the encryption operations to a semi-trusted proxy A and they outsourced the decryption phase to a semi-trusted proxy B following the same technique employed in [12]. Using an encryption secret key generated by the Trusted Authority, the proxy A computes gs^ and uses it as the access policy root’s secret to generate the access policy’s leaf nodes’ components gs^j. Afterward, it multiplies each leaf node’s component with the corresponding attribute component Cj˜=H1aj−s in the partially encrypted ciphertext received from the host. The authors claim that their construction is secure in the generic group model under the assumption that proxy A and proxy B will not collude with unauthorized users and will not collude with each other. However, unauthorized users with at least one attribute (ax) that exists in the access policy can reveal the plaintext using the partially encrypted ciphertext CT˜ and the ciphertext generated by proxy A CT. For each leaf node j of the access policy, the attacker retrieves Cj˜=H1aj−s from CT˜ and Cj=gs^j⋅H1aj−s from CT and computes gs^j=Cj/Cj˜. Then, he executes PolicyGeneration function backward to retrieve gs^ and computes As=eC⌣,D1/egs^⋅H1ax−s,D2⋅eC⌣,Dx3z. Finally, the attacker reveals the plaintext M=C⊕H2As. In addition, their scheme is not correct (i.e., given an SK of a set of attributes S that satisfies the access policy τ, DecEncM,τ,SK≠M). In the PolicyGeneration phase, they used gs^ (instead of s^) as the shared key to get the shares gs^j. However, in the decryption phase they used the polynomial interpolation on s^j, which will result in a value that is different than gs^ and, as a result, the decryption output will be different than M.Subsequently, Zhang et al. [26] presented a fully outsourced CP-ABE scheme that, for the first time, achieves outsourced key generation, encryption, and decryption simultaneously. In their system, two Key Generation Service Providers (KGSP1, KGSP2) help TA to generate Intermediate Secret Keys (ISKs), and two Encryption Service Providers (ESP1, ESP2) help users to generate Intermediate Ciphertexts (ITs). Decryption outsourcing is achieved using the same key blinding used in Green et al.‘s scheme [12]. The extra communication costs that had arisen from outsourced key generation and encryption are offline, meaning that TA and users can communicate with the cloud servers in their spare time. The system is proved to be secure under the assumption that two KGSPs (ESPs) do not collude with each other, so the final combined ISK (IT) should be information-theoretically hidden from two servers. It is selectively CPA-secure against corrupt users colluding with KGSP1, ESP1, and SSP and corrupt users colluding with KGSP2, ESP2, and SSP who can obtain the conversion key at Decryption Service Provider.Other contributions proposed outsourced CP-ABE schemes using trusted parties such as fog nodes [28] or a trusted private cloud provider [29].


## 3. Preliminaries

### 3.1. Bilinear Maps [4]

LetG and GT be two multiplicative cyclic groups of prime order p. Let g be a generator of G and e be a bilinear map, e:G×G⟶GT, that has the following properties:(i)
Bilinearity: for allu,v∈G and a,b∈Zp, we have eua,vb=eu,va.b(ii)
Non-degeneracy:eg,g≠1We sayG is a bilinear group if the group operation in G and the bilinear map e:G×G⟶GT are both efficiently computable.


### 3.2. Access Structure [30]

LetP1,P2,…,Pn be a set of parties. A collection A⊆2P1,P2,…,Pn is monotone if ∀B,C:ifB∈AandB⊆CthenC∈A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of non-empty subsets of P1,P2,…,Pn; i.e., A⊆2P1,P2,…,Pn∖∅. The sets in A are called the authorized sets, and the sets not in A are called the unauthorized sets.In our context, we will use a monotone access structure where the attributes play the role of the parties, which means that the access structureA will contain the authorized sets of attributes.


### 3.3. Linear Secret Sharing Scheme (LSSS) [13]

A secret-sharing schemeΠ over a set of parties P is called linear (over Zp) if the following is satisfied:(i)
The shares for each party form a vector overZp.(ii)
There exists a matrixM with l rows and n columns called the share-generating matrix for Π. For all i=1,…,l, the i’th row of M, we let the function ρ define the party labeling row i as ρi. When we consider the column vector v=s,r2,…,rn, where s∈Zp is the secret to be shared, and r2,…,rn∈Zp are randomly chosen; then M.v is the vector of l shares of the secret s according to Π. The share M.vi belongs to party ρi.It is shown in [30] that every linear secret sharing-scheme according to the above definition also enjoys the linear reconstruction property, defined as follows: suppose that Π is an LSSS for the access structure A. Let S∈A be any authorized set, and let I⊂1,…,l be defined as I=i:ρi∈S. Then, there exist constants wi∈Zpi∈I such that, if λi are valid shares of any secret s according to Π, then ∑i∈Iwi.λi=s.Furthermore, it is shown in [30] that these constants wi can be found in time polynomial in the size of the share-generating matrix M.We note that we use the convention that vector1,0,0,…,0 is the “target” vector for any linear secret sharing scheme. For any satisfying set of rows I in M, we will have that the target vector is in the span of I. For any unauthorized set of rows I, the target vector is not in the span of the rows of the set I. Moreover, there will exist a column vector w such that 1,0,0…,0⋅w=−1 and Mi⋅w=0 for all i∈I.Using standard techniques [30], one can convert any monotonic Boolean formula into an LSSS representation. An access tree of l nodes will result in an LSSS matrix of l rows. We refer the reader to the appendix of [31] for a discussion of how to perform this conversion.


### 3.4. CPA-Security Game

(i)
Setup. The challenger runs the Setup algorithm and gives the public parameters PK to the adversary.(ii)
Phase 1. When the adversary A queries the decryption key and the transformation key on S, the challenger passes S on to the key generation oracle to get the corresponding decryption key and transformation key and then returns the result to A.(iii)
Challenge. The adversary A submits the access structure M∗,ρ∗ (which is not satisfied by any of the sets of attributes S passed in phase 1) to be challenged on and requests the challenge Key∗. The challenger flips a random coin b∈0,1. If b=0, it returns CT∗ to A, where the first element in CT∗ is a random Key∗. If b=1, it returns CT∗ to A, where the first element in CT∗ is a well-constructed Key∗.(iv)
Phase 2. Phase 1 is repeated with the restriction that the adversary cannot obtain a decryption key for a set of attributes that satisfies M∗,ρ∗.(v)
Guess. The adversary outputs 0 if Key∗ is random and 1 if Key∗ is a well-constructed key.


## 3.1. Bilinear Maps [4]

LetG and GT be two multiplicative cyclic groups of prime order p. Let g be a generator of G and e be a bilinear map, e:G×G⟶GT, that has the following properties:(i)
Bilinearity: for allu,v∈G and a,b∈Zp, we have eua,vb=eu,va.b(ii)
Non-degeneracy:eg,g≠1We sayG is a bilinear group if the group operation in G and the bilinear map e:G×G⟶GT are both efficiently computable.


## 3.2. Access Structure [30]

LetP1,P2,…,Pn be a set of parties. A collection A⊆2P1,P2,…,Pn is monotone if ∀B,C:ifB∈AandB⊆CthenC∈A. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) A of non-empty subsets of P1,P2,…,Pn; i.e., A⊆2P1,P2,…,Pn∖∅. The sets in A are called the authorized sets, and the sets not in A are called the unauthorized sets.In our context, we will use a monotone access structure where the attributes play the role of the parties, which means that the access structureA will contain the authorized sets of attributes.


## 3.3. Linear Secret Sharing Scheme (LSSS) [13]

A secret-sharing schemeΠ over a set of parties P is called linear (over Zp) if the following is satisfied:(i)
The shares for each party form a vector overZp.(ii)
There exists a matrixM with l rows and n columns called the share-generating matrix for Π. For all i=1,…,l, the i’th row of M, we let the function ρ define the party labeling row i as ρi. When we consider the column vector v=s,r2,…,rn, where s∈Zp is the secret to be shared, and r2,…,rn∈Zp are randomly chosen; then M.v is the vector of l shares of the secret s according to Π. The share M.vi belongs to party ρi.It is shown in [30] that every linear secret sharing-scheme according to the above definition also enjoys the linear reconstruction property, defined as follows: suppose that Π is an LSSS for the access structure A. Let S∈A be any authorized set, and let I⊂1,…,l be defined as I=i:ρi∈S. Then, there exist constants wi∈Zpi∈I such that, if λi are valid shares of any secret s according to Π, then ∑i∈Iwi.λi=s.Furthermore, it is shown in [30] that these constants wi can be found in time polynomial in the size of the share-generating matrix M.We note that we use the convention that vector1,0,0,…,0 is the “target” vector for any linear secret sharing scheme. For any satisfying set of rows I in M, we will have that the target vector is in the span of I. For any unauthorized set of rows I, the target vector is not in the span of the rows of the set I. Moreover, there will exist a column vector w such that 1,0,0…,0⋅w=−1 and Mi⋅w=0 for all i∈I.Using standard techniques [30], one can convert any monotonic Boolean formula into an LSSS representation. An access tree of l nodes will result in an LSSS matrix of l rows. We refer the reader to the appendix of [31] for a discussion of how to perform this conversion.


## 3.4. CPA-Security Game

(i)
Setup. The challenger runs the Setup algorithm and gives the public parameters PK to the adversary.(ii)
Phase 1. When the adversary A queries the decryption key and the transformation key on S, the challenger passes S on to the key generation oracle to get the corresponding decryption key and transformation key and then returns the result to A.(iii)
Challenge. The adversary A submits the access structure M∗,ρ∗ (which is not satisfied by any of the sets of attributes S passed in phase 1) to be challenged on and requests the challenge Key∗. The challenger flips a random coin b∈0,1. If b=0, it returns CT∗ to A, where the first element in CT∗ is a random Key∗. If b=1, it returns CT∗ to A, where the first element in CT∗ is a well-constructed Key∗.(iv)
Phase 2. Phase 1 is repeated with the restriction that the adversary cannot obtain a decryption key for a set of attributes that satisfies M∗,ρ∗.(v)
Guess. The adversary outputs 0 if Key∗ is random and 1 if Key∗ is a well-constructed key.


## 4. Our Proposed Constructions

### 4.1. The 1st Proposed CP-ABE-OED Key Encapsulation Mechanism

In this scheme, the ABE Service Provider is considered to be an untrusted party.


#### 4.1.1. The Construction

(1)Setup Phase. In this phase, we execute the function setupλ that takes as input a security parameter λ, which determines the size of the groups. setupλ chooses a bilinear group G of prime order p with a generator g and a bilinear map e:G×G⟶GT.It also defines a hash functionH1:0,1∗⟶G mapping each attribute (described as a binary string) to a random group element, and a hash function H2:0,1∗⟶Zp.Afterward, it generates two random numbersα,β∈Zp. Then, it secretly stores the master key MK=gα,β and publishes the public parameters:(1)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ,eg,gα.(2)Registration and Key Generation Phase. In Figure 1, Alice and Bob represent two users. Bob plays the role of the data owner and Alice plays the role of the data receiver. In the registration phase, both Alice and Bob behave in the same way.Figure 1
Registration and key generation's sequence diagram.First, the Trusted Authority (TA) registers Alice and Bob and associates a set of attributes to each of them (SA for Alice and SB for Bob) and executes KeyGenU,MK,Si.KeyGenU,MK,Si is defined as follows:(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,u,1=g1/H2u∥siUPi,u,2=H1u1/H2u∥si∀u∈U.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β⋅zi∀j∈Si:Di,j=gri/zi⋅H1jri,j/ziDi,j′=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.TA sendsEKi,DKi securely to the user i and sends UPi,TKi publically to the ABE Service Provider.(3)Encryption Phase. As shown in Figure 2, the encryption phase consists of two steps. In the first step, Bob uses its encryption key EKB and an l×n LSSS access structure M,ρ and calls the function EncryptPK,EKB,M,ρ.EncryptPK,EKB,M,ρ is defined as follows:(i)
First, it generates a random column vectorv=s,y2,y3,…,yn∈Zpn to share the encryption exponent s.(ii)
For eachi∈1,2,…,l, it computes λi=Mi⋅v where Mi is the ith row of M.(iii)
Then, it generates(2)preCT=M,ρC=hs∀i∈1,2,…,l:Cipre=H2ρi∥sB.λi.(iv)
Finally, it outputspreCT.Figure 2
Encryption phase's sequence diagram.Afterward, Bob sendspreCT to the ABE Service Provider.In the second step, the ABE Service Provider executes the functionOutEncryptPK,UPB,preCT after receiving preCT.OutEncryptPK,UPB,preCT performs the following instructions:(i)
For eachi∈1,2,…,l, it computes(3)Ci=UPB,ρi,1Cipre=g1/H2ρi∥sBH2ρi∥sB.λi=gλi,Ci′=UPB,ρi,2Cipre=H1ρi1/H2ρi∥sBH2ρi∥sB.λi=H1ρiλi.(ii)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.Finally, the ABE Service Provider sendsCT to the Cloud Storage Provider (CSP).(4)Decryption Phase. First, as shown in Figure 3, Alice requests the transformed ciphertext transCT from the ABE Service Provider. The ABE Service Provider receives CT from the CSP and executes the function OutDecryptPK,CT,TKA.OutDecryptPK,CT,TKA is defined as follows:(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(4)A=∏i∈IeDA,i,CieDA,i′,Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλiegrA,i/zA,H1ρiλiwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA=∏i∈Ieg,grA.wi.λi/zA=eg,grA/zA⋅∑i∈Iwi.λi=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(5)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.Figure 3
Decryption phase’s sequence diagram.The ABE Service Provider sendstransCT to Alice.After receivingtransCT, Alice decrypts it using its decryption key DKA by calling the function DecryptPK,transCT,DKA.DecryptPK,transCT,DKA executes the following instructions:(i)
It computes(6)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s.(ii)
Then, it outputs theKey.


#### 4.1.2. Security Analysis

Before starting our security proof, we will create a modified version of Bethencourt et al.‘s CP-ABE scheme [4] and prove that it achieves the same security level of the original scheme in the random oracle. Then, we will prove that our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified version of Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle. Thus, our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle.We create the modified Bethencourt et al.‘s scheme by modifying the encryption phase as follows:(i)
Instead of using Shamir’s Secret Sharing Scheme to build the access policy, we use the LSSS access structureM,ρ in the same way as in our scheme and generate the shares λi.(ii)
We choose a random numbersB∈Zp and compute for each row i of M: ℛi=H2ρi||sB.λi (the hash function H2:0,1∗⟶Zp must be defined in the public parameters).(iii)
The generated ciphertext will be defined as follows:(7)M,ρ,C˜=M.eg,gα.shs,∀i=1,…,l:ℛi=H2ρi||sB.λiCi=gλi,Ci′=H1ρiλi.It is obvious that the modified Bethencourt et al.‘s scheme achieves the same security level as the original scheme in the random oracle. That is because if we considerH2ρi||sB random, then ℛi is random and the attacker cannot compute λi from ℛi without knowing H2ρi||sB. Therefore, an attacker cannot distinguish between the distributions H2ρi||sB.λi,gλi,H1ρiλi and r,gλi,H1ρiλi, where r∈Zp is a random number.Now, we prove the following theorem:Theorem 1.
Our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified Bethencourt et al. scheme is selectively CPA-secure in the random oracle.Suppose that we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack the modified Bethencourt et al. scheme in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends M∗,ρ∗ to the challenger.(2)Setup. The simulator ℬ obtains the public parameters from the challenger:(8)PK′=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,f=g1/β′,eg,gα′.The random oraclesH1⋅ and H2⋅ are programmed by the challenger.Then,ℬ sends the public parameters(9)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,eg,gα′,to the adversary A(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls the challenger’s key generation oracle on S to obtain the key(10)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(11)TK=SD=D′1/z∀j∈Si:Dj=Dj′1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(12)CT′=M∗,ρ∗,ℂ′=mπ.eg,gα′s′,C′=hs′,∀i=1,…,l:ℛi=H2ρi||sB.λi′,Ci′=gλi′,Ci'′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(13)UP∗=UPu,1=Ci′1/ℛiUPu,2=Ci′1/ℛi∀u∈U∩YUPu,1=g1/tuUPu,2=xu1/tu∀u∈U∖Y.where tu∈Zp and xu∈G are random numbers.Then,ℬ creates CT∗ as follows:(14)CT∗=M∗,ρ∗,C=C′,Cipre=ℛi,Finally, the simulator flips a coinb∈0,1 and computes Key∗=C'/mb and then sends CT∗, UP∗, and Key∗ to the adversary.(5)Phase 2. The simulator continues to answer queries as in Phase 1.(6)Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess that Key∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of the modified Bethencourt et al.‘s scheme with the same advantage.


### 4.2. The 2nd Proposed CP-ABE-OED Key Encapsulation Mechanism

#### 4.2.1. The Construction

In this scheme, we consider the ABE Service Provider semi-trusted, which means that it cannot collude with illegitimate users to reveal the plaintext.We will only describe the modified methods that are different from the previous scheme.(1)
KeyGenU,MK,Si(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,1=g1/si,∀u∈U:UPi,u,2=H1u1/si.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β.zi∀j∈Si:Di,j=gri/zi.H1jri,j/ziDi,j'=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.(2)
EncryptPK,EKB,M,ρ(i)
It picks a random numbers∈Zp and computes(15)preCT=M,ρ,C=hs,Cpre=sB.s.(ii)
Then, it outputspreCT.(3)
OutEncryptPK,UPB,preCT(i)
First, it chooses a random column vectorv=Cpre,y2,y3,…,yn∈Zpn.(ii)
For eachi∈1,2,…,l, it computes λi=Mi.v where Mi is the ith row of M.(iii)
Then, for eachi∈1,2,…,l, it computes(16)Ci=UPB,1λi=gλi/sBCi′=UPB,ρi,2λi=H1ρiλi/sB,.(iv)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.The decryption phase will perform in the same way as in the previous scheme; however, we will describe it here to show the correctness of our scheme.(4)
OutDecryptPK,CT,TKA.(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(17)A=∏i∈IeDA,i,CieDA,i',Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλi/sBegrA,i/zA,H1ρiλi/sBwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA.sB=∏i∈Ieg,grA.wi.λi/zA.sB=eg,grA/zA.sB.∑i∈Iwi.λi=eg,grA.sB.s/zA.sB=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(18)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.(5)
DecryptPK,transCT,DKA(i)
It computes(19)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s(ii)
Then, it outputs theKey.


#### 4.2.2. Security Analysis

In this security proof, we will consider two types of adversaries:(i)
Type-1 adversary: which refers to illegitimate users trying to break our scheme(ii)
Type-2 adversary: which refers to a curious ABE cloud provider trying to reveal sensitive informationFor the Type-1 adversary, our scheme is viewed as Bethencourt et al.‘s scheme [4] with outsourced decryption.Now, we prove the following theorem:Theorem 2.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries if Bethencourt et al.‘s scheme [4] is selectively CPA-secure in the random oracle.Suppose we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack Bethencourt et al.‘s scheme [4] in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends the challenge access structure to the challenger.(2)Setup. The simulator ℬ obtains Bethencourt et al.‘s [4] public parameters(20)PK'=G,g,e⋅,⋅,H1⋅,h=gβ′,f=g1/β′,eg,gα′.and forwards them to the adversaryA.(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls Bethencourt et al.‘s [4] key generation oracle on S to obtain the key(21)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(22)TK=SD=D′1/z∀j∈Si:Dj=Dj'1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(23)CT′=M∗,ρ∗,ℂ′=mπ.Key',C′=hs′,∀i=1,…,l:Ci′=gλi′,Ci′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(24)UP∗=UPu,1=g1/tuUPu,2=H1u1/tu∀u∈U.where tu∈Zp are random numbers.Later on, the simulator constructsCT∗ as follows:(25)CT∗=M∗,ρ∗,C∗=C′,∀i=1,…,l:Ci∗=Ci′,C′i∗=Ci'′.Finally, the simulator flips a coinb∈0,1 and computes Key∗=ℂ′/mb , then sends CT∗, UP∗, and Key∗ to the adversary.(5).Phase 2. The simulator continues to answer queries as in Phase 1.(6).Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess thatKey∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of Bethencourt et al.‘s scheme with the same advantage.The Type-2 adversary is not allowed to collude with unauthorized users. Thus, he can request only the transformation keys and not the decryption keys from the key generation oracle.Now, we prove the following theorem:Theorem 3.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-2 adversaries if our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries.It is obvious that Type-2 adversary cannot distinguish between two pre-ciphertextspreCT0∗ and preCT1∗ where(26)preCTb∗=M∗,ρ∗,Keyb∗,C∗=hs,Cpre∗=sB.s.and Keyb∗=eg,gα.s,b=0,eg,gR,b=1. where R∈Zp is a random number.That is becauseCpre∗ is random since sB is random, and the adversary cannot retrieve s without knowing sB. Thus, Type-2 adversary has no advantage over Type-1 adversary since the only additional information (Cpre∗=sB⋅s) he has compared to the Type-1 adversary is not useful. Hence, Theorem 3 is proved.


## 4.1. The 1st Proposed CP-ABE-OED Key Encapsulation Mechanism

In this scheme, the ABE Service Provider is considered to be an untrusted party.


### 4.1.1. The Construction

(1)Setup Phase. In this phase, we execute the function setupλ that takes as input a security parameter λ, which determines the size of the groups. setupλ chooses a bilinear group G of prime order p with a generator g and a bilinear map e:G×G⟶GT.It also defines a hash functionH1:0,1∗⟶G mapping each attribute (described as a binary string) to a random group element, and a hash function H2:0,1∗⟶Zp.Afterward, it generates two random numbersα,β∈Zp. Then, it secretly stores the master key MK=gα,β and publishes the public parameters:(1)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ,eg,gα.(2)Registration and Key Generation Phase. In Figure 1, Alice and Bob represent two users. Bob plays the role of the data owner and Alice plays the role of the data receiver. In the registration phase, both Alice and Bob behave in the same way.Figure 1
Registration and key generation's sequence diagram.First, the Trusted Authority (TA) registers Alice and Bob and associates a set of attributes to each of them (SA for Alice and SB for Bob) and executes KeyGenU,MK,Si.KeyGenU,MK,Si is defined as follows:(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,u,1=g1/H2u∥siUPi,u,2=H1u1/H2u∥si∀u∈U.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β⋅zi∀j∈Si:Di,j=gri/zi⋅H1jri,j/ziDi,j′=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.TA sendsEKi,DKi securely to the user i and sends UPi,TKi publically to the ABE Service Provider.(3)Encryption Phase. As shown in Figure 2, the encryption phase consists of two steps. In the first step, Bob uses its encryption key EKB and an l×n LSSS access structure M,ρ and calls the function EncryptPK,EKB,M,ρ.EncryptPK,EKB,M,ρ is defined as follows:(i)
First, it generates a random column vectorv=s,y2,y3,…,yn∈Zpn to share the encryption exponent s.(ii)
For eachi∈1,2,…,l, it computes λi=Mi⋅v where Mi is the ith row of M.(iii)
Then, it generates(2)preCT=M,ρC=hs∀i∈1,2,…,l:Cipre=H2ρi∥sB.λi.(iv)
Finally, it outputspreCT.Figure 2
Encryption phase's sequence diagram.Afterward, Bob sendspreCT to the ABE Service Provider.In the second step, the ABE Service Provider executes the functionOutEncryptPK,UPB,preCT after receiving preCT.OutEncryptPK,UPB,preCT performs the following instructions:(i)
For eachi∈1,2,…,l, it computes(3)Ci=UPB,ρi,1Cipre=g1/H2ρi∥sBH2ρi∥sB.λi=gλi,Ci′=UPB,ρi,2Cipre=H1ρi1/H2ρi∥sBH2ρi∥sB.λi=H1ρiλi.(ii)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.Finally, the ABE Service Provider sendsCT to the Cloud Storage Provider (CSP).(4)Decryption Phase. First, as shown in Figure 3, Alice requests the transformed ciphertext transCT from the ABE Service Provider. The ABE Service Provider receives CT from the CSP and executes the function OutDecryptPK,CT,TKA.OutDecryptPK,CT,TKA is defined as follows:(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(4)A=∏i∈IeDA,i,CieDA,i′,Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλiegrA,i/zA,H1ρiλiwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA=∏i∈Ieg,grA.wi.λi/zA=eg,grA/zA⋅∑i∈Iwi.λi=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(5)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.Figure 3
Decryption phase’s sequence diagram.The ABE Service Provider sendstransCT to Alice.After receivingtransCT, Alice decrypts it using its decryption key DKA by calling the function DecryptPK,transCT,DKA.DecryptPK,transCT,DKA executes the following instructions:(i)
It computes(6)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s.(ii)
Then, it outputs theKey.


### 4.1.2. Security Analysis

Before starting our security proof, we will create a modified version of Bethencourt et al.‘s CP-ABE scheme [4] and prove that it achieves the same security level of the original scheme in the random oracle. Then, we will prove that our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified version of Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle. Thus, our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle.We create the modified Bethencourt et al.‘s scheme by modifying the encryption phase as follows:(i)
Instead of using Shamir’s Secret Sharing Scheme to build the access policy, we use the LSSS access structureM,ρ in the same way as in our scheme and generate the shares λi.(ii)
We choose a random numbersB∈Zp and compute for each row i of M: ℛi=H2ρi||sB.λi (the hash function H2:0,1∗⟶Zp must be defined in the public parameters).(iii)
The generated ciphertext will be defined as follows:(7)M,ρ,C˜=M.eg,gα.shs,∀i=1,…,l:ℛi=H2ρi||sB.λiCi=gλi,Ci′=H1ρiλi.It is obvious that the modified Bethencourt et al.‘s scheme achieves the same security level as the original scheme in the random oracle. That is because if we considerH2ρi||sB random, then ℛi is random and the attacker cannot compute λi from ℛi without knowing H2ρi||sB. Therefore, an attacker cannot distinguish between the distributions H2ρi||sB.λi,gλi,H1ρiλi and r,gλi,H1ρiλi, where r∈Zp is a random number.Now, we prove the following theorem:Theorem 1.
Our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified Bethencourt et al. scheme is selectively CPA-secure in the random oracle.Suppose that we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack the modified Bethencourt et al. scheme in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends M∗,ρ∗ to the challenger.(2)Setup. The simulator ℬ obtains the public parameters from the challenger:(8)PK′=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,f=g1/β′,eg,gα′.The random oraclesH1⋅ and H2⋅ are programmed by the challenger.Then,ℬ sends the public parameters(9)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,eg,gα′,to the adversary A(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls the challenger’s key generation oracle on S to obtain the key(10)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(11)TK=SD=D′1/z∀j∈Si:Dj=Dj′1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(12)CT′=M∗,ρ∗,ℂ′=mπ.eg,gα′s′,C′=hs′,∀i=1,…,l:ℛi=H2ρi||sB.λi′,Ci′=gλi′,Ci'′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(13)UP∗=UPu,1=Ci′1/ℛiUPu,2=Ci′1/ℛi∀u∈U∩YUPu,1=g1/tuUPu,2=xu1/tu∀u∈U∖Y.where tu∈Zp and xu∈G are random numbers.Then,ℬ creates CT∗ as follows:(14)CT∗=M∗,ρ∗,C=C′,Cipre=ℛi,Finally, the simulator flips a coinb∈0,1 and computes Key∗=C'/mb and then sends CT∗, UP∗, and Key∗ to the adversary.(5)Phase 2. The simulator continues to answer queries as in Phase 1.(6)Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess that Key∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of the modified Bethencourt et al.‘s scheme with the same advantage.


## 4.1.1. The Construction

(1)Setup Phase. In this phase, we execute the function setupλ that takes as input a security parameter λ, which determines the size of the groups. setupλ chooses a bilinear group G of prime order p with a generator g and a bilinear map e:G×G⟶GT.It also defines a hash functionH1:0,1∗⟶G mapping each attribute (described as a binary string) to a random group element, and a hash function H2:0,1∗⟶Zp.Afterward, it generates two random numbersα,β∈Zp. Then, it secretly stores the master key MK=gα,β and publishes the public parameters:(1)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ,eg,gα.(2)Registration and Key Generation Phase. In Figure 1, Alice and Bob represent two users. Bob plays the role of the data owner and Alice plays the role of the data receiver. In the registration phase, both Alice and Bob behave in the same way.Figure 1
Registration and key generation's sequence diagram.First, the Trusted Authority (TA) registers Alice and Bob and associates a set of attributes to each of them (SA for Alice and SB for Bob) and executes KeyGenU,MK,Si.KeyGenU,MK,Si is defined as follows:(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,u,1=g1/H2u∥siUPi,u,2=H1u1/H2u∥si∀u∈U.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β⋅zi∀j∈Si:Di,j=gri/zi⋅H1jri,j/ziDi,j′=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.TA sendsEKi,DKi securely to the user i and sends UPi,TKi publically to the ABE Service Provider.(3)Encryption Phase. As shown in Figure 2, the encryption phase consists of two steps. In the first step, Bob uses its encryption key EKB and an l×n LSSS access structure M,ρ and calls the function EncryptPK,EKB,M,ρ.EncryptPK,EKB,M,ρ is defined as follows:(i)
First, it generates a random column vectorv=s,y2,y3,…,yn∈Zpn to share the encryption exponent s.(ii)
For eachi∈1,2,…,l, it computes λi=Mi⋅v where Mi is the ith row of M.(iii)
Then, it generates(2)preCT=M,ρC=hs∀i∈1,2,…,l:Cipre=H2ρi∥sB.λi.(iv)
Finally, it outputspreCT.Figure 2
Encryption phase's sequence diagram.Afterward, Bob sendspreCT to the ABE Service Provider.In the second step, the ABE Service Provider executes the functionOutEncryptPK,UPB,preCT after receiving preCT.OutEncryptPK,UPB,preCT performs the following instructions:(i)
For eachi∈1,2,…,l, it computes(3)Ci=UPB,ρi,1Cipre=g1/H2ρi∥sBH2ρi∥sB.λi=gλi,Ci′=UPB,ρi,2Cipre=H1ρi1/H2ρi∥sBH2ρi∥sB.λi=H1ρiλi.(ii)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.Finally, the ABE Service Provider sendsCT to the Cloud Storage Provider (CSP).(4)Decryption Phase. First, as shown in Figure 3, Alice requests the transformed ciphertext transCT from the ABE Service Provider. The ABE Service Provider receives CT from the CSP and executes the function OutDecryptPK,CT,TKA.OutDecryptPK,CT,TKA is defined as follows:(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(4)A=∏i∈IeDA,i,CieDA,i′,Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλiegrA,i/zA,H1ρiλiwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA=∏i∈Ieg,grA.wi.λi/zA=eg,grA/zA⋅∑i∈Iwi.λi=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(5)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.Figure 3
Decryption phase’s sequence diagram.The ABE Service Provider sendstransCT to Alice.After receivingtransCT, Alice decrypts it using its decryption key DKA by calling the function DecryptPK,transCT,DKA.DecryptPK,transCT,DKA executes the following instructions:(i)
It computes(6)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s.(ii)
Then, it outputs theKey.


## 4.1.2. Security Analysis

Before starting our security proof, we will create a modified version of Bethencourt et al.‘s CP-ABE scheme [4] and prove that it achieves the same security level of the original scheme in the random oracle. Then, we will prove that our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified version of Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle. Thus, our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if Bethencourt et al.‘s scheme is selectively CPA-secure in the random oracle.We create the modified Bethencourt et al.‘s scheme by modifying the encryption phase as follows:(i)
Instead of using Shamir’s Secret Sharing Scheme to build the access policy, we use the LSSS access structureM,ρ in the same way as in our scheme and generate the shares λi.(ii)
We choose a random numbersB∈Zp and compute for each row i of M: ℛi=H2ρi||sB.λi (the hash function H2:0,1∗⟶Zp must be defined in the public parameters).(iii)
The generated ciphertext will be defined as follows:(7)M,ρ,C˜=M.eg,gα.shs,∀i=1,…,l:ℛi=H2ρi||sB.λiCi=gλi,Ci′=H1ρiλi.It is obvious that the modified Bethencourt et al.‘s scheme achieves the same security level as the original scheme in the random oracle. That is because if we considerH2ρi||sB random, then ℛi is random and the attacker cannot compute λi from ℛi without knowing H2ρi||sB. Therefore, an attacker cannot distinguish between the distributions H2ρi||sB.λi,gλi,H1ρiλi and r,gλi,H1ρiλi, where r∈Zp is a random number.Now, we prove the following theorem:Theorem 1.
Our 1st CP-ABE-OED KEM is selectively CPA-secure in the random oracle if the modified Bethencourt et al. scheme is selectively CPA-secure in the random oracle.Suppose that we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack the modified Bethencourt et al. scheme in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends M∗,ρ∗ to the challenger.(2)Setup. The simulator ℬ obtains the public parameters from the challenger:(8)PK′=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,f=g1/β′,eg,gα′.The random oraclesH1⋅ and H2⋅ are programmed by the challenger.Then,ℬ sends the public parameters(9)PK=G,g,e⋅,⋅,H1⋅,H2⋅,h=gβ′,eg,gα′,to the adversary A(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls the challenger’s key generation oracle on S to obtain the key(10)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(11)TK=SD=D′1/z∀j∈Si:Dj=Dj′1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(12)CT′=M∗,ρ∗,ℂ′=mπ.eg,gα′s′,C′=hs′,∀i=1,…,l:ℛi=H2ρi||sB.λi′,Ci′=gλi′,Ci'′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(13)UP∗=UPu,1=Ci′1/ℛiUPu,2=Ci′1/ℛi∀u∈U∩YUPu,1=g1/tuUPu,2=xu1/tu∀u∈U∖Y.where tu∈Zp and xu∈G are random numbers.Then,ℬ creates CT∗ as follows:(14)CT∗=M∗,ρ∗,C=C′,Cipre=ℛi,Finally, the simulator flips a coinb∈0,1 and computes Key∗=C'/mb and then sends CT∗, UP∗, and Key∗ to the adversary.(5)Phase 2. The simulator continues to answer queries as in Phase 1.(6)Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess that Key∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of the modified Bethencourt et al.‘s scheme with the same advantage.


## 4.2. The 2nd Proposed CP-ABE-OED Key Encapsulation Mechanism

### 4.2.1. The Construction

In this scheme, we consider the ABE Service Provider semi-trusted, which means that it cannot collude with illegitimate users to reveal the plaintext.We will only describe the modified methods that are different from the previous scheme.(1)
KeyGenU,MK,Si(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,1=g1/si,∀u∈U:UPi,u,2=H1u1/si.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β.zi∀j∈Si:Di,j=gri/zi.H1jri,j/ziDi,j'=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.(2)
EncryptPK,EKB,M,ρ(i)
It picks a random numbers∈Zp and computes(15)preCT=M,ρ,C=hs,Cpre=sB.s.(ii)
Then, it outputspreCT.(3)
OutEncryptPK,UPB,preCT(i)
First, it chooses a random column vectorv=Cpre,y2,y3,…,yn∈Zpn.(ii)
For eachi∈1,2,…,l, it computes λi=Mi.v where Mi is the ith row of M.(iii)
Then, for eachi∈1,2,…,l, it computes(16)Ci=UPB,1λi=gλi/sBCi′=UPB,ρi,2λi=H1ρiλi/sB,.(iv)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.The decryption phase will perform in the same way as in the previous scheme; however, we will describe it here to show the correctness of our scheme.(4)
OutDecryptPK,CT,TKA.(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(17)A=∏i∈IeDA,i,CieDA,i',Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλi/sBegrA,i/zA,H1ρiλi/sBwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA.sB=∏i∈Ieg,grA.wi.λi/zA.sB=eg,grA/zA.sB.∑i∈Iwi.λi=eg,grA.sB.s/zA.sB=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(18)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.(5)
DecryptPK,transCT,DKA(i)
It computes(19)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s(ii)
Then, it outputs theKey.


### 4.2.2. Security Analysis

In this security proof, we will consider two types of adversaries:(i)
Type-1 adversary: which refers to illegitimate users trying to break our scheme(ii)
Type-2 adversary: which refers to a curious ABE cloud provider trying to reveal sensitive informationFor the Type-1 adversary, our scheme is viewed as Bethencourt et al.‘s scheme [4] with outsourced decryption.Now, we prove the following theorem:Theorem 2.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries if Bethencourt et al.‘s scheme [4] is selectively CPA-secure in the random oracle.Suppose we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack Bethencourt et al.‘s scheme [4] in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends the challenge access structure to the challenger.(2)Setup. The simulator ℬ obtains Bethencourt et al.‘s [4] public parameters(20)PK'=G,g,e⋅,⋅,H1⋅,h=gβ′,f=g1/β′,eg,gα′.and forwards them to the adversaryA.(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls Bethencourt et al.‘s [4] key generation oracle on S to obtain the key(21)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(22)TK=SD=D′1/z∀j∈Si:Dj=Dj'1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(23)CT′=M∗,ρ∗,ℂ′=mπ.Key',C′=hs′,∀i=1,…,l:Ci′=gλi′,Ci′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(24)UP∗=UPu,1=g1/tuUPu,2=H1u1/tu∀u∈U.where tu∈Zp are random numbers.Later on, the simulator constructsCT∗ as follows:(25)CT∗=M∗,ρ∗,C∗=C′,∀i=1,…,l:Ci∗=Ci′,C′i∗=Ci'′.Finally, the simulator flips a coinb∈0,1 and computes Key∗=ℂ′/mb , then sends CT∗, UP∗, and Key∗ to the adversary.(5).Phase 2. The simulator continues to answer queries as in Phase 1.(6).Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess thatKey∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of Bethencourt et al.‘s scheme with the same advantage.The Type-2 adversary is not allowed to collude with unauthorized users. Thus, he can request only the transformation keys and not the decryption keys from the key generation oracle.Now, we prove the following theorem:Theorem 3.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-2 adversaries if our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries.It is obvious that Type-2 adversary cannot distinguish between two pre-ciphertextspreCT0∗ and preCT1∗ where(26)preCTb∗=M∗,ρ∗,Keyb∗,C∗=hs,Cpre∗=sB.s.and Keyb∗=eg,gα.s,b=0,eg,gR,b=1. where R∈Zp is a random number.That is becauseCpre∗ is random since sB is random, and the adversary cannot retrieve s without knowing sB. Thus, Type-2 adversary has no advantage over Type-1 adversary since the only additional information (Cpre∗=sB⋅s) he has compared to the Type-1 adversary is not useful. Hence, Theorem 3 is proved.


## 4.2.1. The Construction

In this scheme, we consider the ABE Service Provider semi-trusted, which means that it cannot collude with illegitimate users to reveal the plaintext.We will only describe the modified methods that are different from the previous scheme.(1)
KeyGenU,MK,Si(i)
First, it generates the encryption keyEKi=si where si is picked randomly in Zp, and the decryption key DKi=zi where zi is a random number in Zp.(ii)
Afterward, it computes the user’s parameters as follows:UPi=UPi,1=g1/si,∀u∈U:UPi,u,2=H1u1/si.(iii)
It also computes the Transformation Key (TKi). First, it chooses a random number ri∈Zp and for each j∈Si it picks ri,j∈Zp randomly. Then, it computes TKi=SiDi=gα+ri/β.zi∀j∈Si:Di,j=gri/zi.H1jri,j/ziDi,j'=gri,j/zi.(iv)
Finally, it outputsEKi,DKi,UPi,TKi.(2)
EncryptPK,EKB,M,ρ(i)
It picks a random numbers∈Zp and computes(15)preCT=M,ρ,C=hs,Cpre=sB.s.(ii)
Then, it outputspreCT.(3)
OutEncryptPK,UPB,preCT(i)
First, it chooses a random column vectorv=Cpre,y2,y3,…,yn∈Zpn.(ii)
For eachi∈1,2,…,l, it computes λi=Mi.v where Mi is the ith row of M.(iii)
Then, for eachi∈1,2,…,l, it computes(16)Ci=UPB,1λi=gλi/sBCi′=UPB,ρi,2λi=H1ρiλi/sB,.(iv)
Then, it outputsCT=M,ρ,C,Ci,Ci′i∈1,2,…,l.The decryption phase will perform in the same way as in the previous scheme; however, we will describe it here to show the correctness of our scheme.(4)
OutDecryptPK,CT,TKA.(i)
If Alice’s set of attributesSA does not satisfy the access structure, then it outputs ⊥. Otherwise, let I=i:ρi∈SA and wi∈Zpi∈I such that ∑i∈Iwi.Mi=1,0,0,…,0.(ii)
Then, it computes(17)A=∏i∈IeDA,i,CieDA,i',Ci′wi=∏i∈IegrA/zA.H1ρirA,i/zA,gλi/sBegrA,i/zA,H1ρiλi/sBwi=∏i∈IegrA.H1ρirA,i,gegrA,i,H1ρiwi.λi/zA.sB=∏i∈Ieg,grA.wi.λi/zA.sB=eg,grA/zA.sB.∑i∈Iwi.λi=eg,grA.sB.s/zA.sB=eg,grA.s/zA.(iii)
Finally, it outputstransCT generated as follows:(18)transCT=eC,DAA=egβ.s,gα+rA/β.zAeg,grA.s/zA=eg,gα.eg,grAeg,grAs/zA=eg,gα.s/zA.(5)
DecryptPK,transCT,DKA(i)
It computes(19)Key=transCTDKA=eg,gα.s/zAzA=eg,gα.s(ii)
Then, it outputs theKey.


## 4.2.2. Security Analysis

In this security proof, we will consider two types of adversaries:(i)
Type-1 adversary: which refers to illegitimate users trying to break our scheme(ii)
Type-2 adversary: which refers to a curious ABE cloud provider trying to reveal sensitive informationFor the Type-1 adversary, our scheme is viewed as Bethencourt et al.‘s scheme [4] with outsourced decryption.Now, we prove the following theorem:Theorem 2.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries if Bethencourt et al.‘s scheme [4] is selectively CPA-secure in the random oracle.Suppose we have an adversaryA with non-negligible advantage ε in the selective CPA-security game against our construction. We show how to build a simulator ℬ that can attack Bethencourt et al.‘s scheme [4] in the selective CPA-security model with advantage ε.(1)Init. The adversary gives the challenge access structure M∗,ρ∗ to the simulator ℬ. ℬ sends the challenge access structure to the challenger.(2)Setup. The simulator ℬ obtains Bethencourt et al.‘s [4] public parameters(20)PK'=G,g,e⋅,⋅,H1⋅,h=gβ′,f=g1/β′,eg,gα′.and forwards them to the adversaryA.(3)Phase I. The adversary sends request queries of sets of attributes S that do not satisfy the challenge access structure M∗,ρ∗ to ℬ. The simulator ℬ calls Bethencourt et al.‘s [4] key generation oracle on S to obtain the key(21)SK′=SD′=gα′+r/β′∀j∈Si:Dj′=gr.H1jrjDj'′=grj.The simulator chooses a random valuez∈Zp and sets the decryption key as DK=z and the transformation key as(22)TK=SD=D′1/z∀j∈Si:Dj=Dj'1/zDj′=Dj'′1/z.(4)Challenge. The simulator sends two distinct random messages m0 and m1 to the challenger. The challenger flips a coin π∈0,1 and creates(23)CT′=M∗,ρ∗,ℂ′=mπ.Key',C′=hs′,∀i=1,…,l:Ci′=gλi′,Ci′=H1ρiλi′.Then, the challenger sendsCT' to the simulator.Later on, the simulator computes(24)UP∗=UPu,1=g1/tuUPu,2=H1u1/tu∀u∈U.where tu∈Zp are random numbers.Later on, the simulator constructsCT∗ as follows:(25)CT∗=M∗,ρ∗,C∗=C′,∀i=1,…,l:Ci∗=Ci′,C′i∗=Ci'′.Finally, the simulator flips a coinb∈0,1 and computes Key∗=ℂ′/mb , then sends CT∗, UP∗, and Key∗ to the adversary.(5).Phase 2. The simulator continues to answer queries as in Phase 1.(6).Guess. The adversary will eventually output a guess b′ of b. The adversary outputs 0 to guess that Key∗ is random, and outputs 1 to guess thatKey∗=eg,gα′s′. The simulator outputs b if b′=1; otherwise it outputs b¯. Thus, if the adversary wins the selective CPA-security game with a non-negligible advantage, then ℬ can break the security of Bethencourt et al.‘s scheme with the same advantage.The Type-2 adversary is not allowed to collude with unauthorized users. Thus, he can request only the transformation keys and not the decryption keys from the key generation oracle.Now, we prove the following theorem:Theorem 3.
Our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-2 adversaries if our 2nd CP-ABE-OED KEM is selectively CPA-secure in the random oracle against Type-1 adversaries.It is obvious that Type-2 adversary cannot distinguish between two pre-ciphertextspreCT0∗ and preCT1∗ where(26)preCTb∗=M∗,ρ∗,Keyb∗,C∗=hs,Cpre∗=sB.s.and Keyb∗=eg,gα.s,b=0,eg,gR,b=1. where R∈Zp is a random number.That is becauseCpre∗ is random since sB is random, and the adversary cannot retrieve s without knowing sB. Thus, Type-2 adversary has no advantage over Type-1 adversary since the only additional information (Cpre∗=sB⋅s) he has compared to the Type-1 adversary is not useful. Hence, Theorem 3 is proved.


## 5. Performance Results and Analysis

### 5.1. Theoretical Results and Analysis

In this section, we theoretically compare the user’s computation, communication, and storage costs between our two schemes and the following schemes:(i)
The CPA-secure construction of [12].(ii)
The CPA-secure construction of [21] based on [12] using Pedersen Commitment as a commitment scheme.(iii)
Zhou et al.‘s scheme [23].(iv)
Zhang et al.‘s scheme [26].(v)
Li et al.‘s scheme [27].We normalized all the schemes based on the following rules:(i)
The transformation key is created by TA and not the user.(ii)
We will consider all the schemes as Key Encapsulation Mechanisms (KEMs), meaning that we neglect the part where the messagem is encrypted (e.g., C=m⋅eg,gα.s) and leave only the parts responsible for sharing the key eg,gα.s.(iii)
We consider that each user has the ability to encrypt and decrypt.(iv)
We ignored the access structureA and the set of attributes S when computing the size of the ciphertexts and the keys since they are common elements between all the schemes.In Table1, we define the notations used in this section.Table 1
Notations used in the performance results and analysis section.
NotationDefinitionxNumber of elements inxlNumber of rows in the LSSS access structure or number of leaf nodes in the access treeNlAn upper bound greater thanl of all the access policiesSUser’s set of attributesUUniverse of attributesMeGModular exponentiation inGMeGTModular exponentiation inGTMGMultiplication inGMGTMultiplication inGTMZMultiplication inZpHGHashing inGHZHashing inZpGElement inGGTElement inGTZpElement inZpIn Table2, we compare the number of operations executed in each phase (registration phase, encryption phase, and decryption phase) between our proposed schemes and the reviewed schemes.Table 2
User-side computation cost comparison.
PhaseCP-ABE-OED1CP-ABE-OED2[12][21][23][26][27]KeyGen0000000Encrypt1.MeG+l.MZ+l.HZ1.MeG+1.MZ2+3.l.MeG+l.HG3+3.l.MeG+2+l.HG3.MeG+1.HG1.MeG+1+3.Nl.MG+l.MZ3.MeG+l.MG+1.HZDecrypt1.MeGT1.MeGT1.MeGT3.MeGT1.MeGT+1.MGT1.MeGT1.MeGTObviously, the user is not involved in the computations of the registration phase in all the schemes.In [12, 21], the user-side encryption cost is very expensive, because the encryption in these schemes is not outsourced. Based on the results in Table 3, which were computed using a Type A curve of the JPBC Library [32] on a Windows 8.1 Core i7 2 GHz PC with 8 GB of RAM, we have the following:(i)
MG=52MZ(ii)
MeG=10357MZ(iii)
HG=22193MZ(iv)
HZ=84MZTable 3
Running times (in milliseconds) of the main operations using JPBC Library [32] on a Windows 8.1 Core i7 2 GHz PC with 8 Go of RAM.
MeGMeGTMGMGTMZHGHZ14.5 ms0.924 ms0.073 ms0.0072 ms0.0014 ms31.07 ms0.118 msWe mention that the hashes were computed using the Element.setFromHash() method based on SHA-256.If we convert the encryption costs of the reviewed schemes, we get the following:(i)
1.MeG+l.MZ+l.HZ=10357+85.l.MZ for our 1st CP-ABE-OED KEM(ii)
1.MeG+1.MZ=10358.MZ for our 2nd CP-ABE-OED KEM(iii)
3.MeG+1.HG=53264.MZ for [23](iv)
1.MeG+1+3.Nl.MG+l.MZ=10409+156.Nl+l.MZ for [26](v)
3.MeG+l.MG+1.HZ=52.l+31155.MZ for [27]We observe that, for access policies smaller than 425 leaf nodes, the user-side encryption in [27] is more efficient than [23].IfNl=l, which is the smallest value Nl can take, the user-side encryption in [26] will be more efficient than [27] (respectively, [23]) for access policies with less than 200 leaf nodes (respectively, 270 leaf nodes). If Nl=5.l, [27] (respectively, [23]) will achieve better efficiency than [26] for all the access policies bigger than 30 leaf nodes (respectively, 50 leaf nodes). Overall, we can say that [26] is more efficient than [23, 27] for small access policies; however, [23, 27] are more efficient for large access policies.Our 1st CP-ABE-OED KEM achieves a higher user-side encryption efficiency than [26] for all the access policy sizes. It also achieves higher efficiency than [23] for access policies with less than 500 leaf nodes, and higher efficiency than [27] for access policies with less than 630 leaf nodes.Obviously, our 2nd CP-ABE-OED KEM is more efficient than all the schemes for all the access policy sizes.The decryption phase costs are almost the same (one modular exponentiation) in all the schemes since they all use the same key blinding technique used in [12]. In [21], the user performs 2 more modular exponentiations to reveal the commitment.Table4 shows the communication costs generated in the registration phase, the encryption phase, and the decryption phase between our proposed schemes and the reviewed schemes. In [12, 21, 23, 26], TA sends TK and DK to the user in the registration phase, which costs 2+2.S elements in G and 2+S elements in Zp for [26], 1+2.S elements in G and one element in Zp for [23], and 2+S elements in G and one Zp element for [12, 21]. In [27], TA sends the encryption transformation key ETK and DK to the user, which costs two Zp elements and U elements in G. However, in our proposed schemes, only two elements in Zp (EK and DK) are communicated between TA and the user. The reason is that TK in our proposed schemes is transferred by TA directly to the ABE Service Provider.Table 4
User-side communication cost comparison.
PhaseKeyGenEncryptDecryptLinkTA => Bob/AliceBob => CSPABE Service => BobBob => ABE ServiceCSP => AliceABE Service => AliceAlice => ABE ServiceCP-ABE-OED1EK+DK=2.Zp00preCT=1.G+l.Zp0transCT=1.GT0CP-ABE-OED2EK+DK=2.Zp00preCT=1.G+1.Zp0transCT=1.GT0[12]TK+DK=2+S.G+1.ZpCT=1+2.l.G000transCT=1.GTTK=2+S.G[21]TK+DK=2+S.G+1.ZpCT=1+2.l.G001.GtransCT=1.GTTK=2+S.G[23]TK+DK=1+2.S.G+1.Zp00preCT=3.G+1.Zp0transCT=2.GTTK=1+2.S.G[26]TK+DK=2+2.S.G+2+S.ZpCT=1+3.l.G+2.l.Zp2.IT=2.1+3.N1.G+1+3.N1.Zp00transCT=1.GTTK=2+2.S.G+1+S.Zp[27]ETK+DK=U.G+2.Zp00preCT+OP=2+l.G+l+1.Zp0transCT=1.GTTK=2+S.GIn the encryption phase, the user in [26] receives two Intermediate Ciphertexts ITs from the ABE Service Provider offline, each of them containing 1+3.Nl elements in G and 1+3.Nl elements in Zp, and sends the ciphertext CT to CSP, which costs 1+3.l elements in G and 2.l elements in Zp. This makes [26] the most expensive scheme for the users in terms of communication cost produced in the encryption phase. In [12, 21], the user communicates CT to CSP; this costs 1+2.l elements in G for [12] and an additional element in G for [21] generated by the commitment element cm. The user in [27] sends the partially encrypted ciphertext preCT and the outsourcing parameters to the ABE service provider. This costs 2+l elements in G and l+1 elements in Zp, which makes [27] slightly more efficient than [12, 21]. In our 1st CP-ABE-OED KEM, the user sends preCT to the ABE Service Provider, which costs him one G element and l elements in Zp. In [23], the user sends preCT that costs only 3 elements in G and one element in Zp to the ABE Service Provider. In our 2nd CP-ABE-OED KEM, the transfer of preCT to the ABE Service Provider costs only one G element and one Zp element, which makes it the most efficient scheme in terms of user’s communication cost in the encryption phase.In the decryption phase, the user receives the transformed ciphertexttransCT from the ABE Service Provider in all the schemes, which costs two GT elements in [23] and only one GT element in the other schemes. In addition, the user should first communicate his TK to the ABE Service Provider, which costs 2+2.S elements in G and 1+S elements in Zp for [26], 1+2.S elements in G for [23], and 2+S elements in G for [12, 21, 27]. In [21], the user also receives the commitment from CSP, which costs one G element. In our proposed schemes, the user does not need to send or receive anything from CSP or the ABE Service Provider except transCT; TK is already sent by TA to the ABE Service Provider in the Registration Phase. Thus, our proposed schemes are the most efficient schemes in terms of user’s communication cost produced in the decryption phase.Table5 compares the user’s storage cost for each scheme. In general, [26] is the scheme that requires the biggest user-side storage space to store TK, DK, and two Intermediate Ciphertextx (ITs). The user in [27] stores U elements in G and one Zp element for the encryption transformation key ETK, and one Zp element for the decryption key DK. Thus, for large universe applications, [27] is considered the most storage space consuming scheme for users. In [12, 21, 23], the user stores TK and DK. DK costs one Zp element in all the schemes and TK costs 1+2.S elements in G for [23] and 2+S elements in G for [12, 21]. In our proposed schemes, the user stores the encryption key EK and the decryption key DK; each of them costs only one Zp element. Therefore, our proposed schemes are the most lightweight schemes in terms of user-side storage.Table 5
User-side storage cost comparison.
CP-ABE-OED1CP-ABE-OED2[12][21][23][26][27]Bob/AliceEK+DK=2.ZpEK+DK=2.ZpTK+DK=2+S.G+1.ZpTK+DK=2+S.G+1.ZpTK+DK=1+2.S.G+1.ZpTK+DK+2.IT=4+2.S+6.Nl.G+4+S+6.Nl.ZpETK+DK=U.G+2.Zp


### 5.2. Experimental Results and Analysis

In this section, we will experimentally compare the running times of the user-side encryption and decryption of our 1st outsourced CP-ABE scheme (CP-ABE-OED1), our 2nd outsourced CP-ABE scheme (CP-ABE-OED2), the original CP-ABE scheme [4], ZHCP-ABE [23], and LiCP-ABE [27]. The implementations of the studied schemes were developed in Java using the JPBC Library [32] and the hashes were computed using setFromHash method of the Element class based on SHA-256.We run 200 experiments for eachN=5,10,15,20,25,…,1000 on a Windows 8.1 Core i7 2 GHz PC with 8 GB of RAM where the access policy is defined as follows A1ANDA2ANDA3…ANDAN and the user’s set of attributes is A1,A2,A3,…,AN. This approach simulates the worst-case scenario where the decryption phase depends on all the access policy’s components. For each N, we repeat the experiment 10 times and calculate the average running time in milliseconds to smooth any experimental variability.In Figure4, the x-axis represents the size of the access policy and the y-axis represents the Log10 of the user-side encryption running time in milliseconds.Figure 4
User-side encryption running time comparison.The experimental results confirmed our theoretical results. Besides, the theoretical results showed that CP-ABE-OED1 is more efficient than ZHCP-ABE [23] (respectively, LiCP-ABE [27]) for access policies with less than 500 leaf nodes (respectively, for access policies with less than 630 leaf nodes). However, the experimental results showed that CP-ABE-OED1 is more efficient than ZHCP-ABE [23] and LiCP-ABE [27] for all the access policy sizes up to 1000.We observe that the difference in running time between CP-ABE-OED1 and CP-ABE-OED2 is linearly increasing with a relatively small slope, and this is due to the number of multiplications and hashing operations performed in CP-ABE-OED1 that is linear to the size of the access policy.In Figure5, the x-axis represents the size of the user’s set of attributes and the y-axis represents the Log2 of the user-side decryption running time in milliseconds.Figure 5
User-side decryption running time comparison.As expected, the running times of the user-side decryption in all the studied outsourced CP-ABE schemes are constant and equivalent; that is because they all used the same decryption outsourcing technique firstly proposed by [12]. The user needs only about 2 ms (since Log2t=1 according to Figure 5) to decrypt a ciphertext regardless the size of the access policy or the length of her set of attributes.


## 5.1. Theoretical Results and Analysis

In this section, we theoretically compare the user’s computation, communication, and storage costs between our two schemes and the following schemes:(i)
The CPA-secure construction of [12].(ii)
The CPA-secure construction of [21] based on [12] using Pedersen Commitment as a commitment scheme.(iii)
Zhou et al.‘s scheme [23].(iv)
Zhang et al.‘s scheme [26].(v)
Li et al.‘s scheme [27].We normalized all the schemes based on the following rules:(i)
The transformation key is created by TA and not the user.(ii)
We will consider all the schemes as Key Encapsulation Mechanisms (KEMs), meaning that we neglect the part where the messagem is encrypted (e.g., C=m⋅eg,gα.s) and leave only the parts responsible for sharing the key eg,gα.s.(iii)
We consider that each user has the ability to encrypt and decrypt.(iv)
We ignored the access structureA and the set of attributes S when computing the size of the ciphertexts and the keys since they are common elements between all the schemes.In Table1, we define the notations used in this section.Table 1
Notations used in the performance results and analysis section.
NotationDefinitionxNumber of elements inxlNumber of rows in the LSSS access structure or number of leaf nodes in the access treeNlAn upper bound greater thanl of all the access policiesSUser’s set of attributesUUniverse of attributesMeGModular exponentiation inGMeGTModular exponentiation inGTMGMultiplication inGMGTMultiplication inGTMZMultiplication inZpHGHashing inGHZHashing inZpGElement inGGTElement inGTZpElement inZpIn Table2, we compare the number of operations executed in each phase (registration phase, encryption phase, and decryption phase) between our proposed schemes and the reviewed schemes.Table 2
User-side computation cost comparison.
PhaseCP-ABE-OED1CP-ABE-OED2[12][21][23][26][27]KeyGen0000000Encrypt1.MeG+l.MZ+l.HZ1.MeG+1.MZ2+3.l.MeG+l.HG3+3.l.MeG+2+l.HG3.MeG+1.HG1.MeG+1+3.Nl.MG+l.MZ3.MeG+l.MG+1.HZDecrypt1.MeGT1.MeGT1.MeGT3.MeGT1.MeGT+1.MGT1.MeGT1.MeGTObviously, the user is not involved in the computations of the registration phase in all the schemes.In [12, 21], the user-side encryption cost is very expensive, because the encryption in these schemes is not outsourced. Based on the results in Table 3, which were computed using a Type A curve of the JPBC Library [32] on a Windows 8.1 Core i7 2 GHz PC with 8 GB of RAM, we have the following:(i)
MG=52MZ(ii)
MeG=10357MZ(iii)
HG=22193MZ(iv)
HZ=84MZTable 3
Running times (in milliseconds) of the main operations using JPBC Library [32] on a Windows 8.1 Core i7 2 GHz PC with 8 Go of RAM.
MeGMeGTMGMGTMZHGHZ14.5 ms0.924 ms0.073 ms0.0072 ms0.0014 ms31.07 ms0.118 msWe mention that the hashes were computed using the Element.setFromHash() method based on SHA-256.If we convert the encryption costs of the reviewed schemes, we get the following:(i)
1.MeG+l.MZ+l.HZ=10357+85.l.MZ for our 1st CP-ABE-OED KEM(ii)
1.MeG+1.MZ=10358.MZ for our 2nd CP-ABE-OED KEM(iii)
3.MeG+1.HG=53264.MZ for [23](iv)
1.MeG+1+3.Nl.MG+l.MZ=10409+156.Nl+l.MZ for [26](v)
3.MeG+l.MG+1.HZ=52.l+31155.MZ for [27]We observe that, for access policies smaller than 425 leaf nodes, the user-side encryption in [27] is more efficient than [23].IfNl=l, which is the smallest value Nl can take, the user-side encryption in [26] will be more efficient than [27] (respectively, [23]) for access policies with less than 200 leaf nodes (respectively, 270 leaf nodes). If Nl=5.l, [27] (respectively, [23]) will achieve better efficiency than [26] for all the access policies bigger than 30 leaf nodes (respectively, 50 leaf nodes). Overall, we can say that [26] is more efficient than [23, 27] for small access policies; however, [23, 27] are more efficient for large access policies.Our 1st CP-ABE-OED KEM achieves a higher user-side encryption efficiency than [26] for all the access policy sizes. It also achieves higher efficiency than [23] for access policies with less than 500 leaf nodes, and higher efficiency than [27] for access policies with less than 630 leaf nodes.Obviously, our 2nd CP-ABE-OED KEM is more efficient than all the schemes for all the access policy sizes.The decryption phase costs are almost the same (one modular exponentiation) in all the schemes since they all use the same key blinding technique used in [12]. In [21], the user performs 2 more modular exponentiations to reveal the commitment.Table4 shows the communication costs generated in the registration phase, the encryption phase, and the decryption phase between our proposed schemes and the reviewed schemes. In [12, 21, 23, 26], TA sends TK and DK to the user in the registration phase, which costs 2+2.S elements in G and 2+S elements in Zp for [26], 1+2.S elements in G and one element in Zp for [23], and 2+S elements in G and one Zp element for [12, 21]. In [27], TA sends the encryption transformation key ETK and DK to the user, which costs two Zp elements and U elements in G. However, in our proposed schemes, only two elements in Zp (EK and DK) are communicated between TA and the user. The reason is that TK in our proposed schemes is transferred by TA directly to the ABE Service Provider.Table 4
User-side communication cost comparison.
PhaseKeyGenEncryptDecryptLinkTA => Bob/AliceBob => CSPABE Service => BobBob => ABE ServiceCSP => AliceABE Service => AliceAlice => ABE ServiceCP-ABE-OED1EK+DK=2.Zp00preCT=1.G+l.Zp0transCT=1.GT0CP-ABE-OED2EK+DK=2.Zp00preCT=1.G+1.Zp0transCT=1.GT0[12]TK+DK=2+S.G+1.ZpCT=1+2.l.G000transCT=1.GTTK=2+S.G[21]TK+DK=2+S.G+1.ZpCT=1+2.l.G001.GtransCT=1.GTTK=2+S.G[23]TK+DK=1+2.S.G+1.Zp00preCT=3.G+1.Zp0transCT=2.GTTK=1+2.S.G[26]TK+DK=2+2.S.G+2+S.ZpCT=1+3.l.G+2.l.Zp2.IT=2.1+3.N1.G+1+3.N1.Zp00transCT=1.GTTK=2+2.S.G+1+S.Zp[27]ETK+DK=U.G+2.Zp00preCT+OP=2+l.G+l+1.Zp0transCT=1.GTTK=2+S.GIn the encryption phase, the user in [26] receives two Intermediate Ciphertexts ITs from the ABE Service Provider offline, each of them containing 1+3.Nl elements in G and 1+3.Nl elements in Zp, and sends the ciphertext CT to CSP, which costs 1+3.l elements in G and 2.l elements in Zp. This makes [26] the most expensive scheme for the users in terms of communication cost produced in the encryption phase. In [12, 21], the user communicates CT to CSP; this costs 1+2.l elements in G for [12] and an additional element in G for [21] generated by the commitment element cm. The user in [27] sends the partially encrypted ciphertext preCT and the outsourcing parameters to the ABE service provider. This costs 2+l elements in G and l+1 elements in Zp, which makes [27] slightly more efficient than [12, 21]. In our 1st CP-ABE-OED KEM, the user sends preCT to the ABE Service Provider, which costs him one G element and l elements in Zp. In [23], the user sends preCT that costs only 3 elements in G and one element in Zp to the ABE Service Provider. In our 2nd CP-ABE-OED KEM, the transfer of preCT to the ABE Service Provider costs only one G element and one Zp element, which makes it the most efficient scheme in terms of user’s communication cost in the encryption phase.In the decryption phase, the user receives the transformed ciphertexttransCT from the ABE Service Provider in all the schemes, which costs two GT elements in [23] and only one GT element in the other schemes. In addition, the user should first communicate his TK to the ABE Service Provider, which costs 2+2.S elements in G and 1+S elements in Zp for [26], 1+2.S elements in G for [23], and 2+S elements in G for [12, 21, 27]. In [21], the user also receives the commitment from CSP, which costs one G element. In our proposed schemes, the user does not need to send or receive anything from CSP or the ABE Service Provider except transCT; TK is already sent by TA to the ABE Service Provider in the Registration Phase. Thus, our proposed schemes are the most efficient schemes in terms of user’s communication cost produced in the decryption phase.Table5 compares the user’s storage cost for each scheme. In general, [26] is the scheme that requires the biggest user-side storage space to store TK, DK, and two Intermediate Ciphertextx (ITs). The user in [27] stores U elements in G and one Zp element for the encryption transformation key ETK, and one Zp element for the decryption key DK. Thus, for large universe applications, [27] is considered the most storage space consuming scheme for users. In [12, 21, 23], the user stores TK and DK. DK costs one Zp element in all the schemes and TK costs 1+2.S elements in G for [23] and 2+S elements in G for [12, 21]. In our proposed schemes, the user stores the encryption key EK and the decryption key DK; each of them costs only one Zp element. Therefore, our proposed schemes are the most lightweight schemes in terms of user-side storage.Table 5
User-side storage cost comparison.
CP-ABE-OED1CP-ABE-OED2[12][21][23][26][27]Bob/AliceEK+DK=2.ZpEK+DK=2.ZpTK+DK=2+S.G+1.ZpTK+DK=2+S.G+1.ZpTK+DK=1+2.S.G+1.ZpTK+DK+2.IT=4+2.S+6.Nl.G+4+S+6.Nl.ZpETK+DK=U.G+2.Zp


## 5.2. Experimental Results and Analysis

In this section, we will experimentally compare the running times of the user-side encryption and decryption of our 1st outsourced CP-ABE scheme (CP-ABE-OED1), our 2nd outsourced CP-ABE scheme (CP-ABE-OED2), the original CP-ABE scheme [4], ZHCP-ABE [23], and LiCP-ABE [27]. The implementations of the studied schemes were developed in Java using the JPBC Library [32] and the hashes were computed using setFromHash method of the Element class based on SHA-256.We run 200 experiments for eachN=5,10,15,20,25,…,1000 on a Windows 8.1 Core i7 2 GHz PC with 8 GB of RAM where the access policy is defined as follows A1ANDA2ANDA3…ANDAN and the user’s set of attributes is A1,A2,A3,…,AN. This approach simulates the worst-case scenario where the decryption phase depends on all the access policy’s components. For each N, we repeat the experiment 10 times and calculate the average running time in milliseconds to smooth any experimental variability.In Figure4, the x-axis represents the size of the access policy and the y-axis represents the Log10 of the user-side encryption running time in milliseconds.Figure 4
User-side encryption running time comparison.The experimental results confirmed our theoretical results. Besides, the theoretical results showed that CP-ABE-OED1 is more efficient than ZHCP-ABE [23] (respectively, LiCP-ABE [27]) for access policies with less than 500 leaf nodes (respectively, for access policies with less than 630 leaf nodes). However, the experimental results showed that CP-ABE-OED1 is more efficient than ZHCP-ABE [23] and LiCP-ABE [27] for all the access policy sizes up to 1000.We observe that the difference in running time between CP-ABE-OED1 and CP-ABE-OED2 is linearly increasing with a relatively small slope, and this is due to the number of multiplications and hashing operations performed in CP-ABE-OED1 that is linear to the size of the access policy.In Figure5, the x-axis represents the size of the user’s set of attributes and the y-axis represents the Log2 of the user-side decryption running time in milliseconds.Figure 5
User-side decryption running time comparison.As expected, the running times of the user-side decryption in all the studied outsourced CP-ABE schemes are constant and equivalent; that is because they all used the same decryption outsourcing technique firstly proposed by [12]. The user needs only about 2 ms (since Log2t=1 according to Figure 5) to decrypt a ciphertext regardless the size of the access policy or the length of her set of attributes.


## 6. Conclusion

In this paper, we proposed two efficient CP-ABE Key Encapsulation Mechanisms that can be provided as services in the cloud, minimizing the user-side computation, communication, and storage costs. The first scheme is suitable for applications where the ABE Service Provider is untrusted, whereas the second scheme, which is more efficient, requires the ABE Service Provider to be at least semi-trusted. Both schemes are proved to be selectively CPA-secure in the random oracle. However, our systems support only one TA that is responsible for the registration of all the users. Hence, our systems will face a bottleneck problem if TA does not use a very powerful device or if the registration requests are very frequent. Therefore, in the future, it will be interesting to extend our schemes to use a multi-authority architecture to handle this problem. Converting our schemes to support a multi-authority architecture might also improve the security of the systems by preventing the key-escrow problem produced when attackers compromise the TA’s master key. In a multi-authority approach, compromising some authorities’ master keys by attackers will not break the system.



---

*Source: 8834616-2021-05-18.xml*