# Traceable Multiauthority Attribute-Based Encryption with Outsourced Decryption and Hidden Policy for CIoT

Authors: Suhui Liu; Jiguo Yu; Chunqiang Hu; Mengmeng Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Cloud-assisted Internet of Things (IoT) significantly facilitate IoT devices to outsource their data for high efficient management. Unfortunately, some unsettled security issues dramatically impact the popularity of IoT, such as illegal access and key escrow problem. Traditional public-key encryption can be used to guarantees data confidentiality, while it cannot achieve efficient data sharing. The attribute-based encryption (ABE) is the most promising way to ensure data security and to realize one-to-many fine-grained data sharing simultaneously. However, it cannot be well applied in the cloud-assisted IoT due to the complexity of its decryption and the decryption key leakage problem. To prevent the abuse of decryption rights, we propose a multiauthority ABE scheme with white-box traceability in this paper. Moreover, our scheme greatly lightens the overhead on devices by outsourcing the most decryption work to the cloud server. Besides, fully hidden policy is implemented to protect the privacy of the access policy. Our scheme is proved to be selectively secure against replayable chosen ciphertext attack (RCCA) under the random oracle model. Some theory analysis and simulation are described in the end.


---

## Body

## 1. Introduction

In traditional public key encryption schemes, the encryptor encrypts the message with the public key of the decryptor; hence, only the decryptor who owns the corresponding decryption key can decrypt the data. In other words, this type of scheme relies on the public key certificate system which we all know is pretty difficult to manage. In 1984, Shamir first proposed the identity-based encryption (IBE) where the encryptor uses the identity of the decryptor as his/her public key [1]. In [2], Boneh et al. proposed an IBE using the elliptic curve pairing, which greatly promoted the development of this field. Although the IBE solves the public key management problem, it still cannot achieve one-to-many private data sharing. Unfortunately, this kind of application is extremely common in ubiquitous Internet of Things (IoT) scenarios.To tackle this issue, Sahai et al. first proposed a fuzzy identity encryption scheme [3], which is later developed into the attribute-based encryption (ABE). There are two types of ABE, the first one is named as ciphertext-policy attribute-based encryption (CP_ABE) and the other one is key-policy attribute-based encryption (KP_ABE). CP_ABE was proposed by Waters, in which the encryptor needs to know nothing about who can decrypt the ciphertext exactly, and he/she just encrypts the message with a self-defined access policy [4]. Any decryptor can decrypt correctly as long as its attribute set meets the access policy in the ciphertext. In other words, in CP_ABE schemes, data owners own the right to design who can decrypt fully.IoT, which acts as the bridge between the physical world and the cyber world, enables the creation of a bunch of smart applications [5], such as smart city, smart industry, and smart health care system. Considering that most IoT devices are resource constrained and cannot handle the huge amount of data locally and efficiently, the cloud storage server is included in the IoT and forms a new paradigm, the cloud-IoT, where the cloud or a resource-adequated server provides useful services like storage and computing. ABE schemes with a single attribute authority do not adequately address the needs of the ubiquitous IoT devices properly. In [6], Chase first proposed a multiauthority ABE scheme. However, Chase’s scheme still requires the trusted central authority (CA), which can decrypt any ciphertext that it wants to decrypt. Later, Chase et al. improve their scheme by removing the CA and achieve a truly decentralized ABE scheme [7].In [8], Lewko et al. proposed a distributed ABE scheme, which not only realizes multiauthority attribute-based encryption (MAABE) but also proves the system security with dual system encryption methodology. Unfortunately, the application of ABE in IoT still faces an important challenge: IoT devices with limited resources cannot afford the huge number of bilinear pairing operations in ABE schemes. Therefore, Green et al. proposed an outsourced ABE scheme which ensures the data security while minimizing the computational burden of equipments [9].In this paper, a multiauthority attribute-based encryption scheme with white-box traceability and verifiable outsourced decryption was proposed for cloud IoT. Compared with the existing ABE schemes, our scheme has the following contributions:(i)
As there is a great quantity of attributes used in the decryption key generation, each attribute authority controlls a set of disjoint attributes independently in our scheme. The central authority is only responsible for generating the public parameters, and the right to decide who can decrypt is hold by the data owners directly(ii)
Our scheme uses the linear secret sharing schemes (LSSS) to allow any monotone access structures. More importantly, to protect the privacy of IoT users, our scheme realizes fully hidden access policy(iii)
Considering the needs of resource-constrained IoT devices, our scheme outsources most decryption works to the cloud by the verifiable outsourcing technology(iv)
Our scheme adopts the Boneh-Boyen short signature algorithm to implement the user traceability mechanism. In other words, we use a white-box trace algorithm to tackle the private key leaking issue


### 1.1. Paper Organizaiton

Section2 summarizes many related works, and Section 3 introduces all preliminaries of our scheme including some complexity assumptions. The system model and security models are presented in Section 4. In Section 5, we propose the concrete construction and a simple application of our scheme. Section 6 outlines the proof of indistinguishability, verifiability, fully hiding, and traceability of our scheme. We compare our scheme with some other schemes about the storage and computation costs in Section 7. Section 8 contains the conclusion.


## 1.1. Paper Organizaiton

Section2 summarizes many related works, and Section 3 introduces all preliminaries of our scheme including some complexity assumptions. The system model and security models are presented in Section 4. In Section 5, we propose the concrete construction and a simple application of our scheme. Section 6 outlines the proof of indistinguishability, verifiability, fully hiding, and traceability of our scheme. We compare our scheme with some other schemes about the storage and computation costs in Section 7. Section 8 contains the conclusion.


## 2. Related Work

Many works have been proposed since Sahai et al. first proposed the attribute-based encryption [3]. ABE schemes can be classified into two categories generally: the key-policy attribute-based encryption (KP_ABE) and the ciphertext-policy attribute-based encryption (CP_ABE) [4, 16]. Because CP_ABE allows the data owner to decide the access policy, it has been treated as the most promising solution to solve the access control issue in the cloud storage. In ABE schemes, the key pair of data users is generated by attribute authorities (AAs). Thus, the security of ABE schemes is based on the trust of the attribute authorities. To tackle the huge amount of data users contained in IoT, multiauthority attribute-based encryption (MA_ABE) was proposed, which can manage the huge amount of attributes in a more efficient way [6, 17–19], where each attribute authority controls an unique set of attributes independently. To achieve both the data confidentiality and the data authentication in the body area network, Hu et al. proposed a fuzzy attribute-based signcryption scheme [20].Another characteristic of IoT is that most devices are resource-limited [21–23]. As we all know that the decryption overhead of ABE schemes rises along with the attribute number involved in the access policy. Obviously the expensive pairing computations are unacceptable for most IoT devices. Therefore, some ABE schemes using the proxy reencryption concept have been proposed [24–26]. In [9], Green et al. proposed an outsourced ABE scheme, which outsources most decryption overheads to a trusted third-party server, but outsourced ABE schemes all rely on a semitrusted server to semidecrypt that leads to a serious problem: how to ensure the semidecrypted data is correct and not altered. In [27], Lai et al. proposed a verifiable outsourced ABE while this scheme requires heavy costs for decryption. Recently, Li et al. improved an ABE scheme to achieve not only verifiable outsourced decryption but also lightweight user decryption [10], but all outsourced schemes mentioned above rely on a central authority to manage and generate user decryption key. In [11], Belguith et al. proposed an outsourced multiauthority attribute-based encryption scheme. In [28], Deng et al. proposed an efficient outsourced attribute-based signcryption scheme which also solves the user revocation problem.In the cloud-assisted IoT environment, data owners store private data in the shared cloud. In most ABE schemes, the access policy is uploaded to the cloud server in plaintext along with the encrypted data. This may reveal private information of the encryptor and the decrypor. In [29], Nishide et al. proposed an ABE scheme with partially hided access policy, but this scheme has poor expressiveness.When it comes to application in the real word, a common issue of ABE schemes needs to be considered: the leakage of decryption keys. In other words, how to trace/recover the global identity of the guilty user who leaks its secret key to a malicious or illegal user. There are two tracing approaches, white-box traceability and black-box traceability, that can be used to solve this issue. In [30], Hinek et al. used the Boneh-Boyen signature [31] to achieve the white-box traceability. Liu et al. proposed a white-box traceable ABE [32] and a black-box traceable ABE with highly expression [33]. In [12], Liu et al. proposed a traceable and revocable ABE scheme which is more practical for real application. In [34], Yu et al. proposed a traceable ABE scheme with white-box traceability to manage data stored in the cloud storage. In [13], an efficient large-universe MA_CP_ABE with white-box traceability was proposed. While in [35], Qiao et al. proposed a traceable ABE scheme with black-box traceability for fog computing.All traceable ABE schemes mentioned above have a shared issue: their decryption computation burden are intolerable for IoT devices. In [14], an ABE scheme with outsourced decryption designed for electronic health systems was proposed by Li et al. However, Li’s scheme did not consider the privacy of access policies which might contain sensitive personal information of users. We compare our scheme with some existed ABE schemes in Table 1. In a word, our ABE scheme achieves selective replayable CCA security and provides multiple practical functions, such as fully hidden policy, outsourced decryption, and traceability.Table 1
Function comparison.
Scheme[10][11][12][13][14][15]Our schemeMultiauthorityNoYesNoYesNoYesYesAccess policyAND gatesLSSSLSSSLSSSLSSSLSSSLSSSFully hidden policyNoNoNoNoNoYesYesOutdecryptionYesYesNoNoYesNoYesSecurityRCCASelective RCPASelective CPAStatic securitySelective CPASelective CPASelective RCCATraceabilityNoNoYesYesYesNoYes


## 3. Preliminaries

In this section, we provide all mathematical preliminaries needed for our scheme.


### 3.1. Bilinear Maps

LetG and GT be two multiplicative cyclic groups of prime order p. Let g be a generator of G and e be a bilinearmap, e:G×G→GT, with the following three properties [15]:
(1)
Bilinearity: for allu,v∈G and a,b∈ℤp, we have eua,vb=eu,vab, where ℤp is the integers modulo p(2)
Nondegeneracy:eg,g≠1, where 1 is the unit of GT(3)
Computability: there is a polynomial time algorithm to efficiently computeeu,v for any u,v∈GWe say G is a bilineargroup if the group operation in G, and the bilinear map e:G×G→GT is both efficiently computable. Notice that the map e is symmetric since ega,gb=eg,gab=egb,ga.


### 3.2. Access Structure

Definition 1.
(access structure). LetP=P1,⋯Pn be a set of parties. A collection A⊆2P1,⋯Pn is monotone if ∀B,C: ifB∈A and B⊆C, then C∈A. An access structure is a collection A of nonempty subsets of P1,⋯Pn, such as A⊆2P1,⋯Pn\∅. The sets in A are called authorized sets, and the sets not in A are called unauthorized sets [9].


