# CP-ABE with Hidden Policy from Waters Efficient Construction

Authors: Zhiwei Wang; Mingjun He
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

ABE provides a good way for access controlling in cloud computing. However, in many application scenarios, access policies for encryption also should be protected since they may directly contain sensitive information. For example, in smart grid, the access policies may contain the private information about underlying data, data owner or the data recipients, and disclosing some sensitive access policies could result in negative publicity, or loss of market revenue. In this paper, we present a CP-ABE scheme with hidden policy from Waters efficient construction. In our scheme, the access policy is hidden by using the composite order bilinear groups and can be expressed with LSSS. Our scheme is proved CPA secure under four statics assumptions.


---

## Body

## 1. Introduction

With the development of cloud computing, users are apt to store their data on the cloud server. It is inefficient to distribute these encrypted data to a set of users with specific attributes in traditional cryptosystems, for example, PKI, ID-based cryptosystem [1]. For this reason, Sahai and Waters [2] firstly proposed the concept of attribute-based encryption. In attribute-based encryption (ABE), ciphertexts and keys are associated with sets of attributes and access structure over attributes. There are two kinds of ABE systems: the first one is ciphertext-policy ABE (CP-ABE); the second one is key-policy ABE (KP-ABE).How to achieve a more expressive access policy over many attributes is an important problem in ABE. Sahai and Waters [2] scheme was limited to specify as threshold access policies with one threshold gate. After that, Lewko et al. [3] used monotone span programs (MSPs) as access policy to devise a CP-ABE and a KP-ABE, which are proved secure in composite bilinear groups. However, their schemes are very inefficient, since the length of ciphertexts and keys, and the number of pairings in decryption are all polynomial in the size of MSPs. In order to improve the efficiency, some ABE systems make use of linear secret sharing scheme (LSSS) or Boolean formulas as access policy. Waters [4] employed LSSS matrix as access policy to realize CP-ABE. In [5], Goyal et al. provided a mapping from a universal access tree to formulas consisting of threshold gates. They used this technique to construct a bounded CP-ABE scheme. There is a close relation between LSSS and MSP access structure, and Beimel et al. [6] proved it. Pandit and Barua [7] used minimal sets to realize the smallest MSP for describing general access structure in ABE systems.However, in some applications, the access policies may also be sensitive. For example, if the ABE scheme is deployed in smart grid [8], the access policies may contain the private information about underlying data, data owner, or the data recipients. Thus, some grid operators such as electric utilities competing with each other as business entities might not comfortably disclose access policies to other entities. Another example is e-health system: the patients encrypt their health records with access policies and store them in the cloud storage provider. However, the access policies may leak lots of sensitive information. In Figure 1, the access policy reveals that the patient suffers from the heart disease.Figure 1
E-health.Lai et al. [9] proposed a CP-ABE scheme with partially hidden access policy. The attribute values are not disclosed in the access policy. However, it is not a CP-ABE with fully hidden access policy. In 2013, Sreenivasa Rao and Dutta [10] proposed a recipient anonymous CP-ABE, which only uses the AND-gate access policy. Given the widespread applications of ABE schemes, constructing an efficient ABE scheme with hidden policy while supporting more expressive access policy is a crucial problem. In this paper, we propose a CP-ABE with hidden policy (CP-ABE-HP) from Waters efficient construction, which makes use of LSSS as the access policy. A comparison in properties and security levels of current CP-ABE schemes is given in Table 1.Table 1
Properties and security levels comparison.
Schemes
Lewko et al. [3]
Waters [4]
Lai et al. [9]
Sreenivasa Rao and Dutta  [10]
Our scheme
Hidden policy
No
No
Partially
Yes
Yes
Access Policy
MSPs
LSSS
LSSS
AND gate
LSSS
Security Model
Selective
Full security
Selective
Full security
Full securityOrganization. In Section 2, we review four statics assumptions in composite order groups and the LSSS access structure. In Section 3, we provide the definition and security model of CP-ABE-HP. In Section 4, we devise a concrete CP-ABE-HP scheme. In Section 5, we prove our scheme by using the technique of dual system encryption. In Section 6, we conclude our paper.


## 2. Background

In this section, we firstly give the definitions four hard assumptions. Secondly, we provide the formal definitions for LSSS.


### 2.1. Hardness Assumptions

