Efficient and Adaptively Secure Attribute-Based Proxy Reencryption Scheme

Abstract

Ciphertext-Policy Attribute-Based Proxy Reencryption (CP-ABPRE) has found many practical applications in the real world, because it extends the traditional Proxy Reencryption (PRE) and allows a semitrusted proxy to transform a ciphertext under an access policy to the one with the same plaintext under another access policy. The existing CP-ABPRE schemes were proven secure only in the selective security model, a limited model, which is an unnatural constraint on the attacker. The scheme proved in this model can only be called selectively secure one. However, from a security perspective, the adaptively secure CP-ABPRE scheme is more desirable. In this paper, an adaptively secure CP-ABPRE scheme is proposed, which is based on Waters’ dual system encryption technology. The proposed scheme is constructed in composite order bilinear groups and proven secure under the complexity assumptions of the subgroup decision problem for 3 primes (3P-SDP). Analyses show that our proposal provides higher computational efficiency compared with the existing schemes.

1. Introduction

With the development of Internet and open distributed networks, the Attribute-Based Encryption (ABE) scheme [1] has drawn great attention of researchers in recent years. Unlike the Public Key Encryption mechanism, ABE scheme takes attributes as the public key and associates the ciphertext and user's secret key with attributes, so that it provides more flexible access control mechanism over encrypted data. This dramatically reduces the cost of network bandwidth and sending node's operation in fine-grained access control of data sharing. Therefore, ABE has a broad prospect in the large-scale distributed applications to support one-to-many communication mode. Traditional ABE has two variants according to the form of access policy: Key-Policy ABE (KP-ABE) and Ciphertext-Policy ABE (CP-ABE) [2]. In a KP-ABE system, ciphertexts are associated with attribute sets and secret keys are associated with access policies. However, CP-ABE is complementary, and the sender could specify access control policy, so, compared with KP-ABE schemes, CP-ABE schemes are more suitable for the realistic scenes.

As the research and application of the ABE go ahead, Proxy Reencryption (PRE) [3] has been introduced into ABE schemes. Considering such a scenario, in the email forwarding, Alice is going on vacation and wishes the others like Bob could still read the message in her encrypted emails. With an Attribute-Based Proxy Reencryption (ABPRE) system, in which a proxy is allowed to transform a ciphertext under a specified access policy into the one under another access policy, she could meet her intentions without giving her secret key to either the mail server or Bob. So ABPRE schemes [4] are needed in most of practical network applications, especially Ciphertext-Policy ABPRE (CP-ABPRE) schemes [5], which have more flexible access control policy than Key-Policy ABPRE (KP-ABPRE) schemes [4]. Generally speaking, an ABPRE scheme has an authority, a sender, a user called a delegator who needs to delegate his/her decryption ability to someone else, a proxy who helps the delegator to generate a reencrypted ciphertext, and some receivers as participants. Recently, due to their widespread use in the realistic scenes, widespread attention was paid to ABPRE schemes by researchers and some excellent ABPRE schemes have been proposed [6–12].

However, most of existing ABPRE schemes [6–12] were proven secure only in the selective security model [13], in which an adversary must firstly choose an attack target before the public parameters are published. This restriction on an attacker was not natural, which causes attackers to behave differently from the way in a real environment. And most of existing schemes [11–15] demanded a number of paring operations, which indeed costs much in the communications. Therefore, motivated by these concerns, an efficient and adaptively secure CP-ABPRE scheme is proposed in our paper. Our scheme overcomes the restriction on an attacker in a selective security model and could be better applied to the open distributed networks. In the meantime, our proposal supports any monotone access formulas and costs less computational overhead compared with the existing schemes.

The rest of this paper is organized as follows. In the next section, we shall briefly review related works in the field of ABE. In Section 3, some preliminaries including complexity assumptions, access structures, and CP-ABPRE model are provided. Then, the concrete CP-ABPRE scheme is given in Section 4. In Section 5, we analyze the correctness and security of our scheme and compare our scheme with existing schemes in terms of access structure, security, and computations efficiency. Finally, the conclusion is drawn in Section 6.

2. Related Works

In 2005, Sahai and Waters [16] proposed a new type of IBE [17] called Fuzzy IBE (FIBE) which regards identities as a set of descriptive attributes. It is often regarded as the first concept of ABE [1, 18]. ABE can be categorized as either KP-ABE or CP-ABE, and the latter is more flexible and more suitable for the realistic scenes [2]. In 2007, Cheung and Newport [19] used AND gates on positive and negative to express attributes in order to achieve their CP-ABE scheme's access policy and proved the security under the DBDH assumption. And then Nishide et al. [20] designed a new CP-ABE scheme with AND gates on multivalue attributes as its access policy. To realize fine-grained access control strategy, Bethencourt et al. [21] used the Access Tree in their scheme. In order to design CP-ABE schemes with flexible strategy under the DBDH assumption, Goyal et al. [22] and Liang et al. [23] adopted Bounded Access Tree, respectively. Later, Ibraim et al. [24] used the general Access Tree to eliminate the boundary constraints in the literature [22, 23]. In 2011, Waters [25] used Linear Secret Sharing Scheme (LSSS) access structure under q-PBDHE assumption to construct a CP-ABE scheme.

However, unfortunately, the security of those CP-ABE schemes that we mentioned above was proven in a weaker security model, called the selective-policy security model which derived from the selective-ID security model for constructing an IBE scheme without the random oracle model [26]. In the selective security model, the adversary must firstly declare which policy he wishes to be challenged on before the public parameters are published. This restriction on the attacker is not natural, which causes attacker to behave differently from the real environment [13]. Considering the restrictions of the selective security model, researchers expected that the ABE scheme should be designed and proven secure under the adaptive security model. So, in order to overcome the drawbacks of the selectively secure ABE schemes, Lewko et al. [13] proposed an adaptively (or fully) secure ABE scheme by using the dual system encryption technique [27] which is a common method for proving an adaptively secure scheme in IBE or ABE. Later, Lewko and Waters [28] provided a new methodology which can transform the selectively secure schemes to adaptively secure ones and presented a CP-ABE scheme that is proven fully secure. In 2014, Garg et al. [29] constructed the first fully secure ABE scheme that can handle access control policies expressible as polynomial-size circuits. Afterwards, some excellent adaptively secure ABE schemes were proposed [3, 30, 31].

Recently, in the field of cryptography, the concept of PRE has been proposed to make data sharing more efficient. Introduced by Mambo and Okamoto [32] and first defined by Blaze et al. [33], PRE can support the delegation of decryption rights, which is never considered in extending the traditional Public Key Encryption (PKE). In PRE, a semitrusted proxy is enabled to transform a ciphertext encrypted under one's public key into a new ciphertext intended for others with the plaintext unchanged. The decryption proxy, however, can learn nothing about the secret key or the plaintext. Due to these characteristics, PRE has many practical applications. For example, Xu et al. [34] built an encrypted cloud email system with PRE, which allows a user to send an encrypted email to multiple receivers, store his encrypted emails in an email server, and review his history. In addition, it can also be used in secure distributed files systems, cloud storage, on-line Electronic Medical Record (EMR), and so on [4, 5, 35–39].

To date, PRE has been extended to adapt different cryptographic systems. The ABPRE is one of the extensions in which a user is able to empower designated users to decrypt reencrypted ciphertext by deploying attributes. In 2008, Guo et al. [40] proposed the first ABPRE scheme and it is also the first KP-ABPRE scheme. In 2009, Liang et al. [6] proposed the first CP-ABPRE scheme, in which the proxy is enabled to transform a given ciphertext under a specified access policy into the one under another access policy. But, unfortunately, only AND gates on positive and negative attributes are supported by their access policy. In 2010, Luo et al. [7] proposed a new CP-ABPRE scheme which supports AND gates on multivalue and negative attributes. Compared with [6], it has a new property named reencryption control which means that the user can decide which ciphertext can be reencrypted later during the encryption process. Later, Seo and Kim [8] presented another CP-ABPRE scheme which only needs a constant number of bilinear pairing operations. So the computation cost and ciphertext length are reduced significantly compared to previous schemes [7, 27]. In 2013, Li [9] presented a new CP-ABPRE scheme in which the ciphertext policy is matrix access policy based on LSSS matrix access structure. In 2014, Chung et al. [10] analyzed these CP-ABPRE schemes [6–8, 33] and made comparisons of them by some criteria. The aforementioned CP-ABPRE schemes, however, are only CPA-secure. To tackle this problem, Liang et al. [11], for the first time, proposed a new single-hop unidirectional CP-ABPRE scheme supporting any monotonic access formulas. Despite being constructed in the random oracle model, it is proved to be CCA-secure. In 2015, Kawai [12] proposed a flexible CP-ABPRE scheme in which the reencryption key generation can be outsourced in Attribute-Based Encryption and proved their scheme is secure in the selective security model.