### 3.3. Linear Secret Sharing Schemes (LSSS)

Definition 2.
(linear secret sharing schemes (LSSS)). A secret-sharing scheme∏ over a set of parties ℙ is called linear over ℤp if
(1)
The shares of a secrets∈ℤp for each party form a vector over ℤp(2)
There exists a matrixM with l rows and n columns called the share-generating matrix for ∏ and a function ρ which maps each row of the matrix to an associated party. That is, for i=1,..,l, the value ρi is the party associate with the row i. When we consider the column vector v=s,r2,⋯,rn where r2,⋯,rn∈ℤp is randomly chosen, then Mv is the vector of l shares of the secret s according to ∏. The share Mvi belongs to the party ρiAccording to [9], every linear secret-sharing scheme based on the above definition also enjoys the linear reconsruction property defined as follows: Let ∏ be an LSSS for the access structure A. Let S∈A be any authorized set, and let I⊂1,2,⋯,l be defined as I=i:ρi∈S. Then, there exist constants ωi∈ℤpi∈I such that if λi are valid shares of any secret s according to ∏, then ∑i∈Iωiλi=s. It is shown in [9] that these constants ωi can be found in polynomial time in the size of the share-generating matrix M.


### 3.4. One-Way Anonymous Key Agreement

One-way anonymous key agreement [15] scheme can be used to guarantee anonymity of the access structure. This scheme only ensures the anonymity of one participant. Assume that there are two participants Alice (IDA) and Bob (IDB) in this scheme. And the master secret of the key generation center (KGC) is s. When Alice wants to keep anonymity, the process is listed as follows:
(1)
Alice calculatesQB=HIDB. A random number ra∈ℤp∗ is choosed to generate the pseudonym PA=QAra and computes the session key KA,B=edA,QBra=eQA,QBs·ra. Finally, she sends her pseudonyms PA to Bob(2)
Bob uses his secret keydB to calculate the session key KA,B=ePA,dB=eQA,QBs·ra, where di=HIDis∈G is his private key for i∈A,B, and H:0,1∗→G is a strong collision-resistant hash function


### 3.5. Complexity Assumptions

Definition 3.
Strong Diffie Hellman problem (q-SDH). LetG be a multiplicative cyclic group of order p with a generator g. Given a random x∈ℤp∗ and a q+1 tuple g,gx,gx2,⋯,gxq, the problem of computing a pair c,g1/x+c, where c∈ℤp∗, is called the q-strong Diffie Hellman problem [13].Definition 4.
Computational Diffie Hellman problem (CDH). LetG be a multiplicative cyclic group of order p with a generator g. Given two group elements ga,gb∈G where a,b∈ℤp are two random integers. The problem of calculating gab from ga and gb is called Computational Diffie Hellman problem [11].Definition 5.
Decisional Bilinear Diffie Hellman problem (DBDH). LetG be a multiplicative cyclic group of order p with a generator g. Given three group element ga,gb,andgc∈G where a,b,andc∈ℤp∗ are three random integers. The problem of distinguishing tuples of the form ga,gb,gc,eg,gabcandga,gb,gc,eg,gz for some random integer z is called the Decisional Bilinear Diffie Hellman problem [11].


## 3.1. Bilinear Maps

LetG and GT be two multiplicative cyclic groups of prime order p. Let g be a generator of G and e be a bilinearmap, e:G×G→GT, with the following three properties [15]:
(1)
Bilinearity: for allu,v∈G and a,b∈ℤp, we have eua,vb=eu,vab, where ℤp is the integers modulo p(2)
Nondegeneracy:eg,g≠1, where 1 is the unit of GT(3)
Computability: there is a polynomial time algorithm to efficiently computeeu,v for any u,v∈GWe say G is a bilineargroup if the group operation in G, and the bilinear map e:G×G→GT is both efficiently computable. Notice that the map e is symmetric since ega,gb=eg,gab=egb,ga.


## 3.2. Access Structure

Definition 1.
(access structure). LetP=P1,⋯Pn be a set of parties. A collection A⊆2P1,⋯Pn is monotone if ∀B,C: ifB∈A and B⊆C, then C∈A. An access structure is a collection A of nonempty subsets of P1,⋯Pn, such as A⊆2P1,⋯Pn\∅. The sets in A are called authorized sets, and the sets not in A are called unauthorized sets [9].


## 3.3. Linear Secret Sharing Schemes (LSSS)

Definition 2.
(linear secret sharing schemes (LSSS)). A secret-sharing scheme∏ over a set of parties ℙ is called linear over ℤp if
(1)
The shares of a secrets∈ℤp for each party form a vector over ℤp(2)
There exists a matrixM with l rows and n columns called the share-generating matrix for ∏ and a function ρ which maps each row of the matrix to an associated party. That is, for i=1,..,l, the value ρi is the party associate with the row i. When we consider the column vector v=s,r2,⋯,rn where r2,⋯,rn∈ℤp is randomly chosen, then Mv is the vector of l shares of the secret s according to ∏. The share Mvi belongs to the party ρiAccording to [9], every linear secret-sharing scheme based on the above definition also enjoys the linear reconsruction property defined as follows: Let ∏ be an LSSS for the access structure A. Let S∈A be any authorized set, and let I⊂1,2,⋯,l be defined as I=i:ρi∈S. Then, there exist constants ωi∈ℤpi∈I such that if λi are valid shares of any secret s according to ∏, then ∑i∈Iωiλi=s. It is shown in [9] that these constants ωi can be found in polynomial time in the size of the share-generating matrix M.


## 3.4. One-Way Anonymous Key Agreement

One-way anonymous key agreement [15] scheme can be used to guarantee anonymity of the access structure. This scheme only ensures the anonymity of one participant. Assume that there are two participants Alice (IDA) and Bob (IDB) in this scheme. And the master secret of the key generation center (KGC) is s. When Alice wants to keep anonymity, the process is listed as follows:
(1)
Alice calculatesQB=HIDB. A random number ra∈ℤp∗ is choosed to generate the pseudonym PA=QAra and computes the session key KA,B=edA,QBra=eQA,QBs·ra. Finally, she sends her pseudonyms PA to Bob(2)
Bob uses his secret keydB to calculate the session key KA,B=ePA,dB=eQA,QBs·ra, where di=HIDis∈G is his private key for i∈A,B, and H:0,1∗→G is a strong collision-resistant hash function


## 3.5. Complexity Assumptions

Definition 3.
Strong Diffie Hellman problem (q-SDH). LetG be a multiplicative cyclic group of order p with a generator g. Given a random x∈ℤp∗ and a q+1 tuple g,gx,gx2,⋯,gxq, the problem of computing a pair c,g1/x+c, where c∈ℤp∗, is called the q-strong Diffie Hellman problem [13].Definition 4.
Computational Diffie Hellman problem (CDH). LetG be a multiplicative cyclic group of order p with a generator g. Given two group elements ga,gb∈G where a,b∈ℤp are two random integers. The problem of calculating gab from ga and gb is called Computational Diffie Hellman problem [11].Definition 5.
Decisional Bilinear Diffie Hellman problem (DBDH). LetG be a multiplicative cyclic group of order p with a generator g. Given three group element ga,gb,andgc∈G where a,b,andc∈ℤp∗ are three random integers. The problem of distinguishing tuples of the form ga,gb,gc,eg,gabcandga,gb,gc,eg,gz for some random integer z is called the Decisional Bilinear Diffie Hellman problem [11].


## 4. System Definition

### 4.1. System Model

The system model of our scheme is illustrated in Figure1, and the associated five entities are described as follows:
(1)
Central Trusted Authority (CTA): the CTA is only used to generate the public parameter, and it cannot decrypted any data(2)
Attribute authorities (AAs): each AA controls a set of attributes. Multiple attribute authorities work together to generate the user’s decryption key. Besides, attribute authorities can use a trace algorithm to recover the global identity of the guilty user who leaks its private decryption key(3)
Cloud storage service provider (CS): the CS is responsible to store the encrypted data. Moreover, CS performs the outsourcing decryption for users(4)
Data owner (DO): the owner of the data which is responsible to encrypt and upload the data to CS(5)
Data user (DU): the party who wants to access dataFigure 1
System model and procedure.Table2 summarizes notations used in our scheme. Assume that there are n authorities in our scheme and each attribute is associated with an unique AA, such that SA,AAi∩SA,AAj=∅ for ∀i,j and ⋃SA,AAj=SA.Table 2
Notations.
NotationMeaningSAAThe universe set of attribute authoritiesSAA′The set of corrupted attribute authoritiesSAA,GIDThe set of attribute authorities related to the user GIDSAThe universe set of attributesAAjAn attribute authoritySA,AAjThe attribute set controlled byAAjGIDThe global identity of a userSGIDThe attribute set related with userGIDPThe public parameterskAAjSecret key related toAAjpkAAjPublic key related toAAjMSGMessageM,ρThe LSSS access matrix and its row label functionϕAccess control structureSϕThe attribute set related withϕCTThe ciphertextskGIDThe secret key of userGIDokGIDThe outsourced decryption key (opk,osk)


### 4.2. System Procedure

Our MAABE scheme with outsourced decryption and hidden policy contains the following five phases:(1)
Systeminitialization: this phase includes two algorithms. Firstly, the CTA runs the setupλ→PP algorithm to generate the global parameters PP, where λ is the security parameter. Then, each AA runs the SetupauthPP→skAAj,pkAAj algorithm to generate their own key pairs, which is consisted with a private key and a public key(2)
Encryption: the DO runs the EncryptPP,pkAAj,MSG,M,ρ→CT algorithm to encrypt the message MSG, and then it uploads the ciphertext to the cloud server(3)
Keygeneration: this phase contains two algorithms. Firstly, each related AA runs the KeygenPP,skAAj,pkAAj,GID,SGID,j→skGID,j algorithm independently to generate the decryption key for the DU with identity GID. Then, all results are sent to the userTo outsource the decryption work to the cloud, the user runs theKeygenoutPP,skGID,M,ρ,CT→okGID algorithm to generate its outsourced decryption key.
(4)
Decryption: this phase is divided into two steps. Firstly, the CS runs the DecryptoutPP,opkGID,M,ρ,CT→CT′ algorithm to partially decrypt the ciphertext. The second step is performed by the user, who runs the DecryptCT′,oskGID→MSG algorithm to get the plaintext(5)
Trace: to begin with, each AAj verifies the format of the decryption key that needed to be traced, and then it runs the TracePP,skGID,pkAAj→GID algorithm to output the global identity (GID) of the guilty user


### 4.3. Security Models