Bilinear groups of composite order are groups introduced by [11], where the group order is product of two or more distinct primes. In our construction, we use the group order of N=p1p2p3, where p1,p2,p3 are three distinct prime numbers. We denote this group as G, and admit an efficient bilinear map e^:G×G→GT, where GT’s order is the same as G’s. Any element of G can be denoted as g1a1g2a2g3a3, where gi is the generator of subgroup Gpi. Each Gpi has the order pi, and ai∈Zpi. We denote Gpipj as the subgroup of order pipj in G. For all T∈Gpipj, T can be defined as the product of an element in Gpi and an element in Gpj. For all v∈Gpi and w∈Gpj, e^(v,w)=1 if i≠j. The following are three hardness assumptions, which have been analyzed in [10].Definition 1 (assumption1).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (1)Pr⁡AΘ,g1,g3,B0=1-Pr⁡AΘ,g1,g3,B1=1≤ϵ, where the probabilities are over the random choice of g1∈Gp1, g3∈Gp3, and B0∈G, B1∈Gp1p3.Definition 2 (assumption2).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (2)Pr⁡AΘ,g1,X1X2,X3,Y1Y2,B0=1-Pr⁡AΘ,g1,X1X2,X3,Y1Y2,B1=1≤ϵ, where the probabilities are over the random choice of g1,X1,Y1∈Gp1, X2,Y2∈Gp2, X3∈Gp3, B0∈Gp1p2, and B1∈Gp1.Definition 3 (assumption3).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (3)Pr⁡AΘ,g1,g1αX2,X3,g1sY2Y3,Z2,B0=1-Pr⁡AΘ,g1,g1αX2,X3,g1sY2Y3,Z2,B1=1≤ϵ, where the probabilities are over the random choice of s,α∈ZN, g1∈Gp1, X2,Y2,Z2∈Gp2, X3,Y3∈Gp3, B0=e(g1α,g1s), and B1∈RGT.Definition 4 (assumption4).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (4)Pr⁡AΘ,g1X3,g1sZ3,g1X2,Z2,g3,B0=1-Pr⁡AΘ,g1X3,g1sZ3,g1X2,Z2,g3,B1=1≤ϵ, where the probabilities are over the random choice of s∈ZN,g1∈Gp1,X2,Y2,Z2∈Gp2,X3,Y3,Z3∈Gp3,B0=g1sY2Y3, and B1∈RGT.


### 2.2. Access Policy and Linear Secret Sharing Scheme

We adapt our definitions which are given by [12–14].Definition 5 (access policy).
Let{S1,…,Sn} be a set of attributes. An authorized collection A⊂2{S1,…,Sn} is monotone, on the condition that ∀B,C, B∈A and B⊆C; then C∈A.Definition 6 (linear secret sharing scheme (LSSS)).
If the following two conditions are satisfied, then a secret sharing schemeΠ is called linear. (1) The shares for each attribute form a vector from ZN. (2) There exists a sharing-generating l×n matrix A for Π. For all i=1,…,l, the map ρ maps the ith row of A to an attribute labeling ρ(i). Then, we select a random column vector v=(μ,r2,…,rn), where μ∈ZN is the secret to be shared and Av is the vector of l shares of the secret μ according to Π.


## 2.1. Hardness Assumptions

Bilinear groups of composite order are groups introduced by [11], where the group order is product of two or more distinct primes. In our construction, we use the group order of N=p1p2p3, where p1,p2,p3 are three distinct prime numbers. We denote this group as G, and admit an efficient bilinear map e^:G×G→GT, where GT’s order is the same as G’s. Any element of G can be denoted as g1a1g2a2g3a3, where gi is the generator of subgroup Gpi. Each Gpi has the order pi, and ai∈Zpi. We denote Gpipj as the subgroup of order pipj in G. For all T∈Gpipj, T can be defined as the product of an element in Gpi and an element in Gpj. For all v∈Gpi and w∈Gpj, e^(v,w)=1 if i≠j. The following are three hardness assumptions, which have been analyzed in [10].Definition 1 (assumption1).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (1)Pr⁡AΘ,g1,g3,B0=1-Pr⁡AΘ,g1,g3,B1=1≤ϵ, where the probabilities are over the random choice of g1∈Gp1, g3∈Gp3, and B0∈G, B1∈Gp1p3.Definition 2 (assumption2).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (2)Pr⁡AΘ,g1,X1X2,X3,Y1Y2,B0=1-Pr⁡AΘ,g1,X1X2,X3,Y1Y2,B1=1≤ϵ, where the probabilities are over the random choice of g1,X1,Y1∈Gp1, X2,Y2∈Gp2, X3∈Gp3, B0∈Gp1p2, and B1∈Gp1.Definition 3 (assumption3).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (3)Pr⁡AΘ,g1,g1αX2,X3,g1sY2Y3,Z2,B0=1-Pr⁡AΘ,g1,g1αX2,X3,g1sY2Y3,Z2,B1=1≤ϵ, where the probabilities are over the random choice of s,α∈ZN, g1∈Gp1, X2,Y2,Z2∈Gp2, X3,Y3∈Gp3, B0=e(g1α,g1s), and B1∈RGT.Definition 4 (assumption4).
GivenΘ=(N=p1p2p3,G,GT,e), if for all PPT algorithm A, there is a negligible probability ϵ such that (4)Pr⁡AΘ,g1X3,g1sZ3,g1X2,Z2,g3,B0=1-Pr⁡AΘ,g1X3,g1sZ3,g1X2,Z2,g3,B1=1≤ϵ, where the probabilities are over the random choice of s∈ZN,g1∈Gp1,X2,Y2,Z2∈Gp2,X3,Y3,Z3∈Gp3,B0=g1sY2Y3, and B1∈RGT.


## 2.2. Access Policy and Linear Secret Sharing Scheme