All these CP-ABPRE schemes mentioned above, unfortunately, were only proven to be selectively secure [13], which is just discussed above. A CP-ABPRE system with selective security, which limits an adversary to choose an attack target before playing a security game, might not scale well in practice as well. This is because a realistic adversary is able to adaptively choose his attack target when attacking a cryptosystem. Therefore, an adaptively secure CP-ABPRE scheme is extremely desirable in most practical network applications. In 2014, Liang et al. [14], for the first time, formalized the notion of adaptive security for CP-ABPRE systems and proposed a new CP-ABPRE scheme, which is proven adaptively secure in the standard model, but their scheme demands a number of paring operations that imply huge computational overheads. In 2015, Backes et al. [15] presented an Inner-Product Proxy Reencryption scheme. Although their scheme can easily be converted into an Attribute-Based Proxy Reencryption scheme, the ciphertext is only associated with AND gates access structure, which does not conform to the flexible access policy. Motivated by these concerns, in this paper, we propose an efficient and adaptively secure CP-ABPRE scheme which supports any monotone access formulas.

Our contributions can be briefly outlined as follows. (1) A new scheme is proposed and it overcomes the restriction on the attacker in a selective security model in the existing schemes [6–9, 11] and is proved to be adaptively secure. (2) Our proposal supports any monotone access formulas including what the AND gate access structure supports. (3) Our scheme costs less computational overhead compared with the corresponding scheme [14]. (4) We try to construct our scheme in composite order groups and use three assumptions to prove its security.

3. Preliminaries

3.1. Composite Order Bilinear Groups

Composite order bilinear groups were introduced by Boneh et al. [41]. First, let G and $G_T$ be a cyclic additive group and a multiplication cyclic group of order N, where $N=p_1{p}_2{p}_3$ and $p_1$ , $p_2$ , and $p_3$ are three distinct prime numbers. Let $e:G\times G\to G_T$ be a bilinear map.

Then, let $G_{p_{\mathrm{1}}}$ , $G_{p_{\mathrm{2}}}$ , and $G_{p_{\mathrm{3}}}$ denote the subgroups of order $p_1$ , $p_2$ , and $p_3$ in group G, respectively. Because G is a cyclic group, it is easy to conclude that if h and l are group elements chosen from different subgroups, then $e(h,l)=1$ . This is called the orthogonality property in composite order bilinear groups.

3.2. Complexity Assumptions

We now present three assumptions of the subgroup decision problem for 3 primes (3P-SDP) [13]. First, we let G and $G_T$ be two cyclic groups of order N, where $N=p_1{p}_2{p}_3$ and $p_1$ , $p_2$ , and $p_3$ are three distinct primes. And we let $G_{p_{\mathrm{1}}}$ , $G_{p_{\mathrm{2}}}$ , and $G_{p_{\mathrm{3}}}$ denote the subgroups of order $p_1$ , $p_2$ , and $p_3$ in G, respectively. Let $e:G\times G\to G_T$ be a bilinear map.

Assumption 1.

We randomly choose element g as the generator of $G_{p_{\mathrm{1}}}$ and element $X_3$ as the generator of $G_{p_{\mathrm{3}}}$ . Given $D=(N,G,G_T,e,g,X_{\mathrm{3}})$ , $T_{\mathrm{1}}\in G_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ and $T_{\mathrm{2}}\in G_{p_{\mathrm{1}}}$ . Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 1 is defined as