We define four security models of our MAABE scheme in this section.(1)
Confidentiality: the confidentiality of data is the basic security requirement of a scheme, which is used to resist malicious adversaries to gain extral information from the ciphertext. Our scheme adopts the replayable chosen-ciphertext security (RCCA) defined in [36] by Canetti et al. as this type of security is sufficient enough and not to be too strict. Two restrictions are followed in this experiment: all decryption key queries cannot satisfy the challenge access struction fixed in the initialization phase by the adversary. And the attribute authorities can only be corrupted statically be the adversaryThe selective secure against chosen ciphertext attack of our scheme is achieved if no probabilistic polynomial time (PPT) adversary can win theExpConf security experiment described in Figure 2 between an adversary A and a challenger ℂ with nonnegligible advantage.
(2)
Verifiability: our scheme is verifiable if there is no PPT adversary that can win the ExpVerif security experiment described in Figure 3 between an adversary A and a challenger ℂ with nonnegligible advantage.(3)
Fully hidden: in our scheme, the CS knows nothing about the access policy, and the user only knows if his/her attributes satisfy the access policy. Our scheme is an outsourced ABE with fully hidden policy if there is no PPT adversary that can win the ExpHide security experiment described in Figure 4 between an adversary A and a challenger ℂ with nonnegligible advantage. The goal of the adversary is to recover the correct access policy without the required decryption key.(4)
Traceability: our scheme is a traceable ABE if there is no PPT adversary can win the ExpTrace security experiment described in Figure 5 between an adversary A and a challenger ℂ with nonnegligible advantage.Definition 6.
An outsourced ABE scheme is RCCA-secure against static corruption of the attribute authorities ifAdvAExpConf1ξ is negligible for all PPT adversaries.Definition 7.
An outsourced ABE scheme is verifiable ifAdvAExpVerif1ξ is negligible for all PPT adversaries.Definition 8.
An outsourced ABE scheme achieves policy private ifAdvAExpPriv1ξ is negligible for all PPT adversaries.Definition 9.
An outsourced ABE scheme is traceable ifAdvAExpTrace1ξ is negligible for all PPT adversaries.Figure 2
Confidentiality security model.Figure 3
Verifiability security model.Figure 4
Fully hidden security model.Figure 5
Traceability security model.


## 4.1. System Model

The system model of our scheme is illustrated in Figure1, and the associated five entities are described as follows:
(1)
Central Trusted Authority (CTA): the CTA is only used to generate the public parameter, and it cannot decrypted any data(2)
Attribute authorities (AAs): each AA controls a set of attributes. Multiple attribute authorities work together to generate the user’s decryption key. Besides, attribute authorities can use a trace algorithm to recover the global identity of the guilty user who leaks its private decryption key(3)
Cloud storage service provider (CS): the CS is responsible to store the encrypted data. Moreover, CS performs the outsourcing decryption for users(4)
Data owner (DO): the owner of the data which is responsible to encrypt and upload the data to CS(5)
Data user (DU): the party who wants to access dataFigure 1
System model and procedure.Table2 summarizes notations used in our scheme. Assume that there are n authorities in our scheme and each attribute is associated with an unique AA, such that SA,AAi∩SA,AAj=∅ for ∀i,j and ⋃SA,AAj=SA.Table 2
Notations.
NotationMeaningSAAThe universe set of attribute authoritiesSAA′The set of corrupted attribute authoritiesSAA,GIDThe set of attribute authorities related to the user GIDSAThe universe set of attributesAAjAn attribute authoritySA,AAjThe attribute set controlled byAAjGIDThe global identity of a userSGIDThe attribute set related with userGIDPThe public parameterskAAjSecret key related toAAjpkAAjPublic key related toAAjMSGMessageM,ρThe LSSS access matrix and its row label functionϕAccess control structureSϕThe attribute set related withϕCTThe ciphertextskGIDThe secret key of userGIDokGIDThe outsourced decryption key (opk,osk)


## 4.2. System Procedure

Our MAABE scheme with outsourced decryption and hidden policy contains the following five phases:(1)
Systeminitialization: this phase includes two algorithms. Firstly, the CTA runs the setupλ→PP algorithm to generate the global parameters PP, where λ is the security parameter. Then, each AA runs the SetupauthPP→skAAj,pkAAj algorithm to generate their own key pairs, which is consisted with a private key and a public key(2)
Encryption: the DO runs the EncryptPP,pkAAj,MSG,M,ρ→CT algorithm to encrypt the message MSG, and then it uploads the ciphertext to the cloud server(3)
Keygeneration: this phase contains two algorithms. Firstly, each related AA runs the KeygenPP,skAAj,pkAAj,GID,SGID,j→skGID,j algorithm independently to generate the decryption key for the DU with identity GID. Then, all results are sent to the userTo outsource the decryption work to the cloud, the user runs theKeygenoutPP,skGID,M,ρ,CT→okGID algorithm to generate its outsourced decryption key.
(4)
Decryption: this phase is divided into two steps. Firstly, the CS runs the DecryptoutPP,opkGID,M,ρ,CT→CT′ algorithm to partially decrypt the ciphertext. The second step is performed by the user, who runs the DecryptCT′,oskGID→MSG algorithm to get the plaintext(5)
Trace: to begin with, each AAj verifies the format of the decryption key that needed to be traced, and then it runs the TracePP,skGID,pkAAj→GID algorithm to output the global identity (GID) of the guilty user


## 4.3. Security Models

We define four security models of our MAABE scheme in this section.(1)
Confidentiality: the confidentiality of data is the basic security requirement of a scheme, which is used to resist malicious adversaries to gain extral information from the ciphertext. Our scheme adopts the replayable chosen-ciphertext security (RCCA) defined in [36] by Canetti et al. as this type of security is sufficient enough and not to be too strict. Two restrictions are followed in this experiment: all decryption key queries cannot satisfy the challenge access struction fixed in the initialization phase by the adversary. And the attribute authorities can only be corrupted statically be the adversaryThe selective secure against chosen ciphertext attack of our scheme is achieved if no probabilistic polynomial time (PPT) adversary can win theExpConf security experiment described in Figure 2 between an adversary A and a challenger ℂ with nonnegligible advantage.
(2)
Verifiability: our scheme is verifiable if there is no PPT adversary that can win the ExpVerif security experiment described in Figure 3 between an adversary A and a challenger ℂ with nonnegligible advantage.(3)
Fully hidden: in our scheme, the CS knows nothing about the access policy, and the user only knows if his/her attributes satisfy the access policy. Our scheme is an outsourced ABE with fully hidden policy if there is no PPT adversary that can win the ExpHide security experiment described in Figure 4 between an adversary A and a challenger ℂ with nonnegligible advantage. The goal of the adversary is to recover the correct access policy without the required decryption key.(4)
Traceability: our scheme is a traceable ABE if there is no PPT adversary can win the ExpTrace security experiment described in Figure 5 between an adversary A and a challenger ℂ with nonnegligible advantage.Definition 6.
An outsourced ABE scheme is RCCA-secure against static corruption of the attribute authorities ifAdvAExpConf1ξ is negligible for all PPT adversaries.Definition 7.
An outsourced ABE scheme is verifiable ifAdvAExpVerif1ξ is negligible for all PPT adversaries.Definition 8.
An outsourced ABE scheme achieves policy private ifAdvAExpPriv1ξ is negligible for all PPT adversaries.Definition 9.
An outsourced ABE scheme is traceable ifAdvAExpTrace1ξ is negligible for all PPT adversaries.Figure 2
Confidentiality security model.Figure 3
Verifiability security model.Figure 4
Fully hidden security model.Figure 5
Traceability security model.


## 5. Construction and Application

The concrete construction of our MAABE scheme is presented in this section. Firstly, the CTA and all AA perform initialization and generate the PP and the public keys of AAs. Then, the DO can encrypt its data with an access structure. Before accessing the data, the DU needs to request its decryption key to the AAs. Next, the DU can access the data and decrypt successfully with the help of the cloud predecrypting for the DU first. Finally, the trace algorithm is used to reform the global identity of a guilty data user by the AAs. This section also contains a simple application in the end.


### 5.1. Concrete Construction

#### 5.1.1. Phase I: System Initialization

(1)
Systemset−up: this step is performed by the CTAIt defines two multiplicative groupG,GT of prime order p, and g is a generator of G.It defines a symmetric bilinear mape:G×G→GT.It defines three collusion resistant hash functions as follows:H:0.1∗→G,H1:0,1∗→ℤp∗,H2:0,1∗→0,1k where k is the length of the symmetric key.It defines a CPA-secure symmetric encryption schemeEncsym,Decsym.It outputs the global pubic parameterPP:
(1)PP=G,GT,p,e,g,H,H1,H2,Encsym,Decsym(2)
Authorityset−up: each attribute authority performs this step to get their key pair. We take the AAj as an exampleIt chooses two random numbersαi,βi∈ℤp∗ for each attribute i∈SA,AAj.It chooses three random numbershj,aj,bj∈ℤp∗.It generates its pair of private keyskAAj and public key pkAAj as follows:
(2)skAAj=αi,βii∈SAAj,hj,aj,bj,pkAAj=gαi,gβii∈SAAj,ghj,gaj,gbj.


#### 5.1.2. Phase II: Encryption

We assume that the DO encrypts a messageMSG with an self-defined access structure Ψ, and SΨ is the attribute set which contains all attributes in the access structure Ψ. This phase contains three steps defined below:
(1)
FullyHidetheaccesspolicyIt chooses a random numbera∈ℤp∗ and then computes qi=eghja,Hi where i∈SΨ.It replaces each attribute inSΨ with the corresponding qi.It converts the access policy to a LSSS access matrixMl×n,ρ.
(2)
EncryptthekeyseedIt chooses a random elementR∈GT (the key seed) to calculate s=H1R,MSG and the symmetric key Ksym=H2R.It selects api∈ℤp for each row Mi of M and two random vectors v→=s,v1,⋯,vn∈ℤpn,w→=0,w1,⋯,wn∈ℤpn.It computersλi=Mi×v→ and wi=Mi×w→.It outputs the tupleCTABE=h,Ml×n,ρ,C0,C1,i,C2,i,C3,i,C4,i,C5,ii∈1,l where i presents a matrix row corresponding to an attribute.Details of the ciphertext are presented as follows:(3)CT=h=ga,C0=Reg,gs,C1,i=gλigαρipi,C2,i=gpi,.C3,i=gwigβρipi,C4,i=gajpi,C5,i=gbjpi(3)
Encrypt the messageUsesKsym to encrypt the message MSG by the symmetric encryption algorithm Encsym and denote the result as CTsym=EncsymKsym,MSG.It uploadsCT=CTABE,CTsym to the CS.


#### 5.1.3. Phase III: Key Generation

