# Black Box Traceable Ciphertext Policy Attribute-Based Encryption Scheme

^{1}

^{2}

^{*}

*Keywords:*black box; CP-ABE; oblivious transfer; private key generator; tracing

Next Article in Journal

Previous Article in Journal

School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China

School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 611731, China

Author to whom correspondence should be addressed.

Academic Editor: Willy Susilo

Received: 9 June 2015
/
Revised: 5 August 2015
/
Accepted: 5 August 2015
/
Published: 14 August 2015

In the existing attribute-based encryption (ABE) scheme, the authority (i.e., private key generator (PKG)) is able to calculate and issue any user’s private key, which makes it completely trusted, which severely influences the applications of the ABE scheme. To mitigate this problem, we propose the black box traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme in which if the PKG re-distributes the users’ private keys for malicious uses, it might be caught and sued. We provide a construction to realize the T-CP-ABE scheme in a black box model. Our scheme is based on the decisional bilinear Diffie-Hellman (DBDH) assumption in the standard model. In our scheme, we employ a pair (ID, S) to identify a user, where ID denotes the identity of a user and S denotes the attribute set associated with her.

With the advent of cloud computing, more and more data and computations will be migrated to the cloud. Storing the data in the cloud has advantages as follows: individuals can reliably store the data and can easily and conveniently access the data; and organizations can save costs. However, when the data are stored remotely, acute concerns for security and privacy are raised. That is to say the sensitive data, such as financial and medical records, are out of the owners’ control and may be accessed by untrusted parties. A traditional public key cryptosystem cannot be employed to protect the data well, since they have drawbacks as follows: (1) they only provide coarse-grained access to encrypted data decrypted only by a single secret key; (2) access to the encrypted data is all or nothing; one can either decrypt to recover the entire ciphertext or learns nothing from the plaintext, except for its length. In the cloud computing system, the data owner may share the data with groups of data consumers based on their attributes or credentials, and only the data consumers whose attributes satisfy the access policy can decrypt. The traditional public key cryptosystem cannot address these problems [1,2].

To address these problems, Sahai et al. [3] first presented the attribute-based encryption (ABE) scheme enforcing fine-grained access control over the ciphertexts. In their scheme, a ciphertext and a private key are associated with descriptive attribute sets. Decryption will succeed if and only if there exist at least d attributes overlapping them. Their scheme is suitable for error-tolerant encryption. However, one drawback of their scheme is that this construction is only able to address formulae comprising one threshold gate. To enhance the expressiveness, Goyal et al. [4] presented the key policy attribute-based encryption (KP-ABE) scheme in which ciphertexts are associated with attribute sets and the private keys are associated with access structures. While they proposed the CP-ABE scheme, they did not implement it. Bethencourt et al. [5] first implemented the CP-ABE scheme. In their scheme, attribute sets are employed to identify the private keys, and ciphertexts are associated with access structures. The ciphertexts are decrypted by the private keys iff the access structures are satisfied by the attribute sets. However, they proved security in the generic group model. To achieve CP-ABE schemes in the standard model, work has been done as follows: Cheung et al. [6] presented a CP-ABE scheme constructed under a policy with an AND gate. However, their scheme requires that the number of system attributes be fixed at setup, and the access structure of their scheme only supports an AND gate. These two drawbacks make it less expressive. To enhance the expressiveness, Goyal et al. [7] proposed the bounded CP-ABE scheme. However, the encryption and decryption cost blows up greatly, which influences its application in practice. Lewko et al. [8] presented a CP-ABE scheme that is expressive and adaptively secure. However, their scheme is based on a composite order bilinear group, which incurs some efficiency loss, and the assumption is a non-standard strong assumption. Waters [9] proposed an expressive, efficient and provable secure CP-ABE scheme in the standard model and achieves the same performance and functionality as the scheme of [5]. Researchers applied CP-ABE schemes to a cloud storage system, social networks, etc.

In a CP-ABE scheme, a private key for a user’s attributes is not able to be generated by herself. Hence, there exists a trusted party, named the authority, i.e., the private key generator (PKG), which sets up the system. To get a private key from the PKG, a user with some attributes will go to a PKG to get the private key associated with her attributes. During this process, she needs to prove to the PKG that these attributes are entitled to her. Then, the private key is generated and passed on to her by the PKG. Since the authority possesses the master secret of the scheme, it is capable of calculating the private key associated with the users’ arbitrary attributes, and it is able to decrypt any ciphertexts encrypted to any users; it has to be absolutely trusted. If the authority engages in malicious activities, it will not be caught and sued. Thus, it is required that the trust in the authority should be reduced in a CP-ABE scheme. That is to say, there still exists the key escrow problems in the CP-ABE scheme. Due to the inherent key escrow problem, the CP-ABE scheme is restricted to be used in the small and closed groups, where there exists a central trusted authority. If this problem is not solved well, it will influence the adoption of the CP-ABE scheme.

