CP-ABE with Hidden Policy from Waters Efficient Construction

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.

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 security

Organization. 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 = p_{1} p_{2} p_{3}$ , where $p_{1}, p_{2}, p_{3}$ are three distinct prime numbers. We denote this group as $G$ , and admit an efficient bilinear map $\hat{e} : G \times G \to G_{T}$ , where $G_{T}$ 's order is the same as $G$ 's. Any element of $G$ can be denoted as $g_{1}^{a_{1}} g_{2}^{a_{2}} g_{3}^{a_{3}}$ , where $g_{i}$ is the generator of subgroup $G_{p_{i}}$ . Each $G_{p_{i}}$ has the order $p_{i}$ , and $a_{i} \in Z_{p_{i}}$ . We denote $G_{p_{i} p_{j}}$ as the subgroup of order $p_{i} p_{j}$ in $G$ . For all $T \in G_{p_{i} p_{j}}$ , T can be defined as the product of an element in $G_{p_{i}}$ and an element in $G_{p_{j}}$ . For all $v \in G_{p_{i}}$ and $w \in G_{p_{j}}$ , $\hat{e} (v, w) = 1$ if $i \neq j$ . The following are three hardness assumptions, which have been analyzed in [10].

Definition 1 (assumption 1).

Given $Θ = (N = p_{1} p_{2} p_{3}, G, G_{T}, e)$ , if for all PPT algorithm $A$ , there is a negligible probability ϵ such that

\begin{matrix} |\Pr [A (Θ, g_{1}, g_{3}, B_{0}) = 1] - \Pr [A (Θ, g_{1}, g_{3}, B_{1}) = 1]| \leq ϵ, \end{matrix}

(1)

where the probabilities are over the random choice of

g_{1} \in G_{p_{1}}

g_{3} \in G_{p_{3}}

, and

B_{0} \in G

B_{1} \in G_{p_{1} p_{3}}

Definition 2 (assumption 2).

Given $Θ = (N = p_{1} p_{2} p_{3}, G, G_{T}, e)$ , if for all PPT algorithm $A$ , there is a negligible probability ϵ such that

\begin{matrix} |\Pr [A (Θ, g_{1}, X_{1} X_{2}, X_{3}, Y_{1} Y_{2}, B_{0}) = 1] - \Pr [A (Θ, g_{1}, X_{1} X_{2}, X_{3}, Y_{1} Y_{2}, B_{1}) = 1]| \leq ϵ, \end{matrix}

(2)

where the probabilities are over the random choice of

g_{1}, X_{1}, Y_{1} \in G_{p_{1}}

X_{2}, Y_{2} \in G_{p_{2}}

X_{3} \in G_{p_{3}}

B_{0} \in G_{p_{1} p_{2}}

, and

B_{1} \in G_{p_{1}}

Definition 3 (assumption 3).

Given $Θ = (N = p_{1} p_{2} p_{3}, G, G_{T}, e)$ , if for all PPT algorithm $A$ , there is a negligible probability ϵ such that

\begin{matrix} |\Pr [A (Θ, g_{1}, g_{1}^{α} X_{2}, X_{3}, g_{1}^{s} Y_{2} Y_{3}, Z_{2}, B_{0}) = 1] - \Pr [A (Θ, g_{1}, g_{1}^{α} X_{2}, X_{3}, g_{1}^{s} Y_{2} Y_{3}, Z_{2}, B_{1}) = 1]| \leq ϵ, \end{matrix}

(3)

where the probabilities are over the random choice of

s, α \in Z_{N}

g_{1} \in G_{p_{1}}

X_{2}, Y_{2}, Z_{2} \in G_{p_{2}}

X_{3}, Y_{3} \in G_{p_{3}}

B_{0} = e (g_{1}^{α}, g_{1}^{s})

, and

B_{1} \in_{R} G_{T}

Definition 4 (assumption 4).

Given $Θ = (N = p_{1} p_{2} p_{3}, G, G_{T}, e)$ , if for all PPT algorithm $A$ , there is a negligible probability ϵ such that

\begin{matrix} |\Pr [A (Θ, g_{1} X_{3}, g_{1}^{s} Z_{3}, g_{1} X_{2}, Z_{2}, g_{3}, B_{0}) = 1] - \Pr [A (Θ, g_{1} X_{3}, g_{1}^{s} Z_{3}, g_{1} X_{2}, Z_{2}, g_{3}, B_{1}) = 1]| \leq ϵ, \end{matrix}

(4)

where the probabilities are over the random choice of

s \in Z_{N}, g_{1} \in G_{p_{1}}, X_{2}, Y_{2}, Z_{2} \in G_{p_{2}}, X_{3}, Y_{3}, Z_{3} \in G_{p_{3}}, B_{0} = g_{1}^{s} Y_{2} Y_{3}

, and