(1)
Decryption keyEach user owns an unique global identityGID∈ℤp∗ and an attribute set SGID where each attribute is associated with a designed attribute authority. Let SAA,GID be the set of related attribute authorities. According to SAA,GID, we divide SGID into SGID,jj∈SAA,GID. When the user queries its decryption key, each related AA runs the key generation algorithm. We take the AAj as an instance.It chooses a random numberr∈ℤp∗\−aj+GID/bj for each i∈SGID,j.It computes and returns the decryption keyskGID,j=K1,i,K2,i,K3,ii∈SGID:
(4)K1,i=gαi/aj+GID+bjrHGIDβi/aj+GID+bjr,K2,i=Hihj,K3,i=r.The decryption key of the userGID is noted as
(5)skGID=skGID,jj∈SAA,GID,GID=K1,i,K2,i,K3,ii∈SGID,GID(2)
Outsourced decryption key: the data user runs this algorithm(a)
Reconstructs the access policyIt computesqi′=eh,Hihj=ega,Hihj,∀i∈SGID.It usesqi′ to replace the attribute i to get the attribute set SGID′.It gains the access structureMl×n,ρ from CT.It identifies the set of attributesL′=i:ρi∩SGID′i∈l required for the decryption.
(b)
Generates the outdec keyChooses a random numberz∈ℤp∗ to compute the outsourced decryption key okGID=opkGID,oskGID as
(6)opkGID=GID,K1,i1/z,K3,ii∈L′,g1/z,HGID1/z,oskGID=z.


#### 5.1.4. Phase IV: Decryption

(1)
Outsourceddecryption: the CS performs outsourced decryption for the userIt computes the following equation for each matrix row corresponding to an attributei:
(7)Q=eg1/z,C1,ieHGID1/z,C3,ieK1,i1/z,C2,iGIDC4,iC5,iK3,i=eg,gλieHGID,gwi1/z.It chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0.It Computes(8)∏i=1lQci=eg,g∑i=1lλicieg,HGID∑i=1lwici1/z,wherel is the row number of the access matrix.It returnsCT′=∏i=1lQci=eg,gs/z to the user.
(2)
Uerdecryption: this phase contains the following two steps(a)
Recovers the messageR based on the partially decrypted ciphertext CT′ by computing the following equation(9)R=C0CT′osk=C0eg,gs/zz=C0eg,gs.(note that this equation costs one exponentiation only and no pairing performance.)(b)
ComputesKsym=H2R, MSG=DecsymKsym,CTsym, and s=H1R,MSGJudge ifCT′=eg,gs/z. If no, outputs ⊥. Else, the user gains the right MSG.Correctness of Equation (7):Proof.
First for each attributei∈L′, the CS uses opkGID to compute:
(10)Q=eg1/z,gλigαρipieHGID1/z,gβρipigwiegαρi/zaj+GID+bjrHGIDβρi/zaj+GID+bjr,gpiGIDgajpigbjpir=eg,gλi/zeg,gαρipi/zeg,HGIDβρipi/zeg,HGIDwi/zeg,gαρipi/zeg,HGIDβρipi/z=eg,gλi/zeg,HGIDwi/z.
Then, it chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0. Because λi=Miv→ and wi=Miw→, so
(11)∑i=1lλici=∑i=1lMiv→ci=v→1,0,⋯,0=s,∑i=1lwici=∑i=1lMiw→ci=w→1,0,⋯,0=0.
Hence, we can get(12)CT′=∏i=1lQci=∏i=1leg,gciλρi/zeg,HGIDciwi/z=eg,g∑i=1lciλρi/zeg,HGID∑i=1lciwi/z=eg,gs/zeg,HGID0=eg,gs/z.
Then, based onCT′, the user recovers
(13)R=C0CT′osk=Reg,gseg,gs/zz=Reg,gseg,gs.


#### 5.1.5. Phase V: Trace

TheTracePP,skGID,pkAAj algorithm is performed by all attribute authorities. The input is the private key skGID=skGID,jj∈SAA′,GID=K1,i,K2,i,K3,ii∈SGID,GID of a user.Firstly, the AA checks the form of the key. If the key does not satisfies the form, this algorithm aborts.Then, the AA searches its database to find if∃i∈SGID, s.t.
(14)K1,i,K2,i∈G,K3,i,GID∈ℤp∗,eK1,i,gajgbjK3,igGID=eg,gαieHGID,gβi.If yes, the global identityGID of the guilty user will be output.


### 5.2. Application in the EHR System

In this section, we describe a simple application of our scheme based on the electronic health record (EHR) system. The basic procedures are presented in Figure6, and the details are described as follows:
(1)
The central trusted authority (the government) performs the system set-up algorithm to generate and publish the global parametersPP(2)
A set of management companies act as attribute authorities, and each attribute authority needs to set up first. Then, they publish their public keys while keeping private keys secret(3)
A hospital encrypts a patient’s medical recordsRd based on a user-defined access structure M and sends the ciphertext CT along with the fully hidden access structure n to the cloud storing server to store(15)Hospital→EncryptRd,M→CTCloud.(4)
Before a data user (a doctor) requests the wanted records from the cloud server, he/she needs to get the decryption keyskGID from the attribute authorities first(5)
To outsource the decryption work to the cloud server, the doctor generates the outsourced decryption keyopkGID based on skGID. Then, he/she sends opkGID to the cloud server(6)
The cloud server will partially decrypt for the doctor as long as his/her attribute set satisfies the encryption access structure. Then, the cloud sends the partially decrypted ciphertextCT′ back to the doctor(16)Cloud→DecryptoutopkGID,CT→CT′Doctor.(7)
Finally, the doctor can fully decrypt and get the medical records. Note that doctors only require one exponentiation inGT to fully decrypt, and one hash operation to verify whether the ciphertext was tampered(17)DecryptCT′→Rd.(8)
If a malicious user decrypt illegally with a valid decryption key, the attribute authorities can perform the trace algorithm to recover the identity of the guilty user who leaks his/her decryption key to a illegal userFigure 6
Application in an EHR system.


## 5.1. Concrete Construction

### 5.1.1. Phase I: System Initialization

(1)
Systemset−up: this step is performed by the CTAIt defines two multiplicative groupG,GT of prime order p, and g is a generator of G.It defines a symmetric bilinear mape:G×G→GT.It defines three collusion resistant hash functions as follows:H:0.1∗→G,H1:0,1∗→ℤp∗,H2:0,1∗→0,1k where k is the length of the symmetric key.It defines a CPA-secure symmetric encryption schemeEncsym,Decsym.It outputs the global pubic parameterPP:
(1)PP=G,GT,p,e,g,H,H1,H2,Encsym,Decsym(2)
Authorityset−up: each attribute authority performs this step to get their key pair. We take the AAj as an exampleIt chooses two random numbersαi,βi∈ℤp∗ for each attribute i∈SA,AAj.It chooses three random numbershj,aj,bj∈ℤp∗.It generates its pair of private keyskAAj and public key pkAAj as follows:
(2)skAAj=αi,βii∈SAAj,hj,aj,bj,pkAAj=gαi,gβii∈SAAj,ghj,gaj,gbj.


### 5.1.2. Phase II: Encryption

We assume that the DO encrypts a messageMSG with an self-defined access structure Ψ, and SΨ is the attribute set which contains all attributes in the access structure Ψ. This phase contains three steps defined below:
(1)
FullyHidetheaccesspolicyIt chooses a random numbera∈ℤp∗ and then computes qi=eghja,Hi where i∈SΨ.It replaces each attribute inSΨ with the corresponding qi.It converts the access policy to a LSSS access matrixMl×n,ρ.
(2)
EncryptthekeyseedIt chooses a random elementR∈GT (the key seed) to calculate s=H1R,MSG and the symmetric key Ksym=H2R.It selects api∈ℤp for each row Mi of M and two random vectors v→=s,v1,⋯,vn∈ℤpn,w→=0,w1,⋯,wn∈ℤpn.It computersλi=Mi×v→ and wi=Mi×w→.It outputs the tupleCTABE=h,Ml×n,ρ,C0,C1,i,C2,i,C3,i,C4,i,C5,ii∈1,l where i presents a matrix row corresponding to an attribute.Details of the ciphertext are presented as follows:(3)CT=h=ga,C0=Reg,gs,C1,i=gλigαρipi,C2,i=gpi,.C3,i=gwigβρipi,C4,i=gajpi,C5,i=gbjpi(3)
Encrypt the messageUsesKsym to encrypt the message MSG by the symmetric encryption algorithm Encsym and denote the result as CTsym=EncsymKsym,MSG.It uploadsCT=CTABE,CTsym to the CS.


### 5.1.3. Phase III: Key Generation

(1)
Decryption keyEach user owns an unique global identityGID∈ℤp∗ and an attribute set SGID where each attribute is associated with a designed attribute authority. Let SAA,GID be the set of related attribute authorities. According to SAA,GID, we divide SGID into SGID,jj∈SAA,GID. When the user queries its decryption key, each related AA runs the key generation algorithm. We take the AAj as an instance.It chooses a random numberr∈ℤp∗\−aj+GID/bj for each i∈SGID,j.It computes and returns the decryption keyskGID,j=K1,i,K2,i,K3,ii∈SGID:
(4)K1,i=gαi/aj+GID+bjrHGIDβi/aj+GID+bjr,K2,i=Hihj,K3,i=r.The decryption key of the userGID is noted as
(5)skGID=skGID,jj∈SAA,GID,GID=K1,i,K2,i,K3,ii∈SGID,GID(2)
Outsourced decryption key: the data user runs this algorithm(a)
Reconstructs the access policyIt computesqi′=eh,Hihj=ega,Hihj,∀i∈SGID.It usesqi′ to replace the attribute i to get the attribute set SGID′.It gains the access structureMl×n,ρ from CT.It identifies the set of attributesL′=i:ρi∩SGID′i∈l required for the decryption.
(b)
Generates the outdec keyChooses a random numberz∈ℤp∗ to compute the outsourced decryption key okGID=opkGID,oskGID as
(6)opkGID=GID,K1,i1/z,K3,ii∈L′,g1/z,HGID1/z,oskGID=z.


### 5.1.4. Phase IV: Decryption