$$\begin{array}{cc}& \mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{1}}\left(\lambda \right)=\left|\mathrm{P}\mathrm{r}\left[A\left(D,T_{\mathrm{1}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[A\left(D,T_{\mathrm{2}}\right)=\mathrm{1}\right]\right|.\end{array}$$

(1)

Definition 2.

Assumption 1 holds if there is no polynomial time algorithm A which has a nonnegligible advantage $\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{1}}(\lambda )$ .

Assumption 3.

We randomly choose elements $g,X_1\in G_{p_{\mathrm{1}}},\hspace{0.17em}\hspace{0.17em}{X}_2,Y_2\in G_{p_{\mathrm{2}}}$ , and $X_3,Y_3\in G_{p_{\mathrm{3}}}$ . Given $D=(N,G,G_T,e,g,X_{\mathrm{1}}{X}_{\mathrm{2}},X_{\mathrm{3}},Y_{\mathrm{2}}{Y}_{\mathrm{3}})$ and $T_1\in G$ , $T_{\mathrm{2}}\in G_{p_{\mathrm{1}}{p}_{\mathrm{3}}}$ . Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 3 is defined as

$$\begin{array}{cc}& \mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{2}}\left(\lambda \right)=\left|\mathrm{P}\mathrm{r}\left[A\left(D,T_{\mathrm{1}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[A\left(D,T_{\mathrm{2}}\right)=\mathrm{1}\right]\right|.\end{array}$$

(2)

Definition 4.

Assumption 3 holds if there is no polynomial time algorithm A which has a nonnegligible advantage $\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{2}}(\lambda )$ .

Assumption 5.

We randomly choose elements $\alpha ,s\in Z_N,\hspace{0.17em}\hspace{0.17em}g\in G_{p_{\mathrm{1}}},\hspace{0.17em}\hspace{0.17em}{X}_{\mathrm{2}},Y_{\mathrm{2}},Z_{\mathrm{2}}\in G_{p_{\mathrm{2}}}$ , and $X_{\mathrm{3}}\in G_{p_{\mathrm{3}}}$ . Given $D=(N,G,G_T,e,g,g^{\alpha }{X}_{\mathrm{2}},X_{\mathrm{3}},g^s{Y}_{\mathrm{2}},Z_{\mathrm{3}})$ and $T_1=e(g,g{)}^{\alpha s}$ , $T_{\mathrm{2}}\in G_T$ . Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 5 is defined as

$$\begin{array}{cc}& \mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{3}}\left(\lambda \right)=\left|\mathrm{P}\mathrm{r}\left[A\left(D,T_{\mathrm{1}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[A\left(D,T_{\mathrm{2}}\right)=\mathrm{1}\right]\right|.\end{array}$$

(3)

Definition 6.

Assumption 5 holds if there is no polynomial time algorithm A which has a nonnegligible advantage $\mathrm{A}\mathrm{d}{\mathrm{v}}_A^{\mathrm{3}}(\lambda )$ .

3.3. Access Structures

In this paper, the role of the participants is taken by the attributes. As shown in [42], any monotone access structure can be represented by a Linear Secret Sharing Scheme.

Definition 7 (Linear Secret Sharing Schemes (LSSS)).

Let Π denote a secret sharing scheme over a participant collection P. One says that Π is called linear over $Z_p$ if

• (1)

the shares distributed for each participant can form a vector over $Z_p$ ;

(2)

for Π there always exists a share-generating matrix M, which has l rows and n columns. Now, function ρ is defined and used to each party. That is, the party labeling row i can be denoted as $\rho (i)$ for $i=\mathrm{1,2},\dots ,l$ . The column vector $\overrightarrow{v}=(s,y_{\mathrm{2}},y_{\mathrm{3}},\dots ,y_n)$ is randomly chosen in $Z_p^n$ . Then, ${\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}$ is the share belonging to party $\rho (i)$ . We use LSSS matrix ( $M,\rho$ ) to represent an access policy in this paper.

The linear reconstruction property can be defined as follows. Suppose that Π is an LSSS for access structure A. Let $S\in A$ denote the authorized set and define $I\subseteq \{\mathrm{1,2},\dots ,l\}$ as $I=\left\{i\mid \rho \left(i\right)\in S\right\}$ . Then, there exist ${\left\{w_i\in Z_p\right\}}_{i\in I}$ such that if $\left\{{\lambda }_i\right\}$ are valid shares of any secret s, we have ${\sum }_{i\in I}{w}_i{\lambda }_i=s$ [41]. But it does not hold for unauthorized sets. In our scheme, we will employ LSSS matrices over $Z_N$ , where N is the product of 3 different prime numbers.

3.4. CP-ABPRE

3.4.1. Algorithm Model

Generally speaking, a CP-ABPRE scheme is composed of 6 fundamental algorithms and it has an authority, a sender, a user that we call a delegator who needs to delegate his/her decryption ability to someone else, a proxy who helps the delegator to generate a reencrypted ciphertext, and some receivers as participants. The 6 algorithms are shown as follows.

$Setup(1^{\lambda },U)\to (MSK,PK)$ . It is performed by an authority to establish a new CP-ABPRE system. With the security parameter λ and attributes U as input, it generates the public key (PK) and the master secret key (MSK).

$KeyGen(PK,MSK,S)\to S{K}_S$ . With PK, MSK, and a set of attributes S that describe the key as input, this algorithm is executed by the authority for the purpose of generating a secret key $\mathrm{S}{\mathrm{K}}_S$ .

$Enc(PK,W=(M,\rho ),m)\to C{T}_W$ . Performed by a sender, with PK, a message m, and an access policy $W=(M,\rho )$ as input, the algorithm generates a ciphertext $\mathrm{C}{\mathrm{T}}_W$ of m such that only a user whose attributes meet the access policy W can decrypt it.

$ReKeyGen(PK,S{K}_S,W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right))\to R{K}_{S\to W^{\prime }}$ . This algorithm is performed by the delegator. With PK, $\mathrm{S}{\mathrm{K}}_S$ , and an access policy $W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ as input, it generates a reencryption key $\mathrm{R}{\mathrm{K}}_{S\to W^{\prime }}$ for the proxy.

$ReEnc(PK,R{K}_{S\to W^{\prime }},C{T}_W)\to C{T}_{W^{\prime }}$ . It is performed by the proxy, with PK, $\mathrm{R}{\mathrm{K}}_{S\to W^{\prime }}$ , and $\mathrm{C}{\mathrm{T}}_W$ as input. Firstly, the proxy checks whether the attribute in $\mathrm{R}{\mathrm{K}}_{S\to W^{\prime }}$ meets the access policy of $\mathrm{C}{\mathrm{T}}_W$ . If yes, it outputs a reencrypted ciphertext $\mathrm{C}{\mathrm{T}}_{W^{\prime }}$ and otherwise ⊥.

$Dec(PK,C{T}_W,S{K}_S)\to m$ . With PK, an original ciphertext $\mathrm{C}{\mathrm{T}}_W$ , and a secret key $\mathrm{S}{\mathrm{K}}_S$ as input, it returns the plaintext message m if S satisfies the access policy W specified for $\mathrm{C}{\mathrm{T}}_W$ , and otherwise ⊥.

$De{c}_R(PK,C{T}_{W^{\prime }},S{K}_{S^{\prime }})\to m$ . This algorithm returns the plaintext message m if $S^{\prime }$ meets the access policy $W^{\prime }$ specified for $\mathrm{C}{\mathrm{T}}_{W^{\prime }}$ , and otherwise ⊥.

3.4.2. Security Model

The adaptive security definition for a CP-ABPRE scheme is described by a security game between a challenger B and an adversary A, which is shown as follows.

Setup. B runs the Setup algorithm to create a new system and then sends A the public key PK.

Phase 1. A makes the following queries.

(i) Secret Key Extract Queries. B runs the KeyGen algorithm after A submitting sets of attribute $S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_{q_{\mathrm{1}}}$ and returns secret keys $\mathrm{S}{\mathrm{K}}_S$ to A.

(ii) Reencryption Key Extract Queries. A submits sets of attribute $S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_{q_{\mathrm{1}}}$ and an access structure $W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ . Then, B runs the ReKeyGen algorithm and gives the reencryption key $\mathrm{R}{\mathrm{K}}_{S\to W^{\prime }}$ to A.

Challenge. A chooses two messages $M_0$ and $M_1$ with equal length and an access structure $W^{\ast }$ , which cannot be met by any of the queried attribute sets $\{S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_{q_{\mathrm{1}}}\}$ . B randomly flips coin $\theta \in \{0,1\}$ and encrypts $M_{\theta }$ under $W^{\ast }$ to generate $\mathrm{C}{\mathrm{T}}^{\ast }$ , which is then sent to A.

Phase 2. Phase 1 is repeated. Note that there is a restriction that no sets of attributes $\{S_{q_{\mathrm{1}}+\mathrm{1}},S_{q_{\mathrm{1}}+\mathrm{2}},\dots ,S_q\}$ can satisfy the access structure corresponding to B.

Guess. A outputs a guess result ${\theta }^{\prime }$ for θ.

In the above game, the advantage of A is defined as $\mathrm{A}\mathrm{d}{\mathrm{v}}_A=\left|\mathrm{P}\mathrm{r}\left[{\theta }^{\prime }=\theta \right]-\mathrm{1}/\mathrm{2}\right|$ . And the above security model can be easily extended to simulate a game between a CCA adversary and a challenger by permitting Reencryption and Decryption queries during Phases 1 and 2.

Definition 8.

A Ciphertext-Policy Attribute-Based Proxy Reencryption scheme is adaptively secure (or fully secure) if the advantage of any polynomial time adversary is negligible in above game.

3.4.3. Master Secret Security

Master secret security is an important property for unidirectional PRE defined by Ateniese et al. [43]. Roughly speaking, even if the dishonest proxy colludes with the receiver who can decrypt the reencrypted ciphertext, it is still impossible for them to get any information on delegator's secret key and the plaintext [44].

Definition 9.

The master secret security of a CP-ABPRE scheme can be defined based on the following master secret security game.

Setup. The challenger B runs the Setup algorithm to create a new system and then sends the adversary A the public key (PK).

Queries. A makes the following queries.

(i) $Extract(S)$ . B runs the KeyGen algorithm after A submitting attribute sets S and returns secret keys $\mathrm{S}{\mathrm{K}}_S$ to A.

(ii) $RKExtract(S,W^{\prime }).\hspace{0.17em}\hspace{0.17em}A$ submits attribute sets S and an access structure $W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ to B. Then, B runs the ReKeyGen algorithm and returns the reencryption key $\mathrm{R}{\mathrm{K}}_{S\to W^{\prime }}$ to A.

Output. A outputs the secret key $\mathrm{S}{\mathrm{K}}_{S^{\ast }}$ corresponding to the attribute sets $S^{\ast }$ .

In the above game, the advantage of A is defined as $\mathrm{A}\mathrm{d}{\mathrm{v}}_A=\mathrm{P}\mathrm{r}[A\hspace{0.17em}\hspace{0.17em}\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{e}\mathrm{d}\mathrm{s}]$ . A CP-ABPRE scheme meets master secret security if there is no polynomial time adversary A who has a nonnegligible advantage in winning the above game.

Lemma 10.

For a CP-ABPRE scheme, the plaintext security implies the master secret security. That is to say, for a CP-ABPRE scheme, if there is an adversary A who can break its master secret security defined above, then there also exists an adversary $A^{\prime }$ who can break this CP-ABPRE scheme.

In Section 5, we will prove that there is no polynomial time adversary who can break the CP-ABPRE scheme with a nonnegligible advantage. So Lemma 10 is obvious.

4. The Proposed CP-ABPRE Scheme

In this section, we shall introduce our adaptively secure CP-ABPRE scheme. Before this, in order to facilitate understanding, notations used throughout the paper are summarized in Notations.

Our adaptively secure CP-ABPRE scheme is constructed in composite order linear groups of order $N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}}$ ( $p_1$ , $p_2$ , and $p_3$ are 3 different prime numbers) with LSSS access structure. Let $G_{p_i}$ denote the subgroup of order $p_i$ in G where $i\in \{\mathrm{1,2},\mathrm{3}\}$ . The subgroup $G_{p_{\mathrm{2}}}$ is only used in security proof. Our scheme is shown as follows.

(1) $Setup(1^{\lambda },U)$ . Taking as input the security parameter λ and system attribute set U, the trusted authority chooses random elements $\eta ,a\in Z_N$ , a generator $g\in G_{p_{\mathrm{1}}}$ , an element $g_{\mathrm{0}}\in G_{p_{\mathrm{1}}}$ , and a generator $X_{\mathrm{3}}\in G_{p_{\mathrm{3}}}$ . And then it computes $g_{\mathrm{1}}=e(g,g{)}^{\eta }$ and $g_2=g^a$ . For each attribute $x\in U$ , it also chooses a random element $h_x\in Z_N$ and computes $H_x=g^{h_x}$ . The public key is denoted as

$$\begin{array}{cc}& \mathrm{P}\mathrm{K}=\left(N,g_{\mathrm{0}},g_{\mathrm{1}},g_{\mathrm{2}},H_x,\hspace{0.17em}\hspace{0.17em}\forall x\in U\right).\end{array}$$

(4)

The trusted authority sets the master secret key as $\mathrm{M}\mathrm{S}\mathrm{K}=\left(\eta ,X_{\mathrm{3}}\right)$ .

(2) $KeyGen(PK,MSK,S)$ . Taking the public key (PK), the master secret key (MSK), and the user attribute set S as input, this algorithm first chooses a random value $t\in Z_N$ and another three random elements $R_{\mathrm{0}},R_{\mathrm{0}}^{\prime },R_x\in G_{p_{\mathrm{3}}}$ . Then, it computes the secret key as

$$\begin{array}{cc}& \mathrm{S}\mathrm{K}=\left(S,K=g^{\eta }{g}^{at}{R}_{\mathrm{0}},L=g^t{R}_{\mathrm{0}}^{\prime },K_x=H_x^t{R}_x,\hspace{0.17em}\hspace{0.17em}\forall x\in S\right).\end{array}$$

(5)

(3) $Enc(PK,W,m)$ . This algorithm takes as input the public key (PK), an access policy $W=(M,\rho )$ , and a message m, where M is an $l\times n$ matrix and the function ρ associates rows of M to attributes. This algorithm randomly chooses a column vector $\stackrel{⃑}{v}=(s,y_{\mathrm{2}},y_{\mathrm{3}},\dots ,y_n)\in Z_N^n$ . These values will be used to share the encryption exponent s. For $i=\mathrm{1,2},\dots ,l$ , it computes ${\lambda }_i={\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}$ , where ${\stackrel{⃑}{M}}_i$ denotes the ith row of M. Then, the algorithm chooses random numbers $r_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_l\in Z_N$ .

The ciphertext is generated as

$$\begin{array}{cc}& \mathrm{C}\mathrm{T}=\left(C=me{\left(g,g\right)}^{\eta s},C^{\prime }=g^s,C^{\prime \prime }=g_{\mathrm{0}}^s,C_i=g^{a{\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}}{H}_{\rho \left(i\right)}^{-r_i},D_i=g^{r_i},\hspace{0.17em}\hspace{0.17em}\forall i\in \left\{\mathrm{1,2},\dots ,l\right\}\right).\end{array}$$

(6)

(4) $ReKeyGen\left(PK,SK,W^{\prime }\right)$ . To generate a reencryption key for another access policy $W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ , this algorithm takes as input the public key PK, the secret key SK = $(S,K,L,K_x,\hspace{0.17em}\hspace{0.17em}\forall x\in S)$ , and another access policy $W^{\prime }=\left(M^{\prime },{\rho }^{\prime }\right)$ . It needs to choose a random element $\beta \in Z_N$ and computes $\widehat{C}=Enc\left(\mathrm{P}\mathrm{K},W^{\prime },g^{\beta }\right)$ . Then the reencryption key is set to

$$\begin{array}{cc}& \mathrm{R}\mathrm{K}=\left(S,r{k}_{\mathrm{1}}=K{g}_{\mathrm{0}}^{\beta },r{k}_{\mathrm{2}}=L,K_x^{\prime }=K_x,\widehat{C},\hspace{0.17em}\hspace{0.17em}\forall x\in S\right).\end{array}$$

(7)

(5) $ReEnc(PK,RK,CT)$ . This algorithm takes as input the public key (PK), a reencryption key (RK), and a ciphertext $\mathrm{C}\mathrm{T}=\left(C,C^{\prime },C^{\prime \prime },C_i,D_i,\hspace{0.17em}\hspace{0.17em}\forall i\right)$ . It first checks whether the attribute set in RK meets the access policy of CT. It computes

$$\begin{array}{cc}& C_t=\frac{e\left(C^{\prime },r{k}_{\mathrm{1}}\right)}{{\prod }_{i\in I}^{}{\left(e\left(C_i,r{k}_{\mathrm{2}}\right)e\left(D_i,K_{\rho \left(i\right)}^{\prime }\right)\right)}^{w_i}}\end{array}$$

(8)

and outputs a reencrypted ciphertext $\mathrm{C}{\mathrm{T}}^{\prime }=\left(C,C^{\prime },\widehat{C},C_t\right)$ if yes and outputs ⊥ otherwise.

(6) $Dec(PK,CT,SK)$ . The original ciphertext decryption algorithm takes the public key (PK), an original ciphertext (CT) for access policy W, and a secret key (SK) for an attribute set S as input. Assume that S meets W and $I\subset \left\{\mathrm{1,2},\dots ,l\right\}$ is defined as $I=\left\{i\mid \rho \left(i\right)\in S\right\}$ . Then, let ${\left\{w_i\in Z_N\right\}}_{i\in I}$ be a set of constants such that if $\left\{{\lambda }_i\right\}$ are valid shares of any secret s according to M, then, ${\sum }_{i\in I}{w}_i{\lambda }_i=s$ holds.

The message m can be recovered as

$$\begin{array}{cc}& m=\frac{C{\prod }_{i\in I}^{}{\left(e\left(C_i,L\right)e\left(D_i,K_{\rho \left(i\right)}\right)\right)}^{w_i}}{e\left(C^{\prime },K\right)}=\frac{C}{e\left({\prod }_{i\in I}^{}{C}_i^{-w_i},L\right)e\left(C^{\prime },K{\prod }_{i\in I}^{}{K}_{\rho \left(i\right)}^{-w_i}\right)}.\end{array}$$

(9)

(7) $De{c}_R(PK,C{T}^{\prime },S{K}^{\prime })$ . The reencrypted ciphertext decryption algorithm takes the public key (PK), a reencrypted ciphertext ${\mathrm{C}\mathrm{T}}^{\prime }$ for access policy $W^{\prime }$ , and a secret key ${\mathrm{S}\mathrm{K}}^{\prime }$ for an attribute set $S^{\prime }$ as input. If $S^{\prime }$ satisfies $W^{\prime }$ , this algorithm computes as follows:

• (7.1)

Decrypt $g^{\beta }$ from $\widehat{C}$ by the Dec algorithm.

(7.2)

Then compute the message m by $m=Ce(C^{\prime \prime },g^{\beta })/C_t$ .

5. Analyses and Proof

5.1. Correctness Analyses

The correctness of the scheme is based on the bilinear character of pairing $e:G\times G\to G_T$ . First, we show the correctness of the original ciphertext decryption as follows:

$$\begin{array}{cc}& m=\frac{C{\prod }_{i\in I}^{}{\left(e\left(C_i,L\right)e\left(D_i,K_{\rho \left(i\right)}\right)\right)}^{w_i}}{e\left(C^{\prime },K\right)}=\frac{me{\left(g,g\right)}^{\eta s}{\prod }_{i\in I}^{}{\left(e\left(g^{a{\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}}{H}_{\rho \left(i\right)}^{-r_i},g^t{R}_{\mathrm{0}}^{\prime }\right)e\left(g^{r_i},H_{\rho \left(i\right)}^t{R}_{\rho \left(i\right)}\right)\right)}^{w_i}}{e\left(g^s,g^{\eta }{g}^{at}\right)}=\frac{me{\left(g,g\right)}^{\eta s}e{\left(g,g\right)}^{at{\sum }_{i\in I}\left({\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}\right)w_i}}{e{\left(g,g\right)}^{\eta s}e{\left(g,g\right)}^{sat}}=m.\end{array}$$

(10)

Then, the correctness of the decryption algorithm for the reencrypted ciphertext is shown as follows:

$$\begin{array}{cc}& m=\frac{Ce\left(C^{\prime \prime },g^{\beta }\right)}{C_t}=\frac{Ce\left(C^{\prime \prime },g^{\beta }\right){\prod }_{i\in I}^{}{\left(e\left(C_i,r{k}_{\mathrm{2}}\right)e\left(D_i,K_{\rho \left(i\right)}^{\prime }\right)\right)}^{w_i}}{e\left(C^{\prime },r{k}_{\mathrm{1}}\right)}=\frac{me{\left(g,g\right)}^{\eta s}e\left(g_{\mathrm{0}}^s,g^{\beta }\right){\prod }_{i\in I}^{}{\left(e\left(g^{a\left({\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}\right)}{H}_{\rho \left(i\right)}^{-r_i},g^t{R}_{\mathrm{0}}^{\prime }\right)e\left(g^{r_i},H_{\rho \left(i\right)}^t{R}_{\rho \left(i\right)}\right)\right)}^{w_i}}{e\left(g^s,g^{\eta }{g}^{at}{g}_{\mathrm{0}}^{\beta }{R}_{\mathrm{0}}\right)}=\frac{me{\left(g,g\right)}^{s\eta }e\left(g_{\mathrm{0}}^s,g^{\beta }\right)e{\left(g,g\right)}^{at{\sum }_{i\in I}^{}\left({\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}\right)w_i}}{e{\left(g,g\right)}^{s\eta }e{\left(g,g_{\mathrm{0}}\right)}^{s\beta }e{\left(g,g\right)}^{sat}}=m.\end{array}$$

(11)

Both the original ciphertext decryption and the reencrypted ciphertext decryption processes in Section 4 are correct because the message m can be recovered correctly. Hence, our CP-ABPRE scheme is also correct.

5.2. Security Proof

Dual system encryption [27] is considered as a common and powerful tool to transform a selectively secure scheme into an adaptively secure one [13, 45, 46]. In a dual system encryption scheme, both keys and ciphertexts have two forms: normal and semifunctional [13]. A normal key can be used to decrypt normal or semifunctional ciphertexts, while a semifunctional key can only be used to decrypt normal ciphertexts. Notably, the semifunctional keys and ciphertexts are only used in security proof. To prove the security of our CP-ABPRE scheme, we firstly define the semifunctional keys and ciphertexts as follows.

Let $g_2$ be a generator of $G_{p_{\mathrm{2}}}$ .

Semifunctional Ciphertexts. We firstly use the Enc algorithm to generate normal ciphertext and choose element $c\in Z_N$ randomly. Then, we choose random values $z_x\in Z_N$ for each attribute, random values ${\gamma }_i\in Z_N$ for the ith row of matrix M, and a random column vector $\stackrel{⃑}{u}\in Z_N^n$ . The semifunction ciphertext is set as

$$\begin{array}{cc}& C^{\prime }=g^s{g}_{\mathrm{2}}^c,\\ C_i=g^{a{\stackrel{⃑}{M}}_i·\stackrel{⃑}{v}}{H}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{2}}^{{\stackrel{⃑}{M}}_i·\stackrel{⃑}{u}+{\gamma }_i{z}_{\rho \left(i\right)}},\\ D_i=g^{r_i}{g}_{\mathrm{2}}^{-{\gamma }_i}\\ \hspace{1em}\forall i\in \left\{\mathrm{1,2},\dots ,l\right\}.\end{array}$$

(12)

Semifunctional Key. We use KeyGen algorithm to generate normal secret key. And then we choose random exponents $b,d\in Z_N$ to set the semifunctional key as follows.

A semifunctional key of type 1 is

$$\begin{array}{cc}& K=g^{\eta }{g}^{at}{R}_{\mathrm{0}}{g}_{\mathrm{2}}^d,\\ L=g^t{R}_{\mathrm{0}}^{\prime }{g}_{\mathrm{2}}^d,\\ K_x=H_x^t{R}_x{g}_{\mathrm{2}}^{b{z}_x}\hspace{1em}\forall x\in S.\end{array}$$

(13)

A semifunctional key of type 2 (in type 1 $b=0$ ) is

$$\begin{array}{cc}& K=g^{\eta }{g}^{at}{R}_{\mathrm{0}}{g}_{\mathrm{2}}^d,\\ L=g^t{R}_{\mathrm{0}}^{\prime },\\ K_x=H_x^t{R}_x\hspace{1em}\forall x\in S.\end{array}$$

(14)

We should note that there will be an extra factor $e(g_{\mathrm{2}},g_{\mathrm{2}}{)}^{cd-{\sum }_{i\in I}b{\stackrel{⃑}{M}}_i·\stackrel{⃑}{u}{w}_i}=e(g_{\mathrm{2}},g_{\mathrm{2}}{)}^{cd-b{u}_{\mathrm{1}}}$ ( $u_1=(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})·\stackrel{⃑}{u}$ ) when a semifunctional key is used to decrypt a semifunctional ciphertext. But when the formula $cd=b{u}_1$ holds, the semifunctional key of type 1 called a nominally semifunctional key can decrypt the semifunctional ciphertext successfully.

