# Efficient and Adaptively Secure Attribute-Based Proxy Reencryption Scheme

Authors: Huixian Li; Liaojun Pang
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## 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.


---

## Body

## 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 Section3, 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 GT be a cyclic additive group and a multiplication cyclic group of order N, where N=p1p2p3 and p1, p2, and p3 are three distinct prime numbers. Let e:G×G→GT be a bilinear map.Then, letGp1, Gp2, and Gp3 denote the subgroups of order p1, p2, and p3 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 GT be two cyclic groups of order N, where N=p1p2p3 and p1, p2, and p3 are three distinct primes. And we let Gp1, Gp2, and Gp3 denote the subgroups of order p1, p2, and p3 in G, respectively. Let e:G×G→GT be a bilinear map.Assumption 1.
We randomly choose elementg as the generator of Gp1 and element X3 as the generator of Gp3. Given D=(N,G,GT,e,g,X3), T1∈Gp1p2 and T2∈Gp1. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 1 is defined as(1)AdvA1λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 2.
Assumption1 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA1(λ).Assumption 3.
We randomly choose elementsg,X1∈Gp1,X2,Y2∈Gp2, and X3,Y3∈Gp3. Given D=(N,G,GT,e,g,X1X2,X3,Y2Y3) and T1∈G, T2∈Gp1p3. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 3 is defined as(2)AdvA2λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 4.
Assumption3 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA2(λ).Assumption 5.
We randomly choose elementsα,s∈ZN,g∈Gp1,X2,Y2,Z2∈Gp2, and X3∈Gp3. Given D=(N,G,GT,e,g,gαX2,X3,gsY2,Z3) and T1=e(g,g)αs, T2∈GT. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 5 is defined as(3)AdvA3λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 6.
Assumption5 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA3(λ).


### 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 Zp if(1)
the shares distributed for each participant can form a vector overZp;(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 ρ(i) for i=1,2,…,l. The column vector v→=(s,y2,y3,…,yn) is randomly chosen in Zpn. Then, M⃑i·v⃑ is the share belonging to party ρ(i). We use LSSS matrix (M,ρ) 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∈A denote the authorized set and define I⊆{1,2,…,l} as I=i∣ρi∈S. Then, there exist wi∈Zpi∈I such that if λi are valid shares of any secret s, we have ∑i∈Iwiλi=s [41]. But it does not hold for unauthorized sets. In our scheme, we will employ LSSS matrices over ZN, 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.S
e
t
u
p
(
1
λ
,
U
)
→
(
M
S
K
,
P
K
). 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).K
e
y
G
e
n
(
P
K
,
M
S
K
,
S
)
→
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 SKS.E
n
c
(
P
K
,
W
=
(
M
,
ρ
)
,
m
)
→
C
T
W. Performed by a sender, with PK, a message m, and an access policy W=(M,ρ) as input, the algorithm generates a ciphertext CTW of m such that only a user whose attributes meet the access policy W can decrypt it.R
e
K
e
y
G
e
n
(
P
K
,
S
K
S
,
W
′
=
M
′
,
ρ
′
)
→
R
K
S
→
W
′. This algorithm is performed by the delegator. With PK, SKS, and an access policy W′=M′,ρ′ as input, it generates a reencryption key RKS→W′ for the proxy.R
e
E
n
c
(
P
K
,
R
K
S
→
W
′
,
C
T
W
)
→
C
T
W
′. It is performed by the proxy, with PK, RKS→W′, and CTW as input. Firstly, the proxy checks whether the attribute in RKS→W′ meets the access policy of CTW. If yes, it outputs a reencrypted ciphertext CTW′ and otherwise ⊥.D
e
c
(
P
K
,
C
T
W
,
S
K
S
)
→
m. With PK, an original ciphertext CTW, and a secret key SKS as input, it returns the plaintext message m if S satisfies the access policy W specified for CTW, and otherwise ⊥.D
e
c
R
(
P
K
,
C
T
W
′
,
S
K
S
′
)
→
m. This algorithm returns the plaintext message m if S′ meets the access policy W′ specified for CTW′, and otherwise ⊥.


#### 3.4.2. Security Model

The adaptive security definition for a CP-ABPRE scheme is described by a security game between a challengerB and an adversary A, which is shown as follows.Setup. B runs theSetup 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 theKeyGen algorithm after A submitting sets of attribute S1,S2,…,Sq1 and returns secret keys SKS to A.(ii) Reencryption Key Extract Queries. A submits sets of attribute S1,S2,…,Sq1 and an access structure W′=M′,ρ′. Then, B runs theReKeyGen algorithm and gives the reencryption key RKS→W′ to A.Challenge.
A chooses two messages M0 and M1 with equal length and an access structure W∗, which cannot be met by any of the queried attribute sets {S1,S2,…,Sq1}. B randomly flips coin θ∈{0,1} and encrypts Mθ under W∗ to generate CT∗, which is then sent to A.Phase 2. Phase 1 is repeated. Note that there is a restriction that no sets of attributes {Sq1+1,Sq1+2,…,Sq} can satisfy the access structure corresponding to B.Guess. A outputs a guess result θ′ for θ.In the above game, the advantage ofA is defined as AdvA=Prθ′=θ-1/2. 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 theSetup algorithm to create a new system and then sends the adversary A the public key (PK).
Queries. A makes the following queries.
(i)
E
x
t
r
a
c
t
(
S
). B runs theKeyGen algorithm after A submitting attribute sets S and returns secret keys SKS to A.
(ii)
R
K
E
x
t
r
a
c
t
(
S
,
W
′
)
.
A submits attribute sets S and an access structure W′=M′,ρ′ to B. Then, B runs theReKeyGen algorithm and returns the reencryption key RKS→W′ to A.
Output. A outputs the secret key SKS∗ corresponding to the attribute sets S∗.
In the above game, the advantage ofA is defined as AdvA=Pr[Asucceeds]. 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 adversaryA who can break its master secret security defined above, then there also exists an adversary A′ who can break this CP-ABPRE scheme.In Section5, 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.


## 3.1. Composite Order Bilinear Groups

Composite order bilinear groups were introduced by Boneh et al. [41]. First, let G and GT be a cyclic additive group and a multiplication cyclic group of order N, where N=p1p2p3 and p1, p2, and p3 are three distinct prime numbers. Let e:G×G→GT be a bilinear map.Then, letGp1, Gp2, and Gp3 denote the subgroups of order p1, p2, and p3 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 GT be two cyclic groups of order N, where N=p1p2p3 and p1, p2, and p3 are three distinct primes. And we let Gp1, Gp2, and Gp3 denote the subgroups of order p1, p2, and p3 in G, respectively. Let e:G×G→GT be a bilinear map.Assumption 1.
We randomly choose elementg as the generator of Gp1 and element X3 as the generator of Gp3. Given D=(N,G,GT,e,g,X3), T1∈Gp1p2 and T2∈Gp1. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 1 is defined as(1)AdvA1λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 2.
Assumption1 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA1(λ).Assumption 3.
We randomly choose elementsg,X1∈Gp1,X2,Y2∈Gp2, and X3,Y3∈Gp3. Given D=(N,G,GT,e,g,X1X2,X3,Y2Y3) and T1∈G, T2∈Gp1p3. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 3 is defined as(2)AdvA2λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 4.
Assumption3 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA2(λ).Assumption 5.
We randomly choose elementsα,s∈ZN,g∈Gp1,X2,Y2,Z2∈Gp2, and X3∈Gp3. Given D=(N,G,GT,e,g,gαX2,X3,gsY2,Z3) and T1=e(g,g)αs, T2∈GT. Let λ be the security parameter and the advantage of a polynomial time algorithm A in breaking Assumption 5 is defined as(3)AdvA3λ=PrAD,T1=1-Pr⁡AD,T2=1.Definition 6.
Assumption5 holds if there is no polynomial time algorithm A which has a nonnegligible advantage AdvA3(λ).