(1)
Outsourceddecryption: the CS performs outsourced decryption for the userIt computes the following equation for each matrix row corresponding to an attributei:
(7)Q=eg1/z,C1,ieHGID1/z,C3,ieK1,i1/z,C2,iGIDC4,iC5,iK3,i=eg,gλieHGID,gwi1/z.It chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0.It Computes(8)∏i=1lQci=eg,g∑i=1lλicieg,HGID∑i=1lwici1/z,wherel is the row number of the access matrix.It returnsCT′=∏i=1lQci=eg,gs/z to the user.
(2)
Uerdecryption: this phase contains the following two steps(a)
Recovers the messageR based on the partially decrypted ciphertext CT′ by computing the following equation(9)R=C0CT′osk=C0eg,gs/zz=C0eg,gs.(note that this equation costs one exponentiation only and no pairing performance.)(b)
ComputesKsym=H2R, MSG=DecsymKsym,CTsym, and s=H1R,MSGJudge ifCT′=eg,gs/z. If no, outputs ⊥. Else, the user gains the right MSG.Correctness of Equation (7):Proof.
First for each attributei∈L′, the CS uses opkGID to compute:
(10)Q=eg1/z,gλigαρipieHGID1/z,gβρipigwiegαρi/zaj+GID+bjrHGIDβρi/zaj+GID+bjr,gpiGIDgajpigbjpir=eg,gλi/zeg,gαρipi/zeg,HGIDβρipi/zeg,HGIDwi/zeg,gαρipi/zeg,HGIDβρipi/z=eg,gλi/zeg,HGIDwi/z.
Then, it chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0. Because λi=Miv→ and wi=Miw→, so
(11)∑i=1lλici=∑i=1lMiv→ci=v→1,0,⋯,0=s,∑i=1lwici=∑i=1lMiw→ci=w→1,0,⋯,0=0.
Hence, we can get(12)CT′=∏i=1lQci=∏i=1leg,gciλρi/zeg,HGIDciwi/z=eg,g∑i=1lciλρi/zeg,HGID∑i=1lciwi/z=eg,gs/zeg,HGID0=eg,gs/z.
Then, based onCT′, the user recovers
(13)R=C0CT′osk=Reg,gseg,gs/zz=Reg,gseg,gs.


### 5.1.5. Phase V: Trace

TheTracePP,skGID,pkAAj algorithm is performed by all attribute authorities. The input is the private key skGID=skGID,jj∈SAA′,GID=K1,i,K2,i,K3,ii∈SGID,GID of a user.Firstly, the AA checks the form of the key. If the key does not satisfies the form, this algorithm aborts.Then, the AA searches its database to find if∃i∈SGID, s.t.
(14)K1,i,K2,i∈G,K3,i,GID∈ℤp∗,eK1,i,gajgbjK3,igGID=eg,gαieHGID,gβi.If yes, the global identityGID of the guilty user will be output.


## 5.1.1. Phase I: System Initialization

(1)
Systemset−up: this step is performed by the CTAIt defines two multiplicative groupG,GT of prime order p, and g is a generator of G.It defines a symmetric bilinear mape:G×G→GT.It defines three collusion resistant hash functions as follows:H:0.1∗→G,H1:0,1∗→ℤp∗,H2:0,1∗→0,1k where k is the length of the symmetric key.It defines a CPA-secure symmetric encryption schemeEncsym,Decsym.It outputs the global pubic parameterPP:
(1)PP=G,GT,p,e,g,H,H1,H2,Encsym,Decsym(2)
Authorityset−up: each attribute authority performs this step to get their key pair. We take the AAj as an exampleIt chooses two random numbersαi,βi∈ℤp∗ for each attribute i∈SA,AAj.It chooses three random numbershj,aj,bj∈ℤp∗.It generates its pair of private keyskAAj and public key pkAAj as follows:
(2)skAAj=αi,βii∈SAAj,hj,aj,bj,pkAAj=gαi,gβii∈SAAj,ghj,gaj,gbj.


## 5.1.2. Phase II: Encryption

We assume that the DO encrypts a messageMSG with an self-defined access structure Ψ, and SΨ is the attribute set which contains all attributes in the access structure Ψ. This phase contains three steps defined below:
(1)
FullyHidetheaccesspolicyIt chooses a random numbera∈ℤp∗ and then computes qi=eghja,Hi where i∈SΨ.It replaces each attribute inSΨ with the corresponding qi.It converts the access policy to a LSSS access matrixMl×n,ρ.
(2)
EncryptthekeyseedIt chooses a random elementR∈GT (the key seed) to calculate s=H1R,MSG and the symmetric key Ksym=H2R.It selects api∈ℤp for each row Mi of M and two random vectors v→=s,v1,⋯,vn∈ℤpn,w→=0,w1,⋯,wn∈ℤpn.It computersλi=Mi×v→ and wi=Mi×w→.It outputs the tupleCTABE=h,Ml×n,ρ,C0,C1,i,C2,i,C3,i,C4,i,C5,ii∈1,l where i presents a matrix row corresponding to an attribute.Details of the ciphertext are presented as follows:(3)CT=h=ga,C0=Reg,gs,C1,i=gλigαρipi,C2,i=gpi,.C3,i=gwigβρipi,C4,i=gajpi,C5,i=gbjpi(3)
Encrypt the messageUsesKsym to encrypt the message MSG by the symmetric encryption algorithm Encsym and denote the result as CTsym=EncsymKsym,MSG.It uploadsCT=CTABE,CTsym to the CS.


## 5.1.3. Phase III: Key Generation

(1)
Decryption keyEach user owns an unique global identityGID∈ℤp∗ and an attribute set SGID where each attribute is associated with a designed attribute authority. Let SAA,GID be the set of related attribute authorities. According to SAA,GID, we divide SGID into SGID,jj∈SAA,GID. When the user queries its decryption key, each related AA runs the key generation algorithm. We take the AAj as an instance.It chooses a random numberr∈ℤp∗\−aj+GID/bj for each i∈SGID,j.It computes and returns the decryption keyskGID,j=K1,i,K2,i,K3,ii∈SGID:
(4)K1,i=gαi/aj+GID+bjrHGIDβi/aj+GID+bjr,K2,i=Hihj,K3,i=r.The decryption key of the userGID is noted as
(5)skGID=skGID,jj∈SAA,GID,GID=K1,i,K2,i,K3,ii∈SGID,GID(2)
Outsourced decryption key: the data user runs this algorithm(a)
Reconstructs the access policyIt computesqi′=eh,Hihj=ega,Hihj,∀i∈SGID.It usesqi′ to replace the attribute i to get the attribute set SGID′.It gains the access structureMl×n,ρ from CT.It identifies the set of attributesL′=i:ρi∩SGID′i∈l required for the decryption.
(b)
Generates the outdec keyChooses a random numberz∈ℤp∗ to compute the outsourced decryption key okGID=opkGID,oskGID as
(6)opkGID=GID,K1,i1/z,K3,ii∈L′,g1/z,HGID1/z,oskGID=z.


## 5.1.4. Phase IV: Decryption

(1)
Outsourceddecryption: the CS performs outsourced decryption for the userIt computes the following equation for each matrix row corresponding to an attributei:
(7)Q=eg1/z,C1,ieHGID1/z,C3,ieK1,i1/z,C2,iGIDC4,iC5,iK3,i=eg,gλieHGID,gwi1/z.It chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0.It Computes(8)∏i=1lQci=eg,g∑i=1lλicieg,HGID∑i=1lwici1/z,wherel is the row number of the access matrix.It returnsCT′=∏i=1lQci=eg,gs/z to the user.
(2)
Uerdecryption: this phase contains the following two steps(a)
Recovers the messageR based on the partially decrypted ciphertext CT′ by computing the following equation(9)R=C0CT′osk=C0eg,gs/zz=C0eg,gs.(note that this equation costs one exponentiation only and no pairing performance.)(b)
ComputesKsym=H2R, MSG=DecsymKsym,CTsym, and s=H1R,MSGJudge ifCT′=eg,gs/z. If no, outputs ⊥. Else, the user gains the right MSG.Correctness of Equation (7):Proof.
First for each attributei∈L′, the CS uses opkGID to compute:
(10)Q=eg1/z,gλigαρipieHGID1/z,gβρipigwiegαρi/zaj+GID+bjrHGIDβρi/zaj+GID+bjr,gpiGIDgajpigbjpir=eg,gλi/zeg,gαρipi/zeg,HGIDβρipi/zeg,HGIDwi/zeg,gαρipi/zeg,HGIDβρipi/z=eg,gλi/zeg,HGIDwi/z.
Then, it chooses a set of constantscii∈1,l∈ℤp such that ∑iciMi=1,0,⋯,0. Because λi=Miv→ and wi=Miw→, so
(11)∑i=1lλici=∑i=1lMiv→ci=v→1,0,⋯,0=s,∑i=1lwici=∑i=1lMiw→ci=w→1,0,⋯,0=0.
Hence, we can get(12)CT′=∏i=1lQci=∏i=1leg,gciλρi/zeg,HGIDciwi/z=eg,g∑i=1lciλρi/zeg,HGID∑i=1lciwi/z=eg,gs/zeg,HGID0=eg,gs/z.
Then, based onCT′, the user recovers
(13)R=C0CT′osk=Reg,gseg,gs/zz=Reg,gseg,gs.


## 5.1.5. Phase V: Trace

TheTracePP,skGID,pkAAj algorithm is performed by all attribute authorities. The input is the private key skGID=skGID,jj∈SAA′,GID=K1,i,K2,i,K3,ii∈SGID,GID of a user.Firstly, the AA checks the form of the key. If the key does not satisfies the form, this algorithm aborts.Then, the AA searches its database to find if∃i∈SGID, s.t.
(14)K1,i,K2,i∈G,K3,i,GID∈ℤp∗,eK1,i,gajgbjK3,igGID=eg,gαieHGID,gβi.If yes, the global identityGID of the guilty user will be output.


## 5.2. Application in the EHR System

In this section, we describe a simple application of our scheme based on the electronic health record (EHR) system. The basic procedures are presented in Figure6, and the details are described as follows:
(1)
The central trusted authority (the government) performs the system set-up algorithm to generate and publish the global parametersPP(2)
A set of management companies act as attribute authorities, and each attribute authority needs to set up first. Then, they publish their public keys while keeping private keys secret(3)
A hospital encrypts a patient’s medical recordsRd based on a user-defined access structure M and sends the ciphertext CT along with the fully hidden access structure n to the cloud storing server to store(15)Hospital→EncryptRd,M→CTCloud.(4)
Before a data user (a doctor) requests the wanted records from the cloud server, he/she needs to get the decryption keyskGID from the attribute authorities first(5)
To outsource the decryption work to the cloud server, the doctor generates the outsourced decryption keyopkGID based on skGID. Then, he/she sends opkGID to the cloud server(6)
The cloud server will partially decrypt for the doctor as long as his/her attribute set satisfies the encryption access structure. Then, the cloud sends the partially decrypted ciphertextCT′ back to the doctor(16)Cloud→DecryptoutopkGID,CT→CT′Doctor.(7)
Finally, the doctor can fully decrypt and get the medical records. Note that doctors only require one exponentiation inGT to fully decrypt, and one hash operation to verify whether the ciphertext was tampered(17)DecryptCT′→Rd.(8)
If a malicious user decrypt illegally with a valid decryption key, the attribute authorities can perform the trace algorithm to recover the identity of the guilty user who leaks his/her decryption key to a illegal userFigure 6
Application in an EHR system.