We adapt our definitions which are given by [12–14].Definition 5 (access policy).
Let{S1,…,Sn} be a set of attributes. An authorized collection A⊂2{S1,…,Sn} is monotone, on the condition that ∀B,C, B∈A and B⊆C; then C∈A.Definition 6 (linear secret sharing scheme (LSSS)).
If the following two conditions are satisfied, then a secret sharing schemeΠ is called linear. (1) The shares for each attribute form a vector from ZN. (2) There exists a sharing-generating l×n matrix A for Π. For all i=1,…,l, the map ρ maps the ith row of A to an attribute labeling ρ(i). Then, we select a random column vector v=(μ,r2,…,rn), where μ∈ZN is the secret to be shared and Av is the vector of l shares of the secret μ according to Π.


## 3. CP-ABE with Hidden Policy

### 3.1. Definition

A normal CP-ABE scheme is composed of four probabilistic polynomial time algorithms:(1)
Setup(1λ,Σ): the setup algorithm inputs a security parameter λ and an attribute set Σ and outputs system public key MPK and master key MSK.(2)
KeyGen(MSK,S): this algorithm inputs an attribute set S and MSK and outputs a private key SKS.(3)
Encrypt(M,A): the encryption algorithm inputs an access structure A and a message M and outputs a ciphertext CT.(4)
Decrypt(CT,SK): this algorithm inputs a ciphertext CT for an access structure A and a private key SK for a set S and outputs M if and only if the attribute set S satisfies the access structure A.LetΣ and M be the monotone attribute space and the message space, respectively. ∀M∈M, ∀A∈2Σ, ∀S∈A, and M←Decrypt(SK,Encrypt(MPK,M,A)), where (MPK,MSK)←Setup(1λ,Σ) and SK←KeyGen(MSK,S).


### 3.2. Security Model of CP-ABE-HP

In this section, we provide the security definition of CP-ABE for semantic security with hidden policy (CP-ABE-HP).Setup. The challenger C generates MPK and MSK and sends MPK to A.Query 1. The adversary A is allowed to make key extraction queries for the sets of attributes S1,S2,…,Sq1. C runs the KeyGen algorithm and responds to the secret keys SKS1,SKS2,…,SKSq1.Callenge. A outputs two messages M0,M1∈M and two access policies A0∗ and A1∗ such that S1,S2,…,Sq1 does not satisfy A0∗ and A1∗. C randomly chooses a bit b∈{0,1} and returns the ciphertext CT∗←Encrypt(Mb,Ab∗).Query 2. A can make the key extraction queries like Query 1 with the restriction that none of these satisfies A0∗ and A1∗.Response. Finally, A outputs a guess b′ of b. A’s advantage of this game can be defined as ADVA(1λ,Σ)=2Pr⁡b=b′-1.Definition 7 (CP-ABE-HP).
A CP-ABE is CPA secure with respect to hidden policy on the condition thatADVA is negligible in the above game.


## 3.1. Definition

A normal CP-ABE scheme is composed of four probabilistic polynomial time algorithms:(1)
Setup(1λ,Σ): the setup algorithm inputs a security parameter λ and an attribute set Σ and outputs system public key MPK and master key MSK.(2)
KeyGen(MSK,S): this algorithm inputs an attribute set S and MSK and outputs a private key SKS.(3)
Encrypt(M,A): the encryption algorithm inputs an access structure A and a message M and outputs a ciphertext CT.(4)
Decrypt(CT,SK): this algorithm inputs a ciphertext CT for an access structure A and a private key SK for a set S and outputs M if and only if the attribute set S satisfies the access structure A.LetΣ and M be the monotone attribute space and the message space, respectively. ∀M∈M, ∀A∈2Σ, ∀S∈A, and M←Decrypt(SK,Encrypt(MPK,M,A)), where (MPK,MSK)←Setup(1λ,Σ) and SK←KeyGen(MSK,S).


## 3.2. Security Model of CP-ABE-HP

In this section, we provide the security definition of CP-ABE for semantic security with hidden policy (CP-ABE-HP).Setup. The challenger C generates MPK and MSK and sends MPK to A.Query 1. The adversary A is allowed to make key extraction queries for the sets of attributes S1,S2,…,Sq1. C runs the KeyGen algorithm and responds to the secret keys SKS1,SKS2,…,SKSq1.Callenge. A outputs two messages M0,M1∈M and two access policies A0∗ and A1∗ such that S1,S2,…,Sq1 does not satisfy A0∗ and A1∗. C randomly chooses a bit b∈{0,1} and returns the ciphertext CT∗←Encrypt(Mb,Ab∗).Query 2. A can make the key extraction queries like Query 1 with the restriction that none of these satisfies A0∗ and A1∗.Response. Finally, A outputs a guess b′ of b. A’s advantage of this game can be defined as ADVA(1λ,Σ)=2Pr⁡b=b′-1.Definition 7 (CP-ABE-HP).
A CP-ABE is CPA secure with respect to hidden policy on the condition thatADVA is negligible in the above game.