Our proof of security relies on Assumptions 1, 3, and 5 defined in Section 3. The security proof is obtained via a hybrid argument over a sequence of games defined bellow. Let Q be the maximum number of key queries that the adversary makes, and a series of games are defined as follows,

$Gam{e}_{real}$ . It denotes the real CP-ABPRE security game defined in Section 3, with normal keys and ciphertexts.

$Gam{e}_{\mathit{\text{0}}}$ . It is similar to the above real game except that the challenge ciphertext is transformed into semifunctional one.

$Gam{e}_{k\mathit{\text{,1}}}$ . In the game, the challenge ciphertext is semifunctional, the first $k-1$ queried keys are semifunctional ones of type 2, the kth key is semifunctional one of type 1, and the rest of the keys are normal ones.

$Gam{e}_{k\mathit{\text{,2}}}$ . The challenge ciphertext is semifunctional, the first k queried keys are semifunctional ones of type 2, and the remaining keys are normal ones.

$Gam{e}_{Final}$ . All keys are semifunctional ones of type 2 and the challenge ciphertext is semifunctional encryption of a random message which is independent of the two messages provided by the adversary. So the advantage of the adversary in this game is negligible.

In the latter part of this section, we will prove that the above games are indistinguishable under the composite assumption.

Lemma 11.