## 6. Security Analysis

### 6.1. Indistinguishability

Theorem 1.
If Lewko et al.’s scheme [8] is CPA=secure, our multiauthority attribute-based encryption scheme is selectively replayable CCA-secure according to Definition 6 such that AdvAExpConf<AdvAExpLewko.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(1) with an entity B. B running Lewko et al.’s CPA-secure [8] experiment with a challenger ℂ. The proof described below is going to show that the advantage of A to win the experiment ExpConf is smaller than the advantage of B to win Lewko et al.’s CPA-secure experiment ExpLewko. The detailed interactions are described as follows:
(1)
Initialization: the adversaryA submits a challenge access policy Ψ∗=M∗,ρ∗ to the challenge ℂ through B(2)
Set-Up:ℂ runs the Setupλ algorithm to generate the global parameter PP
It chooses two multiplicative cyclic groupsG,GT of prime order p with a generator g of G.
It chooses a bilinear mape:G×G→GT.
It chooses three collusion-resistant hash functionsH∗:0,1∗→G,H1∗:0,1∗→ℤp∗,H2∗:0,1∗→0,1k.
It chooses a cpa-secure symmetric encryption schemeEncsym,Decsym.
It sends the global parameterPP=G,GT,p,e,g,H∗,H1∗,H2∗,Encsym,Decsym to A through B.
It runs theSetupauth algorithm to generate the key pairs of the noncorrupted authorities:
It chooses two random numbersαiandβi∈ℤp∗ for each attribute i∈SA,AAj.
It chooses three random numbershj,aj,andbj∈ℤp∗ to compute the public key pkAAj=gαi,gβii∈SA,AAj,ghj,gaj,gbj.
It sends all attribute authorities’ public keys toA through B.
A runs the Setupauth algorithm to generate the key pairs of the corrupted authorities in the same way.
(3)
Query phase I:B initializes three empty tables T, T1, T2, an empty set D, and an integer j=0. Details of queries are described as follows:(a)
Hash query
H1∗ oracle: if the entry R,MSG,s already existed in Table T1, return s. Otherwise, it chooses a random element s∈ℤp∗ (s is unique in Table T1). Then, it records R,MSG,s in Table T1 and returns s.
H2∗ oracle: if the entry R,Ksym already existed in Table T2, return Ksym. Otherwise, it chooses a random element Ksym∈0,1k. Then, it records R,Ksym in Table T2 and returns Ksym.
(b)
Key query: In theq-th query, A queries the decryption key related with an attribute set SGIDq by sending SGIDq and GIDq to B. B calls ℂ to generate the decryption key and sends it to A. ℂ chooses a random number r∈ℤp∗\−aj+GIDq/bj to compute the decryption key skGIDq=skGIDq,jj∈SAA,GID,GID=K1,i,K2,i,K3,ii∈SGID,GID while setting D=D∪SGIDq(18)K1,i=gαi/aj+GIDq+bjH∗GIDqti/aj+GIDq+bj,K2,i=H∗ihj,K3,i=r.
B chooses a random element a∈ℤp∗ to compute h=ga to simulate the output of the encryption algorithm. B calls ℂ to run the outsourced decryption key generation algorithm: ℂ chooses a random number z∈ℤp∗ to compute
(19)opkGIDq=K1,i1/zi∈L′,g1/z,H∗GID1/z,oskGIDq=z.
SendsokGIDq=opkGIDq,oskGIDq to B. B stores the entry q,SGIDq,skGIDq,okGIDq in the table T. Finally, B returns the key to A.
(c)
Decryption query: without loss of generality, we assume that all ciphertexts input to this query have been partially decrypted. For instance, we assume thatCT′ was correctly decrypted by opk of the entry q,SGIDq,skGIDq,okGIDq. Let CT′ be associated with a structure M,ρ which is not equal with M∗,ρ∗. Let opk be associated with a set of attributes which satisfies M,ρ and not satisfies M∗,ρ∗
Search TableT1 to find if there exists an entry R,MSG,s which satisfies CT′oskGIDq=eg,gs. If not, abort. Else, obtain entry R,Ksym in Table T2. If this entry does not exist, abort. Else, test if C0=Reg,gs and CTsym=EncsymKsym,MSG. If yes, output MSG. Else, abort.
(4)
Challenge:A chooses two message MSG1,MSG2∈0,1∗ with same length then sends them to B. B chooses two message R0,R1∈GT with same length and then sends them to ℂ. ℂ chooses a random bit b∈0,1, then ℂ encrypts Rb under the access structure M∗,ρ∗ by running Lewko’s scheme. Finally, ℂ returns CTb,ABE∗ to B. B guesses b with advantage AdvAExpLewko. Then, B computes Ksym∗=H2∗Rb∗ and CTb,sym∗=EncsymKsym∗,MSGb. Finally, B returns CTb∗=CTb,ABE∗,CTb,sym∗ to A(5)
Query phase II: the adversaryA can query a polynomially bounded number of queries as in query phase II after receiving the ciphertext CTb∗ with restrictions that the queried attribute set cannot satisfy the challenge access structure, and the response of the decryption query cannot be either MSG0 or MSG1(6)
Guess:A tries to guess b′ based on CTb∗. Then, A sends b′ to ℂ through B. If b′=b, we say that A wins this experiment
We can easily get that the advantage ofA to win the experiment Expconf is smaller than the advantage of B to win the experiment ExpLewko, because A has to be based on the right CTb∗ provided by B to guess b successfully. In other words, PrExpALewko1ξ>PrExpAConf−Real1ξ and our scheme achieve selectively replayable CCA secure.


### 6.2. Verifiability

Theorem 2.
IfH1 and H2 are two collision-resistant hash functions, our scheme is verifiable against malicious servers.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(2) with an entity B. B tries to break the collision resistance of the two hash functions H1∗ and H2∗.
(1)
Initialization: the adversaryA submits a challenge access policy Ψ∗=M∗,ρ∗ to the entity B(2)
Set-up:B runs the Setup algorithm to generate the global parameter except the two hash functions(3)
B runs the Setupauth algorithm to generate keypairs of attribute authorities.
Query:A runs the adversary queries as defined in query phase I and query phase II through B to get the related decryption keys and outsourced decryption keys
(4)
Challenge:A sends the challenge message MSG∗ to B, and B answers as follows
It chooses a random messageR∗∈GT to run Lewko’s encryption scheme to encrypt R∗ under the access policy M∗,ρ∗.
It computess∗=H1∗R∗MSG∗ and Ksym∗=H2∗R∗.
It runs the symmetric encrypt algorithm to encryptMSG∗ to generate the ciphertext CT∗=CTABE∗,CTsym∗=h,C0,C1,i,C2,i,C3,i,C4,i,C5,i,CTsym∗.
It returns the ciphertextCT∗=CTABE∗,CTsym∗ to A.
IfB can recover a message MSG∈MSG∗,⊥, then we say A wins this experiment. Hence there are two cases are considered:
(1)
MSG,R≠MSG∗,R∗, which means that B finds a collision of the hash function H1∗(2)
Ksym,CTsym=Ksym∗,CTsym∗ but R∗≠R, which means that B breaks the collision resistance condition of H2∗ such as H2∗R=Ksym=Ksym∗=H2∗R∗
In other words, sinceH1 and H2 are two collision-resistant hash functions, the outsourced decryption of our scheme is verifiable.


### 6.3. Fully Hiding

Theorem 3.
Our scheme is an outsourced ABE with fully hidden policy if the one-way anonymous key agreement protocol [15] is IND-CPA secure.Proof.
The purpose of this proof is that no PPT adversary can recover the access policy without the right decryption key. The setup phase and the query phase 1 are same as the confidentiality experiment.
In the challenge phase, the adversaryA chooses two challenge messages R0∗,R1∗ and two valid access policies Ψ0,Ψ1, and then it sends them to the challenger ℂ. Notice, Ψ0andΨ1 satisfy the following restriction: either all the attribute sets queried in query phase 1 satisfy none of the policy or all attribute sets satisfy both the policies. Then, ℂ computes q′i=eghja,Hi based on the one-way anonymous key agreement protocol where a∈ℤp∗ is a random number. This step is used to hide the real policy by replacing each attributes in the policy with the corresponding q′i. Then, ℂ chooses a random bit b∈0,1 and encrypts the message Rb∗ under the access policy Ψb. Finally, ℂ sends CT∗ to A. After that, A still can query a polynomially bounded number of queries as in query phase I. The none-or-both principle still works in this phase.
In the guess phase,A outputs b′.
WhenA tries to decrypt CT∗, it has to recover the access policy first. In our scheme, the decryption key K2,i=Hihj is necessary for it to compute q′i because we computed the q′i based on the one-way anonymous key agreement protocol before we encrypted the message. It means only the authorized user can get the right access policy. And due to the random value a, unauthorized user cannot guess attribute i from q′i which prevents the collusion of the users. Hence, the advantage of the adversary to win the experiment AdvAExpPriv1ξ is negligible, and our scheme ensures the privacy preservation of the access policy against adaptive chosen plaintext attack.


### 6.4. Traceability