## 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 Zp if(1)
the shares distributed for each participant can form a vector overZp;(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 ρ(i) for i=1,2,…,l. The column vector v→=(s,y2,y3,…,yn) is randomly chosen in Zpn. Then, M⃑i·v⃑ is the share belonging to party ρ(i). We use LSSS matrix (M,ρ) 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∈A denote the authorized set and define I⊆{1,2,…,l} as I=i∣ρi∈S. Then, there exist wi∈Zpi∈I such that if λi are valid shares of any secret s, we have ∑i∈Iwiλi=s [41]. But it does not hold for unauthorized sets. In our scheme, we will employ LSSS matrices over ZN, 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.S
e
t
u
p
(
1
λ
,
U
)
→
(
M
S
K
,
P
K
). 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).K
e
y
G
e
n
(
P
K
,
M
S
K
,
S
)
→
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 SKS.E
n
c
(
P
K
,
W
=
(
M
,
ρ
)
,
m
)
→
C
T
W. Performed by a sender, with PK, a message m, and an access policy W=(M,ρ) as input, the algorithm generates a ciphertext CTW of m such that only a user whose attributes meet the access policy W can decrypt it.R
e
K
e
y
G
e
n
(
P
K
,
S
K
S
,
W
′
=
M
′
,
ρ
′
)
→
R
K
S
→
W
′. This algorithm is performed by the delegator. With PK, SKS, and an access policy W′=M′,ρ′ as input, it generates a reencryption key RKS→W′ for the proxy.R
e
E
n
c
(
P
K
,
R
K
S
→
W
′
,
C
T
W
)
→
C
T
W
′. It is performed by the proxy, with PK, RKS→W′, and CTW as input. Firstly, the proxy checks whether the attribute in RKS→W′ meets the access policy of CTW. If yes, it outputs a reencrypted ciphertext CTW′ and otherwise ⊥.D
e
c
(
P
K
,
C
T
W
,
S
K
S
)
→
m. With PK, an original ciphertext CTW, and a secret key SKS as input, it returns the plaintext message m if S satisfies the access policy W specified for CTW, and otherwise ⊥.D
e
c
R
(
P
K
,
C
T
W
′
,
S
K
S
′
)
→
m. This algorithm returns the plaintext message m if S′ meets the access policy W′ specified for CTW′, and otherwise ⊥.


### 3.4.2. Security Model

The adaptive security definition for a CP-ABPRE scheme is described by a security game between a challengerB and an adversary A, which is shown as follows.Setup. B runs theSetup 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 theKeyGen algorithm after A submitting sets of attribute S1,S2,…,Sq1 and returns secret keys SKS to A.(ii) Reencryption Key Extract Queries. A submits sets of attribute S1,S2,…,Sq1 and an access structure W′=M′,ρ′. Then, B runs theReKeyGen algorithm and gives the reencryption key RKS→W′ to A.Challenge.
A chooses two messages M0 and M1 with equal length and an access structure W∗, which cannot be met by any of the queried attribute sets {S1,S2,…,Sq1}. B randomly flips coin θ∈{0,1} and encrypts Mθ under W∗ to generate CT∗, which is then sent to A.Phase 2. Phase 1 is repeated. Note that there is a restriction that no sets of attributes {Sq1+1,Sq1+2,…,Sq} can satisfy the access structure corresponding to B.Guess. A outputs a guess result θ′ for θ.In the above game, the advantage ofA is defined as AdvA=Prθ′=θ-1/2. 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 theSetup algorithm to create a new system and then sends the adversary A the public key (PK).
Queries. A makes the following queries.
(i)
E
x
t
r
a
c
t
(
S
). B runs theKeyGen algorithm after A submitting attribute sets S and returns secret keys SKS to A.
(ii)
R
K
E
x
t
r
a
c
t
(
S
,
W
′
)
.
A submits attribute sets S and an access structure W′=M′,ρ′ to B. Then, B runs theReKeyGen algorithm and returns the reencryption key RKS→W′ to A.
Output. A outputs the secret key SKS∗ corresponding to the attribute sets S∗.
In the above game, the advantage ofA is defined as AdvA=Pr[Asucceeds]. 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 adversaryA who can break its master secret security defined above, then there also exists an adversary A′ who can break this CP-ABPRE scheme.In Section5, 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.


## 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.S
e
t
u
p
(
1
λ
,
U
)
→
(
M
S
K
,
P
K
). 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).K
e
y
G
e
n
(
P
K
,
M
S
K
,
S
)
→
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 SKS.E
n
c
(
P
K
,
W
=
(
M
,
ρ
)
,
m
)
→
C
T
W. Performed by a sender, with PK, a message m, and an access policy W=(M,ρ) as input, the algorithm generates a ciphertext CTW of m such that only a user whose attributes meet the access policy W can decrypt it.R
e
K
e
y
G
e
n
(
P
K
,
S
K
S
,
W
′
=
M
′
,
ρ
′
)
→
R
K
S
→
W
′. This algorithm is performed by the delegator. With PK, SKS, and an access policy W′=M′,ρ′ as input, it generates a reencryption key RKS→W′ for the proxy.R
e
E
n
c
(
P
K
,
R
K
S
→
W
′
,
C
T
W
)
→
C
T
W
′. It is performed by the proxy, with PK, RKS→W′, and CTW as input. Firstly, the proxy checks whether the attribute in RKS→W′ meets the access policy of CTW. If yes, it outputs a reencrypted ciphertext CTW′ and otherwise ⊥.D
e
c
(
P
K
,
C
T
W
,
S
K
S
)
→
m. With PK, an original ciphertext CTW, and a secret key SKS as input, it returns the plaintext message m if S satisfies the access policy W specified for CTW, and otherwise ⊥.D
e
c
R
(
P
K
,
C
T
W
′
,
S
K
S
′
)
→
m. This algorithm returns the plaintext message m if S′ meets the access policy W′ specified for CTW′, and otherwise ⊥.


## 3.4.2. Security Model