Our contributions: We formalize the conception of the black box traceable ciphertext policy attribute-based encryption scheme and propose its construction. This construction builds on the ciphertext policy attribute-based encryption scheme presented by [9]. In this scheme, a secure private key generation protocol is constructed. A new security proof is presented to show that this scheme is a traceable (T)-CP-ABE scheme, which handles black box decoders. In this T-CP-ABE scheme, the authority will access decryption oracles, and a judge will decide whether the decoder box is created by the malicious authority or the malicious user.

Organization: The remainder of our paper is organized as follows. Preliminaries are presented in Section 2. The scheme definition and the definition of the security game are presented in Section 3. The scheme construction is presented in Section 4. Security is proven in Section 5. Related works are discussed in Section 6. We make a conclusion and specify future work in Section 7.

Let 𝔾 and ${\text{\mathbb{G}}}_{T}$ be two cyclic groups whose orders are prime order p, respectively. $g,u$ are a generator of 𝔾, respectively. e is a bilinear map $e:\text{\mathbb{G}}\times \text{\mathbb{G}}\to {\text{\mathbb{G}}}_{T}$, which has properties as follows. Bilinearity: for any $a,b\in {\text{\mathbb{Z}}}_{p}$, $e({g}^{a},{u}^{b})=e{(g,u)}^{ab}$. Nondegenerate: $e(g,g)\ne {1}_{{\text{\mathbb{G}}}_{T}}$, $e(g,g)$ is a generator of ${\text{\mathbb{G}}}_{T}$. If the group operations on 𝔾 and on the bilinear map $e:\text{\mathbb{G}}\times \text{\mathbb{G}}\to {\text{\mathbb{G}}}_{T}$ are efficiently computable, then 𝔾 is a bilinear group. In our scheme, the symmetric bilinear map is employed, such that: $e({g}^{a},{u}^{b})=e{(g,u)}^{ab}=e({g}^{b},{u}^{a}).$

Let 𝕊 be the universe of attributes. An access structure [10] on 𝕊 is a collection 𝔸 of non-empty subsets of attributes, i.e., $\text{\mathbb{A}}\subseteq {2}^{\text{\mathbb{S}}}\setminus \left\{\right\}$. We call the sets in 𝔸 the authorized attribute sets and the sets not in 𝔸 the unauthorized attribute sets. Specifically, an access structure is monotone if $\forall B,C$: if $B\in \text{\mathbb{A}}$ and $B\subseteq C$, then $C\in \text{\mathbb{A}}$. In this scheme, only the monotone access structure is handled.

A secret sharing scheme [10] Π over the attribute set is called linear over ${\text{\mathbb{Z}}}_{p}$ if .1. The shares for each attribute of a secret form a vector over ${\text{\mathbb{Z}}}_{p}$ .2. There is a matrix M with h rows and c columns for Π. For any $i=1,\cdots ,h$, let the function φ defined the attribute that labels the i-th row as $\phi \left(i\right)$. Given the column vector $\overrightarrow{v}={(s,{x}_{2},\cdots ,{x}_{n})}^{T}$, in which T is the transpose of the vector $\overrightarrow{v}$, s is the secret that will be shared and ${x}_{2},\cdots ,{x}_{n}\in {\text{\mathbb{Z}}}_{p}$ are uniformly picked at random, then $M\overrightarrow{v}$ is the vector of h shares of the secret s based on Π. The share ${\left(M\overrightarrow{v}\right)}_{i}$ belongs to the attribute $\phi \left(i\right)$.

Let attribute set $S\in \text{\mathbb{A}}\bigwedge S\in \text{\mathbb{S}}$ be any authorized attribute set, and let $I=\left\{i\right|i\in \{1,\cdots ,h\}\bigwedge \phi \left(i\right)\in S\}$. Then, there exist constants ${\{{\eta}_{i}\in {\text{\mathbb{Z}}}_{p}\}}_{i\in I}$, such that, if ${\left\{{s}_{i}\right\}}_{i\in I}$ are valid shares of a secret s according to Π, then ${\Pi}_{i\in I}{\eta}_{i}{s}_{i}=s$.