In this section, we prove that our scheme is fully traceable under theq-SDH assumption.Lemma 1.
Our scheme achieves fully user traceability based on that the Boneh-Boyen fully signature scheme [31] is strong existential forgery secure against adaptive chosen message attack.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(4) to attack our scheme through an entity B by B breaking the Boneh-Boyen fully signature scheme with the same advantage under adaptive chosen message attacks. Assuming the advantage of the adversary A to break our scheme is ε, and B can access a random oracle H. Let ℂ be the challenger in the B-B scheme, Sigj∈G be the signature of AAj, and pkAAjsig=G,p,g,gaj,gbj is the associated public key of Sigj.
(1)
Set-up: the challengerℂ runs the Setup algorithm to generate the global parameter PP and sends PP to B. For each noncorrupted authorities in the set S′, ℂ sends pkAAjsig to B. Then, B chooses two random numbers αi,βi for each attribute in the attribute set of the authority, and then B chooses a random number hj to generate the public key of the authority pkAAj=gαi,gβii∈SA,AAj,ghj,gaj,gbj. Finally, B returns PP and pkAAjj∈S′ to A. For corrupted authorities, A runs the Setupauth algorithm to generate the key pairs for them(2)
Key query:A runs m queries. In the q-th query, A sends SGIDq,GIDq to B. B initiates an empty table T and do the following steps(a)
Accesses the random oracleHGIDq: B searches the entry GIDq,tGIDq,gtGIDq in the table T, and if it exists, B outputs gtGIDq. Else, B chooses a random number tGIDq while stores GIDq,tGIDq,gtGIDq in the table T. B outputs gtGIDq(b)
Generates the decryption keyskGIDq,j: ℂ chooses a random number r∈ℤp∗\−aj+GIDq/bj for each attribute i∈SGIDq,j and returns the signature r,σ=g1/aj+GIDq+bjr. Then, B computes the components of skGIDq,j(20)K1,i=σαi+βitGIDq=gαi+βitGIDq/aj+GIDq+bjr=gαi/aj+GIDq+bjrgtGIDqβi/aj+GIDq+bjr=gαi/aj+GIDq+bjrHGIDqβi/aj+GIDq+bjr,K2,i=Hihj,K3,i=r.
Then,B sets D=D∪SGIDq. Finally B returns the following result to A:
(21)skGIDq=skGIDq,jj∈SAA,GID,GIDq=K1,i,K2,i,K3,ii∈SGIDq,GIDq.(3)
Key forgery:A sends a sk∗ to B. The advantage of the adversary to win is defined as(22)PrTracePP,pkAAj,sk∗∈⊥,GID1,⋯,GIDm=ε,where GID1,⋯,GIDm is mGID queried in the last phase. If TracePP,pkAAj,sk∗∈⊥,GID1,⋯,GIDm, it means sk∗=K1,i,K2,i,K3,ii∈SGID,GID passed the form check and GID∈⊥,GID1,⋯,GIDm. Hence, ∃i∈S, s.t.
(23)K1,i,K2,i∈G,K3,i,GID∈ℤp,∗eK1,i,gajgbjK3,igGID=eg,gαieHGID,gti.Without loss of generality, we assume the adversary A accessed the random oracle HGID before it outputs the sk∗. B obtains the entry GID,tGID,gtGID from the table T. According to eK1,i,gajgbjK3,igGID=eg,gαieHGID,gβi, we can get K1,i=gαi+tGIDβi/aj+bjK3,i+GID. Then, B computes the signature σj=K1,i1/αi+tGIDβi. Because GID,K3,i∈ℤp∗, hence K3,i,σj is a valid signature on message GID in the B-B signature scheme. Because GID∈GID1,⋯,GIDm, it means B never queried the signature of GID before, and the advantage of B to break the B-B scheme is equal with the advantage of the adversary A to break our scheme, which is ε.According to the Boneh-Boyen signature scheme, we can also get the following lemma.Lemma 2.
If theq-SDH assumption holds in the group G, the full signature scheme of Boneh and Boyen is strong existential forgery secure against adaptive chosen message attacks.Theorem 4.
If theq-SDH assumption holds in the group G, our scheme achieves fully user traceability.Proof.
It follows directly from the above Lemma1 and Lemma 2.


## 6.1. Indistinguishability

Theorem 1.
If Lewko et al.’s scheme [8] is CPA=secure, our multiauthority attribute-based encryption scheme is selectively replayable CCA-secure according to Definition 6 such that AdvAExpConf<AdvAExpLewko.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(1) with an entity B. B running Lewko et al.’s CPA-secure [8] experiment with a challenger ℂ. The proof described below is going to show that the advantage of A to win the experiment ExpConf is smaller than the advantage of B to win Lewko et al.’s CPA-secure experiment ExpLewko. The detailed interactions are described as follows:
(1)
Initialization: the adversaryA submits a challenge access policy Ψ∗=M∗,ρ∗ to the challenge ℂ through B(2)
Set-Up:ℂ runs the Setupλ algorithm to generate the global parameter PP
It chooses two multiplicative cyclic groupsG,GT of prime order p with a generator g of G.
It chooses a bilinear mape:G×G→GT.
It chooses three collusion-resistant hash functionsH∗:0,1∗→G,H1∗:0,1∗→ℤp∗,H2∗:0,1∗→0,1k.
It chooses a cpa-secure symmetric encryption schemeEncsym,Decsym.
It sends the global parameterPP=G,GT,p,e,g,H∗,H1∗,H2∗,Encsym,Decsym to A through B.
It runs theSetupauth algorithm to generate the key pairs of the noncorrupted authorities:
It chooses two random numbersαiandβi∈ℤp∗ for each attribute i∈SA,AAj.
It chooses three random numbershj,aj,andbj∈ℤp∗ to compute the public key pkAAj=gαi,gβii∈SA,AAj,ghj,gaj,gbj.
It sends all attribute authorities’ public keys toA through B.
A runs the Setupauth algorithm to generate the key pairs of the corrupted authorities in the same way.
(3)
Query phase I:B initializes three empty tables T, T1, T2, an empty set D, and an integer j=0. Details of queries are described as follows:(a)
Hash query
H1∗ oracle: if the entry R,MSG,s already existed in Table T1, return s. Otherwise, it chooses a random element s∈ℤp∗ (s is unique in Table T1). Then, it records R,MSG,s in Table T1 and returns s.
H2∗ oracle: if the entry R,Ksym already existed in Table T2, return Ksym. Otherwise, it chooses a random element Ksym∈0,1k. Then, it records R,Ksym in Table T2 and returns Ksym.
(b)
Key query: In theq-th query, A queries the decryption key related with an attribute set SGIDq by sending SGIDq and GIDq to B. B calls ℂ to generate the decryption key and sends it to A. ℂ chooses a random number r∈ℤp∗\−aj+GIDq/bj to compute the decryption key skGIDq=skGIDq,jj∈SAA,GID,GID=K1,i,K2,i,K3,ii∈SGID,GID while setting D=D∪SGIDq(18)K1,i=gαi/aj+GIDq+bjH∗GIDqti/aj+GIDq+bj,K2,i=H∗ihj,K3,i=r.
B chooses a random element a∈ℤp∗ to compute h=ga to simulate the output of the encryption algorithm. B calls ℂ to run the outsourced decryption key generation algorithm: ℂ chooses a random number z∈ℤp∗ to compute
(19)opkGIDq=K1,i1/zi∈L′,g1/z,H∗GID1/z,oskGIDq=z.
SendsokGIDq=opkGIDq,oskGIDq to B. B stores the entry q,SGIDq,skGIDq,okGIDq in the table T. Finally, B returns the key to A.
(c)
Decryption query: without loss of generality, we assume that all ciphertexts input to this query have been partially decrypted. For instance, we assume thatCT′ was correctly decrypted by opk of the entry q,SGIDq,skGIDq,okGIDq. Let CT′ be associated with a structure M,ρ which is not equal with M∗,ρ∗. Let opk be associated with a set of attributes which satisfies M,ρ and not satisfies M∗,ρ∗
Search TableT1 to find if there exists an entry R,MSG,s which satisfies CT′oskGIDq=eg,gs. If not, abort. Else, obtain entry R,Ksym in Table T2. If this entry does not exist, abort. Else, test if C0=Reg,gs and CTsym=EncsymKsym,MSG. If yes, output MSG. Else, abort.
(4)
Challenge:A chooses two message MSG1,MSG2∈0,1∗ with same length then sends them to B. B chooses two message R0,R1∈GT with same length and then sends them to ℂ. ℂ chooses a random bit b∈0,1, then ℂ encrypts Rb under the access structure M∗,ρ∗ by running Lewko’s scheme. Finally, ℂ returns CTb,ABE∗ to B. B guesses b with advantage AdvAExpLewko. Then, B computes Ksym∗=H2∗Rb∗ and CTb,sym∗=EncsymKsym∗,MSGb. Finally, B returns CTb∗=CTb,ABE∗,CTb,sym∗ to A(5)
Query phase II: the adversaryA can query a polynomially bounded number of queries as in query phase II after receiving the ciphertext CTb∗ with restrictions that the queried attribute set cannot satisfy the challenge access structure, and the response of the decryption query cannot be either MSG0 or MSG1(6)
Guess:A tries to guess b′ based on CTb∗. Then, A sends b′ to ℂ through B. If b′=b, we say that A wins this experiment
We can easily get that the advantage ofA to win the experiment Expconf is smaller than the advantage of B to win the experiment ExpLewko, because A has to be based on the right CTb∗ provided by B to guess b successfully. In other words, PrExpALewko1ξ>PrExpAConf−Real1ξ and our scheme achieve selectively replayable CCA secure.


## 6.2. Verifiability

Theorem 2.
IfH1 and H2 are two collision-resistant hash functions, our scheme is verifiable against malicious servers.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(2) with an entity B. B tries to break the collision resistance of the two hash functions H1∗ and H2∗.
(1)
Initialization: the adversaryA submits a challenge access policy Ψ∗=M∗,ρ∗ to the entity B(2)
Set-up:B runs the Setup algorithm to generate the global parameter except the two hash functions(3)
B runs the Setupauth algorithm to generate keypairs of attribute authorities.
Query:A runs the adversary queries as defined in query phase I and query phase II through B to get the related decryption keys and outsourced decryption keys
(4)
Challenge:A sends the challenge message MSG∗ to B, and B answers as follows
It chooses a random messageR∗∈GT to run Lewko’s encryption scheme to encrypt R∗ under the access policy M∗,ρ∗.
It computess∗=H1∗R∗MSG∗ and Ksym∗=H2∗R∗.
It runs the symmetric encrypt algorithm to encryptMSG∗ to generate the ciphertext CT∗=CTABE∗,CTsym∗=h,C0,C1,i,C2,i,C3,i,C4,i,C5,i,CTsym∗.
It returns the ciphertextCT∗=CTABE∗,CTsym∗ to A.
IfB can recover a message MSG∈MSG∗,⊥, then we say A wins this experiment. Hence there are two cases are considered:
(1)
MSG,R≠MSG∗,R∗, which means that B finds a collision of the hash function H1∗(2)
Ksym,CTsym=Ksym∗,CTsym∗ but R∗≠R, which means that B breaks the collision resistance condition of H2∗ such as H2∗R=Ksym=Ksym∗=H2∗R∗
In other words, sinceH1 and H2 are two collision-resistant hash functions, the outsourced decryption of our scheme is verifiable.


## 6.3. Fully Hiding

Theorem 3.
Our scheme is an outsourced ABE with fully hidden policy if the one-way anonymous key agreement protocol [15] is IND-CPA secure.Proof.
The purpose of this proof is that no PPT adversary can recover the access policy without the right decryption key. The setup phase and the query phase 1 are same as the confidentiality experiment.
In the challenge phase, the adversaryA chooses two challenge messages R0∗,R1∗ and two valid access policies Ψ0,Ψ1, and then it sends them to the challenger ℂ. Notice, Ψ0andΨ1 satisfy the following restriction: either all the attribute sets queried in query phase 1 satisfy none of the policy or all attribute sets satisfy both the policies. Then, ℂ computes q′i=eghja,Hi based on the one-way anonymous key agreement protocol where a∈ℤp∗ is a random number. This step is used to hide the real policy by replacing each attributes in the policy with the corresponding q′i. Then, ℂ chooses a random bit b∈0,1 and encrypts the message Rb∗ under the access policy Ψb. Finally, ℂ sends CT∗ to A. After that, A still can query a polynomially bounded number of queries as in query phase I. The none-or-both principle still works in this phase.
In the guess phase,A outputs b′.
WhenA tries to decrypt CT∗, it has to recover the access policy first. In our scheme, the decryption key K2,i=Hihj is necessary for it to compute q′i because we computed the q′i based on the one-way anonymous key agreement protocol before we encrypted the message. It means only the authorized user can get the right access policy. And due to the random value a, unauthorized user cannot guess attribute i from q′i which prevents the collusion of the users. Hence, the advantage of the adversary to win the experiment AdvAExpPriv1ξ is negligible, and our scheme ensures the privacy preservation of the access policy against adaptive chosen plaintext attack.