Assume that there is a polynomial time adversary A such that $Gam{e}_{real}Ad{v}_A-Gam{e}_{\mathit{\text{0}}}Ad{v}_A=\epsilon .$ Then, we can construct another polynomial time algorithm B that can break Assumption 1 with a nonnegligible advantage ε.

Proof.

We establish a polynomial time algorithm B which receives $\{g,X_3,T\}$ to simulate either $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}$ or $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}$ with A based on setting whether $T\in G_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ or $T\in G_{p_{\mathrm{1}}}$ .

Setup. B chooses random exponents $a,\eta ,h_x\in Z_N\hspace{0.17em}\hspace{0.17em}(\forall x)$ , sends the public key PK = $\left(N,g,g_{\mathrm{0}},e(g,g{)}^{\eta },g^a,H_x=g^{h_x}\hspace{0.17em}\hspace{0.17em}\forall x\right)$ to the adversary A, and at the same time securely keeps the master secret key MSK = $\left(\eta ,X_{\mathrm{3}}\right)$ .

Phase 1. B responds to whatever A's key requests by using the KeyGen algorithm to make normal keys, since it has the MSK.

Challenge. A provides two messages $M_0$ and $M_1$ with equal length and a challenge access matrix $W^{\ast }=(M^{\ast },\rho )$ to B. For each row i of matrix $M^{\ast }$ , B first chooses random values $v_{\mathrm{2}}^{\prime },v_{\mathrm{3}}^{\prime },\dots ,v_n^{\prime }\in Z_N$ and a random element $r_i^{\prime }\in Z_N$ to build the column vector ${\stackrel{⃑}{v}}^{\prime }=\left(1,v_2^{\prime },v_3^{\prime },\dots ,v_n^{\prime }\right)$ . Then, B chooses a random message $M_{\theta }$ from $M_0$ and $M_1$ and computes the challenge ciphertext $C^{\ast }$ as

$$\begin{array}{cc}& C=M_{\theta }e{\left(g,g\right)}^{s\eta }=M_{\theta }e{\left(g,T\right)}^{\eta },\\ C^{\prime }=T\\ C_i=T^{a{\stackrel{⃑}{M}}_i^{\ast }·{\stackrel{⃑}{v}}^{\prime }}{T}^{-r_i^{\prime }{h}_{\rho \left(i\right)}},\\ D_i=T^{r_i^{\prime }},\end{array}$$

(15)

where $\theta \in \{\mathrm{0,1}\}$ is the random coin.

Phase 2. Repeat Phase 1.

Guess. A outputs its guess result ${\theta }^{\prime }$ of θ.

If $T\in G_{p_{\mathrm{1}}}$ , let $T=g^s$ . This is a normal ciphertext with $\stackrel{⃑}{v}=s{\stackrel{⃑}{v}}^{\prime }$ and $r_i=r_i^{\prime }s$ . B has simulated $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}$ for A. If $T\in G_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ , let $T=g^s{g}_{\mathrm{2}}^c$ . This is a semifunctional ciphertext with $u=ca{v}^{\prime },\hspace{0.17em}\hspace{0.17em}{\gamma }_i=-c{r}_i^{\prime }$ , and $z_{\rho (i)}=h_{\rho (i)}$ . By the Chinese Remainder Theorem (CRT), the values of $a,v_2^{\prime },v_3^{\prime },\dots ,v_n^{\prime },r_i^{\prime },h_{\rho (i)}$ modulo $p_2$ are uncorrelated to their values modulo $p_1$ . B has simulated $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}$ for A.

Hence, if A can distinguish $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}$ and $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{0}}$ with a nonnegligible advantage ε, B can distinguish element on $G_{p_{\mathrm{1}}}$ and $G_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ with a nonnegligible advantage ε.

Lemma 12.

Assume that there is a polynomial time adversary A such that $Gam{e}_{k-\mathit{\text{1,2}}}Ad{v}_A-Gam{e}_{k\mathit{\text{,1}}}Ad{v}_A=\epsilon .$ Then, another polynomial time algorithm B, which can break Assumption 3 with a nonnegligible advantage ε, can be constructed.

Proof.

B receives $\left\{g,X_1{X}_2,X_3,Y_2{Y}_3,T\right\}$ to simulate either $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k-\mathrm{1,2}}$ or $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ with A based on setting whether $T\in G$ or $T\in G_{p_1{p}_3}$ .