Decisional bilinear Diffie-Hellman (DBDH): Let $\mathcal{G}\left({1}^{\kappa}\right)\to (p,g,\text{\mathbb{G}},{\text{\mathbb{G}}}_{T},e)$. Pick $\xi ,\varpi ,\rho ,d\in {\text{\mathbb{Z}}}_{p}$ uniformly at random. No probabilistic polynomial time (PPT) attackers 𝓐 are able to distinguish the tuple $(A={g}^{\xi},B={g}^{\varpi},C={g}^{\rho},D=e{(g,g)}^{\xi \varpi \rho})$ from the tuple $(A={g}^{\xi},B={g}^{\varpi},C={g}^{\rho},D=e{(g,g)}^{d})$ with non-negligible advantages.

A k-out-of-N oblivious transfer protocol makes a recipient pick and receive exactly k of the N messages from the sender, such that the remaining messages are hidden from the recipient and the choices of the recipient are hidden from the sender. We employ fully-simulatable oblivious transfer [11].

Waters [9] proposed the ciphertext policy attribute-based encryption (CP-ABE) scheme, which is expressive, efficient and provably secure. In this scheme, ciphertexts are associated with access structures, and private keys are associated with attribute sets. They proposed a CP-ABE scheme, which is proven secure in the DBDH assumption in the standard model. Our scheme in part builds on this scheme.

$\mathit{Setup}\left({1}^{k}\right)\to (\mathit{MSK},\mathit{PP}):$ The **Setup** algorithm takes in a security parameter κ, and it returns a master secret key MSK and the public parameters PP.

$\mathit{PriKeyGen}(\mathit{PP},\mathit{MSK},\mathit{ID},S)(\to ){K}_{ID,S}:$ This is a private key generation algorithm, which takes in PP,MSK, S and ID employed to trace back to the corresponding owner and the Authority engages in an oblivious transfer protocol with a user U, where S is an attribute set belonging to the user U. At the end, U receives a private key for her ID and her attribute set S, ${K}_{(ID,S)}$. The notation $(\to )$ denotes the fact that the authority may not exactly know which key the user has received.

$\mathit{Encrypt}(\mathit{PP},\mathit{ID},\text{\mathbb{A}},m)\to {\mathit{CT}}_{\mathit{ID},\text{\mathbb{A}}}$: The **Encrypt** algorithm takes in the public parameters PP, the identity ID, access structure 𝔸 and a message m and it returns a ciphertext ${\mathit{CT}}_{\mathit{ID},\text{\mathbb{A}}}$.

$\mathit{Decrypt}(\mathit{PP},{\mathit{CT}}_{\mathit{ID},\text{\mathbb{A}}},{K}_{ID,S})\to m$: The **Decrypt** algorithm takes in the public parameters PP, the ciphertext ${\mathit{CT}}_{\mathit{ID},\text{\mathbb{A}}}$ and a private key ${K}_{ID,S}$. It returns a plaintext message m if the identity of the private key matches that of the ciphertext and the attribute set S satisfies the access structure 𝔸, else it returns an error symbol ⊥.

${\mathit{Trace}}^{\mathit{\mathcal{D}}}(\mathit{PP},\mathit{ID},{K}_{ID,S},\epsilon )\to \{\mathit{User},\mathit{Authority}\}$: The **Trace** algorithm takes in the identity ID, the public parameters PP, a well-formed private key ${K}_{ID,S}$, a parameter ε and has black box access to a ε useful decoder box $\mathcal{D}$. It outputs User or Authority.

The tracing algorithm allows an honest user to present her private key and a captured decoder box to a judge to incriminate the misfeasance of Authority; furthermore, the tracing algorithm hinders a dishonest user from falsely incriminating that the Authority has created the decoder box.

A secure black box traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme holds if the following three requirements are met: (1) it satisfies **IND-ID-CCA** security; (2) if the Authority created a decoder box $\mathcal{D}$, the tracing algorithm should incriminate the Authority; (3) if the colluding users created the decoder box $\mathcal{D}$, it should incriminate these users. We capture the security conditions in the three games as follows:

$$|Pr[{\beta}^{\prime}=\beta ]-\frac{1}{2}|$$

The above game can be extended to obtain security against chosen ciphertext attacks where decryption oracles are allowed for in **Phase 1** and **Phase 2**. Such a game is called the **IND-ID-CCA** security game.