## 4. Construction of CP-ABE with Hidden Policy

### 4.1. Waters CP-ABE Construction

Waters most efficient CP-ABE construction [4] takes as input a LSSS access matrix M and hides a random number s∈Zp according to M.Setup(
U
). This algorithm inputs the number of attributes U. Then, it chooses a prime order p group G, a generator g, and random group elements u1,…,uU that are corresponding to the U attributes in the system. And then, it selects random exponents α,a∈Zp. The master public key MPK=(g,e(g,g)α,ga,u1,…,uU) and the master secret key MSK=gα.Encrypt(
M
P
K
,
(
M
,
ρ
)
,
M
). Here, M is a l×n matrix and (M,ρ) is a LSSS structure, where the map ρ maps rows of M to attributes. This algorithm randomly chooses v=(s,y2,…,yn)∈Zpn. For i=1 to l, it calculates λi=v·Mi, where Mi is the ith row of M. Then, the algorithm randomly chooses r1,…,rl∈Zp. The ciphertext CT is as follows: (5)C1=Meg,gαs,C2=gs,T1=gaλ1uρ1-r1,W1=gr1,…,Tl=gaλluρl-rl,Wl=gr1 along with an access structure of (M,ρ).KeyGen(
M
S
K
,
S
). This algorithm chooses a random t∈Zp and computes the secret key SK on a set S of attributes as (6)K1=gαgat,K2=gt,Kx=uxt∀S.Decrypt(
C
T
,
S
K
). This algorithm inputs a ciphertext CT associated with (M,ρ) and a secret key SK on a set S of attributes. We suppose that S satisfies (M,ρ) and let I={i:ρ(i)∈S}. Then, {ωi∈Zp}i∈I is a set of constants such that ∑i∈I‍ωiλi=s, if {λi} are valid shares. This algorithm can compute (7)eC2,K1Πi∈IeTi,K2eWi,Kρiωi=eg,gαs.Then, the algorithm can recover the message M from C1 by (7).We now argue that the above scheme is not hidden policy. Some componentsC2,Ti,Wi in ciphertext expose some information of access policy. Precisely, given an access policy (M,ρ), the adversary chooses I⊂{1,…,l} and {ωi∈Zp}i∈I. (Note that there could be different ways for choosing the value of ωi to satisfy ∑i∈I‍ωiλi=s, if {λi} are valid shares.) Then, the adversary can run a test (8)Πi∈IeTi,geWi,uρiωi=?eC2,ga.The adversary can use (8) to determine whether CT is encrypted by the access policy (M,ρ). Thus, the above CP-ABE scheme is said to provide no hidden policy.


### 4.2. Our Construction