The adaptive security definition for a CP-ABPRE scheme is described by a security game between a challengerB and an adversary A, which is shown as follows.Setup. B runs theSetup 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 theKeyGen algorithm after A submitting sets of attribute S1,S2,…,Sq1 and returns secret keys SKS to A.(ii) Reencryption Key Extract Queries. A submits sets of attribute S1,S2,…,Sq1 and an access structure W′=M′,ρ′. Then, B runs theReKeyGen algorithm and gives the reencryption key RKS→W′ to A.Challenge.
A chooses two messages M0 and M1 with equal length and an access structure W∗, which cannot be met by any of the queried attribute sets {S1,S2,…,Sq1}. B randomly flips coin θ∈{0,1} and encrypts Mθ under W∗ to generate CT∗, which is then sent to A.Phase 2. Phase 1 is repeated. Note that there is a restriction that no sets of attributes {Sq1+1,Sq1+2,…,Sq} can satisfy the access structure corresponding to B.Guess. A outputs a guess result θ′ for θ.In the above game, the advantage ofA is defined as AdvA=Prθ′=θ-1/2. 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 theSetup algorithm to create a new system and then sends the adversary A the public key (PK).
Queries. A makes the following queries.
(i)
E
x
t
r
a
c
t
(
S
). B runs theKeyGen algorithm after A submitting attribute sets S and returns secret keys SKS to A.
(ii)
R
K
E
x
t
r
a
c
t
(
S
,
W
′
)
.
A submits attribute sets S and an access structure W′=M′,ρ′ to B. Then, B runs theReKeyGen algorithm and returns the reencryption key RKS→W′ to A.
Output. A outputs the secret key SKS∗ corresponding to the attribute sets S∗.
In the above game, the advantage ofA is defined as AdvA=Pr[Asucceeds]. 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 adversaryA who can break its master secret security defined above, then there also exists an adversary A′ who can break this CP-ABPRE scheme.In Section5, 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 orderN=p1p2p3 (p1, p2, and p3 are 3 different prime numbers) with LSSS access structure. Let Gpi denote the subgroup of order pi in G where i∈{1,2,3}. The subgroup Gp2 is only used in security proof. Our scheme is shown as follows.(1)
S
e
t
u
p
(
1
λ
,
U
). Taking as input the security parameter λ and system attribute set U, the trusted authority chooses random elements η,a∈ZN, a generator g∈Gp1, an element g0∈Gp1, and a generator X3∈Gp3. And then it computes g1=e(g,g)η and g2=ga. For each attribute x∈U, it also chooses a random element hx∈ZN and computes Hx=ghx. The public key is denoted as(4)PK=N,g0,g1,g2,Hx,∀x∈U.The trusted authority sets the master secret key as MSK=η,X3.(2)
K
e
y
G
e
n
(
P
K
,
M
S
K
,
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∈ZN and another three random elements R0,R0′,Rx∈Gp3. Then, it computes the secret key as(5)SK=S,K=gηgatR0,L=gtR0′,Kx=HxtRx,∀x∈S.(3)
E
n
c
(
P
K
,
W
,
m
)
. This algorithm takes as input the public key (PK), an access policy W=(M,ρ), and a message m, where M is an l×n matrix and the function ρ associates rows of M to attributes. This algorithm randomly chooses a column vector v⃑=(s,y2,y3,…,yn)∈ZNn. These values will be used to share the encryption exponent s. For i=1,2,…,l, it computes λi=M⃑i·v⃑, where M⃑i denotes the ith row of M. Then, the algorithm chooses random numbers r1,r2,…,rl∈ZN.The ciphertext is generated as(6)CT=C=meg,gηs,C′=gs,C′′=g0s,Ci=gaM⃑i·v⃑Hρi-ri,Di=gri,∀i∈1,2,…,l.(4)
R
e
K
e
y
G
e
n
P
K
,
S
K
,
W
′. To generate a reencryption key for another access policy W′=M′,ρ′, this algorithm takes as input the public key PK, the secret key SK = (S,K,L,Kx,∀x∈S), and another access policy W′=M′,ρ′. It needs to choose a random element β∈ZN and computes C^=EncPK,W′,gβ. Then the reencryption key is set to (7)RK=S,rk1=Kg0β,rk2=L,Kx′=Kx,C^,∀x∈S.(5)
R
e
E
n
c
(
P
K
,
R
K
,
C
T
). This algorithm takes as input the public key (PK), a reencryption key (RK), and a ciphertext CT=C,C′,C′′,Ci,Di,∀i. It first checks whether the attribute set in RK meets the access policy of CT. It computes(8)Ct=eC′,rk1∏i∈IeCi,rk2eDi,Kρi′wiand outputs a reencrypted ciphertext CT′=C,C′,C^,Ct if yes and outputs ⊥ otherwise.(6)
D
e
c
(
P
K
,
C
T
,
S
K
). 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⊂1,2,…,l is defined as I=i∣ρi∈S. Then, let wi∈ZNi∈I be a set of constants such that if λi are valid shares of any secret s according to M, then, ∑i∈Iwiλi=s holds.The messagem can be recovered as(9)m=C∏i∈IeCi,LeDi,KρiwieC′,K=Ce∏i∈ICi-wi,LeC′,K∏i∈IKρi-wi.(7)
D
e
c
R
(
P
K
,
C
T
′
,
S
K
′
). The reencrypted ciphertext decryption algorithm takes the public key (PK), a reencrypted ciphertext CT′ for access policy W′, and a secret key SK′ for an attribute set S′ as input. If S′ satisfies W′, this algorithm computes as follows:(7.1)
Decryptgβ from C^ by theDec algorithm.(7.2)
Then compute the messagem by m=Ce(C′′,gβ)/Ct.


## 5. Analyses and Proof

### 5.1. Correctness Analyses

The correctness of the scheme is based on the bilinear character of pairinge:G×G→GT. First, we show the correctness of the original ciphertext decryption as follows:(10)m=C∏i∈IeCi,LeDi,KρiwieC′,K=meg,gηs∏i∈IegaM⃑i·v⃑Hρi-ri,gtR0′egri,HρitRρiwiegs,gηgat=meg,gηseg,gat∑i∈IM⃑i·v⃑wieg,gηseg,gsat=m.Then, the correctness of the decryption algorithm for the reencrypted ciphertext is shown as follows:(11)m=CeC′′,gβCt=CeC′′,gβ∏i∈IeCi,rk2eDi,Kρi′wieC′,rk1=meg,gηseg0s,gβ∏i∈IegaM⃑i·v⃑Hρi-ri,gtR0′egri,HρitRρiwiegs,gηgatg0βR0=meg,gsηeg0s,gβeg,gat∑i∈IM⃑i·v⃑wieg,gsηeg,g0sβeg,gsat=m.Both the original ciphertext decryption and the reencrypted ciphertext decryption processes in Section4 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.Letg2 be a generator of Gp2.Semifunctional Ciphertexts. We firstly use theEnc algorithm to generate normal ciphertext and choose element c∈ZN randomly. Then, we choose random values zx∈ZN for each attribute, random values γi∈ZN for the ith row of matrix M, and a random column vector u⃑∈ZNn. The semifunction ciphertext is set as(12)C′=gsg2c,Ci=gaM⃑i·v⃑Hρi-rig2M⃑i·u⃑+γizρi,Di=grig2-γi∀i∈1,2,…,l.Semifunctional Key. We useKeyGen algorithm to generate normal secret key. And then we choose random exponents b,d∈ZN to set the semifunctional key as follows.A semifunctional key of type 1 is(13)K=gηgatR0g2d,L=gtR0′g2d,Kx=HxtRxg2bzx∀x∈S.A semifunctional key of type 2 (in type 1b=0) is(14)K=gηgatR0g2d,L=gtR0′,Kx=HxtRx∀x∈S.We should note that there will be an extra factore(g2,g2)cd-∑i∈IbM⃑i·u⃑wi=e(g2,g2)cd-bu1 (u1=(1,0,0,…,0)·u⃑) when a semifunctional key is used to decrypt a semifunctional ciphertext. But when the formula cd=bu1 holds, the semifunctional key of type 1 called a nominally semifunctional key can decrypt the semifunctional ciphertext successfully.Our proof of security relies on Assumptions1, 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,G
a
m
e
r
e
a
l. It denotes the real CP-ABPRE security game defined in Section 3, with normal keys and ciphertexts.G
a
m
e
0. It is similar to the above real game except that the challenge ciphertext is transformed into semifunctional one.G
a
m
e
k
,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.G
a
m
e
k
,2. The challenge ciphertext is semifunctional, the first k queried keys are semifunctional ones of type 2, and the remaining keys are normal ones.G
a
m
e
F
i
n
a
l. 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 adversaryA such that GamerealAdvA-Game0AdvA=ε. Then, we can construct another polynomial time algorithm B that can break Assumption 1 with a nonnegligible advantage ε.Proof.
We establish a polynomial time algorithmB which receives {g,X3,T} to simulate either Gamereal or Game0 with A based on setting whether T∈Gp1p2 or T∈Gp1.
Setup. B chooses random exponents a,η,hx∈ZN(∀x), sends the public key PK = N,g,g0,e(g,g)η,ga,Hx=ghx∀x to the adversary A, and at the same time securely keeps the master secret key MSK = η,X3.
Phase 1. B responds to whatever A’s key requests by using theKeyGen algorithm to make normal keys, since it has the MSK.
Challenge.
A provides two messages M0 and M1 with equal length and a challenge access matrix W∗=(M∗,ρ) to B. For each row i of matrix M∗, B first chooses random values v2′,v3′,…,vn′∈ZN and a random element ri′∈ZN to build the column vector v⃑′=1,v2′,v3′,…,vn′. Then, B chooses a random message Mθ from M0 and M1 and computes the challenge ciphertext C∗ as(15)C=Mθeg,gsη=Mθeg,Tη,C′=TCi=TaM⃑i∗·v⃑′T-ri′hρi,Di=Tri′,where θ∈{0,1} is the random coin.
Phase 2. Repeat Phase 1.
Guess. A outputs its guess result θ′ of θ.
IfT∈Gp1, let T=gs. This is a normal ciphertext with v⃑=sv⃑′ and ri=ri′s. B has simulated Gamereal for A. If T∈Gp1p2, let T=gsg2c. This is a semifunctional ciphertext with u=cav′,γi=-cri′, and zρ(i)=hρ(i). By the Chinese Remainder Theorem (CRT), the values of a,v2′,v3′,…,vn′,ri′,hρ(i) modulo p2 are uncorrelated to their values modulo p1. B has simulated Game0 for A.
Hence, ifA can distinguish Gamereal and Game0 with a nonnegligible advantage ε, B can distinguish element on Gp1 and Gp1p2 with a nonnegligible advantage ε.Lemma 12.
Assume that there is a polynomial time adversaryA such that Gamek-1,2AdvA-Gamek,1AdvA=ε. Then, another polynomial time algorithm B, which can break Assumption 3 with a nonnegligible advantage ε, can be constructed.Proof.
B receives g,X1X2,X3,Y2Y3,T to simulate either Gamek-1,2 or Gamek,1 with A based on setting whether T∈G or T∈Gp1p3.
Setup. B chooses random exponents a,η,hx∈ZN(∀x∈U) to generate the public key PK = N,g,g0,e(g,g)η,ga,Hx=ghx∀x and sends it to A. At the same time, B should securely keep the master secret key MSK = η,X3.
Phase 1. This phase can be divided into three parts.(1)
To form the firstk-1 semifunctional keys of type 2, B responds to each A’s key query by randomly choosing elements t∈ZN and R0′,Rx∈Gp3 and sets(16)K=gηgatY2Y3t,L=gtR0′,Kx=HxtRx∀x∈S.(2)
To generate the normal keys of queries greater thank, B needs to run theKeyGen algorithm since it has the master secret key (MSK).(3)
To answer thekth query, set gt equal to the Gp1 part of T. Then, B randomly chooses elements R0,R0′,Rx∈Gp3 and computes(17)K=gηTaR0,L=TR0′,Kx=ThxRx∀x∈S.If T∈Gp1p3, the above key is a normal one. And if T∈G, it is a semifunctional one of type 1. In this case, there exists zx=hx. If we let factor g2b denote the Gp2 part of T, there is d≡bamodp2. Note that zxmodp2 is uncorrelated to hxmodulop1, let g2ba be equal to the Gp2 part of K, let g2b be equal to the Gp2 part of L, and let g2bzx be equal to the Gp2 part of Kx.
Challenge. A provides two messages M0 and M1 with equal length and a challenge access matrix (M∗,ρ) for B. B sets gs=X1 and g2b=X2. Then, B chooses random values u2,u3,…,un∈ZN to define the vector u⃑′=a,u2,u3,…,un and randomly chooses exponent ri′∈ZN. B chooses a random message Mθ from M0 and M1 and computes the challenge ciphertext C∗ as(18)C=Mθeg,X1X2η,C′=X1X2,Ci=X1X2M⃑i∗·u′X1X2-ri′hρi,Di=X1X2ri′,where θ∈{0,1} is the random coin. We set v⃑=a-1su⃑′ and u⃑=cu⃑′, so s is shared in the subgroup Gp1 and c·a is shared in the subgroup Gp2. It also sets ri=s·ri′ and γi=-c·ri′. The values zρ(i)=hρ(i) match those in the kth key if it is semifunctional of type 1.
Actually, if thekth key can be used to decrypt the challenge ciphertext, then cd-bu1=cba-bca=0 modulo p2 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∉S, zx 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 (1,0,…,0). Thus, we denote a vector σ⃑ that is orthogonal to R and not orthogonal to vector (1,0,…,0). We set an equation that u⃑=fσ⃑+u⃑′′ for f∈ZN and u′′ is in the span of the basis elements not equal to σ⃑. We note that u′′ is properly distributed and reveals nothing about f. Since u1=u⃑·(1,0,0,…,0)=f(1,0,0,…,0)·σ⃑+(1,0,0,…,0)·u⃑′′ and (1,0,0,…,0)·σ⃑≠0, the item u⃑·(1,0,0,…,0) is correlated to f.
Forρ(i)∈S, the equation M⃑i·u⃑=M⃑i·(fσ⃑+u⃑′′)=M⃑i·u⃑′′ has nothing to do with f. And forρ(i)∉S, fσ⃑ can be obtained only in the equation M⃑i∗·u⃑+γizρ(i), where ρ(i) is attribute which does not appear in the kth key. As long as each γi mod p2 is not congruent to 0, each equation brings a new unknown factor zρ(i) that appears nowhere else, and so the adversary A can get nothing about f. More precisely, for any value of u1, there is the same number of solutions to these equations. Hence, as long as each γi is nonzero modulo p2, the ciphertext and the kth key are properly distributed in the adversary’s view with a probability negligibly close to 1.
Thus, ifT∈Gp1p3, then B has simulated Gamek-1,2 with A. If T∈G and γi is nonzero modulo p2, then B has simulated Gamek,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 adversaryA has a nonnegligible advantage ε to distinguish Gamek-1,2 and Gamek,1, B can also distinguish element on Gp1p3 and G with a nonnegligible advantage ε.Lemma 13.
Suppose that there is a polynomial time adversaryA such that Gamek,1AdvA-Gamek,2AdvA=ε. Then, another polynomial time algorithm B, which breaks Assumption 3 with a nonnegligible advantage ε, can be constructed.Proof.
B receives {g,X1X2,X3,Y2Y3,T} to simulate either Gamek,1 or Gamek,2 with the adversary A depending on whether T∈G or T∈Gp1p3. 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∈ZN and then computes(19)K=gηTaR0Y2Y3h,L=TR0′,Kx=ThxRx∀x∈S.The only difference from Lemma 12 here is adding a term Y2Y3h which randomizes the Gp2 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-bu1 ≡ 0mod p2 is no longer established.
Phase 2. Phase 1 is repeated.
Hence, ifT∈Gp1p3, the kth key is a properly distributed semifunctional key of type 2 and therefore B simulates Gamek,2 for A. If T∈G, the kth key is a properly distributed semifunctional key of type 1 and therefore B simulates Gamek,1 for A. As a result, if A has a nonnegligible advantage ε to distinguish Gamek,2 and Gamek,1, B also has a nonnegligible advantage ε to distinguish element in Gp1p3 and G.Lemma 14.
Assume that there is a polynomial time adversaryA such that GameQ,2AdvA-GameFinalAdvA=ε. 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 Lemmas11–13. B receives {g,gαX2,X3,gsY2,Z2,T} to simulate GameQ,2 or GameFinal with A based on whether T=eg,gηs or T is a random element of GT.
Setup. B chooses random values a,hx∈ZN(∀x∈U) and sends the public key PK = N,g,g0,e(g,g)η=e(g,gηX2),ga,Hx=ghx∀x 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∈ZN and R0,R0′,Rx∈Gp3 and sets(20)K=gηgatZ2tR0,L=gtR0′,Kx=HxtRx∀x∈Swhich is similar as in the previous lemmas.
Challenge. A submits two messages M0 and M1 with equal length and a matrix (M∗,ρ) to B. B then takes s from the assumption term gsY2. It randomly chooses values u2,u3,…,un∈ZN to define a vector u′=(a,u2,u3,…,un) and randomly chooses an exponent ri′∈ZN. B chooses a random message Mθ from M0 and M1 and generates the challenge ciphertext C∗ as(21)C=MθT,C′=gsY2,Ci=gsY2M⃑i∗u⃑′gsY2-ri′hρi,Di=gsY2ri′,where θ∈{0,1} is the random coin. We note that there exists v=a-1su′ and u=cu′, so s is being shared in the subgroup Gp1 and ca is being shared in the subgroup Gp2. At the same time, set ri=sri′ and γi=-cri′.
Phase 2. Repeat Phase 1.
Guess.A outputs its guess result θ′ of θ.
IfT=e(g,g)ηs, then this is a properly distributed semifunctional ciphertext with message Mθ. Otherwise, this is a semifunctional ciphertext of a random message and will not give anything about θ to the attacker.
Hence, ifA can distinguish GameQ,2 and GameFinal with a nonnegligible advantage ε, B can distinguish the element e(g,g)ηs and a random element in GT with a nonnegligible advantage ε.Theorem 15.
If Assumptions1, 3, and 5 hold, our CP-ABPRE scheme is adaptively secure.Proof.
If Assumptions1, 3, and 5 hold, we have proved that the real CP-ABPRE security game Gamereal is indistinguishable from GameFinal by previous Lemmas 11–14. And because the challenger in GameFinal chooses a random message Mθ to encrypt, the adversary could not get any information on θ. In other words, the advantage of adversary in GameFinal can be negligible, so the advantage of the adversary in Gamereal 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′′=g0s 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 g0s, 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 Tables1–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 AU, AC, 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, GT for the operation in group GT, and P for the bilinear pairing operation. We use symbol L∗ to denote the bit length of element in ∗. At last, we use N′=∑i=1nni to denote the total number of possible values of attributes, where ni 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
ADBDHCTDH
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
ADBDHCTDH
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: Decisionalq-Parallel Bilinear Diffie-Hellman Exponent.Table 2
Performance comparisons (I).
Schemes
PK
MK
SK
Ciphertext
Liang et al.’s [6]
(
6
n
+
2
)
L
G
+
L
G
T
(
3
n
+
1
)
L
Z
q
(
2
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Luo et al.’s [7]
(
N
′
+
2
n
+
4
)
L
G
+
L
G
T
(
N
′
+
2
n
+
1
)
L
Z
q
(
4
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Seo and Kim’s [8]
(
3
n
+
2
)
L
G
+
L
G
T
+
3
n
L
Z
q
(
3
n
+
3
)
L
Z
q
(
n
+
1
)
L
G
+
L
Z
q
(
n
+
2
)
L
G
+
L
G
T
Li’s [9]
(
n
+
2
)
L
G
+
L
G
T
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
T
Liang et al.’s [11]
3
L
G
+
L
G
T
+
6
H
a
s
h
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
3
)
L
G
+
L
0
,
1
2
k
Liang et al.’s [14]
(
n
+
6
)
L
G
+
L
G
T
2
L
G
(
A
U
+
3
)
L
G
(
2
A
C
+
5
)
L
G
+
L
G
T
Backes et al.’s [15]
(
n
+
2
)
L
G
+
L
G
T
L
G
+
(
1
+
n
)
L
Z
q
(
n
+
1
)
L
G
3
L
G
+
L
G
T
+
n
L
Z
q
Our scheme
(
n
+
2
)
L
G
+
L
G
T
L
G
+
L
Z
q
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
TTable 3
Performance comparisons (II).
Schemes
Encryption
Decryption
Reencryption
Reencrypted decryption
Liang et al.’s [6]
(
n
+
2
)
G
+
2
G
T
(
n
+
2
)
P
+
2
G
T
(
n
+
1
)
P
+
G
T
(
n
+
3
)
P
+
4
G
T
Luo et al.’s [7]
(
n
+
2
)
G
+
2
G
T
2
n
P
+
3
G
T
(
2
n
+
1
)
P
+
(
n
+
1
)
G
T
(
2
n
+
1
)
P
+
5
G
T
Seo and Kim’s [8]
(
n
+
2
)
G
+
2
G
T
2
P
+
(
3
n
+
2
)
G
+
2
G
T
2
P
+
3
n
G
+
G
T
3
P
+
3
n
G
+
4
G
T
Li’s [9]
(
4
A
C
+
2
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
3
G
T
(
2
A
C
+
1
)
P
+
4
A
C
G
+
3
A
C
G
T
(
2
A
U
+
1
)
P
+
(
3
A
U
+
2
)
G
T
Liang et al.’s [11]
(
4
A
C
+
2
)
G
+
G
T
(
2
A
U
+
1
)
P
+
3
A
U
G
T
(
2
A
U
+
2
)
P
+
(
3
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
3
A
U
G
T
Liang et al.’s [14]
(
4
A
C
+
4
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
(
2
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
(
2
A
U
+
2
)
G
T
(
2
A
U
+
3
)
P
+
(
2
A
U
+
4
)
G
T
Backes et al.’s [15]
(
n
+
3
)
G
+
2
G
T
2
P
+
n
G
n
P
+
(
n
-
1
)
G
n
P
+
2
G
+
G
T
Our scheme
(
4
A
C
+
2
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
3
P
+
(
4
A
U
-
1
)
G
+
4
G
TFrom Tables1–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.


## 5.1. Correctness Analyses

The correctness of the scheme is based on the bilinear character of pairinge:G×G→GT. First, we show the correctness of the original ciphertext decryption as follows:(10)m=C∏i∈IeCi,LeDi,KρiwieC′,K=meg,gηs∏i∈IegaM⃑i·v⃑Hρi-ri,gtR0′egri,HρitRρiwiegs,gηgat=meg,gηseg,gat∑i∈IM⃑i·v⃑wieg,gηseg,gsat=m.Then, the correctness of the decryption algorithm for the reencrypted ciphertext is shown as follows:(11)m=CeC′′,gβCt=CeC′′,gβ∏i∈IeCi,rk2eDi,Kρi′wieC′,rk1=meg,gηseg0s,gβ∏i∈IegaM⃑i·v⃑Hρi-ri,gtR0′egri,HρitRρiwiegs,gηgatg0βR0=meg,gsηeg0s,gβeg,gat∑i∈IM⃑i·v⃑wieg,gsηeg,g0sβeg,gsat=m.Both the original ciphertext decryption and the reencrypted ciphertext decryption processes in Section4 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.Letg2 be a generator of Gp2.Semifunctional Ciphertexts. We firstly use theEnc algorithm to generate normal ciphertext and choose element c∈ZN randomly. Then, we choose random values zx∈ZN for each attribute, random values γi∈ZN for the ith row of matrix M, and a random column vector u⃑∈ZNn. The semifunction ciphertext is set as(12)C′=gsg2c,Ci=gaM⃑i·v⃑Hρi-rig2M⃑i·u⃑+γizρi,Di=grig2-γi∀i∈1,2,…,l.Semifunctional Key. We useKeyGen algorithm to generate normal secret key. And then we choose random exponents b,d∈ZN to set the semifunctional key as follows.A semifunctional key of type 1 is(13)K=gηgatR0g2d,L=gtR0′g2d,Kx=HxtRxg2bzx∀x∈S.A semifunctional key of type 2 (in type 1b=0) is(14)K=gηgatR0g2d,L=gtR0′,Kx=HxtRx∀x∈S.We should note that there will be an extra factore(g2,g2)cd-∑i∈IbM⃑i·u⃑wi=e(g2,g2)cd-bu1 (u1=(1,0,0,…,0)·u⃑) when a semifunctional key is used to decrypt a semifunctional ciphertext. But when the formula cd=bu1 holds, the semifunctional key of type 1 called a nominally semifunctional key can decrypt the semifunctional ciphertext successfully.Our proof of security relies on Assumptions1, 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,G
a
m
e
r
e
a
l. It denotes the real CP-ABPRE security game defined in Section 3, with normal keys and ciphertexts.G
a
m
e
0. It is similar to the above real game except that the challenge ciphertext is transformed into semifunctional one.G
a
m
e
k
,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.G
a
m
e
k
,2. The challenge ciphertext is semifunctional, the first k queried keys are semifunctional ones of type 2, and the remaining keys are normal ones.G
a
m
e
F
i
n
a
l. 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 adversaryA such that GamerealAdvA-Game0AdvA=ε. Then, we can construct another polynomial time algorithm B that can break Assumption 1 with a nonnegligible advantage ε.Proof.
We establish a polynomial time algorithmB which receives {g,X3,T} to simulate either Gamereal or Game0 with A based on setting whether T∈Gp1p2 or T∈Gp1.
Setup. B chooses random exponents a,η,hx∈ZN(∀x), sends the public key PK = N,g,g0,e(g,g)η,ga,Hx=ghx∀x to the adversary A, and at the same time securely keeps the master secret key MSK = η,X3.
Phase 1. B responds to whatever A’s key requests by using theKeyGen algorithm to make normal keys, since it has the MSK.
Challenge.
A provides two messages M0 and M1 with equal length and a challenge access matrix W∗=(M∗,ρ) to B. For each row i of matrix M∗, B first chooses random values v2′,v3′,…,vn′∈ZN and a random element ri′∈ZN to build the column vector v⃑′=1,v2′,v3′,…,vn′. Then, B chooses a random message Mθ from M0 and M1 and computes the challenge ciphertext C∗ as(15)C=Mθeg,gsη=Mθeg,Tη,C′=TCi=TaM⃑i∗·v⃑′T-ri′hρi,Di=Tri′,where θ∈{0,1} is the random coin.
Phase 2. Repeat Phase 1.
Guess. A outputs its guess result θ′ of θ.
IfT∈Gp1, let T=gs. This is a normal ciphertext with v⃑=sv⃑′ and ri=ri′s. B has simulated Gamereal for A. If T∈Gp1p2, let T=gsg2c. This is a semifunctional ciphertext with u=cav′,γi=-cri′, and zρ(i)=hρ(i). By the Chinese Remainder Theorem (CRT), the values of a,v2′,v3′,…,vn′,ri′,hρ(i) modulo p2 are uncorrelated to their values modulo p1. B has simulated Game0 for A.
Hence, ifA can distinguish Gamereal and Game0 with a nonnegligible advantage ε, B can distinguish element on Gp1 and Gp1p2 with a nonnegligible advantage ε.Lemma 12.
Assume that there is a polynomial time adversaryA such that Gamek-1,2AdvA-Gamek,1AdvA=ε. Then, another polynomial time algorithm B, which can break Assumption 3 with a nonnegligible advantage ε, can be constructed.Proof.
B receives g,X1X2,X3,Y2Y3,T to simulate either Gamek-1,2 or Gamek,1 with A based on setting whether T∈G or T∈Gp1p3.
Setup. B chooses random exponents a,η,hx∈ZN(∀x∈U) to generate the public key PK = N,g,g0,e(g,g)η,ga,Hx=ghx∀x and sends it to A. At the same time, B should securely keep the master secret key MSK = η,X3.
Phase 1. This phase can be divided into three parts.(1)
To form the firstk-1 semifunctional keys of type 2, B responds to each A’s key query by randomly choosing elements t∈ZN and R0′,Rx∈Gp3 and sets(16)K=gηgatY2Y3t,L=gtR0′,Kx=HxtRx∀x∈S.(2)
To generate the normal keys of queries greater thank, B needs to run theKeyGen algorithm since it has the master secret key (MSK).(3)
To answer thekth query, set gt equal to the Gp1 part of T. Then, B randomly chooses elements R0,R0′,Rx∈Gp3 and computes(17)K=gηTaR0,L=TR0′,Kx=ThxRx∀x∈S.If T∈Gp1p3, the above key is a normal one. And if T∈G, it is a semifunctional one of type 1. In this case, there exists zx=hx. If we let factor g2b denote the Gp2 part of T, there is d≡bamodp2. Note that zxmodp2 is uncorrelated to hxmodulop1, let g2ba be equal to the Gp2 part of K, let g2b be equal to the Gp2 part of L, and let g2bzx be equal to the Gp2 part of Kx.
Challenge. A provides two messages M0 and M1 with equal length and a challenge access matrix (M∗,ρ) for B. B sets gs=X1 and g2b=X2. Then, B chooses random values u2,u3,…,un∈ZN to define the vector u⃑′=a,u2,u3,…,un and randomly chooses exponent ri′∈ZN. B chooses a random message Mθ from M0 and M1 and computes the challenge ciphertext C∗ as(18)C=Mθeg,X1X2η,C′=X1X2,Ci=X1X2M⃑i∗·u′X1X2-ri′hρi,Di=X1X2ri′,where θ∈{0,1} is the random coin. We set v⃑=a-1su⃑′ and u⃑=cu⃑′, so s is shared in the subgroup Gp1 and c·a is shared in the subgroup Gp2. It also sets ri=s·ri′ and γi=-c·ri′. The values zρ(i)=hρ(i) match those in the kth key if it is semifunctional of type 1.
Actually, if thekth key can be used to decrypt the challenge ciphertext, then cd-bu1=cba-bca=0 modulo p2 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∉S, zx 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 (1,0,…,0). Thus, we denote a vector σ⃑ that is orthogonal to R and not orthogonal to vector (1,0,…,0). We set an equation that u⃑=fσ⃑+u⃑′′ for f∈ZN and u′′ is in the span of the basis elements not equal to σ⃑. We note that u′′ is properly distributed and reveals nothing about f. Since u1=u⃑·(1,0,0,…,0)=f(1,0,0,…,0)·σ⃑+(1,0,0,…,0)·u⃑′′ and (1,0,0,…,0)·σ⃑≠0, the item u⃑·(1,0,0,…,0) is correlated to f.
Forρ(i)∈S, the equation M⃑i·u⃑=M⃑i·(fσ⃑+u⃑′′)=M⃑i·u⃑′′ has nothing to do with f. And forρ(i)∉S, fσ⃑ can be obtained only in the equation M⃑i∗·u⃑+γizρ(i), where ρ(i) is attribute which does not appear in the kth key. As long as each γi mod p2 is not congruent to 0, each equation brings a new unknown factor zρ(i) that appears nowhere else, and so the adversary A can get nothing about f. More precisely, for any value of u1, there is the same number of solutions to these equations. Hence, as long as each γi is nonzero modulo p2, the ciphertext and the kth key are properly distributed in the adversary’s view with a probability negligibly close to 1.
Thus, ifT∈Gp1p3, then B has simulated Gamek-1,2 with A. If T∈G and γi is nonzero modulo p2, then B has simulated Gamek,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 adversaryA has a nonnegligible advantage ε to distinguish Gamek-1,2 and Gamek,1, B can also distinguish element on Gp1p3 and G with a nonnegligible advantage ε.Lemma 13.
Suppose that there is a polynomial time adversaryA such that Gamek,1AdvA-Gamek,2AdvA=ε. Then, another polynomial time algorithm B, which breaks Assumption 3 with a nonnegligible advantage ε, can be constructed.Proof.
B receives {g,X1X2,X3,Y2Y3,T} to simulate either Gamek,1 or Gamek,2 with the adversary A depending on whether T∈G or T∈Gp1p3. 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∈ZN and then computes(19)K=gηTaR0Y2Y3h,L=TR0′,Kx=ThxRx∀x∈S.The only difference from Lemma 12 here is adding a term Y2Y3h which randomizes the Gp2 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-bu1 ≡ 0mod p2 is no longer established.
Phase 2. Phase 1 is repeated.
Hence, ifT∈Gp1p3, the kth key is a properly distributed semifunctional key of type 2 and therefore B simulates Gamek,2 for A. If T∈G, the kth key is a properly distributed semifunctional key of type 1 and therefore B simulates Gamek,1 for A. As a result, if A has a nonnegligible advantage ε to distinguish Gamek,2 and Gamek,1, B also has a nonnegligible advantage ε to distinguish element in Gp1p3 and G.Lemma 14.
Assume that there is a polynomial time adversaryA such that GameQ,2AdvA-GameFinalAdvA=ε. 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 Lemmas11–13. B receives {g,gαX2,X3,gsY2,Z2,T} to simulate GameQ,2 or GameFinal with A based on whether T=eg,gηs or T is a random element of GT.
Setup. B chooses random values a,hx∈ZN(∀x∈U) and sends the public key PK = N,g,g0,e(g,g)η=e(g,gηX2),ga,Hx=ghx∀x 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∈ZN and R0,R0′,Rx∈Gp3 and sets(20)K=gηgatZ2tR0,L=gtR0′,Kx=HxtRx∀x∈Swhich is similar as in the previous lemmas.
Challenge. A submits two messages M0 and M1 with equal length and a matrix (M∗,ρ) to B. B then takes s from the assumption term gsY2. It randomly chooses values u2,u3,…,un∈ZN to define a vector u′=(a,u2,u3,…,un) and randomly chooses an exponent ri′∈ZN. B chooses a random message Mθ from M0 and M1 and generates the challenge ciphertext C∗ as(21)C=MθT,C′=gsY2,Ci=gsY2M⃑i∗u⃑′gsY2-ri′hρi,Di=gsY2ri′,where θ∈{0,1} is the random coin. We note that there exists v=a-1su′ and u=cu′, so s is being shared in the subgroup Gp1 and ca is being shared in the subgroup Gp2. At the same time, set ri=sri′ and γi=-cri′.
Phase 2. Repeat Phase 1.
Guess.A outputs its guess result θ′ of θ.
IfT=e(g,g)ηs, then this is a properly distributed semifunctional ciphertext with message Mθ. Otherwise, this is a semifunctional ciphertext of a random message and will not give anything about θ to the attacker.
Hence, ifA can distinguish GameQ,2 and GameFinal with a nonnegligible advantage ε, B can distinguish the element e(g,g)ηs and a random element in GT with a nonnegligible advantage ε.Theorem 15.
If Assumptions1, 3, and 5 hold, our CP-ABPRE scheme is adaptively secure.Proof.
If Assumptions1, 3, and 5 hold, we have proved that the real CP-ABPRE security game Gamereal is indistinguishable from GameFinal by previous Lemmas 11–14. And because the challenger in GameFinal chooses a random message Mθ to encrypt, the adversary could not get any information on θ. In other words, the advantage of adversary in GameFinal can be negligible, so the advantage of the adversary in Gamereal 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′′=g0s 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 g0s, 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 Tables1–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 AU, AC, 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, GT for the operation in group GT, and P for the bilinear pairing operation. We use symbol L∗ to denote the bit length of element in ∗. At last, we use N′=∑i=1nni to denote the total number of possible values of attributes, where ni 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
ADBDHCTDH
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
ADBDHCTDH
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: Decisionalq-Parallel Bilinear Diffie-Hellman Exponent.Table 2
Performance comparisons (I).
Schemes
PK
MK
SK
Ciphertext
Liang et al.’s [6]
(
6
n
+
2
)
L
G
+
L
G
T
(
3
n
+
1
)
L
Z
q
(
2
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Luo et al.’s [7]
(
N
′
+
2
n
+
4
)
L
G
+
L
G
T
(
N
′
+
2
n
+
1
)
L
Z
q
(
4
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Seo and Kim’s [8]
(
3
n
+
2
)
L
G
+
L
G
T
+
3
n
L
Z
q
(
3
n
+
3
)
L
Z
q
(
n
+
1
)
L
G
+
L
Z
q
(
n
+
2
)
L
G
+
L
G
T
Li’s [9]
(
n
+
2
)
L
G
+
L
G
T
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
T
Liang et al.’s [11]
3
L
G
+
L
G
T
+
6
H
a
s
h
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
3
)
L
G
+
L
0
,
1
2
k
Liang et al.’s [14]
(
n
+
6
)
L
G
+
L
G
T
2
L
G
(
A
U
+
3
)
L
G
(
2
A
C
+
5
)
L
G
+
L
G
T
Backes et al.’s [15]
(
n
+
2
)
L
G
+
L
G
T
L
G
+
(
1
+
n
)
L
Z
q
(
n
+
1
)
L
G
3
L
G
+
L
G
T
+
n
L
Z
q
Our scheme
(
n
+
2
)
L
G
+
L
G
T
L
G
+
L
Z
q
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
TTable 3
Performance comparisons (II).
Schemes
Encryption
Decryption
Reencryption
Reencrypted decryption
Liang et al.’s [6]
(
n
+
2
)
G
+
2
G
T
(
n
+
2
)
P
+
2
G
T
(
n
+
1
)
P
+
G
T
(
n
+
3
)
P
+
4
G
T
Luo et al.’s [7]
(
n
+
2
)
G
+
2
G
T
2
n
P
+
3
G
T
(
2
n
+
1
)
P
+
(
n
+
1
)
G
T
(
2
n
+
1
)
P
+
5
G
T
Seo and Kim’s [8]
(
n
+
2
)
G
+
2
G
T
2
P
+
(
3
n
+
2
)
G
+
2
G
T
2
P
+
3
n
G
+
G
T
3
P
+
3
n
G
+
4
G
T
Li’s [9]
(
4
A
C
+
2
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
3
G
T
(
2
A
C
+
1
)
P
+
4
A
C
G
+
3
A
C
G
T
(
2
A
U
+
1
)
P
+
(
3
A
U
+
2
)
G
T
Liang et al.’s [11]
(
4
A
C
+
2
)
G
+
G
T
(
2
A
U
+
1
)
P
+
3
A
U
G
T
(
2
A
U
+
2
)
P
+
(
3
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
3
A
U
G
T
Liang et al.’s [14]
(
4
A
C
+
4
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
(
2
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
(
2
A
U
+
2
)
G
T
(
2
A
U
+
3
)
P
+
(
2
A
U
+
4
)
G
T
Backes et al.’s [15]
(
n
+
3
)
G
+
2
G
T
2
P
+
n
G
n
P
+
(
n
-
1
)
G
n
P
+
2
G
+
G
T
Our scheme
(
4
A
C
+
2
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
3
P
+
(
4
A
U
-
1
)
G
+
4
G
TFrom Tables1–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.


## 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′′=g0s 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 g0s, 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 Tables1–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 AU, AC, 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, GT for the operation in group GT, and P for the bilinear pairing operation. We use symbol L∗ to denote the bit length of element in ∗. At last, we use N′=∑i=1nni to denote the total number of possible values of attributes, where ni 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
ADBDHCTDH
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
ADBDHCTDH
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: Decisionalq-Parallel Bilinear Diffie-Hellman Exponent.Table 2
Performance comparisons (I).
Schemes
PK
MK
SK
Ciphertext
Liang et al.’s [6]
(
6
n
+
2
)
L
G
+
L
G
T
(
3
n
+
1
)
L
Z
q
(
2
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Luo et al.’s [7]
(
N
′
+
2
n
+
4
)
L
G
+
L
G
T
(
N
′
+
2
n
+
1
)
L
Z
q
(
4
n
+
1
)
L
G
(
n
+
2
)
L
G
+
L
G
T
Seo and Kim’s [8]
(
3
n
+
2
)
L
G
+
L
G
T
+
3
n
L
Z
q
(
3
n
+
3
)
L
Z
q
(
n
+
1
)
L
G
+
L
Z
q
(
n
+
2
)
L
G
+
L
G
T
Li’s [9]
(
n
+
2
)
L
G
+
L
G
T
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
T
Liang et al.’s [11]
3
L
G
+
L
G
T
+
6
H
a
s
h
L
G
(
A
U
+
2
)
L
G
(
2
A
C
+
3
)
L
G
+
L
0
,
1
2
k
Liang et al.’s [14]
(
n
+
6
)
L
G
+
L
G
T
2
L
G
(
A
U
+
3
)
L
G
(
2
A
C
+
5
)
L
G
+
L
G
T
Backes et al.’s [15]
(
n
+
2
)
L
G
+
L
G
T
L
G
+
(
1
+
n
)
L
Z
q
(
n
+
1
)
L
G
3
L
G
+
L
G
T
+
n
L
Z
q
Our scheme
(
n
+
2
)
L
G
+
L
G
T
L
G
+
L
Z
q
(
A
U
+
2
)
L
G
(
2
A
C
+
2
)
L
G
+
L
G
TTable 3
Performance comparisons (II).
Schemes
Encryption
Decryption
Reencryption
Reencrypted decryption
Liang et al.’s [6]
(
n
+
2
)
G
+
2
G
T
(
n
+
2
)
P
+
2
G
T
(
n
+
1
)
P
+
G
T
(
n
+
3
)
P
+
4
G
T
Luo et al.’s [7]
(
n
+
2
)
G
+
2
G
T
2
n
P
+
3
G
T
(
2
n
+
1
)
P
+
(
n
+
1
)
G
T
(
2
n
+
1
)
P
+
5
G
T
Seo and Kim’s [8]
(
n
+
2
)
G
+
2
G
T
2
P
+
(
3
n
+
2
)
G
+
2
G
T
2
P
+
3
n
G
+
G
T
3
P
+
3
n
G
+
4
G
T
Li’s [9]
(
4
A
C
+
2
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
3
G
T
(
2
A
C
+
1
)
P
+
4
A
C
G
+
3
A
C
G
T
(
2
A
U
+
1
)
P
+
(
3
A
U
+
2
)
G
T
Liang et al.’s [11]
(
4
A
C
+
2
)
G
+
G
T
(
2
A
U
+
1
)
P
+
3
A
U
G
T
(
2
A
U
+
2
)
P
+
(
3
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
3
A
U
G
T
Liang et al.’s [14]
(
4
A
C
+
4
)
G
+
2
G
T
(
2
A
U
+
1
)
P
+
(
2
A
U
+
1
)
G
T
(
2
A
U
+
2
)
P
+
(
2
A
U
+
2
)
G
T
(
2
A
U
+
3
)
P
+
(
2
A
U
+
4
)
G
T
Backes et al.’s [15]
(
n
+
3
)
G
+
2
G
T
2
P
+
n
G
n
P
+
(
n
-
1
)
G
n
P
+
2
G
+
G
T
Our scheme
(
4
A
C
+
2
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
2
P
+
(
4
A
U
-
1
)
G
+
2
G
T
3
P
+
(
4
A
U
-
1
)
G
+
4
G
TFrom Tables1–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.



---

*Source: 5235714-2016-05-25.xml*