Black Box Traceable Ciphertext Policy Attribute-Based Encryption Scheme

Abstract

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.

1. Introduction

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.

2. Preliminaries

2.1. Bilinear Map

Let 𝔾 and ${\text{𝔾}}_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{𝔾}\times \text{𝔾}\to {\text{𝔾}}_T$, which has properties as follows. Bilinearity: for any $a,b\in {\text{ℤ}}_p$, $e(g^a,u^b)=e{(g,u)}^{ab}$. Nondegenerate: $e(g,g)\ne 1_{{\text{𝔾}}_T}$, $e(g,g)$ is a generator of ${\text{𝔾}}_T$. If the group operations on 𝔾 and on the bilinear map $e:\text{𝔾}\times \text{𝔾}\to {\text{𝔾}}_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).$

2.2. Access Structure

Let 𝕊 be the universe of attributes. An access structure [10] on 𝕊 is a collection 𝔸 of non-empty subsets of attributes, i.e., $\text{𝔸}\subseteq 2^{\text{𝕊}}\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{𝔸}$ and $B\subseteq C$, then $C\in \text{𝔸}$. In this scheme, only the monotone access structure is handled.

2.3. Linear Secret Sharing Scheme

A secret sharing scheme [10] Π over the attribute set is called linear over ${\text{ℤ}}_p$ if .1. The shares for each attribute of a secret form a vector over ${\text{ℤ}}_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{ℤ}}_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{𝔸}\bigwedge S\in \text{𝕊}$ 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{ℤ}}_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$.

2.4. Complexity Assumptions

Decisional bilinear Diffie-Hellman (DBDH): Let $\mathcal{G}\left(1^{\kappa }\right)\to (p,g,\text{𝔾},{\text{𝔾}}_T,e)$. Pick $\xi ,\varpi ,\rho ,d\in {\text{ℤ}}_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.

2.5. Fully Simulatable k-out-of-N Oblivious Transfer

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

2.6. Ciphertext Policy Attribute-Based Encryption

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.

3. Syntax and Definition of Security

3.1. Our Scheme Definition

Definition 1. A traceable ciphertext policy attribute-based encryption (T-CP-ABE) scheme comprises five components.

$\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{𝔸},m)\to {\mathit{CT}}_{\mathit{ID},\text{𝔸}}$: 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{𝔸}}$.

$\mathit{Decrypt}(\mathit{PP},{\mathit{CT}}_{\mathit{ID},\text{𝔸}},K_{ID,S})\to m$: The Decrypt algorithm takes in the public parameters PP, the ciphertext ${\mathit{CT}}_{\mathit{ID},\text{𝔸}}$ 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 ⊥.

Definition 2. (ε Useful Decoder Box) A PPT algorithm $𝒟$ is a ε Useful Decoder Box for the identity ID, where ε is non-negligible, if $Pr\left[𝒟\right(\mathit{Encrypt}(\mathit{PP},\mathit{ID},\text{𝔸},m))=m]>\epsilon$.

