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

Definition 1 (assumption 1).

Given $\Theta =(N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,e)$ , if for all PPT algorithm $\mathfrak{A}$ , there is a negligible probability ϵ such that

$$\begin{array}{cc}& \left|\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},g_{\mathrm{3}},B_{\mathrm{0}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},g_{\mathrm{3}},B_{\mathrm{1}}\right)=\mathrm{1}\right]\right|\le ϵ,\end{array}$$

(1)

where the probabilities are over the random choice of $g_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}}$ , $g_{\mathrm{3}}\in {\mathbb{G}}_{p_{\mathrm{3}}}$ , and $B_{\mathrm{0}}\in \mathbb{G}$ , $B_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{3}}}$ .

Definition 2 (assumption 2).

Given $\Theta =(N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,e)$ , if for all PPT algorithm $\mathfrak{A}$ , there is a negligible probability ϵ such that

$$\begin{array}{cc}& \left|\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},X_{\mathrm{1}}{X}_{\mathrm{2}},X_{\mathrm{3}},Y_{\mathrm{1}}{Y}_{\mathrm{2}},B_{\mathrm{0}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},X_{\mathrm{1}}{X}_{\mathrm{2}},X_{\mathrm{3}},Y_{\mathrm{1}}{Y}_{\mathrm{2}},B_{\mathrm{1}}\right)=\mathrm{1}\right]\right|\le ϵ,\end{array}$$

(2)

where the probabilities are over the random choice of $g_{\mathrm{1}},X_{\mathrm{1}},Y_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}}$ , $X_{\mathrm{2}},Y_{\mathrm{2}}\in {\mathbb{G}}_{p_{\mathrm{2}}}$ , $X_{\mathrm{3}}\in {\mathbb{G}}_{p_{\mathrm{3}}}$ , $B_{\mathrm{0}}\in {\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ , and $B_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}}$ .

Definition 3 (assumption 3).

Given $\Theta =(N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,e)$ , if for all PPT algorithm $\mathfrak{A}$ , there is a negligible probability ϵ such that

$$\begin{array}{cc}& \left|\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},g_{\mathrm{1}}^{\alpha }{X}_{\mathrm{2}},X_{\mathrm{3}},g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}},Z_{\mathrm{2}},B_{\mathrm{0}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}},g_{\mathrm{1}}^{\alpha }{X}_{\mathrm{2}},X_{\mathrm{3}},g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}},Z_{\mathrm{2}},B_{\mathrm{1}}\right)=\mathrm{1}\right]\right|\le ϵ,\end{array}$$

(3)

where the probabilities are over the random choice of $s,\alpha \in {\mathbb{Z}}_N$ , $g_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}}$ , $X_{\mathrm{2}},Y_{\mathrm{2}},Z_{\mathrm{2}}\in {\mathbb{G}}_{p_{\mathrm{2}}}$ , $X_{\mathrm{3}},Y_{\mathrm{3}}\in {\mathbb{G}}_{p_{\mathrm{3}}}$ , $B_{\mathrm{0}}=e(g_{\mathrm{1}}^{\alpha },g_{\mathrm{1}}^s)$ , and $B_{\mathrm{1}}{\in }_R{\mathbb{G}}_T$ .

Definition 4 (assumption 4).

Given $\Theta =(N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,e)$ , if for all PPT algorithm $\mathfrak{A}$ , there is a negligible probability ϵ such that

$$\begin{array}{cc}& \left|\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}}{X}_{\mathrm{3}},g_{\mathrm{1}}^s{Z}_{\mathrm{3}},g_{\mathrm{1}}{X}_{\mathrm{2}},Z_{\mathrm{2}},g_{\mathrm{3}},B_{\mathrm{0}}\right)=\mathrm{1}\right]-\mathrm{Pr}\left[\mathfrak{A}\left(\Theta ,g_{\mathrm{1}}{X}_{\mathrm{3}},g_{\mathrm{1}}^s{Z}_{\mathrm{3}},g_{\mathrm{1}}{X}_{\mathrm{2}},Z_{\mathrm{2}},g_{\mathrm{3}},B_{\mathrm{1}}\right)=\mathrm{1}\right]\right|\le ϵ,\end{array}$$

(4)