A ciphertext has a structure as follows: (ID,${\text{\mathbb{A}}}_{1},\cdots ,{\text{\mathbb{A}}}_{Z}$), where ID is the identity of the user and ${\text{\mathbb{A}}}_{1},\cdots ,{\text{\mathbb{A}}}_{Z}$ are Z (where Z is a positive integer) parallel repetitions, each comprising monotone access structure ${\text{\mathbb{A}}}_{z}(1\le z\le Z)$. A private key has a structure as follows: (ID,${S}_{1},\cdots ,{S}_{Z}$), where each ${S}_{z}(1\le z\le Z)$ comprises k out of N attributes. A ciphertext can be decrypted by a user U iff (the ID of the private key matches that of the ciphertext) AND (${S}_{1}$ satisfies monotone access structure ${\text{\mathbb{A}}}_{1}$) AND⋯ AND (${S}_{Z}$ satisfies monotone access structure ${\text{\mathbb{A}}}_{Z}$). Let L be the length of bits of the identity string ID $\in {\text{\mathbb{Z}}}_{p}$, N the global security parameter, Z super-logarithmic in N, ${C}_{max}$ the maximum number of columns of the matrix M and ${\mathrm{ID}}_{j}$ the j-th bit of the identity ID $\in {\text{\mathbb{Z}}}_{p}$. Let $\left[L\right]$, $\left[N\right]$, $\left[{C}_{max}\right]$ and $\left[Z\right]$ be the sets $\{1,\cdots ,L\}$, $\{1,\cdots ,N\}$, $\{1,\cdots ,{C}_{max}\}$ and $\{1,\cdots ,Z\}$, respectively.

$\mathbf{Setup}:$ For each $j\in \left[L\right]$, pick two random elements ${\omega}_{j,0}$ and ${\omega}_{j,1}$ from ${\text{\mathbb{Z}}}_{p}$ with the restriction that these $2L$ values are all different. For each $c\in \left[{C}_{max}\right]$, $j\in \left[N\right]$ and $z\in \left[Z\right]$, pick a random ${t}_{c,j,z}$ uniformly from ${\text{\mathbb{Z}}}_{p}$. Pick two random elements $\mu ,\theta \in {\text{\mathbb{Z}}}_{p}$ uniformly. The public parameters are:

$$\begin{array}{c}PP=(\{{W}_{j,z}={g}^{{\omega}_{j,z}}:j\in \left[L\right],z\in \{0,1\}\}\hfill \\ \{{T}_{c,j,z}={g}^{{t}_{c,j,z}}:c\in \left[{C}_{max}\right],j\in \left[N\right],z\in \left[Z\right]\},U=e{(g,g)}^{\mu},g,{g}^{\theta}).\hfill \end{array}$$

The master secret key $MSK=(\{{\omega}_{j,z}:j\in \left[L\right],z\in \{0,1\}\},\{{t}_{c,j,z}:c\in \left[{C}_{max}\right],j\in \left[N\right],z\in \left[Z\right]\},\mu )$.

$\mathbf{PriKeyGen}:$ This protocol enables a user U to obliviously pick which attributes she needs, employing a k-out-of-N oblivious transfer protocol upon each repetition. The corresponding same index in each repetition has distinct attributes. Distinct attributes correspond to distinct elements in ${\text{\mathbb{Z}}}_{p}$. The repetitions are conducted in parallel and are viewed as individual components of the private key.

The private key generation protocol between the **Authority** and a user U is performed as follows:

Step 1. The user will abort if ${W}_{j,z}$ and ${T}_{c,j,z}$ are not all different.

Step 2. The **Authority** picks $Z+1$ elements ${\mu}_{0},\cdots ,{\mu}_{Z}\in {\text{\mathbb{Z}}}_{p}$ uniformly at random with the restriction that ${\mu}_{0}+\cdots +{\mu}_{Z}=\mu $, where ${\mu}_{0}$ is associated with the identity and ${\mu}_{1},\cdots ,{\mu}_{Z}$ are associated with the sets of attributes.

Step 3. The **Authority** picks L elements ${\nu}_{1},\cdots ,{\nu}_{L}\in {\text{\mathbb{Z}}}_{p}$ uniformly at random with the restriction that ${\nu}_{1}+\cdots +{\nu}_{L}={\mu}_{0}$.

Step 4. The **Authority** picks ${r}_{c,z},{\mu}_{z}\in {\text{\mathbb{Z}}}_{p}:c\in \left[{C}_{max}\right],z\in \left[Z\right]$ uniformly at random with the restriction that ${\mu}_{1}+\cdots +{\mu}_{Z}=\mu -{\mu}_{0}$.