We realize Waters CP-ABE scheme in the composite order groupsGp1p2p3. In our scheme, the ciphertext consists of 3 groups elements and the secret key consists of 2 groups elements. Therefore, the access policy along with the ciphertext is hidden by the elements in group Gp2.Setup(
1
λ
,
U
). The setup algorithm inputs a security parameter λ and a number U of attributes in the system. This algorithm runs the bilinear group generator to produce Θ=(N=p1p2p3,G,GT,e), where p1,p2,p3 are three distinct λ-bit primes. Then, it selects random generators g1,u1,…,uU∈Gp1 and g3∈Gp3. It picks a,α,y1,…,yU∈ZN and sets A1=u1g3y1,…,AU=uUg3yU. Consider(9)MPK:Θ,g1,g3,g1a,eg1,g1α,A1,…,AU, and MSK=g1α.Encrypt(
M
P
K
,
(
M
,
ρ
)
,
M
). Here, M is a l×n matrix and (M,ρ) is a LSSS structure. This algorithm chooses a vector v=(s,y2,…,yn)∈Zpn. For i=1 to l, it calculates λi=v·Mi, where Mi denotes the ith row of matrix M. Then, the algorithm randomly chooses r1,…,rl∈ZN and R0∈Gp3,{Ri,Ri′∈Gp3}i∈{1,…,l}. The ciphertext CT is as follows: (10)C1=Meg1,g1αs,C2=g1sR0,T1=g1aλ1Aρ1-r1Ri′,W1=g1r1R1,…,Tl=g1aλlAρl-rlRl′,Wl=g1rlRl along with an access structure of (M,ρ).KeyGen(
M
S
K
,
S
). This algorithm chooses a random t∈Zp and computes the secret key SK on a set S of attributes as (11)K1=g1αg1at,K2=g1t,Kx=uxt∀S.Decrypt(
C
T
,
S
K
). The receiver can decrypt the ciphertext by his secret key SK. Let I={i:ρ(i)∈S} and let {ωi∈ZN}i∈I be a set of constants such that ∑i∈I‍ωiλi=s, if {λi} are valid shares. The receiver can compute (12)eC2,K1Πi∈IeTi,K2eWi,Kρiωi=eg1,g1αs.Then, the algorithm can recover the message M from C1 by (12).Hidden Policy. Our scheme can provide hidden policy by using the subgroup Gp3. Suppose the adversary is given an arbitrary access policy (M′,ρ′) and a ciphertext CT=(C1,C2,(T1,W1),…,(Tl,Wl)). Let CT be encrypted under an access policy (M,ρ). The adversary chooses I′⊂{1,…,l} and {ωi′∈ZN}i∈I′ according to M′. (Note that {ωi′}i∈I is a set of constants such that if {λi′} are valid shares, then ∑i∈I′‍ωi′λi′=s.) Then, the adversary can perform the test as follows: (13)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=eg1sR0,g1aΠi∈I′eg1aλiuρ′ig3yρ′i-riRi′,g1eg1riRi,uρ′ig3yρ′iωi′=eg1,g1asΠi∈I′eg1aλiuρ′i-ri,g1eg1riRi,uρ′ig3yρ′iωi′=eg1,g1asΠi∈I′eg1aλiuρ′i-ri,g1eg1ri,uρ′ieRi,g3yρ′iωi′=eg1,g1asΠi∈I′eg1aλi,g1eRi,g3yρ′iωi′=eg1,g1aseg1,g1a∑i∈I′λiωi′Πi∈I′eRi,g3yρ′iωi′.Note that some pairings in the above equation equal identity inGT due to the orthogonal property in composite order groups. There are two possible cases:(1)
IfM′,ρ′=(M,ρ), then ∑i∈I′‍λiωi′=s. Thus, (14)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=1Πi∈I′eRi,g3yρ′iωi′.(2)
IfM′,ρ′≠(M,ρ), then ∑i∈I′‍λiωi′≠s. Thus, (15)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=eg1,g1aseg1,g1a∑i∈I′λiωi′Πi∈I′eRi,g3yρ′iωi′.In the above two cases, the test gives a random element inGT. So the adversary cannot determine whether the ciphertext CT is associated with the access policy M′,ρ′ or not. Thus, our scheme provides the property of hidden policy.Performance Comparison. Let Pr denote the computation cost of pairing and let Ex denote the exponent cost. For [4] and our scheme, we assume that the LSSS matrix is l×n. In Table 2, we provide the performance comparison with Waters scheme [4], Sreenivasa Rao and Dutta’s scheme [10], and our scheme. In decryption, we only evaluate the computational costs of pairing, since the pairing operation is very time-consuming compared to the other operations.Table 2
Performance comparison.
Schemes
Encrypt
Decrypt
Hidden policy
Expressiveness of access policy
Waters [4]
(
2
l
+
1
)
E
x
(
2
|
I
|
+
1
)
P
r
No
LSSS
Sreenivasa Rao and Dutta  [10]
1
2
Yes
AND
Our scheme
(
2
l
+
1
)
E
x
(
2
|
I
|
+
1
)
P
r
Yes
LSSSFrom Table2, we can see that the number of operations in our scheme is almost the same as Waters scheme. However, the operations in our scheme are operated in the composite order groups, while the operations in Waters scheme are operated in the prime order groups.


## 4.1. Waters CP-ABE Construction

Waters most efficient CP-ABE construction [4] takes as input a LSSS access matrix M and hides a random number s∈Zp according to M.Setup(
U
). This algorithm inputs the number of attributes U. Then, it chooses a prime order p group G, a generator g, and random group elements u1,…,uU that are corresponding to the U attributes in the system. And then, it selects random exponents α,a∈Zp. The master public key MPK=(g,e(g,g)α,ga,u1,…,uU) and the master secret key MSK=gα.Encrypt(
M
P
K
,
(
M
,
ρ
)
,
M
). Here, M is a l×n matrix and (M,ρ) is a LSSS structure, where the map ρ maps rows of M to attributes. This algorithm randomly chooses v=(s,y2,…,yn)∈Zpn. For i=1 to l, it calculates λi=v·Mi, where Mi is the ith row of M. Then, the algorithm randomly chooses r1,…,rl∈Zp. The ciphertext CT is as follows: (5)C1=Meg,gαs,C2=gs,T1=gaλ1uρ1-r1,W1=gr1,…,Tl=gaλluρl-rl,Wl=gr1 along with an access structure of (M,ρ).KeyGen(
M
S
K
,
S
). This algorithm chooses a random t∈Zp and computes the secret key SK on a set S of attributes as (6)K1=gαgat,K2=gt,Kx=uxt∀S.Decrypt(
C
T
,
S
K
). This algorithm inputs a ciphertext CT associated with (M,ρ) and a secret key SK on a set S of attributes. We suppose that S satisfies (M,ρ) and let I={i:ρ(i)∈S}. Then, {ωi∈Zp}i∈I is a set of constants such that ∑i∈I‍ωiλi=s, if {λi} are valid shares. This algorithm can compute (7)eC2,K1Πi∈IeTi,K2eWi,Kρiωi=eg,gαs.Then, the algorithm can recover the message M from C1 by (7).We now argue that the above scheme is not hidden policy. Some componentsC2,Ti,Wi in ciphertext expose some information of access policy. Precisely, given an access policy (M,ρ), the adversary chooses I⊂{1,…,l} and {ωi∈Zp}i∈I. (Note that there could be different ways for choosing the value of ωi to satisfy ∑i∈I‍ωiλi=s, if {λi} are valid shares.) Then, the adversary can run a test (8)Πi∈IeTi,geWi,uρiωi=?eC2,ga.The adversary can use (8) to determine whether CT is encrypted by the access policy (M,ρ). Thus, the above CP-ABE scheme is said to provide no hidden policy.