Setup. B chooses random exponents $a,\eta ,h_x\in Z_N\hspace{0.17em}\hspace{0.17em}(\forall x\in U)$ to generate the public key PK = $\left(N,g,g_{\mathrm{0}},e(g,g{)}^{\eta },g^a,H_x=g^{h_x}\hspace{0.17em}\hspace{0.17em}\forall x\right)$ and sends it to A. At the same time, B should securely keep the master secret key MSK = $\left(\eta ,X_{\mathrm{3}}\right)$ .

Phase 1. This phase can be divided into three parts.

• (1)

To form the first $k-1$ semifunctional keys of type 2, B responds to each A's key query by randomly choosing elements $t\in Z_N$ and $R_{\mathrm{0}}^{\prime },R_x\in G_{p_{\mathrm{3}}}$ and sets

$$\begin{array}{cc}& K=g^{\eta }{g}^{at}{\left(Y_{\mathrm{2}}{Y}_{\mathrm{3}}\right)}^t,\\ L=g^t{R}_{\mathrm{0}}^{\prime },\\ K_x=H_x^t{R}_x\hspace{1em}\forall x\in S.\end{array}$$

(16)

(2)

To generate the normal keys of queries greater than k, B needs to run the KeyGen algorithm since it has the master secret key (MSK).

(3)

To answer the kth query, set $g^t$ equal to the $G_{p_1}$ part of T. Then, B randomly chooses elements $R_{\mathrm{0}},R_{\mathrm{0}}^{\prime },R_x\in G_{p_{\mathrm{3}}}$ and computes

$$\begin{array}{cc}& K=g^{\eta }{T}^a{R}_{\mathrm{0}},\\ L=T{R}_{\mathrm{0}}^{\prime },\\ K_x=T^{h_x}{R}_x\hspace{1em}\forall x\in S.\end{array}$$

(17)

If $T\in G_{p_1{p}_3}$ , the above key is a normal one. And if $T\in G$ , it is a semifunctional one of type 1. In this case, there exists $z_x=h_x$ . If we let factor $g_{\mathrm{2}}^b$ denote the $G_{p_2}$ part of T, there is $d\equiv ba\hspace{0.17em}\mathrm{m}\mathrm{o}\mathrm{d}\hspace{0.17em}{p}_{\mathrm{2}}$ . Note that $z_x\hspace{0.17em}\mathrm{m}\mathrm{o}\mathrm{d}\hspace{0.17em}{p}_2$ is uncorrelated to $h_x\hspace{0.17em}\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{l}\mathrm{o}\hspace{0.17em}{p}_1$ , let $g_{\mathrm{2}}^{b}a$ be equal to the $G_{p_{\mathrm{2}}}$ part of K, let $g_{\mathrm{2}}^b$ be equal to the $G_{p_{\mathrm{2}}}$ part of L, and let $g_{\mathrm{2}}^{b{z}_x}$ be equal to the $G_{p_{\mathrm{2}}}$ part of $K_x$ .

Challenge. A provides two messages $M_0$ and $M_1$ with equal length and a challenge access matrix ( $M^{\ast },\rho$ ) for B. B sets $g^s=X_{\mathrm{1}}$ and $g_{\mathrm{2}}^b=X_{\mathrm{2}}$ . Then, B chooses random values $u_2,u_3,\dots ,u_n\in Z_N$ to define the vector ${\stackrel{⃑}{u}}^{\prime }=\left(a,u_2,u_3,\dots ,u_n\right)$ and randomly chooses exponent $r_i^{\prime }\in Z_N$ . B chooses a random message $M_{\theta }$ from $M_0$ and $M_1$ and computes the challenge ciphertext $C^{\ast }$ as

$$\begin{array}{cc}& C=M_{\theta }e{\left(g,X_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{\eta },\\ C^{\prime }=X_{\mathrm{1}}{X}_{\mathrm{2}},\\ C_i={\left(X_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{{\stackrel{⃑}{M}}_i^{\ast }·u^{\prime }}{\left(X_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{-r_i^{\prime }{h}_{\rho \left(i\right)}},\\ D_i={\left(X_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{r_i^{\prime }},\end{array}$$

(18)

where $\theta \in \{\mathrm{0,1}\}$ is the random coin. We set $\stackrel{⃑}{v}=a^{-\mathrm{1}}s{\stackrel{⃑}{u}}^{\prime }$ and $\stackrel{⃑}{u}=c{\stackrel{⃑}{u}}^{\prime }$ , so s is shared in the subgroup $G_{p_1}$ and $c·a$ is shared in the subgroup $G_{p_2}$ . It also sets $r_i=s·r_i^{\prime }$ and ${\gamma }_i=-c·r_i^{\prime }$ . The values $z_{\rho (i)}=h_{\rho (i)}$ match those in the kth key if it is semifunctional of type 1.

Actually, if the kth key can be used to decrypt the challenge ciphertext, then $cd-b{u}_1=cba-bca=0$ modulo $p_2$ holds, so our key is either normal or nominally semifunctional. We must argue that this is hidden to A that cannot request any keys that can be used to decrypt the challenge ciphertext. Note that attributes are only used once in labeling the rows of the matrix. When attribute $x\notin S$ , $z_x$ only appeared in the kth key because all keys are semifunctional ones of type 2 except for the kth one. Because the kth key cannot be used, decrypting the challenge ciphertext, which implies the row space R formed by the rows of the matrix M whose attributes are in the key, does not include the vector ( $\mathrm{1,0},\dots ,0$ ). Thus, we denote a vector $\stackrel{⃑}{\sigma }$ that is orthogonal to R and not orthogonal to vector ( $\mathrm{1,0},\dots ,0$ ). We set an equation that $\stackrel{⃑}{u}=f\stackrel{⃑}{\sigma }+{\stackrel{⃑}{u}}^{\prime \prime }$ for $f\in Z_N$ and $u^{\prime \prime }$ is in the span of the basis elements not equal to $\stackrel{⃑}{\sigma }$ . We note that $u^{\prime \prime }$ is properly distributed and reveals nothing about f. Since $u_{\mathrm{1}}=\stackrel{⃑}{u}·(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})=f(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})·\stackrel{⃑}{\sigma }+(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})·{\stackrel{⃑}{u}}^{\prime \prime }$ and $(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})·\stackrel{⃑}{\sigma }\ne \mathrm{0}$ , the item $\stackrel{⃑}{u}·(\mathrm{1,0},\mathrm{0},\dots ,\mathrm{0})$ is correlated to f.

For $\rho (i)\in S$ , the equation ${\stackrel{⃑}{M}}_i·\stackrel{⃑}{u}={\stackrel{⃑}{M}}_i·(f\stackrel{⃑}{\sigma }+{\stackrel{⃑}{u}}^{\prime \prime })={\stackrel{⃑}{M}}_i·{\stackrel{⃑}{u}}^{\prime \prime }$ has nothing to do with f. And for $\rho (i)\notin S$ , $f\stackrel{⃑}{\sigma }$ can be obtained only in the equation ${\stackrel{⃑}{M}}_i^{\ast }·\stackrel{⃑}{u}+{\gamma }_i{z}_{\rho (i)}$ , where $\rho (i)$ is attribute which does not appear in the kth key. As long as each ${\gamma }_i$ mod $p_2$ is not congruent to 0, each equation brings a new unknown factor $z_{\rho (i)}$ that appears nowhere else, and so the adversary A can get nothing about f. More precisely, for any value of $u_1$ , there is the same number of solutions to these equations. Hence, as long as each ${\gamma }_i$ is nonzero modulo $p_2$ , the ciphertext and the kth key are properly distributed in the adversary's view with a probability negligibly close to 1.

Thus, if $T\in G_{p_1{p}_3}$ , then B has simulated $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k-\mathrm{1,2}}$ with A. If $T\in G$ and ${\gamma }_i$ is nonzero modulo $p_2$ , then B has simulated $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ . Hence, B can use the output result of A to distinguish between these possibilities for T. In other words, B can break Assumption 3 with advantage ε.

Hence, if the adversary A has a nonnegligible advantage ε to distinguish $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k-\mathrm{1,2}}$ and $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ , B can also distinguish element on $G_{p_{\mathrm{1}}{p}_{\mathrm{3}}}$ and G with a nonnegligible advantage ε.

Lemma 13.

Suppose that there is a polynomial time adversary A such that $Gam{e}_{k\mathit{\text{,1}}}Ad{v}_A-Gam{e}_{k\mathit{\text{,2}}}Ad{v}_A=\epsilon .$ Then, another polynomial time algorithm B, which breaks Assumption 3 with a nonnegligible advantage ε, can be constructed.

Proof.

B receives $\{g,X_{\mathrm{1}}{X}_{\mathrm{2}},X_{\mathrm{3}},Y_{\mathrm{2}}{Y}_{\mathrm{3}},T\}$ to simulate either $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ or ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_{k,2}$ with the adversary A depending on whether $T\in G$ or $T\in G_{p_1{p}_3}$ . This proof is very similar to that of Lemma 12, so here we only describe Phases 1 and 2.

Phase 1. The first ( $k-1$ ) semifunctional keys of type 2 and the last ( $Q-k$ ) normal keys are constructed exactly as in Lemma 12. To answer the kth query, B randomly chooses an exponent $h\in Z_N$ and then computes

$$\begin{array}{cc}& K=g^{\eta }{T}^a{R}_{\mathrm{0}}{\left(Y_{\mathrm{2}}{Y}_{\mathrm{3}}\right)}^h,\\ L=T{R}_{\mathrm{0}}^{\prime },\\ K_x=T^{h_x}{R}_x\hspace{1em}\forall x\in S.\end{array}$$

(19)

The only difference from Lemma 12 here is adding a term ${\left(Y_2{Y}_3\right)}^h$ which randomizes the $G_{p_2}$ part of K, so the kth key is no longer a semifunctional one. It would be failed if we try to use it to decrypt the semifunctional ciphertext, because condition $cd-b{u}_1$ ≡ 0mod $p_2$ is no longer established.

Phase 2. Phase 1 is repeated.

Hence, if $T\in G_{p_1{p}_3}$ , the kth key is a properly distributed semifunctional key of type 2 and therefore B simulates $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,2}$ for A. If $T\in G$ , the kth key is a properly distributed semifunctional key of type 1 and therefore B simulates $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ for A. As a result, if A has a nonnegligible advantage ε to distinguish $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,\mathrm{2}}$ and $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{k,1}$ , B also has a nonnegligible advantage ε to distinguish element in $G_{p_{\mathrm{1}}{p}_{\mathrm{3}}}$ and G.