Step 5. The **Authority** calculates the private key components ${K}_{j}={g}^{{\nu}_{j}/{\omega}_{j,I{D}_{j}}}$ for any $j\in \left[L\right]$ and passes them on to the user U. It picks elements ${r}_{c,z}\in {\text{\mathbb{Z}}}_{p}:c\in \left[{C}_{max}\right],z\in \left[Z\right]$ uniformly at random, calculates the private key components ({${K}_{b,z}={g}^{{\mu}_{z}}{g}^{\theta {r}_{1,z}},{D}_{c,z}={g}^{{r}_{c,z}}:c\in \left[{C}_{max}\right],z\in \left[Z\right]\},\{\forall j\in {S}_{z},{K}_{j,z}={\prod}_{c\in \left[{C}_{max}\right]}{T}_{c,j,z}^{{r}_{c,z}}:c\in \left[{C}_{max}\right],j\in \left[N\right],z\in \left[Z\right]\}$), sends {${K}_{b,z},{D}_{c,z}$} to the user U and stores ${K}_{j,z}$.

Step 6. The **Authority** picks permutations $\text{\mathcal{P}}=({P}_{1},\cdots ,{P}_{Z})\in {S}_{N}^{Z}$ at random.

Step 7. The **Authority** and the user U conduct Z executions of a k-out-of-N oblivious transfer protocol in which the **Authority** is a sender and the user U is a receiver. In the z-th execution, the private input of the **Authority** is the private key components ${\left\{{K}_{{P}_{z}\left(j\right),z}\right\}}_{j=1}^{N}$, and the private input of the user U is a set ${S}_{z}$ of k attributes picked at random. The private output of the user is the private key component ${\{{P}_{z}\left(j\right),{K}_{{P}_{z}\left(j\right),z}\}}_{j\in {S}_{z}}$

Step 8. The **Authority** passes the permutation list $\mathcal{P}$ to the user U. The user U checks whether she obtains the correct private key components as a percent $\mathcal{P}$. If not, it will abort.

Step 9. The user U sets ${K}_{ID,S}^{\prime}=({\left\{{K}_{j}\right\}}_{j\in \left[L\right]},\{{K}_{b,z}={g}^{{\mu}_{z}}{g}^{\theta {r}_{1,z}},{D}_{c,z}={g}^{{r}_{c,z}}:c\in \left[{C}_{max}\right],z\in \left[Z\right]\},{\{\left({S}_{z}\right),{\left\{{K}_{j,z}\right\}}_{j\in {S}_{z}}\}}_{z\in \left[Z\right]})$ and checks whether a private key validity check on ${K}_{ID,S}^{\prime}$ passes. If not, the user U will abort.

Step 1.

$$e({K}_{b,z},g)\xb7e{({g}^{\theta},{D}_{1,z})}^{-1}=e({g}^{{\mu}_{z}}{g}^{\theta {r}_{1,z}},g)\xb7e{({g}^{\theta},{g}^{{r}_{1,z}})}^{-1}=e({g}^{{\mu}_{z}},g)=e{(g,g)}^{{\mu}_{z}}$$

Step 2. Check whether $e{(g,g)}^{\mu}={\prod}_{j\in \left[L\right]}e({W}_{j,z},{K}_{j}){\prod}_{z\in \left[Z\right]}e{(g,g)}^{{\mu}_{z}}$ and $\forall j\in {S}_{z}$, $e({K}_{j,z},g)=e({T}_{c,j,z},{\prod}_{c\in \left[{C}_{max}\right]}{D}_{c,z})$ holds. If not, it fails. If so, the private key validity check passed, and the user U sets ${K}_{ID,S}={K}_{ID,S}^{\prime}$.

$\mathbf{Encrypt}:$ The encryption algorithm takes in $PP$, a message $m\in {G}_{T}$ and an LSSS access structure ${\text{\mathbb{A}}}_{z}=({M}_{z},{\phi}_{z}):z\in \left[Z\right]$, where ${\phi}_{z}$ associates rows of ${M}_{z}$ to attributes and ${\phi}_{z}$ is an injective function. Let ${M}_{z}$ denote an $h\times {C}_{max}$ matrix. This algorithm picks a random vector ${\overrightarrow{v}}_{z}=(s,{y}_{2,z},\cdots ,{y}_{{C}_{max},z})$ employed to share the encryption exponent $s\in {\text{\mathbb{Z}}}_{p}$. The ciphertext ${\mathrm{CT}}_{\mathrm{ID},\text{\mathbb{A}}}^{\prime}$ is constructed as follows:

$$\begin{array}{c}{\mathrm{CT}}_{\mathrm{ID},\text{\mathbb{A}}}^{\prime}=({\left\{{\text{\mathbb{A}}}_{z}\right\}}_{z\in \left[Z\right]},E=m\xb7e{(g,g)}^{\mu s},{E}_{b,z}={g}^{s},\left\{({E}_{j}={W}_{j,I{D}_{j}}^{s}\}\right):j\in \left[L\right]\},\hfill \\ \{{E}_{i,c,z}={g}^{\theta {M}_{i,c,z}{v}_{c,z}}{T}_{c,j,z}^{-s}:i\in \{1,\cdots ,h\},c\in \left[{C}_{max}\right],j\in {S}_{z},z\in \left[Z\right]\})\hfill \end{array}$$