## 4.2. Our Construction

We realize Waters CP-ABE scheme in the composite order groupsGp1p2p3. In our scheme, the ciphertext consists of 3 groups elements and the secret key consists of 2 groups elements. Therefore, the access policy along with the ciphertext is hidden by the elements in group Gp2.Setup(
1
λ
,
U
). The setup algorithm inputs a security parameter λ and a number U of attributes in the system. This algorithm runs the bilinear group generator to produce Θ=(N=p1p2p3,G,GT,e), where p1,p2,p3 are three distinct λ-bit primes. Then, it selects random generators g1,u1,…,uU∈Gp1 and g3∈Gp3. It picks a,α,y1,…,yU∈ZN and sets A1=u1g3y1,…,AU=uUg3yU. Consider(9)MPK:Θ,g1,g3,g1a,eg1,g1α,A1,…,AU, and MSK=g1α.Encrypt(
M
P
K
,
(
M
,
ρ
)
,
M
). Here, M is a l×n matrix and (M,ρ) is a LSSS structure. This algorithm chooses a vector v=(s,y2,…,yn)∈Zpn. For i=1 to l, it calculates λi=v·Mi, where Mi denotes the ith row of matrix M. Then, the algorithm randomly chooses r1,…,rl∈ZN and R0∈Gp3,{Ri,Ri′∈Gp3}i∈{1,…,l}. The ciphertext CT is as follows: (10)C1=Meg1,g1αs,C2=g1sR0,T1=g1aλ1Aρ1-r1Ri′,W1=g1r1R1,…,Tl=g1aλlAρl-rlRl′,Wl=g1rlRl along with an access structure of (M,ρ).KeyGen(
M
S
K
,
S
). This algorithm chooses a random t∈Zp and computes the secret key SK on a set S of attributes as (11)K1=g1αg1at,K2=g1t,Kx=uxt∀S.Decrypt(
C
T
,
S
K
). The receiver can decrypt the ciphertext by his secret key SK. Let I={i:ρ(i)∈S} and let {ωi∈ZN}i∈I be a set of constants such that ∑i∈I‍ωiλi=s, if {λi} are valid shares. The receiver can compute (12)eC2,K1Πi∈IeTi,K2eWi,Kρiωi=eg1,g1αs.Then, the algorithm can recover the message M from C1 by (12).Hidden Policy. Our scheme can provide hidden policy by using the subgroup Gp3. Suppose the adversary is given an arbitrary access policy (M′,ρ′) and a ciphertext CT=(C1,C2,(T1,W1),…,(Tl,Wl)). Let CT be encrypted under an access policy (M,ρ). The adversary chooses I′⊂{1,…,l} and {ωi′∈ZN}i∈I′ according to M′. (Note that {ωi′}i∈I is a set of constants such that if {λi′} are valid shares, then ∑i∈I′‍ωi′λi′=s.) Then, the adversary can perform the test as follows: (13)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=eg1sR0,g1aΠi∈I′eg1aλiuρ′ig3yρ′i-riRi′,g1eg1riRi,uρ′ig3yρ′iωi′=eg1,g1asΠi∈I′eg1aλiuρ′i-ri,g1eg1riRi,uρ′ig3yρ′iωi′=eg1,g1asΠi∈I′eg1aλiuρ′i-ri,g1eg1ri,uρ′ieRi,g3yρ′iωi′=eg1,g1asΠi∈I′eg1aλi,g1eRi,g3yρ′iωi′=eg1,g1aseg1,g1a∑i∈I′λiωi′Πi∈I′eRi,g3yρ′iωi′.Note that some pairings in the above equation equal identity inGT due to the orthogonal property in composite order groups. There are two possible cases:(1)
IfM′,ρ′=(M,ρ), then ∑i∈I′‍λiωi′=s. Thus, (14)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=1Πi∈I′eRi,g3yρ′iωi′.(2)
IfM′,ρ′≠(M,ρ), then ∑i∈I′‍λiωi′≠s. Thus, (15)eC2,g1aΠi∈I′eTi,g1eWi,Aρ′iωi′=eg1,g1aseg1,g1a∑i∈I′λiωi′Πi∈I′eRi,g3yρ′iωi′.In the above two cases, the test gives a random element inGT. So the adversary cannot determine whether the ciphertext CT is associated with the access policy M′,ρ′ or not. Thus, our scheme provides the property of hidden policy.Performance Comparison. Let Pr denote the computation cost of pairing and let Ex denote the exponent cost. For [4] and our scheme, we assume that the LSSS matrix is l×n. In Table 2, we provide the performance comparison with Waters scheme [4], Sreenivasa Rao and Dutta’s scheme [10], and our scheme. In decryption, we only evaluate the computational costs of pairing, since the pairing operation is very time-consuming compared to the other operations.Table 2
Performance comparison.
Schemes
Encrypt
Decrypt
Hidden policy
Expressiveness of access policy
Waters [4]
(
2
l
+
1
)
E
x
(
2
|
I
|
+
1
)
P
r
No
LSSS
Sreenivasa Rao and Dutta  [10]
1
2
Yes
AND
Our scheme
(
2
l
+
1
)
E
x
(
2
|
I
|
+
1
)
P
r
Yes
LSSSFrom Table2, we can see that the number of operations in our scheme is almost the same as Waters scheme. However, the operations in our scheme are operated in the composite order groups, while the operations in Waters scheme are operated in the prime order groups.