B_{1} \in_{R} G_{T}

2.2. Access Policy and Linear Secret Sharing Scheme

We adapt our definitions which are given by [12–14].

Definition 5 (access policy).

Let ${S_{1}, \dots, S_{n}}$ be a set of attributes. An authorized collection $A \subset 2^{{S_{1}, \dots, S_{n}}}$ is monotone, on the condition that $\forall B, C$ , $B \in A$ and $B \subseteq C$ ; then $C \in 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 $Z_{N}$ . (2) There exists a sharing-generating $l \times n$ matrix $A$ for Π. For all $i = 1, \dots, l$ , the map ρ maps the $i t h$ row of $A$ to an attribute labeling $ρ (i)$ . Then, we select a random column vector $v = (μ, r_{2}, \dots, r_{n})$ , where $μ \in Z_{N}$ is the secret to be shared and $A v$ 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)

$S e t u p (1^{λ}, Σ)$ : the setup algorithm inputs a security parameter λ and an attribute set Σ and outputs system public key $M P K$ and master key $M S K$ .

(2)

$K e y G e n (M S K, S)$ : this algorithm inputs an attribute set $S$ and $M S K$ and outputs a private key $S K_{S}$ .

(3)

$E n c r y p t (M, A)$ : the encryption algorithm inputs an access structure $A$ and a message $M$ and outputs a ciphertext $C T$ .

(4)