$\mathbf{Decrypt}:$ The **Decrypt** algorithm takes in the public parameters PP, the well-formed ${\mathrm{CT}}_{\mathrm{ID},\text{\mathbb{A}}}$ and ${K}_{ID,S}$. If the identity of the private key matches that of the ciphertext and the attribute sets ${S}_{z}$ of the private keys satisfy the access structures ${\text{\mathbb{A}}}_{z}$ of the ciphertexts, then there exist coefficients ${\eta}_{i,z}\in {\text{\mathbb{Z}}}_{p}$, such that ${\sum}_{\phi \left(i\right)\in {S}_{z}}{\eta}_{i,z}\xb7{\overrightarrow{M}}_{i,z}=(1,0,\cdots ,0)$; the ciphertext is decrypted to recover the message m as follows:

$$\begin{array}{l}\hspace{1em}E/{\prod}_{j\in \left[L\right]}e({E}_{j},{K}_{j}){\prod}_{z\in \left[Z\right]}\{e({E}_{b,z},{K}_{b,z})/{\prod}_{c\in \left[{C}_{max}\right]}e{({D}_{c,z},{\prod}_{\phi \left(i\right)\in {S}_{z}}{E}_{i,c,z})}^{{\eta}_{i,z}}{\prod}_{\phi \left(i\right)\in {S}_{z}}e{({K}_{j,z},{E}_{b,z})}^{{\eta}_{i,z}}\}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/{\prod}_{j\in \left[L\right]}e({W}_{j,I{D}_{j}}^{s},{g}^{{\nu}_{j}/{\omega}_{j,I{D}_{j}}})\xb7{\prod}_{z\in \left[Z\right]}\hfill \\ \hspace{1em}\{e({E}_{b,z},{K}_{b,z})/{\prod}_{c\in \left[{C}_{max}\right]}e{({g}^{{r}_{c,z}},{\prod}_{\phi \left(i\right)\in {S}_{z}}{g}^{\theta {M}_{i,c,z}{v}_{c,z}}{T}_{c,j,z}^{-s})}^{{\eta}_{i,z}}{\prod}_{\phi \left(i\right)\in {S}_{z}}e{({\prod}_{c\in \left[{C}_{max}\right]}{T}_{c,j,z}^{{r}_{c,z}},{g}^{s})}^{{\eta}_{i,z}}\}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/e{(g,g)}^{{\mu}_{0}s}{\prod}_{z\in \left[Z\right]}\{e({E}_{b,z},{K}_{b,z})/{\prod}_{c\in \left[{C}_{max}\right]}e{({g}^{{r}_{c,z}},{\prod}_{\phi \left(i\right)\in {S}_{z}}{g}^{\theta {M}_{i,c,z}{v}_{c,z}})}^{{\eta}_{i,z}}\}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/e{(g,g)}^{{\mu}_{0}s}{\prod}_{z\in \left[Z\right]}\{e({E}_{b,z},{K}_{b,z})/e{({g}^{{r}_{1,z}},{\prod}_{\phi \left(i\right)\in {S}_{z}}{g}^{\theta {M}_{i,1,z}{v}_{1,z}})}^{{\eta}_{i,z}}\}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/e{(g,g)}^{{\mu}_{0}s}{\prod}_{z\in \left[Z\right]}\{e({g}^{s},{g}^{{\mu}_{z}}{g}^{\theta {r}_{1,z}})/e({g}^{{r}_{1,z}},{g}^{\theta s})\}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/e{(g,g)}^{{\mu}_{0}s}e{(g,g)}^{({\mu}_{1}+\cdots +{\mu}_{Z})s}\hfill \\ =m\xb7e{(g,g)}^{\mu s}/e{(g,g)}^{\mu s}\hfill \\ =m\hfill \end{array}$$

$\mathbf{Trace}:$ The tracing algorithm runs a **Key Validity Check** to check whether the private key is well formed. It repeats the experiments $poly\left(\kappa \right)$ times as follows:

Pick a set of attributes ${S}_{z}$ with the restriction with ${S}_{z}$ not satisfying the access structure ${\text{\mathbb{A}}}_{z}$.

Pick a message m at random and encrypt m using the access structure ${\text{\mathbb{A}}}_{z}$.