## 5. Security Proof

Our security proof employs a new mechanism which is calleddual system encryption, which requires two semifunctional (SF) structures. Let g2 be the generator of Gp2.SF Secret Key. K~1=K1·g2z1, K~2=K2·g2z2, and ∀x∈SK~x=Kx, where z1,z2∈ZN.SF  Ciphertext. C~1=C1, C~2=C2·g2δ, and T~1=T1·g2τ1,W~1=W1,…,(T~l=Tl·g2τl,W~l=Wl), where δ,τ1,…,τl∈ZN.When an SF secret key is used to decrypt an SF ciphertext, we will obtain an extra terme(g2,g2)z1δ-z2∑i∈I‍τiωi. If z1δ-z2∑i∈I‍τiωi=0, we call anSF secret key anominally semifunctional (NSF) secret key. An NSF secret key is a special kind of SF secret keys; that means z1δ=z2∑i∈I‍τiωi.Theorem 8.
Our CP-ABE scheme with hidden policy is chosen message attacks (CPA) secure under assumptions 1, 2, 3, and 4.Proof. We prove this theorem by a series of games. In the first real Gamer, the key and ciphertext are normal forms. Then, we convert the challenge ciphertext into SF in Game0 and transform the keys into SF forms one by one in Gamek (1≤k≤q-1). In Gameq, the challenge ciphertext and all secret keys are SF. In Gamef′, the message is distinguishable from a random message in the challenge ciphertext. Finally, in Gamef, Ti is randomly chosen from G. Thus, the ciphertext is independent of the policy chosen by the adversary.Lemma 9.
IfAdvAGamer-AdvAGame0≥ϵ, then assumption 1 is broken.Proof.
Given an instance(N,g1,g3,G,GT,(Bi)i∈{0,1}) of assumption 1, C constructs MPK as (16)g1,g3,g1a,eg1,g1α,A1=u1g3y1,…,AU=uUg3yU,where a,α,y1,…,yU∈ZN and u1,…,uU∈Gp3. Consider MSK=g1α. C can answer the key extraction queries A because it knows the master secret key. In the challenge phase, A provides the two challenge messages and two access policies as (M0,M1,(M0,ρ0)∗,(M1,ρ1)∗). Then, C randomly chooses μ∈{0,1},b∈{0,1} and values t0,t1,…,tl,r1,…,rl∈ZN and outputs the ciphertext CT∗ under access policy (Mμ,ρμ)∗ as (17)Mb·eg1α,B,B·g3t0,Baλ~iAρi-rig3-ti,g1rig3tii∈l.
IfB=g1sg2δX3∈G, where X3 is a random element in Gp3, then CT∗ is (18)Mb·eg1α,g1s,g1sg2δR0,Ti=g1aλiAρi-rig2τiRi′,Wi=g1riRii∈l, where λi=λ~i·s,τi=aδλ~i. This ciphertext is SF, and C simulates Game0. If B∈Gp1p2, C can simulate a normal ciphertext game, Gamer. Thus, if A can distinguish between an SF ciphertext and a normal ciphertext with a nonnegligible probability, then C can break assumption 1 by using the output of A.Lemma 10.
IfAdvAGamek-AdvAGamek-1≥ϵ, then assumption 2 is broken.Proof.
Given an instance (N,g1,g3,G,GT,X1X2X3,Y1Y2, (Bi)i∈{0,1}) of assumption 2, C constructs MPK as (19)g1,g3,g1a,eg1,g1α,A1=u1g3y1,…,AU=uUg3yU,where a,α,y1,…,yU∈ZN and u1,…,uU∈Gp3. Consider MSK=g1α. In order to make the first k-1 secret keys SF, the challenger C randomly chooses β∈ZN and implicitly sets Y1=g1ν1 and Y2=g2ν2 and responds to each key extraction query from A on a set of attributes S as (20)K1′=g1αY1Y2aβ,K2′=Y1Y2β.This implicitly sets z1=aν2β, t=ν1β, and z2=ν2β, so K1′, K2′ are properly distributed as semifunctional secret key components.
SinceC knows g1α, it can generate the normal secret keys for the last q-k key extraction queries from A.
For thekth key extraction query from A, C implicitly sets g1t as the Gp1 part of B and sets the secret key as (21)K1′=g1αBa,K2′=B.If B∈Gp1, then the secret key is distributed as normal secret key. If B=g1tg2z2∈Gp1p2, then the secret key is properly distributed as semifunctional key.
In the challenge phase,A provides the two challenge messages and two access policies as (M0,M1,(M0,ρ0)∗,(M1,ρ1)∗). Then, C randomly chooses μ∈{0,1},b∈{0,1} and values t0,t1,…,tl,r1,…,rl∈ZN. In order to generate the SF ciphertext, C implicitly sets X1X2X3=g1sg2δX3∈G and outputs CT∗ under access policy (Mμ,ρμ)∗ as (22)Mb·eg1α,X1X2X3,X1X2X3·g3t0,X1X2X3aλ~iAρi-rig3-ti,g1rig3tii∈l.
IfB∈Gp1, then C can simulate Gamek-1, and if B∈Gp1p2, then C can simulate Gamek. Thus, if A can distinguish between an SF secret key and a normal secret key with a nonnegligible probability, then C can break assumption 2 by using the output of A.Lemma 11.
IfAdvAGameq-AdvAGamef′≥ϵ, then assumption 3 is broken.Proof.
Given an instance (N,g1,G,GT,g1αX2,X3,g1sY2Y3,Z2, (Bi)i∈{0,1}) of assumption 3, C constructs MPK as (23)g1,g3,g1a,eg1αX2,g1,A1=u1g3y1,…,AU=uUg3yU,where a,y1,…,yU∈ZN and u1,…,uU∈Gp3. In order to make the secret keys SF, the challenger C randomly chooses t,κ∈ZN and responds to each key extraction query from A on a set of attributes S as (24)K1′=g1αX2g1tZ2a,K2′=g1tZ2κ.This implicitly sets X2=g2az2(1-1/κ) and Z2=g2z2/κ. So K1′, K2′ are properly distributed as SF secret key components.
In the challenge phase,A provides the two challenge messages and two access policies as (M0,M1,(M0,ρ0)∗,(M1,ρ1)∗). Then, C randomly chooses b∈{0,1} and values t0,t1,…,tl,r1,…,rl∈ZN. In order to generate the SF ciphertext, C implicitly sets g1sY2Y3=g1sg2δY3∈G and outputs CT∗ under access policy (Mb,ρb)∗ as (25)Mb·B,g1sY2Y3·g3t0,g1sY2Y3aλ~iAρi-rig3-ti,g1rig3tii∈l.
IfB=e(g1,g1)αs, then C can simulate Gameq, since CT∗ is distributed SF encryption of Mb. If B is a random element in G, then C can simulate Gamef′, since CT∗ is distributed SF encryption of a random element. Thus, C can can break assumption 3 by using the output of A.Lemma 12.
IfAdvAGamef′-AdvAGamef≥ϵ, then assumption 4 is broken.Proof.
Given an instance (N,G,GT,g1X3,g1sZ3,g1X2,Z2,g3, (Bi)i∈{0,1}) of assumption 4, C constructs MPK as (26)g1X2,g3,g1X3,g1X2a,eg1X2α,g1X3,A1=u1g3y1,…,AU=uUg3yU,where a,α,y1,…,yU∈ZN and u1,…,uU∈Gp3. Consider MSK=(g1X2)α. In order to make the secret keys SF, the challenger C randomly chooses t∈ZN and responds to each key extraction query from A on a set of attributes S as (27)K1′=g1X2αg1X2at,K2′=g1X2t.If X2=g2l, then this implicitly sets z1=αl(1+t),z2=lt. So K1′, K2′ are properly distributed as SF secret key components.
In the challenge phase,A provides the two challenge messages and two access policies as (M0,M1,(M0,ρ0)∗,(M1,ρ1)∗). Then, C randomly chooses b∈{0,1} and values t0,t1,…,tl,r1,…,rl∈ZN. In order to generate the SF ciphertext, C randomly chooses an element Δ∈GT and outputs CT∗ under access policy (Mb,ρb)∗ as (28)Δ,g1sZ3Z2g3t0,Baλ~iAρi-rig3-ti,g1rig3tii∈l. This implicitly sets Z2=g2δ.
IfB=g1sY2Y3, then C can simulate Gamef′, since CT∗ is distributed SF encryption of a random element in GT. If B is a random element in G, then C can simulate Gamef, since CT∗ is distributed SF encryption of a random element in GT with Ti being random in G. Thus, C can can break assumption 4 by using the output of A.From Lemmas9–12, if assumptions 1, 2, 3, and 4 hold, then Gamer is indistinguishable from Gamef. Obviously, the adversary can win Gamer with negligible probability. Thus, our CP-ABE scheme is CPA secure with hidden policy. This completes the proof.


## 6. Conclusion

In many applications, such as smart grid and e-health system, access policies for encryption should also be protected as well as the encrypted data, since the access policies may directly contain sensitive information. In this paper, we present a CP-ABE scheme with hidden policy from Waters construction, in which the access policy can be expressed with LSSS structure. Our scheme can be proved CPA secure under four static hardness assumptions.



---

*Source: 3257029-2016-01-28.xml*