$D e c r y p t (C T, S K)$ : this algorithm inputs a ciphertext $C T$ for an access structure $A$ and a private key $S K$ 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. $\forall M \in M$ , $\forall A \in 2^{Σ}$ , $\forall S \in A$ , and $M \leftarrow D e c r y p t (S K, E n c r y p t (M P K, M, A))$ , where $(M P K, M S K) \leftarrow S e t u p (1^{λ}, Σ)$ and $S K \leftarrow K e y G e n (M S K, 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 $M P K$ and $M S K$ and sends $M P K$ to $A$ .

Query 1. The adversary $A$ is allowed to make key extraction queries for the sets of attributes $S_{1}, S_{2}, \dots, S_{q_{1}}$ . $C$ runs the KeyGen algorithm and responds to the secret keys ${S K}_{S_{1}}, {S K}_{S_{2}}, \dots, {S K}_{S_{q_{1}}}$ .

Callenge. $A$ outputs two messages $M_{0}, M_{1} \in M$ and two access policies $A_{0}^{*}$ and $A_{1}^{*}$ such that $S_{1}, S_{2}, \dots, S_{q_{1}}$ does not satisfy $A_{0}^{*}$ and $A_{1}^{*}$ . $C$ randomly chooses a bit $b \in {0,1}$ and returns the ciphertext $C T^{*} \leftarrow E n c r y p t (M_{b}, A_{b}^{*})$ .

Query 2. $A$ can make the key extraction queries like Query 1 with the restriction that none of these satisfies $A_{0}^{*}$ and $A_{1}^{*}$ .

Response. Finally, $A$ outputs a guess $b^{'}$ of b. $A$ 's advantage of this game can be defined as $A D V_{A} (1^{λ}, Σ) = |2 \Pr [b = b^{'}] - 1|$ .

Definition 7 (CP-ABE-HP).

A CP-ABE is CPA secure with respect to hidden policy on the condition that $A D V_{A}$ 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 \in Z_{p}$ 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 $u_{1}, \dots, u_{U}$ that are corresponding to the U attributes in the system. And then, it selects random exponents $α, a \in Z_{p}$ . The master public key $M P K = (g, e (g, g)^{α}, g^{a}, u_{1}, \dots, u_{U})$ and the master secret key $M S K = g^{α}$ .

Encrypt( $M P K, (M, ρ), M$ ). Here, M is a $l \times n$ matrix and $(M, ρ)$ is a LSSS structure, where the map ρ maps rows of M to attributes. This algorithm randomly chooses $v = (s, y_{2}, \dots, y_{n}) \in Z_{p}^{n}$ . For $i = 1$ to l, it calculates $λ_{i} = v \cdot M_{i}$ , where $M_{i}$ is the ith row of M. Then, the algorithm randomly chooses $r_{1}, \dots, r_{l} \in Z_{p}$ . The ciphertext $C T$ is as follows:

\begin{matrix} C_{1} = M e {(g, g)}^{α s}, \\ C_{2} = g^{s}, \\ (T_{1} = g^{a λ_{1}} u_{ρ (1)}^{- r_{1}}, W_{1} = g^{r_{1}}), \dots, (T_{l} = g^{a λ_{l}} u_{ρ (l)}^{- r_{l}}, W_{l} = g^{r_{1}}) \end{matrix}

(5)

along with an access structure of

(M, ρ)

KeyGen( $M S K, S$ ). This algorithm chooses a random $t \in Z_{p}$ and computes the secret key $S K$ on a set S of attributes as

\begin{matrix} K_{1} = g^{α} g^{a t}, \\ K_{2} = g^{t}, \\ K_{x} = u_{x}^{t} \forall S . \end{matrix}

(6)

Decrypt( $C T, S K$ ). This algorithm inputs a ciphertext $C T$ associated with $(M, ρ)$ and a secret key $S K$ on a set S of attributes. We suppose that S satisfies $(M, ρ)$ and let $I = {i : ρ (i) \in S}$ . Then, ${ω_{i} \in Z_{p}}_{i \in I}$ is a set of constants such that $\sum_{i \in I} ‍ ω_{i} λ_{i} = s$ , if ${λ_{i}}$ are valid shares. This algorithm can compute

\begin{matrix} \frac{e (C_{2}, K_{1})}{(Π_{i \in I} {(e (T_{i}, K_{2}) e (W_{i}, K_{ρ (i)}))}^{ω_{i}})} = e {(g, g)}^{α s} . \end{matrix}

(7)

Then, the algorithm can recover the message

M

from

C_{1}

by (7).

We now argue that the above scheme is not hidden policy. Some components $C_{2}, T_{i}, W_{i}$ in ciphertext expose some information of access policy. Precisely, given an access policy $(M, ρ)$ , the adversary chooses $I \subset {1, \dots, l}$ and ${ω_{i} \in Z_{p}}_{i \in I}$ . (Note that there could be different ways for choosing the value of $ω_{i}$ to satisfy $\sum_{i \in I} ‍ ω_{i} λ_{i} = s$ , if ${λ_{i}}$ are valid shares.) Then, the adversary can run a test

\begin{matrix} Π_{i \in I} {(e (T_{i}, g) e (W_{i}, u_{ρ (i)}))}^{ω_{i}} \overset{?}{=} e (C_{2}, g^{a}) . \end{matrix}

(8)

The adversary can use (8) to determine whether

C T

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 groups $G_{p_{1} p_{2} p_{3}}$ . 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 $G_{p_{2}}$ .

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 = p_{1} p_{2} p_{3}, G, G_{T}, e)$ , where $p_{1}, p_{2}, p_{3}$ are three distinct λ-bit primes. Then, it selects random generators $g_{1}, u_{1}, \dots, u_{U} \in G_{p_{1}}$ and $g_{3} \in G_{p_{3}}$ . It picks $a, α, y_{1}, \dots, y_{U} \in Z_{N}$ and sets $A_{1} = u_{1} g_{3}^{y_{1}}, \dots, A_{U} = u_{U} g_{3}^{y_{U}}$ . Consider

\begin{matrix} MPK : 〈Θ, g_{1}, g_{3}, g_{1}^{a}, e {(g_{1}, g_{1})}^{α}, A_{1}, \dots, A_{U}〉, \end{matrix}

(9)

and

M S K = g_{1}^{α}

Encrypt( $M P K, (M, ρ), M$ ). Here, M is a $l \times n$ matrix and $(M, ρ)$ is a LSSS structure. This algorithm chooses a vector $v = (s, y_{2}, \dots, y_{n}) \in Z_{p}^{n}$ . For $i = 1$ to l, it calculates $λ_{i} = v \cdot M_{i}$ , where $M_{i}$ denotes the ith row of matrix M. Then, the algorithm randomly chooses $r_{1}, \dots, r_{l} \in Z_{N}$ and $R_{0} \in G_{p_{3}}, {R_{i}, R_{i}^{'} \in G_{p_{3}}}_{i \in {1, \dots, l}}$ . The ciphertext $C T$ is as follows:

\begin{matrix} C_{1} = M e {(g_{1}, g_{1})}^{α s}, \\ C_{2} = g_{1}^{s} R_{0}, \\ (T_{1} = g_{1}^{a λ_{1}} A_{ρ (1)}^{- r_{1}} R_{i}^{'}, W_{1} = g_{1}^{r_{1}} R_{1}), \dots, (T_{l} = g_{1}^{a λ_{l}} A_{ρ (l)}^{- r_{l}} R_{l}^{'}, W_{l} = g_{1}^{r_{l}} R_{l}) \end{matrix}

(10)

along with an access structure of

(M, ρ)

KeyGen( $M S K, S$ ). This algorithm chooses a random $t \in Z_{p}$ and computes the secret key $S K$ on a set S of attributes as

\begin{matrix} K_{1} = g_{1}^{α} g_{1}^{a t}, \\ K_{2} = g_{1}^{t}, \\ K_{x} = u_{x}^{t} \forall S . \end{matrix}

(11)

Decrypt( $C T, S K$ ). The receiver can decrypt the ciphertext by his secret key $S K$ . Let $I = {i : ρ (i) \in S}$ and let ${ω_{i} \in Z_{N}}_{i \in I}$ be a set of constants such that $\sum_{i \in I} ‍ ω_{i} λ_{i} = s$ , if ${λ_{i}}$ are valid shares. The receiver can compute

\begin{matrix} \frac{e (C_{2}, K_{1})}{(Π_{i \in I} {(e (T_{i}, K_{2}) e (W_{i}, K_{ρ (i)}))}^{ω_{i}})} = e {(g_{1}, g_{1})}^{α s} . \end{matrix}

(12)

Then, the algorithm can recover the message

M

from

C_{1}

by (12).

Hidden Policy. Our scheme can provide hidden policy by using the subgroup $G_{p_{3}}$ . Suppose the adversary is given an arbitrary access policy $(M^{'}, ρ^{'})$ and a ciphertext $C T = (C_{1}, C_{2}, (T_{1}, W_{1}), \dots, (T_{l}, W_{l}))$ . Let $C T$ be encrypted under an access policy $(M, ρ)$ . The adversary chooses $I^{'} \subset {1, \dots, l}$ and ${ω_{i}^{'} \in Z_{N}}_{i \in I^{'}}$ according to $M^{'}$ . (Note that ${ω_{i}^{'}}_{i \in I}$ is a set of constants such that if ${λ_{i}^{'}}$ are valid shares, then $\sum_{i \in I^{'}} ‍ ω_{i}^{'} λ_{i}^{'} = s$ .) Then, the adversary can perform the test as follows:

\begin{matrix} \frac{e (C_{2}, g_{1}^{a})}{Π_{i \in I^{'}} {(e (T_{i}, g_{1}) e (W_{i}, A_{ρ^{'} (i)}))}^{ω_{i}^{'}}} = \frac{e (g_{1}^{s} R_{0}, g_{1}^{a})}{Π_{i \in I^{'}} {(e (g_{1}^{a λ_{i}} {(u_{ρ^{'} (i)} g_{3}^{y_{ρ^{'} (i)}})}^{- r_{i}} R_{i}^{'}, g_{1}) e (g_{1}^{r_{i}} R_{i}, u_{ρ^{'} (i)} g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} = \frac{e {(g_{1}, g_{1})}^{a s}}{Π_{i \in I^{'}} {(e (g_{1}^{a λ_{i}} u_{ρ^{'} (i)}^{- r_{i}}, g_{1}) e (g_{1}^{r_{i}} R_{i}, u_{ρ^{'} (i)} g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} = \frac{e {(g_{1}, g_{1})}^{a s}}{Π_{i \in I^{'}} {(e (g_{1}^{a λ_{i}} u_{ρ^{'} (i)}^{- r_{i}}, g_{1}) e (g_{1}^{r_{i}}, u_{ρ^{'} (i)}) e (R_{i}, g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} = \frac{e {(g_{1}, g_{1})}^{a s}}{Π_{i \in I^{'}} {(e (g_{1}^{a λ_{i}}, g_{1}) e (R_{i}, g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} = \frac{e {(g_{1}, g_{1})}^{a s}}{e {(g_{1}, g_{1})}^{a \sum_{i \in I^{'}} λ_{i} ω_{i}^{'}} Π_{i \in I^{'}} {(e (R_{i}, g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} . \end{matrix}

(13)

Note that some pairings in the above equation equal identity in $G_{T}$ due to the orthogonal property in composite order groups. There are two possible cases: (1)

If $(M^{'}, ρ^{'}) = (M, ρ)$ , then $\sum_{i \in I^{'}} ‍ λ_{i} ω_{i}^{'} = s$ . Thus,

\begin{matrix} \frac{e (C_{2}, g_{1}^{a})}{Π_{i \in I^{'}} {(e (T_{i}, g_{1}) e (W_{i}, A_{ρ^{'} (i)}))}^{ω_{i}^{'}}} = \frac{1}{Π_{i \in I^{'}} {(e (R_{i}, g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} . \end{matrix}

(14)

(2)

If $(M^{'}, ρ^{'}) \neq (M, ρ)$ , then $\sum_{i \in I^{'}} ‍ λ_{i} ω_{i}^{'} \neq s$ . Thus,

\begin{matrix} \frac{e (C_{2}, g_{1}^{a})}{Π_{i \in I^{'}} {(e (T_{i}, g_{1}) e (W_{i}, A_{ρ^{'} (i)}))}^{ω_{i}^{'}}} = \frac{{e (g_{1}, g_{1})}^{a s}}{{e (g_{1}, g_{1})}^{a \sum_{i \in I^{'}} λ_{i} ω_{i}^{'}} Π_{i \in I^{'}} {(e (R_{i}, g_{3}^{y_{ρ^{'} (i)}}))}^{ω_{i}^{'}}} . \end{matrix}

(15)

In the above two cases, the test gives a random element in $G_{T}$ . So the adversary cannot determine whether the ciphertext $C T$ is associated with the access policy $(M^{'}, ρ^{'})$ or not. Thus, our scheme provides the property of hidden policy.

Performance Comparison. Let $P r$ denote the computation cost of pairing and let $E x$ denote the exponent cost. For [4] and our scheme, we assume that the LSSS matrix is $l \times 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	LSSS

From Table 2, 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 called dual system encryption, which requires two semifunctional (SF) structures. Let $g_{2}$ be the generator of $G_{p_{2}}$ .

SF Secret Key. ${\tilde{K}}_{1} = K_{1} \cdot g_{2}^{z_{1}}$ , ${\tilde{K}}_{2} = K_{2} \cdot g_{2}^{z_{2}}$ , and $\forall x \in S {\tilde{K}}_{x} = K_{x}$ , where $z_{1}, z_{2} \in Z_{N}$ .

SF Ciphertext. ${\tilde{C}}_{1} = C_{1}$ , ${\tilde{C}}_{2} = C_{2} \cdot g_{2}^{δ}$ , and $({\tilde{T}}_{1} = T_{1} \cdot g_{2}^{τ_{1}}, {\tilde{W}}_{1} = W_{1}), \dots, ({\tilde{T}}_{l} = T_{l} \cdot g_{2}^{τ_{l}}, {\tilde{W}}_{l} = W_{l})$ , where $δ, τ_{1}, \dots, τ_{l} \in Z_{N}$ .

When an SF secret key is used to decrypt an SF ciphertext, we will obtain an extra term $e (g_{2}, g_{2})^{z_{1} δ - z_{2} \sum_{i \in I} ‍ τ_{i} ω_{i}}$ . If $z_{1} δ - z_{2} \sum_{i \in I} ‍ τ_{i} ω_{i} = 0$ , we call an SF secret key a nominally semifunctional (NSF) secret key. An NSF secret key is a special kind of SF secret keys; that means $z_{1} δ = z_{2} \sum_{i \in 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 ${G a m e}_{r}$ , the key and ciphertext are normal forms. Then, we convert the challenge ciphertext into SF in ${G a m e}_{0}$ and transform the keys into SF forms one by one in ${G a m e}_{k}$ ( $1 \leq k \leq q - 1$ ). In ${G a m e}_{q}$ , the challenge ciphertext and all secret keys are SF. In ${G a m e}_{f^{'}}$ , the message is distinguishable from a random message in the challenge ciphertext. Finally, in ${G a m e}_{f}$ , $T_{i}$ is randomly chosen from $G$ . Thus, the ciphertext is independent of the policy chosen by the adversary.

Lemma 9.

If ${A d v}_{A}^{{G a m e}_{r}} - {A d v}_{A}^{{G a m e}_{0}} \geq ϵ$ , then assumption 1 is broken.

Proof.

Given an instance $(N, g_{1}, g_{3}, G, G_{T}, (B_{i})_{i \in {0,1}})$ of assumption 1, $C$ constructs $M P K$ as

\begin{matrix} 〈g_{1}, g_{3}, g_{1}^{a}, e {(g_{1}, g_{1})}^{α}, A_{1} = u_{1} g_{3}^{y_{1}}, \dots, A_{U} = u_{U} g_{3}^{y_{U}}〉, \end{matrix}

(16)

where

a, α, y_{1}, \dots, y_{U} \in Z_{N}

and

u_{1}, \dots, u_{U} \in G_{p_{3}}

. Consider

MSK = g_{1}^{α}

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

(M_{0}, M_{1}, (M_{0}, ρ_{0})^{*}, (M_{1}, ρ_{1})^{*})

. Then,

C

randomly chooses

μ \in {0,1}, b \in {0,1}

and values

t_{0}, t_{1}, \dots, t_{l}, r_{1}, \dots, r_{l} \in Z_{N}

and outputs the ciphertext

C T^{*}

under access policy

(M_{μ}, ρ_{μ})^{*}

\begin{matrix} 〈M_{b} \cdot e (g_{1}^{α}, B), B \cdot g_{3}^{t_{0}}, {(B^{a {\tilde{λ}}_{i}} A_{ρ (i)}^{- r_{i}} g_{3}^{- t_{i}}, g_{1}^{r_{i}} g_{3}^{t_{i}})}_{i \in [l]}〉 . \end{matrix}

(17)

If $B = g_{1}^{s} g_{2}^{δ} X_{3} \in G$ , where $X_{3}$ is a random element in $G_{p_{3}}$ , then $C T^{*}$ is

\begin{matrix} 〈M_{b} \cdot e (g_{1}^{α}, g_{1}^{s}), g_{1}^{s} g_{2}^{δ} R_{0}, {(T_{i} = g_{1}^{a λ_{i}} A_{ρ (i)}^{- r_{i}} g_{2}^{τ_{i}} R_{i}^{'}, W_{i} = g_{1}^{r_{i}} R_{i})}_{i \in [l]}〉, \end{matrix}

(18)

where

λ_{i} = {\tilde{λ}}_{i} \cdot s, τ_{i} = a δ {\tilde{λ}}_{i}

. This ciphertext is SF, and

C

simulates

{Game}_{0}

. If

B \in G_{p_{1} p_{2}}

C

can simulate a normal ciphertext game,

{Game}_{r}

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

If ${A d v}_{A}^{{G a m e}_{k}} - {A d v}_{A}^{{G a m e}_{k - 1}} \geq ϵ$ , then assumption 2 is broken.

Proof.

Given an instance ( $N, g_{1}, g_{3}, G, G_{T}, X_{1} X_{2} X_{3}, Y_{1} Y_{2}$ , $(B_{i})_{i \in {0,1}}$ ) of assumption 2, $C$ constructs $M P K$ as

\begin{matrix} 〈g_{1}, g_{3}, g_{1}^{a}, e {(g_{1}, g_{1})}^{α}, A_{1} = u_{1} g_{3}^{y_{1}}, \dots, A_{U} = u_{U} g_{3}^{y_{U}}〉, \end{matrix}

(19)

where

a, α, y_{1}, \dots, y_{U} \in Z_{N}

and

u_{1}, \dots, u_{U} \in G_{p_{3}}

. Consider

M S K = g_{1}^{α}

. In order to make the first

k - 1

secret keys SF, the challenger

C

randomly chooses

β \in Z_{N}

and implicitly sets

Y_{1} = g_{1}^{ν_{1}}

and

Y_{2} = g_{2}^{ν_{2}}

and responds to each key extraction query from

A

on a set of attributes S as

\begin{matrix} K_{1}^{'} = g_{1}^{α} {(Y_{1} Y_{2})}^{a β}, \\ K_{2}^{'} = {(Y_{1} Y_{2})}^{β} . \end{matrix}

(20)

This implicitly sets

z_{1} = a ν_{2} β

t = ν_{1} β

, and

z_{2} = ν_{2} β

, so

K_{1}^{'}

K_{2}^{'}

are properly distributed as semifunctional secret key components.

Since $C$ knows $g_{1}^{α}$ , it can generate the normal secret keys for the last $q - k$ key extraction queries from $A$ .

For the kth key extraction query from $A$ , $C$ implicitly sets $g_{1}^{t}$ as the $G_{p_{1}}$ part of B and sets the secret key as

\begin{matrix} K_{1}^{'} = g_{1}^{α} B^{a}, \\ K_{2}^{'} = B . \end{matrix}

(21)

B \in G_{p_{1}}

, then the secret key is distributed as normal secret key. If

B = g_{1}^{t} g_{2}^{z_{2}} \in G_{p_{1} p_{2}}

, 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 $(M_{0}, M_{1}, (M_{0}, ρ_{0})^{*}, (M_{1}, ρ_{1})^{*})$ . Then, $C$ randomly chooses $μ \in {0,1}, b \in {0,1}$ and values $t_{0}, t_{1}, \dots, t_{l}, r_{1}, \dots, r_{l} \in Z_{N}$ . In order to generate the SF ciphertext, $C$ implicitly sets $X_{1} X_{2} X_{3} = g_{1}^{s} g_{2}^{δ} X_{3} \in G$ and outputs $C T^{*}$ under access policy $(M_{μ}, ρ_{μ})^{*}$ as

\begin{matrix} 〈M_{b} \cdot e (g_{1}^{α}, X_{1} X_{2} X_{3}), X_{1} X_{2} X_{3} \cdot g_{3}^{t_{0}}, {({(X_{1} X_{2} X_{3})}^{a {\tilde{λ}}_{i}} A_{ρ (i)}^{- r_{i}} g_{3}^{- t_{i}}, g_{1}^{r_{i}} g_{3}^{t_{i}})}_{i \in [l]}〉 . \end{matrix}

(22)

If $B \in G_{p_{1}}$ , then $C$ can simulate ${G a m e}_{k - 1}$ , and if $B \in G_{p_{1} p_{2}}$ , then $C$ can simulate ${Game}_{k}$ . 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.

If ${A d v}_{A}^{{G a m e}_{q}} - {A d v}_{A}^{{G a m e}_{f^{'}}} \geq ϵ$ , then assumption 3 is broken.

Proof.

Given an instance ( $N, g_{1}, G, G_{T}, g_{1}^{α} X_{2}, X_{3}, g_{1}^{s} Y_{2} Y_{3}, Z_{2}$ , $(B_{i})_{i \in {0,1}}$ ) of assumption 3, $C$ constructs $M P K$ as

\begin{matrix} 〈g_{1}, g_{3}, g_{1}^{a}, e (g_{1}^{α} X_{2}, g_{1}), A_{1} = u_{1} g_{3}^{y_{1}}, \dots, A_{U} = u_{U} g_{3}^{y_{U}}〉, \end{matrix}

(23)

where

a, y_{1}, \dots, y_{U} \in Z_{N}

and

u_{1}, \dots, u_{U} \in G_{p_{3}}

. In order to make the secret keys SF, the challenger

C

randomly chooses

t, κ \in Z_{N}

and responds to each key extraction query from

A

on a set of attributes S as

\begin{matrix} K_{1}^{'} = g_{1}^{α} X_{2} {(g_{1}^{t} Z_{2})}^{a}, \\ K_{2}^{'} = g_{1}^{t} Z_{2}^{κ} . \end{matrix}

(24)

This implicitly sets

X_{2} = g_{2}^{a z_{2} (1 - 1 / κ)}

and

Z_{2} = g_{2}^{z_{2} / κ} .

K_{1}^{'}

K_{2}^{'}

are properly distributed as SF secret key components.

In the challenge phase, $A$ provides the two challenge messages and two access policies as $(M_{0}, M_{1}, (M_{0}, ρ_{0})^{*}, (M_{1}, ρ_{1})^{*})$ . Then, $C$ randomly chooses $b \in {0,1}$ and values $t_{0}, t_{1}, \dots, t_{l}, r_{1}, \dots, r_{l} \in Z_{N}$ . In order to generate the SF ciphertext, $C$ implicitly sets $g_{1}^{s} Y_{2} Y_{3} = g_{1}^{s} g_{2}^{δ} Y_{3} \in G$ and outputs $C T^{*}$ under access policy $(M_{b}, ρ_{b})^{*}$ as

\begin{matrix} 〈M_{b} \cdot B, g_{1}^{s} Y_{2} Y_{3} \cdot g_{3}^{t_{0}}, {({(g_{1}^{s} Y_{2} Y_{3})}^{a {\tilde{λ}}_{i}} A_{ρ (i)}^{- r_{i}} g_{3}^{- t_{i}}, g_{1}^{r_{i}} g_{3}^{t_{i}})}_{i \in [l]}〉 . \end{matrix}

(25)

If $B = e (g_{1}, g_{1})^{α s}$ , then $C$ can simulate ${Game}_{q}$ , since $C T^{*}$ is distributed SF encryption of $M_{b}$ . If B is a random element in $G$ , then $C$ can simulate ${G a m e}_{f^{'}}$ , since $C T^{*}$ is distributed SF encryption of a random element. Thus, $C$ can can break assumption 3 by using the output of $A$ .

Lemma 12.

If ${A d v}_{A}^{{G a m e}_{f^{'}}} - {A d v}_{A}^{{G a m e}_{f}} \geq ϵ$ , then assumption 4 is broken.

Proof.

Given an instance ( $N, G, G_{T}, g_{1} X_{3}, g_{1}^{s} Z_{3}, g_{1} X_{2}, Z_{2}, g_{3}$ , $(B_{i})_{i \in {0,1}}$ ) of assumption 4, $C$ constructs $M P K$ as

\begin{matrix} 〈g_{1} X_{2}, g_{3}, g_{1} X_{3}, {(g_{1} X_{2})}^{a}, e ({(g_{1} X_{2})}^{α}, g_{1} X_{3}), A_{1} = u_{1} g_{3}^{y_{1}}, \dots, A_{U} = u_{U} g_{3}^{y_{U}}〉, \end{matrix}

(26)

where

a, α, y_{1}, \dots, y_{U} \in Z_{N}

and

u_{1}, \dots, u_{U} \in G_{p_{3}}

. Consider

M S K = (g_{1} X_{2})^{α}

. In order to make the secret keys SF, the challenger

C

randomly chooses

t \in Z_{N}

and responds to each key extraction query from

A

on a set of attributes S as

\begin{matrix} K_{1}^{'} = {(g_{1} X_{2})}^{α} {(g_{1} X_{2})}^{a t}, \\ K_{2}^{'} = {(g_{1} X_{2})}^{t} . \end{matrix}

(27)

X_{2} = g_{2}^{l}

, then this implicitly sets

z_{1} = α l (1 + t), z_{2} = l t .

K_{1}^{'}

K_{2}^{'}

are properly distributed as SF secret key components.

In the challenge phase, $A$ provides the two challenge messages and two access policies as $(M_{0}, M_{1}, (M_{0}, ρ_{0})^{*}, (M_{1}, ρ_{1})^{*})$ . Then, $C$ randomly chooses $b \in {0,1}$ and values $t_{0}, t_{1}, \dots, t_{l}, r_{1}, \dots, r_{l} \in Z_{N}$ . In order to generate the SF ciphertext, $C$ randomly chooses an element $Δ \in G_{T}$ and outputs $C T^{*}$ under access policy $(M_{b}, ρ_{b})^{*}$ as

\begin{matrix} 〈Δ, (g_{1}^{s} Z_{3}) Z_{2} g_{3}^{t_{0}}, {({(B)}^{a {\tilde{λ}}_{i}} A_{ρ (i)}^{- r_{i}} g_{3}^{- t_{i}}, g_{1}^{r_{i}} g_{3}^{t_{i}})}_{i \in [l]}〉 . \end{matrix}

(28)

This implicitly sets

Z_{2} = g_{2}^{δ}

If $B = g_{1}^{s} Y_{2} Y_{3}$ , then $C$ can simulate ${Game}_{f^{'}}$ , since $C T^{*}$ is distributed SF encryption of a random element in $G_{T}$ . If B is a random element in $G$ , then $C$ can simulate ${Game}_{f}$ , since $C T^{*}$ is distributed SF encryption of a random element in $G_{T}$ with $T_{i}$ being random in $G$ . Thus, $C$ can can break assumption 4 by using the output of $A$ .

From Lemmas 9–12, if assumptions 1, 2, 3, and 4 hold, then ${Game}_{r}$ is indistinguishable from ${Game}_{f}$ . Obviously, the adversary can win ${Game}_{r}$ 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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This research is partially supported by the National Natural Science Foundation of China under Grant nos. 61373006, 61232016, U1405254, and the PAPD fund.

References

Wang

Chen

An ID-based online/offline signature scheme without random oracles for wireless sensor networks

Personal and Ubiquitous Computing 2013 17 5 837 841

10.1007/s00779-012-0534-1

2-s2.0-84883445487

Sahai

Waters

Fuzzy identity-based encryption

Advances in Cryptology—EUROCRYPT 2005 2005 3494

Berlin, Germany

Springer

457 473 Lecture Notes in Computer Science

10.1007/11426639_27

Lewko

Okamoto

Sahai

Takashima

Waters

Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption

Advances in Cryptology—EUROCRYPT 2010 2010 6110

Berlin, Germany

Springer

62 91 Lecture Notes in Computer Science

10.1007/978-3-642-13190-5_4

Waters

Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization

Public Key Cryptography—PKC 2011 2011 6571

Berlin, Germany

Springer

53 70 Lecture Notes in Computer Science

10.1007/978-3-642-19379-8_4

Goyal

Jain

Pandey

Sahai

Bounded ciphertext policy attribute based encryption

Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II 2008 5126

Berlin, Germany

Springer

579 591 Lecture Notes in Computer Science

10.1007/978-3-540-70583-3_47

Beimel

Gál

Paterson

Lower bounds for monotone span programs

Computational Complexity 1997 6 1 29 45

10.1007/bf01202040

MR1436301

2-s2.0-0040304685

Pandit

Barua

Efficient fully secure attribute-based encryption schemes for general access structures

Provable Security: 6th International Conference, ProvSec 2012, Chengdu, China, September 26–28, 2012. Proceedings 2012 7496

Berlin, Germany

Springer

193 214 Lecture Notes in Computer Science

10.1007/978-3-642-33272-2_13

Hur

Attribute-based secure data sharing with hidden policies in smart grid

IEEE Transactions on Parallel and Distributed Systems 2013 24 11 2171 2180

10.1109/tpds.2012.61

2-s2.0-84885145341

Lai

Deng

R. H.

Expressive CP-ABE with partially hidden access structures

Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security (ASIACCS ‘12)

May 2012

Seoul, Republic of Korea

ACM

18 19

10.1145/2414456.2414465

10.

Sreenivasa Rao

Dutta

Recipient anonymous ciphertext-policy attribute based encryption

Information Systems Security: 9th International Conference, ICISS 2013, Kolkata, India, December 16–20, 2013. Proceedings 2013 8303

Berlin, Germany

Springer

329 344 Lecture Notes in Computer Science

10.1007/978-3-642-45204-8_25

11.

Boneh

Goh

E.-J.

Nissim

Evaluating 2-DNF formulas on ciphertexts

Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10–12, 2005. Proceedings 2005 3378

Berlin, Germany

Springer

325 341 Lecture Notes in Computer Science

10.1007/978-3-540-30576-7_18

12.

Beimel

Secure schemes for secret sharing and key distribution [Ph.D. thesis] 1996

Haifa, Israel

Israel Institute of Technology, Technion

13.

Wang

Chu

Efficient mediated ciphertext-policy attribute-based encryption for personal health records systems

Journal of Internet Technology 2015 16 5 877 884

14.

Wang

A new authenticated group key transfer protocol for actual network environment

International Journal of Ad Hoc and Ubiquitous Computing 2013 12 3 188 192

10.1504/ijahuc.2013.052411

2-s2.0-84878273763