The decoder box returns some message ${m}^{\star}=D\left(C{T}_{ID,\text{\mathbb{A}}}\right)$.

For any iteration, if ${m}^{\star}=m$, incriminate the **Authority**, else incriminate the user U.

The security of the aforementioned scheme is proven as follows:

This theorem is trivially reduced to the **IND-ID-CCA** security of [9] and [12]. If an attacker breaks the **IND-ID-CCA** security of our scheme, it is trivial to construct an attacker breaking the **IND-ID-CCA** security of Naccache’s scheme [12] and Waters’s scheme [9]. For any message m, it is a secret shared with ${m}_{1}\oplus {m}_{2}$ in which a random ${m}_{1}$ is picked uniformly and encrypted with the CP-ABE scheme [9] and ${m}_{2}$ with Naccache’s IBE scheme [12] to achieve the T-CP-ABE scheme under the DBDH assumption.

Let $\mathcal{D}$ be a ε useful decoder box, where ε is non-negligible. Perform the experiment as follows:

Pick a set of attributes ${S}_{z}$, except that ${S}_{z}$ does not satisfy the access structure ${\text{\mathbb{A}}}_{z}$.

Pick a message m at random; encrypt it employing the access structure ${\text{\mathbb{A}}}_{z}$, and this returns the resulting ciphertext ${\mathrm{CT}}_{\mathrm{ID},\text{\mathbb{A}}}$.

The decoder box returns ${m}^{\star}=\mathcal{D}\left({\mathrm{CT}}_{\mathrm{ID},\text{\mathbb{A}}}\right)$.

Return the **Authority** if ${m}^{\star}=m$. □

To mitigate the trust on the PKG, Boneh et al. [13] proposed an approach that has the multiple PKGs distributed based on threshold cryptography. However, their scheme brings about extra infrastructure and communication. Without employing multiple PKGs, the known mitigation approaches are as follows: Goyal [14] presented a traceable identity based encryption scheme. To obtain black box security, Libert et al. [15] presented an IBE scheme, which is weak black box traceable, while ciphertexts and private keys are short, and Goyal et al. [16] proposed the black box traceable IBE scheme. Both schemes are selectively secure. To enhance the security, Libert et al. [15] proposed the fully-secure traceable IBE scheme. Since ABE schemes are the generalizations of IBE schemes, they inherit the key escrow problem from IBE schemes. Some traceable CP-ABE schemes [17] have been presented to handle this problem. Unfortunately, the access structures of these schemes only support the AND gate, which makes them less expressive. To enhance the expressiveness, Liu et al. [18] presented a novel T-CP-ABE scheme, which supports access polices as monotone access structures. Their scheme achieves traceability and high expressiveness at the same time. However, their scheme only achieves white box traceability. Furthermore, since their scheme builds on Lewko et al.’s scheme [8], which is based on the composite order group, which incurs some efficiency loss, and Lewko et al.’s scheme is based on non-standard assumption, Liu et al’s scheme [18] inherits the same drawbacks as Lewko et al.’s scheme.

We present a traceable ciphertext policy attribute-based encryption scheme that addresses black box decoders. Security is proven in the **IND-ID-CCA** security game, **Dishonest User Security Game** and **Dishonest Authority Security Game**. Here, we only investigate the accountability of the attribute-based encryption scheme, which is only payload hiding, but not attribute hiding. In future work, we will design a traceable predicate encryption scheme to catch the malicious authority. Furthermore, there exists the key escrow problem in the attribute-based encryption scheme from lattice resisting quantum cryptoanalysis. To the best of our knowledge, the problem is still an open problem. In future work, we will solve this problem.

This work is supported by the NSF of China (No. 61402376) and the science and technology foundation of Sichuan Province of China (No. 2014GZ0109). The authors thank Shengke Zeng for many helpful suggestions and gratefully acknowledge the anonymous reviewers for their valuable comments.

Xingbing Fu designed research and wrote the paper, Xunyun Nie and Fagen Li proposed suggestions and revised this paper. All authors have read and approved the final manuscript.

The authors declare no conflict of interest.