Lemma 14.

Assume that there is a polynomial time adversary A such that $Gam{e}_{Q\mathit{\text{,2}}}Ad{v}_A-Gam{e}_{Final}Ad{v}_A=\epsilon .$ Then, we can construct a polynomial time algorithm B, which can break Assumption 5 with a nonnegligible advantage ε, which can be constructed.

Proof.

The proof is similar to those of Lemmas 11–13. B receives $\{g,g^{\alpha }{X}_{\mathrm{2}},X_{\mathrm{3}},g^s{Y}_{\mathrm{2}},Z_{\mathrm{2}},T\}$ to simulate $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{Q,2}$ or $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}$ with A based on whether $T=e{\left(g,g\right)}^{\eta s}$ or T is a random element of $G_T$ .

Setup. B chooses random values $a,h_x\in Z_N\hspace{0.17em}\hspace{0.17em}(\forall x\in U)$ and sends the public key PK = $\left(N,g,g_{\mathrm{0}},e(g,g{)}^{\eta }=e(g,g^{\eta }{X}_{\mathrm{2}}),g^a,H_x=g^{h_x}\hspace{0.17em}\hspace{0.17em}\forall x\right)$ to A. Note that B does not know η.

Phase 1. To form semifunctional keys of type 2, B responds to each A's key query by randomly choosing elements $t\in Z_N$ and $R_{\mathrm{0}},R_{\mathrm{0}}^{\prime },R_x\in G_{p_{\mathrm{3}}}$ and sets

$$\begin{array}{cc}& K=g^{\eta }{g}^{at}{Z}_{\mathrm{2}}^t{R}_{\mathrm{0}},\\ L=g^t{R}_{\mathrm{0}}^{\prime },\\ K_x=H_x^t{R}_x\hspace{1em}\forall x\in S\end{array}$$

(20)

which is similar as in the previous lemmas.

Challenge. A submits two messages $M_0$ and $M_1$ with equal length and a matrix ( $M^{\ast },\rho$ ) to B. B then takes s from the assumption term $g^s{Y}_2$ . It randomly chooses values $u_2,u_3,\dots ,u_n\in Z_N$ to define a vector $u^{\prime }=(a,u_{\mathrm{2}},u_{\mathrm{3}},\dots ,u_n)$ and randomly chooses an exponent $r_i^{\prime }\in Z_N$ . B chooses a random message $M_{\theta }$ from $M_0$ and $M_1$ and generates the challenge ciphertext $C^{\ast }$ as

$$\begin{array}{cc}& C=M_{\theta }T,\\ C^{\prime }=g^s{Y}_{\mathrm{2}},\\ C_i={\left(g^s{Y}_{\mathrm{2}}\right)}^{{\stackrel{⃑}{M}}_i^{\ast }{\stackrel{⃑}{u}}^{\prime }}{\left(g^s{Y}_{\mathrm{2}}\right)}^{-r_i^{\prime }{h}_{\rho \left(i\right)}},\\ D_i={\left(g^s{Y}_{\mathrm{2}}\right)}^{r_i^{\prime }},\end{array}$$

(21)

where $\theta \in \{\mathrm{0,1}\}$ is the random coin. We note that there exists $v=a^{-\mathrm{1}}s{u}^{\prime }$ and $u=c{u}^{\prime }$ , so s is being shared in the subgroup $G_{p_{\mathrm{1}}}$ and $ca$ is being shared in the subgroup $G_{p_{\mathrm{2}}}$ . At the same time, set $r_i=s{r}_i^{\prime }$ and ${\gamma }_i=-c{r}_i^{\prime }$ .

Phase 2. Repeat Phase 1.

Guess. A outputs its guess result ${\theta }^{\prime }$ of θ.

If $T=e(g,g{)}^{\eta s}$ , then this is a properly distributed semifunctional ciphertext with message $M_{\theta }$ . Otherwise, this is a semifunctional ciphertext of a random message and will not give anything about θ to the attacker.

Hence, if A can distinguish $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{Q,2}$ and $\mathrm{G}\mathrm{a}\mathrm{m}{\mathrm{e}}_{\mathrm{F}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}$ with a nonnegligible advantage ε, B can distinguish the element $e(g,g{)}^{\eta s}$ and a random element in $G_T$ with a nonnegligible advantage ε.

Theorem 15.

If Assumptions 1, 3, and 5 hold, our CP-ABPRE scheme is adaptively secure.

Proof.

If Assumptions 1, 3, and 5 hold, we have proved that the real CP-ABPRE security game $\text{Gam}{\text{e}}_{\text{real}}$ is indistinguishable from $\text{Gam}{\text{e}}_{\text{Final}}$ by previous Lemmas 11–14. And because the challenger in $\text{Gam}{\text{e}}_{\text{Final}}$ chooses a random message $M_{\theta }$ to encrypt, the adversary could not get any information on θ. In other words, the advantage of adversary in $\text{Gam}{\text{e}}_{\text{Final}}$ can be negligible, so the advantage of the adversary in $\text{Gam}{\text{e}}_{\text{real}}$ can be also negligible. Hence, our CP-ABPRE scheme is secure.

5.3. Analyses and Discussions

5.3.1. Security Analysis

The reencryption control, which allows the encryptor to decide whether the ciphertext can be reencrypted, was first put forward by Luo et al. in [7]. In our CP-ABPRE scheme, we can see that the element $C^{\prime \prime }=g_0^s$ is of no use in the original ciphertext decryption phase, and it is only used in the reencrypted ciphertext decryption phase. If the encryptor does not provide the factor $g_0^s$ , it is impossible for the decryption of reencrypted ciphertext. So in our scheme, the encryptor can control whether the ciphertext can be reencrypted (in fact he can decide whether the reencrypted ciphertext can be decrypted). In addition, our scheme overcomes the restriction on the attacker in a selective security model in the existing schemes [6–9, 11] and is proven adaptively secure in the standard model without jeopardizing the expressiveness of access policy.

5.3.2. Performance Analyses

In this part, we will make some comparisons of different CP-ABPRE schemes, and the results are summarized in Tables 1–3. A comparison of access expression and some properties is given in Table 1. In addition, we shall compare the performance and efficiency of our proposal with the existing ones in Tables 2 and 3. We use $\left|A_U\right|$ , $\left|A_C\right|$ , and n to denote the attributes held by user U, the attributes required by the ciphertext, and the number of attributes in systems, respectively. We use G to denote the operation in group G, $G_T$ for the operation in group $G_T$ , and P for the bilinear pairing operation. We use symbol $L_{\ast }$ to denote the bit length of element in ∗. At last, we use $N^{\prime }={\sum }_{i=\mathrm{1}}^n{n}_i$ to denote the total number of possible values of attributes, where $n_i$ is the number of possible values for attribute i.

Table 1

Property comparisons.