${\mathit{Trace}}^{\mathit{𝒟}}(\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 $𝒟$. 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.

3.2. Definition of Security

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 $𝒟$, the tracing algorithm should incriminate the Authority; (3) if the colluding users created the decoder box $𝒟$, it should incriminate these users. We capture the security conditions in the three games as follows:

Definition 3. (IND-ID-Chosen Plaintext Attacks (CPA) Security Game) A T-CP-ABE scheme is IND-ID-CPA secure if no PPT attacker 𝒜 has non-negligible advantages in this game:

Setup: The challenger runs the Setup algorithm generating MSK and PP given to the attacker 𝒜.

Query Phase 1: The attacker 𝒜 runs the interactive PriKeyGen protocol with the challenger for adaptively-picked identities ${\mathit{ID}}_i$ and attribute sets $S_i$, where $i\in \{1,\cdots ,q\}$, and receives the corresponding private keys $K_{{\mathit{ID}}_i,S_i}$.

Challenge: The attacker 𝒜 submits two plaintext messages $m_0$ and $m_1$, which are of equal length, challenge identity ${\mathit{ID}}^{\star }$ and a challenge access structure ${\text{𝔸}}^{\star }$, except that ${\mathit{ID}}^{\star }$ should not be equal to any of the identities queried in Query Phase 1, and the access structure ${\text{𝔸}}^{\star }$ is satisfied by none of the attribute sets $S_i$ where $i\in \{1,\cdots ,q\}$ in Query Phase 1. The challenger flips a fair binary coin $\beta \in \{0,1\}$ and encrypts $m_{\beta }$ with ${\mathit{ID}}^{\star }$ and ${\text{𝔸}}^{\star }$. The resulting ciphertext $\mathit{CT}=\mathit{Encrypt}(PP,I{D}^{\star },{\text{𝔸}}^{\star },m_{\beta })$ is passed on to the attacker 𝒜.

Query Phase 2: Phase 1 is repeated, except that ${\mathit{ID}}^{\star }$ should not be equal to any of the identities in ${\mathit{ID}}_i$, and the access structure ${\text{𝔸}}^{\star }$ is satisfied by none of the attribute sets $S_i$ in which $i\in \{q+1,\cdots ,Q\}$, where Q is the number of the queries made by the attacker.

Guess: The attacker returns a guess ${\beta }^{\prime }\in \{0,1\}$ of β; if ${\beta }^{\prime }=\beta$, the attacker will win.

Definition 4. The proposed scheme is secure against chosen plaintext attacks (CPA) if no probabilistic polynomial time adversary has a non-negligible advantage in the aforementioned game, in which the advantage is defined as:

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

Definition 5. (Dishonest User Security Game) In this game, some dishonest users ${\mathit{ID}}_i$ where $i\in \{1,\cdots ,Q\}$ collude to try to create a decoder box framing the Authority. The challenger and the attacker have the following common inputs: the security parameter κ and another parameter $\epsilon =1/poly\left(\kappa \right)$. A T-CP-ABE scheme is Dishonest User secure if no PPT attacker 𝒜 has a non-negligible advantage in the following game:

Init: The attacker 𝒜 commits to a challenge identity ${\mathit{ID}}^{\star }$ to the challenger.

Setup: The challenger runs the Setup algorithm, which generates MSK and PP that are given to the attacker 𝒜.

Private Key Generation Queries: The attacker 𝒜 runs the interactive PriKeyGen protocol with the challenger for adaptively-picked identities ${\mathit{ID}}_i$ and attribute sets $S_i$, where $i\in \{1,\cdots ,Q\}$, and receives the corresponding private keys $K_{{\mathit{ID}}_i,S_i}$.

Create Decoder Box: The attacker 𝒜 submits a private key $K_{{\mathit{ID}}^{*},S}$ and a decoder box $𝒟$ for the challenge identity ${\mathit{ID}}^{\star }$ declared in the Init phase.

Tracing Failure: The tracing algorithm falsely incriminates the Authority, i.e., ${\mathit{Trace}}^{\text{𝒟}}(\mathit{ID},K_{\mathit{ID},S},\epsilon )=\mathit{Authority}$. Furthermore, the decoder box $𝒟$ is ε useful for ID, i.e., $Pr\left[\text{𝒟}\right(\mathit{Encrypt}(\mathit{PP},\mathit{ID},\text{𝔸},m))=m]>\epsilon$. If these two conditions hold, the attacker 𝒜 will win this game.

Definition 6. (Dishonest Authority Security Game) In this game, a malicious Authority tries to create a decoder box framing the user. Both the challenger and the attacker Authority have common inputs as follows: the security parameter κ and another parameter $\epsilon =1/poly\left(\kappa \right)$. A traceable CP-ABE scheme is Dishonest Authority secure if no PPT attacker 𝒜 has non-negligible advantages in the following game:

Setup: The challenger is given an identity ID and PP, which are generated by the attacker 𝒜 (acting as a malicious Authority) and checks whether ID and PP are well formed, aborting if these checks fail.

PriKeyGen: The attacker 𝒜 and the challenger conduct the private key generation protocol to generate a private key for the identity ID and the attribute set S. If no party aborts, the private key $K_{\mathit{ID},S}$ is received by the challenger as output.

Decryption Queries: The attacker 𝒜 adaptively makes queries for ciphertexts ${\mathit{CT}}_1,\cdots ,{\mathit{CT}}_Q$ of the challenger, and the challenger responds with the decryption values under $K_{\mathit{ID},S}$.

Create Decoder Box: The attacker 𝒜 returns a decoder box $𝒟$.

Tracing Failure: The tracing algorithm falsely incriminates the User, i.e., ${\mathit{Trace}}^{\text{𝒟}}(\mathit{ID},K_{\mathit{ID},S},\epsilon )=\mathit{User}$. Furthermore, the decoder box $𝒟$ is ε useful for ID, i.e., $Pr\left[\text{𝒟}\right(\mathit{Encrypt}(\mathit{PP},\mathit{ID},\text{𝔸},m))=m]>\epsilon$. If these two conditions hold, the attacker 𝒜 will win this game.

Definition 7 A black box T-CP-ABE scheme is secure if no PPT attacker 𝒜 has non-negligible advantage in κ in the IND-ID-CCA security game, Dishonest User Security Game and Dishonest Authority Security Game.

4. Scheme Construction

A ciphertext has a structure as follows: (ID,${\text{𝔸}}_1,\cdots ,{\text{𝔸}}_Z$), where ID is the identity of the user and ${\text{𝔸}}_1,\cdots ,{\text{𝔸}}_Z$ are Z (where Z is a positive integer) parallel repetitions, each comprising monotone access structure ${\text{𝔸}}_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{𝔸}}_1$) AND⋯ AND ($S_Z$ satisfies monotone access structure ${\text{𝔸}}_Z$). Let L be the length of bits of the identity string ID $\in {\text{ℤ}}_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{ℤ}}_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{ℤ}}_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{ℤ}}_p$. Pick two random elements $\mu ,\theta \in {\text{ℤ}}_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{ℤ}}_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{ℤ}}_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{ℤ}}_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{ℤ}}_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{ℤ}}_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{𝒫}=(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 $𝒫$ to the user U. The user U checks whether she obtains the correct private key components as a percent $𝒫$. 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.

Key Validity Check: For a given private key $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]})$ for the ID and attribute set S, to check whether this private key is well formed, a deterministic algorithm Key Validity Check is defined as follows:

Step 1.

$$e(K_{b,z},g)·e{(g^{\theta },D_{1,z})}^{-1}=e(g^{{\mu }_z}{g}^{\theta r_{1,z}},g)·e{(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{𝔸}}_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{ℤ}}_p$. The ciphertext ${\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}^{\prime }$ is constructed as follows:

$$\begin{array}{c}{\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}^{\prime }=({\left\{{\text{𝔸}}_z\right\}}_{z\in \left[Z\right]},E=m·e{(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}$$

Ciphertext Validity Check: To check whether this ciphertext ${\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}^{\prime }$ is well formed, a deterministic Ciphertext Validity Check algorithm is defined as follows: If the attribute sets $S_z$ of the private keys satisfy the access structures ${\text{𝔸}}_z$ of the ciphertexts, then there exist coefficients $\left\{{\eta }_{i,z}\right|{\eta }_{i,z}\in {\text{ℤ}}_p:i=1,\cdots ,h,z\in \left[Z\right]\}$, such that ${\sum }_{\phi \left(i\right)\in S_z}{\eta }_{i,z}·{\overrightarrow{M}}_{i,z}=(1,0,\cdots ,0)$, where ${\overrightarrow{M}}_{i,z}$ is the i-th row vector of the access matrix $M_z$. Check if $e(E_j,W_{1,I{D}_1})=e(W_{j,I{D}_j},E_1)$, $j\in \left[L\right]$ and ${\prod }_{\phi \left(i\right)\in S_z}e{(E_{i,c,z},g)}^{{\eta }_{i,z}}=e(g^{\theta },E_{b,z})·{\prod }_{\phi \left(i\right)\in S_z}e{(T_{c,j,z}^{-1},E_{b,z})}^{{\eta }_{i,z}}$,$j\in S_z,z\in \left[Z\right]$ holds. If not, it fails and returns ⊥. If so, the ciphertext validity check passed, and the user U sets ${\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}={\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}^{\prime }$.

$\mathbf{Decrypt}:$ The Decrypt algorithm takes in the public parameters PP, the well-formed ${\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}$ 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{𝔸}}_z$ of the ciphertexts, then there exist coefficients ${\eta }_{i,z}\in {\text{ℤ}}_p$, such that ${\sum }_{\phi \left(i\right)\in S_z}{\eta }_{i,z}·{\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·e{(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}})·{\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·e{(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·e{(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·e{(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·e{(g,g)}^{\mu s}/e{(g,g)}^{{\mu }_{0}s}e{(g,g)}^{({\mu }_1+\cdots +{\mu }_Z)s}\hfill \\ =m·e{(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{𝔸}}_z$.

Pick a message m at random and encrypt m using the access structure ${\text{𝔸}}_z$.

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

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

5. Security Proofs

The security of the aforementioned scheme is proven as follows:

Theorem 1. The advantage of an attacker in the IND-ID-CCA security game is negligible for the T-CP-ABE scheme under the DBDH assumption.

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.

Theorem 2. Provided that the k-out-of-N oblivious transfer is secure based on the real/ideal world security definition, the advantage of an attacker in the Dishonest Authority Security Game is negligible for the T-CP-ABE scheme.

Proof. This scheme comprises Z attribute sets in parallel and employs fully-simulatable oblivious transfer in the private key generation phase. If Key Validity Check and Ciphertext Validity Check pass, this scheme will incriminate the Authority, which can access a decryption oracle $𝒟$. Via Key Validity Check and Ciphertext Validity Check, all of the same ciphertexts can be decrypted by the users whose attributes satisfy the access structures associated with these ciphertexts to the same value, and the Authority can decrypt to this value.

Let $𝒟$ 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{𝔸}}_z$.

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

The decoder box returns $m^{\star }=𝒟\left({\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}\right)$.

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

Theorem 3. The advantage of an attacker in the Dishonest User Security Game is negligible for the T-CP-ABE scheme under the DBDH assumption.

Proof. A user can adapt the security proof in [9] to show that the selective ID Dishonest User Security Game can be reduced to the decisional bilinear Diffie-Hellman (DBDH) assumption. □

Init: The attacker 𝒜 declares a challenge identity ${\mathrm{ID}}^{\star }$. The ideal functionality $ℱ$ from the ideal world in the simulation based model of Oblivious Transfer picks $W_{j,z}$ and the challenge access structures ${\left\{{\text{𝔸}}_z^{\star }\right\}}_{z\in \left[Z\right]}$, which are employed to obtain the resulting challenge ciphertexts sent to the challenger $𝒞$ by $ℱ$.

Setup: The challenger $𝒞$ sends public parameters $PP$ to $ℱ$, which transfers $PP$ to 𝒜.

Private Key Generation Query: If 𝒜 makes a request for a private key on $ID\ne I{D}^{\star }$, then sends the corresponding user attributes to $ℱ$ that passes it to $𝒞$, it outputs a well-formed private key that $ℱ$ sends back to 𝒜. If $ID=I{D}^{*}$, since $ℱ$ obtains the private keys, it can pick permutations $P_1,\cdots ,P_Z$, such that the private key received by 𝒜 cannot decrypt a ciphertext containing the previously-picked access structure. $ℱ$ queries $𝒞$ for this private key and sends it back to 𝒜.

Create Decoder Box: 𝒜 submits a private key $K_{I{D}^{\star },S}$ and a decoder box $𝒟$. If 𝒜 wins the Dishonest User Security Game, then the Authority will be incriminated by the decoder box. $ℱ$ picks two messages $m_0,m_1$ at random sent to $𝒞$ that sends $ℱ$ a challenge ciphertext ${\mathrm{CT}}_{\mathrm{ID},\text{𝔸}}^{\star }$ under the previously-picked access structures. If $K_{I{D}^{\star },S}$ can decrypt this message, so can $ℱ$, and $ℱ$ sends the right guess to $𝒞$; else ${\mathrm{CT}}_{{\mathrm{ID}}^{*},\text{𝔸}}$ is a random ciphertext that $I{D}^{\star }$ cannot decrypt. Hence, if 𝒜 wins the Dishonest User Security Game, $𝒟$ has a non-negligible advantage in decrypting this ciphertext. Therefore, $ℱ$ has a non-negligible advantage in the attribute-based selective set game against $𝒞$, which is in contradiction with the security of the CP-ABE scheme under the DBDH assumption.

6. Related Work

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.

7. Conclusions and Future Work

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.