- Boneh, D.; Sahai, A.; Waters, B. Functional encryption: Definitions and challenges. In Theory of Cryptography, Proceedings of the 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, 28–30 March 2011; Springer: Berlin/Heidelberg, Germany, 2011. Lecture Notes in Computer Science. Volume 6597, pp. 253–273. [Google Scholar]
- Hoeteckee, W. Functional Encryption and Its Impact on Cryptography. In Security and Cryptography for Networks, Proceedings of the 9th International Conference, SCN 2014, Amalfi, Italy, 3–5 September 2014; Springer: Berlin/Heidelberg, Germany, 2014. Lecture Notes in Computer Science. Volume 8642, pp. 318–323. [Google Scholar]
- Sahai, A.; Waters, B. Fuzzy identity-based encryption. In Advances in Cryptology—EUROCRYPT 2005, Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 22–26 May 2005; Springer: Berlin/Heidelberg, Germany, 2005. Lecture Notes in Computer Science. Volume 3494, pp. 457–473. [Google Scholar]
- Goyal, V.; Pandey, O.; Sahai, A.; Waters, B. Attribute-based Encryption for Fine-Grained access Control of Encrypted Data. In Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 30 October–3 November 2006; pp. 89–98.
- Bethencourt, J.; Sahai, A.; Waters, B. Ciphertext-Policy Attribute-Based Encryption. In Proceedings of the IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 20–23 May 2007; pp. 321–334.
- Cheung, L.; Newport, C. Provably Secure Ciphertext Policy ABE. In Proceedings of the 14th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 29 October–2 November 2007; pp. 456–465.
- Goyal, V.; Jain, A.; Pandey, O.; Sahai, A. Bounded Ciphertext Policy Attribute-Based Encryption. In Automata, Languages and Programming, Proceedings of the 35th International Colloquium, ICALP 2008, Part II, Reykjavik, Iceland, 7–11 July 2008; Springer: Berlin/Heidelberg, Germany, 2008. Lecture Notes in Computer Science. Volume 5126, pp. 579–591. [Google Scholar]
- Lewko, A.; Okamoto, T.; Sahai, A.; Takashima, K.; Waters, B. Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption. In Advances in Cryptology—EUROCRYPT 2010, Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, French, 30 May–3 June 2010; Springer: Berlin/Heidelberg, Germany, 2010. Lecture Notes in Computer Science. Volume 6110, pp. 62–91. [Google Scholar]
- Waters, B. Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization. In Public Key Cryptography—PKC 2011, Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, 6–9 March 2011; Springer: Berlin/Heidelberg, Germany, 2011. Lecture Notes in Computer Science. Volume 6571, pp. 53–70. [Google Scholar]
- Beimel, A. Secure Schemes for Secret Sharing and Key Distribution. Ph.D. Thesis, Israel Institute of Technology, Technion, Israel, 1996. [Google Scholar]
- Camenisch, J.; Neven, G.; Shelat, A. Simulatable Adaptive Oblivious Transfer. In Advances in Cryptology—EUROCRYPT 2007, Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, 20–24 May 2007; Springer: Berlin/Heidelberg, Germany, 2007. Lecture Notes in Computer Science. Volume 4515, pp. 573–590. [Google Scholar]
- Naccache, D. Secure and Practical Identity-Based Encryption. IET Inf. Secur.
**2007**, 1, 59–64. [Google Scholar] [CrossRef] - Boneh, D.; Franklin, M. Identity-Based Encryption from the Weil Pairing. In Advances in Cryptology—CRYPTO 2001, Proceedings of the 21st Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2001; Springer: Berlin/Heidelberg, Germany, 2001. Lecture Notes in Computer Science. Volume 2139, pp. 213–229. [Google Scholar]
- Goyal, V. Reducing Trust in the PKG in Identity Based Cryptosystems. In Advances in Cryptology—CRYPTO 2007, Proceedings of the 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, 19–23 August 2007; Springer: Berlin/Heidelberg, Germany, 2007. Lecture Notes in Computer Science. Volume 4622, pp. 430–447. [Google Scholar]
- Libert, B.; Vergnaud, D. Towards Black-Box Accountable Authority IBE with Short Ciphertexts and Private Keys. In Public Key Cryptography—PKC, Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, 18–20 March 2009; Springer: Berlin/Heidelberg, Germany, 2009. Lecture Notes in Computer Science. Volume 5443, pp. 235–255. [Google Scholar]
- Goyal, V.; Lu, S.; Sahai, A.; Waters, B. Black-Box Accountable Authority Identity-Based Encryption. In Proceedings of the 15th ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 27–31 October 2008; pp. 427–436.
- Li, J.; Ren, K.; Kim, K. A2BE: Accountable Attribute-based Encryption for Abuse Free Access Control. IACR Cryptology ePrint Archive. 2009; 118. [Google Scholar]
- Liu, Z.; Cao, Z.; Wong, D. White-Box Traceable Ciphertext-Policy Attribute-Based Encryption Supporting Any Monotone Access Structures. IEEE Trans Inf. Forensics Secur.
**2013**, 8, 76–88. [Google Scholar]

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).