## 6.4. Traceability

In this section, we prove that our scheme is fully traceable under theq-SDH assumption.Lemma 1.
Our scheme achieves fully user traceability based on that the Boneh-Boyen fully signature scheme [31] is strong existential forgery secure against adaptive chosen message attack.Proof.
We define a PPT adversaryA running the experiment defined in Section 4.3(4) to attack our scheme through an entity B by B breaking the Boneh-Boyen fully signature scheme with the same advantage under adaptive chosen message attacks. Assuming the advantage of the adversary A to break our scheme is ε, and B can access a random oracle H. Let ℂ be the challenger in the B-B scheme, Sigj∈G be the signature of AAj, and pkAAjsig=G,p,g,gaj,gbj is the associated public key of Sigj.
(1)
Set-up: the challengerℂ runs the Setup algorithm to generate the global parameter PP and sends PP to B. For each noncorrupted authorities in the set S′, ℂ sends pkAAjsig to B. Then, B chooses two random numbers αi,βi for each attribute in the attribute set of the authority, and then B chooses a random number hj to generate the public key of the authority pkAAj=gαi,gβii∈SA,AAj,ghj,gaj,gbj. Finally, B returns PP and pkAAjj∈S′ to A. For corrupted authorities, A runs the Setupauth algorithm to generate the key pairs for them(2)
Key query:A runs m queries. In the q-th query, A sends SGIDq,GIDq to B. B initiates an empty table T and do the following steps(a)
Accesses the random oracleHGIDq: B searches the entry GIDq,tGIDq,gtGIDq in the table T, and if it exists, B outputs gtGIDq. Else, B chooses a random number tGIDq while stores GIDq,tGIDq,gtGIDq in the table T. B outputs gtGIDq(b)
Generates the decryption keyskGIDq,j: ℂ chooses a random number r∈ℤp∗\−aj+GIDq/bj for each attribute i∈SGIDq,j and returns the signature r,σ=g1/aj+GIDq+bjr. Then, B computes the components of skGIDq,j(20)K1,i=σαi+βitGIDq=gαi+βitGIDq/aj+GIDq+bjr=gαi/aj+GIDq+bjrgtGIDqβi/aj+GIDq+bjr=gαi/aj+GIDq+bjrHGIDqβi/aj+GIDq+bjr,K2,i=Hihj,K3,i=r.
Then,B sets D=D∪SGIDq. Finally B returns the following result to A:
(21)skGIDq=skGIDq,jj∈SAA,GID,GIDq=K1,i,K2,i,K3,ii∈SGIDq,GIDq.(3)
Key forgery:A sends a sk∗ to B. The advantage of the adversary to win is defined as(22)PrTracePP,pkAAj,sk∗∈⊥,GID1,⋯,GIDm=ε,where GID1,⋯,GIDm is mGID queried in the last phase. If TracePP,pkAAj,sk∗∈⊥,GID1,⋯,GIDm, it means sk∗=K1,i,K2,i,K3,ii∈SGID,GID passed the form check and GID∈⊥,GID1,⋯,GIDm. Hence, ∃i∈S, s.t.
(23)K1,i,K2,i∈G,K3,i,GID∈ℤp,∗eK1,i,gajgbjK3,igGID=eg,gαieHGID,gti.Without loss of generality, we assume the adversary A accessed the random oracle HGID before it outputs the sk∗. B obtains the entry GID,tGID,gtGID from the table T. According to eK1,i,gajgbjK3,igGID=eg,gαieHGID,gβi, we can get K1,i=gαi+tGIDβi/aj+bjK3,i+GID. Then, B computes the signature σj=K1,i1/αi+tGIDβi. Because GID,K3,i∈ℤp∗, hence K3,i,σj is a valid signature on message GID in the B-B signature scheme. Because GID∈GID1,⋯,GIDm, it means B never queried the signature of GID before, and the advantage of B to break the B-B scheme is equal with the advantage of the adversary A to break our scheme, which is ε.According to the Boneh-Boyen signature scheme, we can also get the following lemma.Lemma 2.
If theq-SDH assumption holds in the group G, the full signature scheme of Boneh and Boyen is strong existential forgery secure against adaptive chosen message attacks.Theorem 4.
If theq-SDH assumption holds in the group G, our scheme achieves fully user traceability.Proof.
It follows directly from the above Lemma1 and Lemma 2.


## 7. Performance Analysis

The notations used in our performance analysis are summarized in Table3.Table 3
Notations.
NotationMeaningE,/ETOne exponentiation in groupG/GTPeOne pairing operation of the pairing functione.NeThe row number of the encryption LSSS access matrix.NuThe attribute number of the user attribute set.NdThe attribute number required in decryption.NaThe attribute number of the attribute universe set.The comparison of storage cost and computational cost between our scheme and some other ABE schemes is illustrated in Tables4 and 5separately. Notice that all results do not contain the costs of the symmetric cryptography including hash operations.Table 4
Storage cost comparison.
Scheme[11][13][14]Our schemeDecryption key length2Nu∣G∣3Nu∣G∣+Nu∣ℤp∗∣+∣ℤp∣2Nu+3∣G∣+2∣ℤp∣2Nu∣G∣+Nu∣ℤp∣Outdec key lengthNd+2∣G∣+∣ℤp∗∣—2Nu+2∣G∣Nd+2∣G∣+∣ℤp∗∣Ciphertext length3Ne+1∣G∣+1∣GT∣5Ne∣G∣+Ne+1∣GT∣3Ne+2∣G∣+1∣GT∣5Ne+1∣G∣+1∣GT∣Table 5
Computational cost comparison.
Scheme[11][13][14]Our schemeKey generation3NuE5NuE4Nu+4E3NuEEncryptionNu+5Ne+1E+1ET+NuPe2Ne+1ET+6NeE5Ne+2E+1ETNu+7Ne+1E+1ET+NuPeOutdecryptionNdET+3NdPe—NdET+3Nd+1Pe3NdET+3NdPeUser decryption1ET4NdET+3NdPe3ET1ETFrom Table4, we can see that the decryption key lengths of scheme [11] and ours are related to the number of attributes used in decryption as both scheme outsource the most decryption work to the cloud server, while the decryption key length of scheme [14] is related to the number of attributes in user attribute sets. Speaking of the length of the ciphertext, of all four schemes are associated with the row number of the encryption LSSS access matrix.As we can see from Table4, scheme [13] needs 5Nu exponentiations in group G to generate the user decryption key. It needs 2Ne+1 exponentiations in group GT and 6Ne exponentiations in group G in the encryption phase. Specially, 4Nd exponentiations in group GT and 3Nd pairings are costed by a user who needs to decrypt in scheme [13], which is too heavy for resource-limited IoT devices. Scheme [11] is an ABE scheme with outsourced decryption which needs 3Nu exponentiations in group G in the key generation phase. It requires Nu+5Ne+1 exponentiations in group G, one exponentiation in group GT, and Nu pairings to encrypt. As the most pairing operations are done by the cloud server, users only cost one exponentiation in group GT to decrypt in [11].Li et al. proposed a traceable ABE scheme which needs4Nu+4 exponentiations in group G to generate the private key [14]. In encryption phase, users spends 5Ne+2 exponentiations in group GT and one exponentiation in group G, while the cloud server performs Nd exponentiations in group GT as well as 3Nd+1 pairings to predecrypt in [14]. As a result, users only cost three exponentiations in group GT to fully decrypt.Our scheme needs3Nu exponentiations in group G in the key generation phase. To achieve fully policy hidden which is deeply valuable in some healthy data application, our scheme requires Nu+7Ne+1 exponentiations in group G, one exponentiation in group GT, and Nu pairings to encrypt. Meanwhile, our scheme realizes verifiable outsourced decryption. Our scheme outsources 3Nd exponentiations in group GT and 3Nd pairings to the cloud server. Thus, IoT devices in our scheme only require one exponentiation in group GT to decrypt, which dramaticlly reduces the computational overhead of resource-limited devices.Figure7 illustrates the time overhead of decryption. The simulation is performed in a Ubuntu 16.4 desktop system with 3.0-GHz Intel Core (TM) i5-7400 CPU and 2-GB RAM, and all experiments are done by using the Charm (version 0.50) [37], a rapid prototyping framework for cryptographic schemes based with Python.Figure 7
Decryption cost.Compared with the outsourced multiauthority ABE scheme [11] with no traceability, our traceable MAABE scheme is with little extra computational cost. However, the user decryption cost of [11] and our scheme is same owing to the outsourced decryption. While comparing with the traceable single-authority ABE scheme [14], our multiauthority scheme can handle more attributes and is more suitable for a large number of devices of IoT systems. In addition, another traceable MAABE [13] is not applicable for resource-limited IoT devices due to its heavy decryption cost.More importantly, our scheme costs barely one hash operation to achieve the verification of decryption results. About another practical function is achieved by our scheme, traceability, and the cost of our scheme isNa2E+H+3P. Although it looks like that this result is linear to the size of the attribute universe set, the real computational cost of this algorithm for each AA is linear to the size of its own attribute set as we assumed that attribute sets controlled by different attribute authorities are disjoint in our scheme.


## 8. Conclusion

In this paper, we propose a multiauthority ABE scheme supporting verifiable outsourced decryption and white-box traceability. Our scheme outsources most decryption works to the honest-but-curious resource-rich cloud server; thus, our scheme meets the special needs of resource-limited IoT devices. Moreover, our scheme protects the privacy of both the encryptor and the decryptor by the fully hiding policy technology. At the same time, another issue influences the application of ABE—the key leakage problem—which is solved by the user traceability algorithm. In a word, our scheme realizes several practical functions while achieving replayable chosen-ciphertext attack security.In the future, we plan to improve the scheme with fixed key size and ciphertext size to further reduce equipment overheads. Moreover, we can also consider how to solve another difficulty of the practical application of the ABE—attribute revocation and user revocation. How to dynamically withdraw attributes or users without affecting other authorized users is the focus of our future works.



---

*Source: 6682580-2021-04-21.xml*