Schemes	Access structure	Adaptive security	Complexity assumption	Supported policy
Liang et al.'s [6]	AND gate between two-value attributes	N	ADBDH CTDH	And
Luo et al.'s [7]	AND gate among multivalue attributes	N	DBDH	And
Seo and Kim's [8]	AND gate between two-value attributes	N	ADBDH CTDH	And
Li's [9]	LSSS matrix	N	DPBDHE	Any monotonic access formula
Liang et al.'s [11]	LSSS matrix	N	DPBDHE	Any monotonic access formula
Liang et al.'s [14]	LSSS matrix	Y	DPBDHE	Any monotonic access formula
Backes et al.'s [15]	LSSS matrix	Y	DPBDHE	And
Our scheme	LSSS matrix	Y	3P-SDP	Any monotonic access formula

DBDH: Decisional Bilinear Diffie-Hellman, CTDH: Complex Triple Diffie-Hellman, ADBDH: Augment Decisional Bilinear Diffie-Hellman, 3P-SDP: subgroup decision problem for 3 primes, and DPBDHE: Decisional q-Parallel Bilinear Diffie-Hellman Exponent.

Table 2

Performance comparisons (I).

Schemes	PK	MK	SK	Ciphertext
Liang et al.'s [6]	$$(\mathrm{6}n+\mathrm{2})L_G+L_{G_T}$$	$$(\mathrm{3}n+\mathrm{1})L_{Z_q}$$	$$(\mathrm{2}n+\mathrm{1})L_G$$	$$(n+\mathrm{2})L_G+L_{G_T}$$
Luo et al.'s [7]	$$(N^{\prime }+\mathrm{2}n+\mathrm{4})L_G+L_{G_T}$$	$$(N^{\prime }+\mathrm{2}n+\mathrm{1})L_{Zq}$$	$$(\mathrm{4}n+\mathrm{1})L_G$$	$$(n+\mathrm{2})L_G+L_{G_T}$$
Seo and Kim's [8]	$$(\mathrm{3}n+\mathrm{2})L_G+L_{G_T}+\mathrm{3}n{L}_{Z_q}$$	$$(\mathrm{3}n+\mathrm{3})L_{Z_q}$$	$$(n+\mathrm{1})L_G+L_{Z_q}$$	$$(n+\mathrm{2})L_G+L_{G_T}$$
Li's [9]	$$(n+\mathrm{2})L_G+L_{G_T}$$	$$L_G$$	$$(\left|A_U\right|+\mathrm{2})L_G$$	$$(\mathrm{2}\left|A_C\right|+\mathrm{2})L_G+L_{G_T}$$
Liang et al.'s [11]	$$\mathrm{3}{L}_G+L_{G_T}+\mathrm{6}\mathrm{H}\mathrm{a}\mathrm{s}\mathrm{h}$$	$$L_G$$	$$(\left|A_U\right|+\mathrm{2})L_G$$	$$(\mathrm{2}\left|A_C\right|+\mathrm{3})L_G+L_{{\left\{\mathrm{0},\mathrm{1}\right\}}^{\mathrm{2}k}}$$
Liang et al.'s [14]	$$(n+\mathrm{6})L_G+L_{G_T}$$	$$\mathrm{2}{L}_G$$	$$(\left|A_U\right|+\mathrm{3})L_G$$	$$(\mathrm{2}\left|A_C\right|+\mathrm{5})L_G+L_{G_T}$$
Backes et al.'s [15]	$$(n+\mathrm{2})L_G+L_{G_T}$$	$$L_G+(\mathrm{1}+n)L_{Z_q}$$	$$(n+\mathrm{1})L_G$$	$$\mathrm{3}{L}_G+L_{G_T}+n{L}_{Z_q}$$
Our scheme	$$(n+\mathrm{2})L_G+L_{G_T}$$	$$L_G+L_{Z_q}$$	$$(\left|A_U\right|+\mathrm{2})L_G$$	$$(\mathrm{2}\left|A_C\right|+\mathrm{2})L_G+L_{G_T}$$

Table 3

Performance comparisons (II).

Schemes	Encryption	Decryption	Reencryption	Reencrypted decryption
Liang et al.'s [6]	$$(n+\mathrm{2})G+\mathrm{2}{G}_T$$	$$(n+\mathrm{2})P+\mathrm{2}{G}_T$$	$$(n+\mathrm{1})P+G_T$$	$$(n+\mathrm{3})P+\mathrm{4}{G}_T$$
Luo et al.'s [7]	$$(n+\mathrm{2})G+\mathrm{2}{G}_T$$	$$\mathrm{2}nP+\mathrm{3}{G}_T$$	$$(\mathrm{2}n+\mathrm{1})P+(n+\mathrm{1})G_T$$	$$(\mathrm{2}n+\mathrm{1})P+\mathrm{5}{G}_T$$
Seo and Kim's [8]	$$(n+\mathrm{2})G+\mathrm{2}{G}_T$$	$$\mathrm{2}P+(\mathrm{3}n+\mathrm{2})G+\mathrm{2}{G}_T$$	$$\mathrm{2}P+\mathrm{3}nG+G_T$$	$$\mathrm{3}P+\mathrm{3}nG+\mathrm{4}{G}_T$$
Li's [9]	$$(\mathrm{4}\left|A_C\right|+\mathrm{2})G+\mathrm{2}{G}_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{1})P+\mathrm{3}{G}_T$$	$$(\mathrm{2}\left|A_C\right|+\mathrm{1})P+\mathrm{4}\left|A_C\right|G+\mathrm{3}\left|A_C\right|G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{1})P+(\mathrm{3}\left|A_U\right|+\mathrm{2})G_T$$
Liang et al.'s [11]	$$(\mathrm{4}\left|A_C\right|+\mathrm{2})G+G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{1})P+\mathrm{3}\left|A_U\right|G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{2})P+(\mathrm{3}\left|A_U\right|+\mathrm{1})G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{2})P+\mathrm{3}\left|A_U\right|G_T$$
Liang et al.'s [14]	$$(\mathrm{4}\left|A_C\right|+\mathrm{4})G+\mathrm{2}{G}_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{1})P+(\mathrm{2}\left|A_U\right|+\mathrm{1})G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{2})P+(\mathrm{2}\left|A_U\right|+\mathrm{2})G_T$$	$$(\mathrm{2}\left|A_U\right|+\mathrm{3})P+(\mathrm{2}\left|A_U\right|+\mathrm{4})G_T$$
Backes et al.'s [15]	$$(n+\mathrm{3})G+\mathrm{2}{G}_T$$	$$\mathrm{2}P+nG$$	$$nP+(n-\mathrm{1})G$$	$$nP+\mathrm{2}G+G_T$$
Our scheme	$$(\mathrm{4}\left|A_C\right|+\mathrm{2})G+\mathrm{2}{G}_T$$	$$\mathrm{2}P+(\mathrm{4}\left|A_U\right|-\mathrm{1})G+\mathrm{2}{G}_T$$	$$\mathrm{2}P+(\mathrm{4}\left|A_U\right|-\mathrm{1})G+\mathrm{2}{G}_T$$	$$\mathrm{3}P+(\mathrm{4}\left|A_U\right|-\mathrm{1})G+\mathrm{4}{G}_T$$

From Tables 1–3, we can draw the following conclusions. Liang et al. [6], Luo et al. [7], Seo and Kim [8], and Backes et al. [15], respectively, proposed their schemes based on the CP-ABE in which the ciphertext is associated with AND gates access structure. However, the access policy in these four schemes is not flexible enough; it can only support AND operation on attributes. The ciphertext policy realized in Li's [9], Liang et al.'s [11, 14], and our scheme is LSSS matrix access structure which supports any monotonic access formula including what the AND gate access structure supports. Different from Li's [9] and Liang et al.'s [11] schemes, our scheme is adaptively secure. And, what is more, our scheme needs only a constant number of paring operations in Reencryption and Decryption phase when compared with Liang et al.'s scheme [14]. That is, our scheme greatly reduces the computational overhead.

From the above analysis, we can conclude that our scheme is more efficient and secure than previous CP-ABPRE schemes.

6. Conclusions

CP-ABPRE employs the PRE technology in the ABE cryptographic setting and could be applicable to many real world applications, such as email forwarding. The existing CP-ABPRE systems, however, were proven secure only in the selective security model which causes attacker to behave differently from real environment. So an efficient and adaptively secure Attribute-Based Proxy Reencryption scheme is proposed in this paper. By using the dual system encryption, the proposed scheme can be proven to be adaptively secure rather than selectively secure which is much less practical. Meantime, our scheme supports any monotone access formulas including what the AND gate access structure supports. And compared with the existing schemes, our scheme needs only a constant number of paring operations in Reencryption and Decryption phase, which greatly reduces the computational overhead.