where the probabilities are over the random choice of $s\in {\mathbb{Z}}_N,g_{\mathrm{1}}\in {\mathbb{G}}_{p_{\mathrm{1}}},X_{\mathrm{2}},Y_{\mathrm{2}},Z_{\mathrm{2}}\in {\mathbb{G}}_{p_{\mathrm{2}}},X_{\mathrm{3}},Y_{\mathrm{3}},Z_{\mathrm{3}}\in {\mathbb{G}}_{p_{\mathrm{3}}},B_{\mathrm{0}}=g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}}$ , and $B_{\mathrm{1}}{\in }_R{\mathbb{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_{\mathrm{1}},\dots ,S_n\}$ be a set of attributes. An authorized collection $\mathbb{A}\subset {\mathrm{2}}^{\{S_{\mathrm{1}},\dots ,S_n\}}$ is monotone, on the condition that $\forall B,C$ , $B\in \mathbb{A}$ and $B\subseteq C$ ; then $C\in \mathbb{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 ${\mathbb{Z}}_N$ . (2) There exists a sharing-generating $l\times n$ matrix $\mathcal{A}$ for Π. For all $i=\mathrm{1},\dots ,l$ , the map ρ maps the $i\mathrm{t}\mathrm{h}$ row of $\mathcal{A}$ to an attribute labeling $\rho (i)$ . Then, we select a random column vector $v=(\mu ,r_{\mathrm{2}},\dots ,r_n)$ , where $\mu \in {\mathbb{Z}}_N$ is the secret to be shared and $\mathcal{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)

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

(2)

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

(3)

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

(4)

$\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{C}\mathrm{T},\mathrm{S}\mathrm{K})$ : this algorithm inputs a ciphertext $\mathrm{C}\mathrm{T}$ for an access structure $\mathbb{A}$ and a private key $\mathrm{S}\mathrm{K}$ for a set $\mathbb{S}$ and outputs $\mathcal{M}$ if and only if the attribute set $\mathbb{S}$ satisfies the access structure $\mathbb{A}$ .

Let Σ and $\mathfrak{M}$ be the monotone attribute space and the message space, respectively. $\forall \mathcal{M}\in \mathfrak{M}$ , $\forall \mathbb{A}\in {\mathrm{2}}^{\Sigma }$ , $\forall \mathbb{S}\in \mathbb{A}$ , and $M\leftarrow \mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{S}\mathrm{K},\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}(\mathrm{M}\mathrm{P}\mathrm{K},M,\mathbb{A}))$ , where $(\mathrm{M}\mathrm{P}\mathrm{K},\mathrm{M}\mathrm{S}\mathrm{K})\leftarrow \mathrm{S}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{p}({\mathrm{1}}^{\lambda },\Sigma )$ and $\mathrm{S}\mathrm{K}\leftarrow \mathrm{K}\mathrm{e}\mathrm{y}\mathrm{G}\mathrm{e}\mathrm{n}(\mathrm{M}\mathrm{S}\mathrm{K},\mathbb{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 $\mathfrak{C}$ generates $\mathrm{M}\mathrm{P}\mathrm{K}$ and $\mathrm{M}\mathrm{S}\mathrm{K}$ and sends $\mathrm{M}\mathrm{P}\mathrm{K}$ to $\mathfrak{A}$ .

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

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

Query 2. $\mathfrak{A}$ can make the key extraction queries like Query 1 with the restriction that none of these satisfies ${\mathbb{A}}_{\mathrm{0}}^{\ast }$ and ${\mathbb{A}}_{\mathrm{1}}^{\ast }$ .

Response. Finally, $\mathfrak{A}$ outputs a guess $b^{\prime }$ of b. $\mathfrak{A}$ 's advantage of this game can be defined as $\mathrm{A}\mathrm{D}{\mathrm{V}}_{\mathfrak{A}}({\mathrm{1}}^{\lambda },\Sigma )=\left|\mathrm{2}\mathrm{Pr}\left[b=b^{\prime }\right]-\mathrm{1}\right|$ .

Definition 7 (CP-ABE-HP).

A CP-ABE is CPA secure with respect to hidden policy on the condition that $\mathrm{A}\mathrm{D}{\mathrm{V}}_{\mathfrak{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 {\mathbb{Z}}_p$ according to M.

Setup(U). This algorithm inputs the number of attributes U. Then, it chooses a prime order p group $\mathbb{G}$ , a generator g, and random group elements $u_{\mathrm{1}},\dots ,u_U$ that are corresponding to the U attributes in the system. And then, it selects random exponents $\alpha ,a\in {\mathbb{Z}}_p$ . The master public key $\mathrm{M}\mathrm{P}\mathrm{K}=(g,e(g,g{)}^{\alpha },g^a,u_{\mathrm{1}},\dots ,u_U)$ and the master secret key $\mathrm{M}\mathrm{S}\mathrm{K}=g^{\alpha }$ .

Encrypt( $MPK,(M,\rho ),\mathcal{M}$ ). Here, M is a $l\times n$ matrix and $(M,\rho )$ is a LSSS structure, where the map ρ maps rows of M to attributes. This algorithm randomly chooses $v=(s,y_{\mathrm{2}},\dots ,y_n)\in {\mathbb{Z}}_p^n$ . For $i=\mathrm{1}$ to l, it calculates ${\lambda }_i=v·M_i$ , where $M_i$ is the ith row of M. Then, the algorithm randomly chooses $r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_p$ . The ciphertext $\mathrm{C}\mathrm{T}$ is as follows:

$$\begin{array}{cc}& C_{\mathrm{1}}=\mathcal{M}e{\left(g,g\right)}^{\alpha s},\\ C_{\mathrm{2}}=g^s,\\ \left(T_{\mathrm{1}}=g^{a{\lambda }_{\mathrm{1}}}{u}_{\rho \left(\mathrm{1}\right)}^{-r_{\mathrm{1}}},W_{\mathrm{1}}=g^{r_{\mathrm{1}}}\right),\dots ,\left(T_l=g^{a{\lambda }_l}{u}_{\rho \left(l\right)}^{-r_l},W_l=g^{r_{\mathrm{1}}}\right)\end{array}$$

(5)

along with an access structure of $(M,\rho )$ .

KeyGen( $MSK,S$ ). This algorithm chooses a random $t\in {\mathbb{Z}}_p$ and computes the secret key $\mathrm{S}\mathrm{K}$ on a set S of attributes as

$$\begin{array}{cc}& K_{\mathrm{1}}=g^{\alpha }{g}^{at},\\ K_{\mathrm{2}}=g^t,\\ K_x=u_x^t\hspace{1em}\forall S.\end{array}$$

(6)

Decrypt( $CT,SK$ ). This algorithm inputs a ciphertext $\mathrm{C}\mathrm{T}$ associated with $(M,\rho )$ and a secret key $\mathrm{S}\mathrm{K}$ on a set S of attributes. We suppose that S satisfies $(M,\rho )$ and let $I=\{i:\rho (i)\in S\}$ . Then, $\{{\omega }_i\in {\mathbb{Z}}_p{\}}_{i\in I}$ is a set of constants such that ${\sum }_{i\in I}‍{\omega }_i{\lambda }_i=s$ , if $\{{\lambda }_i\}$ are valid shares. This algorithm can compute

$$\begin{array}{cc}& \frac{e\left(C_{\mathrm{2}},K_{\mathrm{1}}\right)}{\left({\Pi }_{i\in I}{\left(e\left(T_i,K_{\mathrm{2}}\right)e\left(W_i,K_{\rho \left(i\right)}\right)\right)}^{{\omega }_i}\right)}=e{\left(g,g\right)}^{\alpha s}.\end{array}$$

(7)

Then, the algorithm can recover the message $\mathcal{M}$ from $C_{\mathrm{1}}$ by (7).

We now argue that the above scheme is not hidden policy. Some components $C_{\mathrm{2}},T_i,W_i$ in ciphertext expose some information of access policy. Precisely, given an access policy $(M,\rho )$ , the adversary chooses $\mathcal{I}\subset \{\mathrm{1},\dots ,l\}$ and $\{{\omega }_i\in {\mathbb{Z}}_p{\}}_{i\in \mathcal{I}}$ . (Note that there could be different ways for choosing the value of ${\omega }_i$ to satisfy ${\sum }_{i\in \mathcal{I}}‍{\omega }_i{\lambda }_i=s$ , if $\{{\lambda }_i\}$ are valid shares.) Then, the adversary can run a test

$$\begin{array}{cc}& {\Pi }_{i\in \mathcal{I}}{\left(e\left(T_i,g\right)e\left(W_i,u_{\rho \left(i\right)}\right)\right)}^{{\omega }_i}\stackrel{?}{=}e\left(C_{\mathrm{2}},g^a\right).\end{array}$$

(8)

The adversary can use (8) to determine whether $\mathrm{C}\mathrm{T}$ is encrypted by the access policy $(M,\rho )$ . 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 ${\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{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 ${\mathbb{G}}_{p_{\mathrm{2}}}$ .

Setup( $1^{\lambda },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 $\Theta =(N=p_{\mathrm{1}}{p}_{\mathrm{2}}{p}_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,e)$ , where $p_{\mathrm{1}},p_{\mathrm{2}},p_{\mathrm{3}}$ are three distinct λ-bit primes. Then, it selects random generators $g_{\mathrm{1}},u_{\mathrm{1}},\dots ,u_U\in G_{p_{\mathrm{1}}}$ and $g_{\mathrm{3}}\in G_{p_{\mathrm{3}}}$ . It picks $a,\alpha ,y_{\mathrm{1}},\dots ,y_U\in {\mathbb{Z}}_N$ and sets $A_{\mathrm{1}}=u_{\mathrm{1}}{g}_{\mathrm{3}}^{y_{\mathrm{1}}},\dots ,A_U=u_U{g}_{\mathrm{3}}^{y_U}$ . Consider

$$\begin{array}{cc}& \text{MPK}:〈\Theta ,g_{\mathrm{1}},g_{\mathrm{3}},g_{\mathrm{1}}^a,e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{\alpha },A_{\mathrm{1}},\dots ,A_U〉,\end{array}$$

(9)

and $\mathrm{M}\mathrm{S}\mathrm{K}=g_{\mathrm{1}}^{\alpha }$ .

Encrypt( $MPK,(M,\rho ),\mathcal{M}$ ). Here, M is a $l\times n$ matrix and $(M,\rho )$ is a LSSS structure. This algorithm chooses a vector $v=(s,y_{\mathrm{2}},\dots ,y_n)\in {\mathbb{Z}}_p^n$ . For $i=\mathrm{1}$ to l, it calculates ${\lambda }_i=v·M_i$ , where $M_i$ denotes the ith row of matrix M. Then, the algorithm randomly chooses $r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_N$ and $R_{\mathrm{0}}\in {\mathbb{G}}_{p_{\mathrm{3}}},\{R_i,R_i^{\prime }\in {\mathbb{G}}_{p_{\mathrm{3}}}{\}}_{i\in \{\mathrm{1},\dots ,l\}}$ . The ciphertext $\mathrm{C}\mathrm{T}$ is as follows:

$$\begin{array}{cc}& C_{\mathrm{1}}=\mathcal{M}e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{\alpha s},\\ C_{\mathrm{2}}=g_{\mathrm{1}}^s{R}_{\mathrm{0}},\\ \left(T_{\mathrm{1}}=g_{\mathrm{1}}^{a{\lambda }_{\mathrm{1}}}{A}_{\rho \left(\mathrm{1}\right)}^{-r_{\mathrm{1}}}{R}_i^{\prime },W_{\mathrm{1}}=g_{\mathrm{1}}^{r_{\mathrm{1}}}{R}_{\mathrm{1}}\right),\dots ,\left(T_l=g_{\mathrm{1}}^{a{\lambda }_l}{A}_{\rho \left(l\right)}^{-r_l}{R}_l^{\prime },W_l=g_{\mathrm{1}}^{r_l}{R}_l\right)\end{array}$$

(10)

along with an access structure of $(M,\rho )$ .

KeyGen( $MSK,S$ ). This algorithm chooses a random $t\in {\mathbb{Z}}_p$ and computes the secret key $\mathrm{S}\mathrm{K}$ on a set S of attributes as

$$\begin{array}{cc}& K_{\mathrm{1}}=g_{\mathrm{1}}^{\alpha }{g}_{\mathrm{1}}^{at},\\ K_{\mathrm{2}}=g_{\mathrm{1}}^t,\\ K_x=u_x^t\hspace{1em}\forall S.\end{array}$$

(11)

Decrypt( $CT,SK$ ). The receiver can decrypt the ciphertext by his secret key $\mathrm{S}\mathrm{K}$ . Let $I=\{i:\rho (i)\in S\}$ and let $\{{\omega }_i\in {\mathbb{Z}}_N{\}}_{i\in I}$ be a set of constants such that ${\sum }_{i\in I}‍{\omega }_i{\lambda }_i=s$ , if $\{{\lambda }_i\}$ are valid shares. The receiver can compute

$$\begin{array}{cc}& \frac{e\left(C_{\mathrm{2}},K_{\mathrm{1}}\right)}{\left({\Pi }_{i\in I}{\left(e\left(T_i,K_{\mathrm{2}}\right)e\left(W_i,K_{\rho \left(i\right)}\right)\right)}^{{\omega }_i}\right)}=e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{\alpha s}.\end{array}$$

(12)

Then, the algorithm can recover the message $\mathcal{M}$ from $C_{\mathrm{1}}$ by (12).

Hidden Policy. Our scheme can provide hidden policy by using the subgroup ${\mathbb{G}}_{p_{\mathrm{3}}}$ . Suppose the adversary is given an arbitrary access policy $(M^{\prime },{\rho }^{\prime })$ and a ciphertext $\mathrm{C}\mathrm{T}=(C_{\mathrm{1}},C_{\mathrm{2}},(T_{\mathrm{1}},W_{\mathrm{1}}),\dots ,(T_l,W_l))$ . Let $\mathrm{C}\mathrm{T}$ be encrypted under an access policy $(M,\rho )$ . The adversary chooses $I^{\prime }\subset \{\mathrm{1},\dots ,l\}$ and $\{{\omega }_i^{\prime }\in {\mathbb{Z}}_N{\}}_{i\in I^{\prime }}$ according to $M^{\prime }$ . (Note that $\{{\omega }_i^{\prime }{\}}_{i\in I}$ is a set of constants such that if $\{{\lambda }_i^{\prime }\}$ are valid shares, then ${\sum }_{i\in I^{\prime }}‍{\omega }_i^{\prime }{\lambda }_i^{\prime }=s$ .) Then, the adversary can perform the test as follows:

$$\begin{array}{cc}& \frac{e\left(C_{\mathrm{2}},g_{\mathrm{1}}^a\right)}{{\Pi }_{i\in I^{\prime }}{\left(e\left(T_i,g_{\mathrm{1}}\right)e\left(W_i,A_{{\rho }^{\prime }\left(i\right)}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{e\left(g_{\mathrm{1}}^s{R}_{\mathrm{0}},g_{\mathrm{1}}^a\right)}{{\Pi }_{i\in I^{\prime }}{\left(e\left(g_{\mathrm{1}}^{a{\lambda }_i}{\left(u_{{\rho }^{\prime }\left(i\right)}{g}_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)}^{-r_i}{R}_i^{\prime },g_{\mathrm{1}}\right)e\left(g_{\mathrm{1}}^{r_i}{R}_i,u_{{\rho }^{\prime }\left(i\right)}{g}_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{as}}{{\Pi }_{i\in I^{\prime }}{\left(e\left(g_{\mathrm{1}}^{a{\lambda }_i}{u}_{{\rho }^{\prime }\left(i\right)}^{-r_i},g_{\mathrm{1}}\right)e\left(g_{\mathrm{1}}^{r_i}{R}_i,u_{{\rho }^{\prime }\left(i\right)}{g}_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{as}}{{\Pi }_{i\in I^{\prime }}{\left(e\left(g_{\mathrm{1}}^{a{\lambda }_i}{u}_{{\rho }^{\prime }\left(i\right)}^{-r_i},g_{\mathrm{1}}\right)e\left(g_{\mathrm{1}}^{r_i},u_{{\rho }^{\prime }\left(i\right)}\right)e\left(R_i,g_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{as}}{{\Pi }_{i\in I^{\prime }}{\left(e\left(g_{\mathrm{1}}^{a{\lambda }_i},g_{\mathrm{1}}\right)e\left(R_i,g_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{as}}{e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{a{\sum }_{i\in I^{\prime }}{\lambda }_i{\omega }_i^{\prime }}{\Pi }_{i\in I^{\prime }}{\left(e\left(R_i,g_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}.\end{array}$$

(13)

Note that some pairings in the above equation equal identity in ${\mathbb{G}}_T$ due to the orthogonal property in composite order groups. There are two possible cases:

• (1)

If $\left(M^{\prime },{\rho }^{\prime }\right)=(M,\rho )$ , then ${\sum }_{i\in I^{\prime }}‍{\lambda }_i{\omega }_i^{\prime }=s$ . Thus,

$$\begin{array}{cc}& \frac{e\left(C_{\mathrm{2}},g_{\mathrm{1}}^a\right)}{{\Pi }_{i\in I^{\prime }}{\left(e\left(T_i,g_{\mathrm{1}}\right)e\left(W_i,A_{{\rho }^{\prime }\left(i\right)}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{\mathrm{1}}{{\Pi }_{i\in I^{\prime }}{\left(e\left(R_i,g_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}.\end{array}$$

(14)

(2)

If $\left(M^{\prime },{\rho }^{\prime }\right)\ne (M,\rho )$ , then ${\sum }_{i\in I^{\prime }}‍{\lambda }_i{\omega }_i^{\prime }\ne s$ . Thus,

$$\begin{array}{cc}& \frac{e\left(C_{\mathrm{2}},g_{\mathrm{1}}^a\right)}{{\Pi }_{i\in I^{\prime }}{\left(e\left(T_i,g_{\mathrm{1}}\right)e\left(W_i,A_{{\rho }^{\prime }\left(i\right)}\right)\right)}^{{\omega }_i^{\prime }}}=\frac{{e\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{as}}{{e\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{a{\sum }_{i\in I^{\prime }}{\lambda }_i{\omega }_i^{\prime }}{\Pi }_{i\in I^{\prime }}{\left(e\left(R_i,g_{\mathrm{3}}^{y_{{\rho }^{\prime }\left(i\right)}}\right)\right)}^{{\omega }_i^{\prime }}}.\end{array}$$

(15)

In the above two cases, the test gives a random element in ${\mathbb{G}}_T$ . So the adversary cannot determine whether the ciphertext $\mathrm{C}\mathrm{T}$ is associated with the access policy $\left(M^{\prime },{\rho }^{\prime }\right)$ or not. Thus, our scheme provides the property of hidden policy.

Performance Comparison. Let $\mathrm{P}\mathrm{r}$ denote the computation cost of pairing and let $\mathrm{E}\mathrm{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]	$(\mathrm{2}l+\mathrm{1})\mathrm{E}\mathrm{x}$	$(\mathrm{2}|I|+\mathrm{1})\mathrm{P}\mathrm{r}$	No	LSSS
Sreenivasa Rao and Dutta[10]	1	2	Yes	AND
Our scheme	$(\mathrm{2}l+\mathrm{1})\mathrm{E}\mathrm{x}$	$(\mathrm{2}|I|+\mathrm{1})\mathrm{P}\mathrm{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_{\mathrm{2}}$ be the generator of ${\mathbb{G}}_{p_{\mathrm{2}}}$ .

SF Secret Key. ${\tilde{K}}_{\mathrm{1}}=K_{\mathrm{1}}·g_{\mathrm{2}}^{z_{\mathrm{1}}}$ , ${\tilde{K}}_{\mathrm{2}}=K_{\mathrm{2}}·g_{\mathrm{2}}^{z_{\mathrm{2}}}$ , and $\forall x\in S\hspace{0.17em}\hspace{0.17em}{\tilde{K}}_x=K_x$ , where $z_{\mathrm{1}},z_{\mathrm{2}}\in {\mathbb{Z}}_N$ .

SF  Ciphertext. ${\tilde{C}}_{\mathrm{1}}=C_{\mathrm{1}}$ , ${\tilde{C}}_{\mathrm{2}}=C_{\mathrm{2}}·g_{\mathrm{2}}^{\delta }$ , and $\left({\tilde{T}}_{\mathrm{1}}=T_{\mathrm{1}}·g_{\mathrm{2}}^{{\tau }_{\mathrm{1}}},{\tilde{W}}_{\mathrm{1}}=W_{\mathrm{1}}\right),\dots ,({\tilde{T}}_l=T_l·g_{\mathrm{2}}^{{\tau }_l},{\tilde{W}}_l=W_l)$ , where $\delta ,{\tau }_{\mathrm{1}},\dots ,{\tau }_l\in {\mathbb{Z}}_N$ .

When an SF secret key is used to decrypt an SF ciphertext, we will obtain an extra term $e(g_{\mathrm{2}},g_{\mathrm{2}}{)}^{z_{\mathrm{1}}\delta -z_{\mathrm{2}}{\sum }_{i\in I}‍{\tau }_i{\omega }_i}$ . If $z_{\mathrm{1}}\delta -z_{\mathrm{2}}{\sum }_{i\in I}‍{\tau }_i{\omega }_i=\mathrm{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_{\mathrm{1}}\delta =z_{\mathrm{2}}{\sum }_{i\in I}‍{\tau }_i{\omega }_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 ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_r$ , the key and ciphertext are normal forms. Then, we convert the challenge ciphertext into SF in ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_{\mathrm{0}}$ and transform the keys into SF forms one by one in ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_k$ ( $\mathrm{1}\le k\le q-\mathrm{1}$ ). In ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_q$ , the challenge ciphertext and all secret keys are SF. In ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_{f^{\prime }}$ , the message is distinguishable from a random message in the challenge ciphertext. Finally, in ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_f$ , $T_i$ is randomly chosen from $\mathbb{G}$ . Thus, the ciphertext is independent of the policy chosen by the adversary.

Lemma 9.

If ${Adv}_A^{{Game}_r}-{Adv}_A^{{Game}_{\mathrm{0}}}\ge ϵ$ , then assumption 1 is broken.

Proof.

Given an instance $(N,g_{\mathrm{1}},g_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,(B_i{)}_{i\in \{\mathrm{0,1}\}})$ of assumption 1, $\mathfrak{C}$ constructs $\mathrm{M}\mathrm{P}\mathrm{K}$ as

$$\begin{array}{cc}& 〈g_{\mathrm{1}},g_{\mathrm{3}},g_{\mathrm{1}}^a,e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{\alpha },A_{\mathrm{1}}=u_{\mathrm{1}}{g}_{\mathrm{3}}^{y_{\mathrm{1}}},\dots ,A_U=u_U{g}_{\mathrm{3}}^{y_U}〉,\end{array}$$

(16)

where $a,\alpha ,y_{\mathrm{1}},\dots ,y_U\in {\mathbb{Z}}_N$ and $u_{\mathrm{1}},\dots ,u_U\in {\mathbb{G}}_{p_{\mathrm{3}}}$ . Consider $\text{MSK}=g_{\mathrm{1}}^{\alpha }$ . $\mathfrak{C}$ can answer the key extraction queries $\mathfrak{A}$ because it knows the master secret key. In the challenge phase, $\mathfrak{A}$ provides the two challenge messages and two access policies as $({\mathcal{M}}_{\mathrm{0}},{\mathcal{M}}_{\mathrm{1}},(M_{\mathrm{0}},{\rho }_{\mathrm{0}}{)}^{\ast },(M_{\mathrm{1}},{\rho }_{\mathrm{1}}{)}^{\ast })$ . Then, $\mathfrak{C}$ randomly chooses $\mu \in \{\mathrm{0,1}\},b\in \{\mathrm{0,1}\}$ and values $t_{\mathrm{0}},t_{\mathrm{1}},\dots ,t_l,r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_N$ and outputs the ciphertext $\mathrm{C}{\mathrm{T}}^{\ast }$ under access policy $(M_{\mu },{\rho }_{\mu }{)}^{\ast }$ as

$$\begin{array}{cc}& 〈{\mathcal{M}}_b·e\left(g_{\mathrm{1}}^{\alpha },B\right),B·g_{\mathrm{3}}^{t_{\mathrm{0}}},{\left(B^{a{\tilde{\lambda }}_i}{A}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{3}}^{-t_i},g_{\mathrm{1}}^{r_i}{g}_{\mathrm{3}}^{t_i}\right)}_{i\in \left[l\right]}〉.\end{array}$$

(17)

If $B=g_{\mathrm{1}}^s{g}_{\mathrm{2}}^{\delta }{X}_{\mathrm{3}}\in \mathbb{G}$ , where $X_{\mathrm{3}}$ is a random element in ${\mathbb{G}}_{p_{\mathrm{3}}}$ , then $\mathrm{C}{\mathrm{T}}^{\ast }$ is

$$\begin{array}{cc}& 〈{\mathcal{M}}_b·e\left(g_{\mathrm{1}}^{\alpha },g_{\mathrm{1}}^s\right),g_{\mathrm{1}}^s{g}_{\mathrm{2}}^{\delta }{R}_{\mathrm{0}},{\left(T_i=g_{\mathrm{1}}^{a{\lambda }_i}{A}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{2}}^{{\tau }_i}{R}_i^{\prime },W_i=g_{\mathrm{1}}^{r_i}{R}_i\right)}_{i\in \left[l\right]}〉,\end{array}$$

(18)

where ${\lambda }_i={\tilde{\lambda }}_i·s,{\tau }_i=a\delta {\tilde{\lambda }}_i$ . This ciphertext is SF, and $\mathfrak{C}$ simulates ${\text{Game}}_{\mathrm{0}}$ . If $B\in {\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ , $\mathfrak{C}$ can simulate a normal ciphertext game, ${\text{Game}}_r$ . Thus, if $\mathfrak{A}$ can distinguish between an SF ciphertext and a normal ciphertext with a nonnegligible probability, then $\mathfrak{C}$ can break assumption 1 by using the output of $\mathfrak{A}$ .

Lemma 10.

If ${Adv}_A^{{Game}_k}-{Adv}_A^{{Game}_{k-\mathrm{1}}}\ge ϵ$ , then assumption 2 is broken.

Proof.

Given an instance ( $N,g_{\mathrm{1}},g_{\mathrm{3}},\mathbb{G},{\mathbb{G}}_T,X_{\mathrm{1}}{X}_{\mathrm{2}}{X}_{\mathrm{3}},Y_{\mathrm{1}}{Y}_{\mathrm{2}}$ , $(B_i{)}_{i\in \{\mathrm{0,1}\}}$ ) of assumption 2, $\mathfrak{C}$ constructs $\mathrm{M}\mathrm{P}\mathrm{K}$ as

$$\begin{array}{cc}& 〈g_{\mathrm{1}},g_{\mathrm{3}},g_{\mathrm{1}}^a,e{\left(g_{\mathrm{1}},g_{\mathrm{1}}\right)}^{\alpha },A_{\mathrm{1}}=u_{\mathrm{1}}{g}_{\mathrm{3}}^{y_{\mathrm{1}}},\dots ,A_U=u_U{g}_{\mathrm{3}}^{y_U}〉,\end{array}$$

(19)

where $a,\alpha ,y_{\mathrm{1}},\dots ,y_U\in {\mathbb{Z}}_N$ and $u_{\mathrm{1}},\dots ,u_U\in {\mathbb{G}}_{p_{\mathrm{3}}}$ . Consider $\mathrm{M}\mathrm{S}\mathrm{K}=g_{\mathrm{1}}^{\alpha }$ . In order to make the first $k-\mathrm{1}$ secret keys SF, the challenger $\mathfrak{C}$ randomly chooses $\beta \in {\mathbb{Z}}_N$ and implicitly sets $Y_{\mathrm{1}}=g_{\mathrm{1}}^{{\nu }_{\mathrm{1}}}$ and $Y_{\mathrm{2}}=g_{\mathrm{2}}^{{\nu }_{\mathrm{2}}}$ and responds to each key extraction query from $\mathfrak{A}$ on a set of attributes S as

$$\begin{array}{cc}& K_{\mathrm{1}}^{\prime }=g_{\mathrm{1}}^{\alpha }{\left(Y_{\mathrm{1}}{Y}_{\mathrm{2}}\right)}^{a\beta },\\ K_{\mathrm{2}}^{\prime }={\left(Y_{\mathrm{1}}{Y}_{\mathrm{2}}\right)}^{\beta }.\end{array}$$

(20)

This implicitly sets $z_{\mathrm{1}}=a{\nu }_{\mathrm{2}}\beta$ , $t={\nu }_{\mathrm{1}}\beta$ , and $z_{\mathrm{2}}={\nu }_{\mathrm{2}}\beta$ , so $K_{\mathrm{1}}^{\prime }$ , $K_{\mathrm{2}}^{\prime }$ are properly distributed as semifunctional secret key components.

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

For the kth key extraction query from $\mathfrak{A}$ , $\mathfrak{C}$ implicitly sets $g_{\mathrm{1}}^t$ as the ${\mathbb{G}}_{p_{\mathrm{1}}}$ part of B and sets the secret key as

$$\begin{array}{cc}& K_{\mathrm{1}}^{\prime }=g_{\mathrm{1}}^{\alpha }{B}^a,\\ K_{\mathrm{2}}^{\prime }=B.\end{array}$$

(21)

If $B\in {\mathbb{G}}_{p_{\mathrm{1}}}$ , then the secret key is distributed as normal secret key. If $B=g_{\mathrm{1}}^t{g}_{\mathrm{2}}^{z_{\mathrm{2}}}\in {\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ , then the secret key is properly distributed as semifunctional key.

In the challenge phase, $\mathfrak{A}$ provides the two challenge messages and two access policies as $({\mathcal{M}}_{\mathrm{0}},{\mathcal{M}}_{\mathrm{1}},(M_{\mathrm{0}},{\rho }_{\mathrm{0}}{)}^{\ast },(M_{\mathrm{1}},{\rho }_{\mathrm{1}}{)}^{\ast })$ . Then, $\mathfrak{C}$ randomly chooses $\mu \in \{\mathrm{0,1}\},b\in \{\mathrm{0,1}\}$ and values $t_{\mathrm{0}},t_{\mathrm{1}},\dots ,t_l,r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_N$ . In order to generate the SF ciphertext, $\mathfrak{C}$ implicitly sets $X_{\mathrm{1}}{X}_{\mathrm{2}}{X}_{\mathrm{3}}=g_{\mathrm{1}}^s{g}_{\mathrm{2}}^{\delta }{X}_{\mathrm{3}}\in \mathbb{G}$ and outputs $\mathrm{C}{\mathrm{T}}^{\ast }$ under access policy $(M_{\mu },{\rho }_{\mu }{)}^{\ast }$ as

$$\begin{array}{cc}& 〈{\mathcal{M}}_b·e\left(g_{\mathrm{1}}^{\alpha },X_{\mathrm{1}}{X}_{\mathrm{2}}{X}_{\mathrm{3}}\right),X_{\mathrm{1}}{X}_{\mathrm{2}}{X}_{\mathrm{3}}·g_{\mathrm{3}}^{t_{\mathrm{0}}},{\left({\left(X_{\mathrm{1}}{X}_{\mathrm{2}}{X}_{\mathrm{3}}\right)}^{a{\tilde{\lambda }}_i}{A}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{3}}^{-t_i},g_{\mathrm{1}}^{r_i}{g}_{\mathrm{3}}^{t_i}\right)}_{i\in \left[l\right]}〉.\end{array}$$

(22)

If $B\in {\mathbb{G}}_{p_{\mathrm{1}}}$ , then $\mathfrak{C}$ can simulate ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_{k-\mathrm{1}}$ , and if $B\in {\mathbb{G}}_{p_{\mathrm{1}}{p}_{\mathrm{2}}}$ , then $\mathfrak{C}$ can simulate ${\text{Game}}_k$ . Thus, if $\mathfrak{A}$ can distinguish between an SF secret key and a normal secret key with a nonnegligible probability, then $\mathfrak{C}$ can break assumption 2 by using the output of $\mathfrak{A}$ .

Lemma 11.

If ${Adv}_A^{{Game}_q}-{Adv}_A^{{Game}_{f^{\prime }}}\ge ϵ$ , then assumption 3 is broken.

Proof.

Given an instance ( $N,g_{\mathrm{1}},\mathbb{G},{\mathbb{G}}_T,g_{\mathrm{1}}^{\alpha }{X}_{\mathrm{2}},X_{\mathrm{3}},g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}},Z_{\mathrm{2}}$ , $(B_i{)}_{i\in \{\mathrm{0,1}\}}$ ) of assumption 3, $\mathfrak{C}$ constructs $\mathrm{M}\mathrm{P}\mathrm{K}$ as

$$\begin{array}{cc}& 〈g_{\mathrm{1}},g_{\mathrm{3}},g_{\mathrm{1}}^a,e\left(g_{\mathrm{1}}^{\alpha }{X}_{\mathrm{2}},g_{\mathrm{1}}\right),A_{\mathrm{1}}=u_{\mathrm{1}}{g}_{\mathrm{3}}^{y_{\mathrm{1}}},\dots ,A_U=u_U{g}_{\mathrm{3}}^{y_U}〉,\end{array}$$

(23)

where $a,y_{\mathrm{1}},\dots ,y_U\in {\mathbb{Z}}_N$ and $u_{\mathrm{1}},\dots ,u_U\in {\mathbb{G}}_{p_{\mathrm{3}}}$ . In order to make the secret keys SF, the challenger $\mathfrak{C}$ randomly chooses $t,\kappa \in {\mathbb{Z}}_N$ and responds to each key extraction query from $\mathfrak{A}$ on a set of attributes S as

$$\begin{array}{cc}& K_{\mathrm{1}}^{\prime }=g_{\mathrm{1}}^{\alpha }{X}_{\mathrm{2}}{\left(g_{\mathrm{1}}^t{Z}_{\mathrm{2}}\right)}^a,\\ K_{\mathrm{2}}^{\prime }=g_{\mathrm{1}}^t{Z}_{\mathrm{2}}^{\kappa }.\end{array}$$

(24)

This implicitly sets $X_{\mathrm{2}}=g_{\mathrm{2}}^{a{z}_{\mathrm{2}}(\mathrm{1}-\mathrm{1}/\kappa )}$ and $Z_{\mathrm{2}}=g_{\mathrm{2}}^{z_{\mathrm{2}}/\kappa }.$ So $K_{\mathrm{1}}^{\prime }$ , $K_{\mathrm{2}}^{\prime }$ are properly distributed as SF secret key components.

In the challenge phase, $\mathfrak{A}$ provides the two challenge messages and two access policies as $({\mathcal{M}}_{\mathrm{0}},{\mathcal{M}}_{\mathrm{1}},(M_{\mathrm{0}},{\rho }_{\mathrm{0}}{)}^{\ast },(M_{\mathrm{1}},{\rho }_{\mathrm{1}}{)}^{\ast })$ . Then, $\mathfrak{C}$ randomly chooses $b\in \{\mathrm{0,1}\}$ and values $t_{\mathrm{0}},t_{\mathrm{1}},\dots ,t_l,r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_N$ . In order to generate the SF ciphertext, $\mathfrak{C}$ implicitly sets $g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}}=g_{\mathrm{1}}^s{g}_{\mathrm{2}}^{\delta }{Y}_{\mathrm{3}}\in \mathbb{G}$ and outputs $\mathrm{C}{\mathrm{T}}^{\ast }$ under access policy $(M_b,{\rho }_b{)}^{\ast }$ as

$$\begin{array}{cc}& 〈{\mathcal{M}}_b·B,g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}}·g_{\mathrm{3}}^{t_{\mathrm{0}}},{\left({\left(g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}}\right)}^{a{\tilde{\lambda }}_i}{A}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{3}}^{-t_i},g_{\mathrm{1}}^{r_i}{g}_{\mathrm{3}}^{t_i}\right)}_{i\in \left[l\right]}〉.\end{array}$$

(25)

If $B=e(g_{\mathrm{1}},g_{\mathrm{1}}{)}^{\alpha s}$ , then $\mathfrak{C}$ can simulate ${\text{Game}}_q$ , since $\mathrm{C}{\mathrm{T}}^{\ast }$ is distributed SF encryption of ${\mathcal{M}}_b$ . If B is a random element in $\mathbb{G}$ , then $\mathfrak{C}$ can simulate ${\mathrm{G}\mathrm{a}\mathrm{m}\mathrm{e}}_{f^{\prime }}$ , since $\mathrm{C}{\mathrm{T}}^{\ast }$ is distributed SF encryption of a random element. Thus, $\mathfrak{C}$ can can break assumption 3 by using the output of $\mathfrak{A}$ .

Lemma 12.

If ${Adv}_A^{{Game}_{f^{\prime }}}-{Adv}_A^{{Game}_f}\ge ϵ$ , then assumption 4 is broken.

Proof.

Given an instance ( $N,\mathbb{G},{\mathbb{G}}_T,g_{\mathrm{1}}{X}_{\mathrm{3}},g_{\mathrm{1}}^s{Z}_{\mathrm{3}},g_{\mathrm{1}}{X}_{\mathrm{2}},Z_{\mathrm{2}},g_{\mathrm{3}}$ , $(B_i{)}_{i\in \{\mathrm{0,1}\}}$ ) of assumption 4, $\mathfrak{C}$ constructs $\mathrm{M}\mathrm{P}\mathrm{K}$ as

$$\begin{array}{cc}& 〈g_{\mathrm{1}}{X}_{\mathrm{2}},g_{\mathrm{3}},g_{\mathrm{1}}{X}_{\mathrm{3}},{\left(g_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^a,e\left({\left(g_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{\alpha },g_{\mathrm{1}}{X}_{\mathrm{3}}\right),A_{\mathrm{1}}=u_{\mathrm{1}}{g}_{\mathrm{3}}^{y_{\mathrm{1}}},\dots ,A_U=u_U{g}_{\mathrm{3}}^{y_U}〉,\end{array}$$

(26)

where $a,\alpha ,y_{\mathrm{1}},\dots ,y_U\in {\mathbb{Z}}_N$ and $u_{\mathrm{1}},\dots ,u_U\in {\mathbb{G}}_{p_{\mathrm{3}}}$ . Consider $\mathrm{M}\mathrm{S}\mathrm{K}=(g_{\mathrm{1}}{X}_{\mathrm{2}}{)}^{\alpha }$ . In order to make the secret keys SF, the challenger $\mathfrak{C}$ randomly chooses $t\in {\mathbb{Z}}_N$ and responds to each key extraction query from $\mathfrak{A}$ on a set of attributes S as

$$\begin{array}{cc}& K_{\mathrm{1}}^{\prime }={\left(g_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{\alpha }{\left(g_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^{at},\\ K_{\mathrm{2}}^{\prime }={\left(g_{\mathrm{1}}{X}_{\mathrm{2}}\right)}^t.\end{array}$$

(27)

If $X_{\mathrm{2}}=g_{\mathrm{2}}^l$ , then this implicitly sets $z_{\mathrm{1}}=\alpha l(\mathrm{1}+t),z_{\mathrm{2}}=lt.$ So $K_{\mathrm{1}}^{\prime }$ , $K_{\mathrm{2}}^{\prime }$ are properly distributed as SF secret key components.

In the challenge phase, $\mathfrak{A}$ provides the two challenge messages and two access policies as $({\mathcal{M}}_{\mathrm{0}},{\mathcal{M}}_{\mathrm{1}},(M_{\mathrm{0}},{\rho }_{\mathrm{0}}{)}^{\ast },(M_{\mathrm{1}},{\rho }_{\mathrm{1}}{)}^{\ast })$ . Then, $\mathfrak{C}$ randomly chooses $b\in \{\mathrm{0,1}\}$ and values $t_{\mathrm{0}},t_{\mathrm{1}},\dots ,t_l,r_{\mathrm{1}},\dots ,r_l\in {\mathbb{Z}}_N$ . In order to generate the SF ciphertext, $\mathfrak{C}$ randomly chooses an element $\Delta \in {\mathbb{G}}_T$ and outputs $\mathrm{C}{\mathrm{T}}^{\ast }$ under access policy $(M_b,{\rho }_b{)}^{\ast }$ as

$$\begin{array}{cc}& 〈\Delta ,\left(g_{\mathrm{1}}^s{Z}_{\mathrm{3}}\right)Z_{\mathrm{2}}{g}_{\mathrm{3}}^{t_{\mathrm{0}}},{\left({\left(B\right)}^{a{\tilde{\lambda }}_i}{A}_{\rho \left(i\right)}^{-r_i}{g}_{\mathrm{3}}^{-t_i},g_{\mathrm{1}}^{r_i}{g}_{\mathrm{3}}^{t_i}\right)}_{i\in \left[l\right]}〉.\end{array}$$

(28)

This implicitly sets $Z_{\mathrm{2}}=g_{\mathrm{2}}^{\delta }$ .

If $B=g_{\mathrm{1}}^s{Y}_{\mathrm{2}}{Y}_{\mathrm{3}}$ , then $\mathfrak{C}$ can simulate ${\text{Game}}_{f^{\prime }}$ , since $\mathrm{C}{\mathrm{T}}^{\ast }$ is distributed SF encryption of a random element in ${\mathbb{G}}_T$ . If B is a random element in $\mathbb{G}$ , then $\mathfrak{C}$ can simulate ${\text{Game}}_f$ , since $\mathrm{C}{\mathrm{T}}^{\ast }$ is distributed SF encryption of a random element in ${\mathbb{G}}_T$ with $T_i$ being random in $\mathbb{G}$ . Thus, $\mathfrak{C}$ can can break assumption 4 by using the output of $\mathfrak{A}$ .

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