In this section, we provide the detailed construction of our RM-CP-ABE scheme for access structure represented by an AND gate over positive and negative attributes. The positive attribute in the access policy requires that the user must have this attribute to decrypt the corresponding ciphertext. On the other hand, the negative attribute in the access policy requires that the attribute set of the decrypting user cannot contain this attribute. The scheme supports N attribute authorities in the system, and efficient user revocation. The details are given below.
\(\text {KeyGen}(pk_{\theta }, msk_{\theta },st,\textbf{S})\rightarrow sk\): The algorithm takes the public key
\(pk_{\theta }\), the master secret key
\(msk_{\theta }\) of
\(AA_{\theta }\), the state
st and a user’s attribute set
\(\textbf{S}\subseteq l_{\theta }\) as input, where
\(l_{\theta }\) is the set of attributes managed by the
\(AA_{\theta }\). It then proceeds as follows.
1
CA takes a polynomial \(P(x)=\beta +\sum _{i=1}^{N-1} a_{i} x^{i}\) of degree \(N-1\) for \(a_{i}\leftarrow \mathcal {R}_{q}\), computes \(\beta _{\theta }=P\left( \theta \right)\) and assigns \(\beta _{\theta }\) to \(AA_{\theta }\).
2
For each \(i\in l_{\theta }\), \(AA_{\theta }\) chooses a vector \(\textbf{k}_{\theta , i} \leftarrow D_{\mathcal {R}_{q}^{m}, \sigma _{s}}\). If \(i\in \textbf{S}\), it computes \(u_{\theta , i} \leftarrow \textbf{B}_{\theta ,i}^{+} \textbf{k}_{\theta , i}\), else, it computes \(u_{\theta , i} \leftarrow \textbf{B}_{\theta ,i}^{-} \textbf{k}_{\theta , i}\).
3
For each node \(\alpha \in Path(id)\setminus Path(id')\), if the node is empty, \(AA_{\theta }\) randomly chooses \(u_{A_{\theta }, \alpha , 2} \leftarrow R_{q}\) and store it in the node, where id denotes the user’s identity who generated the secret key and \(id'\) denotes the user’s identity who has been revoked. It implies that the nodes \(\alpha \in Path(id')\) corresponding to the revoked user identity \(id'\) have been invalidated, and the \(AA_{\theta }\) does not need to generate secret keys corresponding to these potentially shared nodes for subsequent users.
4
\(AA_{\theta }\) calculates
\(u_{A_{\theta }, \alpha , 1}=\beta _{\theta }-u_{A_{\theta , \alpha , 2}}-\sum _{i \in l_{\theta }} u_{\theta , i}\) and samples
$$\begin{aligned} \textbf{k}_{\textbf{A}_{\theta }, \alpha , 1} \leftarrow \text{ SamplePre }\left( \textbf{A}_{\theta }, \textbf{T}_{\textbf{A}_{\varvec{\theta }}}, u_{A_{\theta }, \alpha , 1}, \sigma , \sigma _{s}\right) .\end{aligned}$$
5
\(AA_{\theta }\) samples \(\textbf{k}_{\textbf{A}_{\theta },3}\leftarrow D_{\mathcal {R}_{q}^{2m},\sigma _{s}}\) and calculates \(u_{A_{\theta }, 3}\leftarrow \left( \textbf{A}_{\theta }\mid \textbf{E}_{\theta } \right) \textbf{k}_{\textbf{A}_{\theta },3}\).
6
\(AA_{\theta }\) chooses \(u_{A_{\theta }, 4}\leftarrow \mathcal {R}_{q}\) and stores it.
7
Then
\(AA_{\theta }\) samples
$$\begin{aligned} \textbf{k}_{\textbf{A}_{\theta },4} \leftarrow \text{ SamplePre }\left( \textbf{A}_{\theta }, \textbf{T}_{\textbf{A}_{\varvec{\theta }}}, u_{A_{\theta },4}-u_{A_{\theta },3}, \sigma , \sigma _{s}\right) \end{aligned}$$
.
8
Finally, it outputs the secret key
$$\begin{aligned} sk_{\theta }=\left( \left\{ \textbf{k}_{\textbf{A}_{\theta }, \alpha , 1} \right\} _{\alpha \in Path(id)\setminus Path(id')}, \left\{ \textbf{k}_{\theta , i} \right\} _{i\in S},\textbf{k}_{\textbf{A}_{\theta },3},\textbf{k}_{\textbf{A}_{\theta },4} \right) \end{aligned}$$
\(\text {KeyUpdate}(pk_{\theta }, msk_{\theta },rl,st,t)\rightarrow ku\): Given the public key
\(pk_{\theta }\), the master secret key
\(msk_{\theta }\) of
\(AA_{\theta }\), the revocation list
rl, the state
st and a revocation time
t, the algorithm proceeds as follows.
1
It samples \(r_{t}\leftarrow D_{\mathcal {R}_{q},\sigma _{s}}\) and samples \(\textbf{k}_{\textbf{A}_{\theta },5}\leftarrow D_{\mathcal {R}_{q}^{2m},\sigma _{s}}\).
2
It calculates \(u_{A_{\theta }, 5}=\left( \textbf{A}_{\theta }\mid \textbf{E}_{\theta } \right) \textbf{k}_{\textbf{A}_{\theta },5}\).
3
Next, it fetches
\(u_{A_{\theta }, \alpha , 2}\) and
\(u_{A_{\theta }, 4}\), and samples
$$\begin{aligned} \textbf{k}_{\textbf{A}_{\theta }, \alpha , 2} \leftarrow \text{ SampleLeft }\left( \textbf{A}_{\theta }, \textbf{D}_{\theta }+\textbf{H}_{t}, \textbf{T}_{\textbf{A}_{\mathbf {\theta }}}, u'_{A_{\theta },\alpha , 2} \right) \end{aligned}$$
where
\(\alpha \in \text {KUNodes}(st,rl,t)\),
\(u'_{A_{\theta },\alpha , 2}=u_{A_{\theta },\alpha , 2}-u_{A_{\theta }, 4}r_{t}+u_{A_{\theta }, 5}\) and
\(\textbf{H}_{t} = Tran_{M\rightarrow V}\left( Tran_{V\rightarrow M} \left( \textbf{y}^{\top } \right) \textrm{H} \left( t \right) \right)\).
4
Finally, it outputs the key update
$$\begin{aligned} ku_{\theta ,t}=\left( \left\{ \textbf{k}_{\textbf{A}_{\theta }, \alpha , 2} \right\} _{\alpha \in \text {KUNodes}(st,rl,t)},\textbf{k}_{\textbf{A}_{\theta }, 5},r_{t} \right) . \end{aligned}$$
\(\text {DKGen} \left( \{sk_{\theta }, ku_{\theta }\}_{\theta \in N} \right) \rightarrow dk\): The algorithm takes the secret key
\(\{sk_{\theta }\}_{\theta \in N}\) and the key update
\(\{ku_{\theta }\}_{\theta \in N}\) as input. If
\(Path(id)\cap \text {KUNodes}(st,rl,t)=\emptyset\), it returns a failure symbol
\(\perp\). Otherwise, it can find a unique node
\(\alpha \in Path(id) \cap \text {KUNodes}(st,rl,t)\) and store
\(\left( \textbf{k}_{\textbf{A}_{\theta },\alpha , 1}, \textbf{k}_{\textbf{A}_{\theta }, \alpha , 2}, \textbf{k}_{\theta , i} \right)\) in
\(dk_{\theta }\) for ench
\(\theta \in N\). For simplicity, we can omit the subscript
\(\alpha\). Then, let
\(\textbf{dk}_{\textbf{A}_{\theta }, 1}= \textbf{k}_{\textbf{A}_{\theta },1}+\textbf{k}_{\textbf{A}_{\theta },4}r_{t}\),
\(\textbf{dk}_{\textbf{A}_{\theta },2}= \textbf{k}_{\textbf{A}_{\theta },2}\), and
\(\textbf{dk}_{\textbf{A}_{\theta },3}= \textbf{k}_{\textbf{A}_{\theta },3}r_{t}-\textbf{k}_{\textbf{A}_{\theta },5}\), Finally, it outputs the decryption key
$$\begin{aligned} dk=\left\{ \textbf{dk}_{\textbf{A}_{\theta },1}, \textbf{dk}_{\textbf{A}_{\theta },2},\textbf{dk}_{\textbf{A}_{\theta },3}, \left\{ \textbf{k}_{\theta , i} \right\} _{i\in S} \right\} _{\theta \in N}. \end{aligned}$$
\(\text {Enc} \left( pp, \{pk_{\theta }\}_{\theta \in N}, \mu ,\mathbb {W} \right) \rightarrow CT\): Given the public parameters
pp, the public key
\(\{pk_{\theta }\}_{\theta \in N}\), a message
\(\mu\), and an access structure
\(\mathbb {W}=\left( \mathbb {W}^{+}\cap \mathbb {W}^{-} \right)\), which determines the set of positive and negative attributes, the algorithm samples
\(s\leftarrow \mathcal {R}_{q}\) and
\(e_{0}\leftarrow D_{\mathcal {R}_{q}, \sigma _{s}}\), and computes
\(\textbf{C}_{0} \leftarrow s \beta +e_{0}+\mu [q / 2]\). Then it samples vectors
\(\left\{ \textbf{e}_{\textbf{A}_{\theta }} \right\} _{\theta \in N}\leftarrow D_{\mathcal {R}_{q}^{m}, \sigma _{s}}\), and computes
\(\textbf{C}_{\textbf{A}_{\theta }} \leftarrow \textbf{A}_{\theta }^{T}s+\textbf{e}_{\textbf{A}_{\theta }}\). For each
\(\theta \in N\) and
\(i \in l_{\theta }\), if
\(i \in \mathbb {W}^{+}\), it samples vectors
\(\textbf{e}_{\theta ,i}\leftarrow D_{\mathcal {R}_{q}^{m}, \sigma _{s}}\) and computes
\(\textbf{C}_{\theta , i} \leftarrow \left( \textbf{B}_{\theta ,i}^{+}\right) ^{T}s+\textbf{e}_{\theta , i}\), else if
\(i \in \mathbb {W}^{-}\), it samples vectors
\(\textbf{e}_{\theta ,i}\leftarrow D_{\mathcal {R}_{q}^{m}, \sigma _{s}}\) and computes
\(\textbf{C}_{\theta , i} \leftarrow \left( \textbf{B}_{\theta ,i}^{-}\right) ^{T}s+\textbf{e}_{\theta , i}\). Otherwise, it samples vectors
\(\left\{ \textbf{e}_{\theta ,i}^{+},\textbf{e}_{\theta ,i}^{-} \right\} \leftarrow D_{\mathcal {R}_{q}^{m}, \sigma _{s}}\), and computes
\(\textbf{C}_{\theta , i}^{+} \leftarrow \left( \textbf{B}_{\theta ,i}^{+}\right) ^{T}s+\textbf{e}_{\theta , i}^{+}\) and
\(\textbf{C}_{\theta , i}^{-} \leftarrow \left( \textbf{B}_{\theta ,i}^{-}\right) ^{T}s+\textbf{e}_{\theta , i}^{-}\). Next, it samples matrices
\(\left\{ \mathbf {R_{\theta ,1}},\mathbf {R_{\theta ,2}} \right\} \leftarrow \left\{ \pm 1 \right\} ^{m\times m}\), and computes
\(\textbf{C}_{\theta , t,1}=\left( \textbf{D}_{\theta }+\textbf{H}_{t}\right) ^{T} s+\textbf{R}_{\theta ,1} \textbf{e}_{\textbf{A}_{\theta }}\) and
\(\textbf{C}_{\theta ,t,2}=\left( \textbf{E}_{\theta }\right) ^{T} s+\textbf{R}_{\theta ,2} \textbf{e}_{\textbf{A}_{\theta }}\). Finally, it outputs the ciphertext
$$\begin{aligned} CT =\left( \textbf{C}_{0}, \left\{ \textbf{C}_{\textbf{A}_{\theta }}, \textbf{C}_{\theta ,t,1}, \textbf{C}_{\theta ,t,2}\right\} _{\theta \in N},\left\{ \textbf{C}_{\theta , i}, \textbf{C}_{\theta , i}^{\pm }\right\} _{\theta \in N,i\in l_{\theta }}\right) . \end{aligned}$$
Security proof
In the security proof, we divided the adversary into two types, one is the adversary who has not obtained legal authorization, and the user’s private key they have does not satisfies the challenge access policy \(\mathbb {W}^{*}\). The other category is revoked users who indicate malicious intent. Adversary can query the user’s private key that satisfies the challenge access policy and the updated key and decryption key before the revoked time t \((t<t^{*})\). To prove the above theorem, we will describe several security games that differ from each other in the formation of public parameters, the key queried by adversary \(\mathcal {A}\) and the challenge ciphertext. The first game is the same as the ABE game we defined in the security model, and the adversary’s advantage is zero in the last game of the sequence. And we argue that the adversary \(\mathcal {A}\)’s advantage varies negligibly between each successive security game. This will prove that the adversary has a negligible advantage in winning the original ABE security game.
\(\textbf{Game}_{\varvec{0}}\): This is the real selective security game form
Security model section between an adversary
\(\mathcal {A}\) against our scheme and a RM-CP-ABE challenger
\(\mathcal {B}\).
\(\textbf{Game}_{\varvec{1}}\): This game is the same as the previous game except the way the public key vectors \(\left\{ \textbf{A}_{\theta }, \textbf{B}_{\theta ,i}^{\pm },\textbf{D}_{\theta },\right\}\) are generated for all \(\theta \in N\) and \(i\in l_{\theta }\) during the setup phase. In this game, the public key vectors \(\left\{ \textbf{A}_{\theta } \right\} _{\theta \in N}\) is uniformly randomly chosen over \(\mathcal {R}_{q}^{1 \times m}\) instead of by the \(\text {TrapGen}\) algorithm. For all \(\theta \in N\) and \(i \in l_{\theta }\setminus \mathbb {W}^{*}\), \(\mathcal {B}\) samples \(\left\{ \textbf{B}^{+}_{\theta ,i},\textbf{B}^{-}_{\theta ,i} \right\} \leftarrow \mathcal {R}_{q}^{1\times m}\). For each \(i \in \mathbb {W}^{+}\), \(\mathcal {B}\) samples \(\textbf{B}^{+}_{\theta ,i}\leftarrow \mathcal {R}_{q}^{1\times m}\) and computes \(\left\{ \textbf{B}^{-}_{\theta ,i},\textbf{T}_{\textbf{B}_{\theta ,i}}^{-} \right\} \leftarrow \text {TrapGen}(\lambda )\). Correspondingly, \(\mathcal {B}\) samples \(\textbf{B}^{-}_{\theta ,i}\leftarrow \mathcal {R}_{q}^{1\times m}\) and computes \(\left\{ \textbf{B}^{+}_{\theta ,i},\textbf{T}_{\textbf{B}_{\theta ,i}}^{+} \right\} \leftarrow \text {TrapGen}(\lambda )\) for each \(i \in \mathbb {W}^{-}\). Then, \(\mathcal {B}\) samples \(\left\{ \textbf{R}_{\theta ,1},\textbf{R}_{\theta ,2} \right\} \leftarrow \left\{ -1,1 \right\} ^{m\times m}\) for each \(\theta \in N\). Next, it computes \(\textbf{D}_{\theta }\leftarrow \textbf{A}_{\theta }\textbf{R}_{\theta ,1}-\textbf{H}_{t^{*}}\) and \(\textbf{E}_{\theta }\leftarrow \textbf{A}_{\theta }\textbf{R}_{\theta ,2}\). According to the properties of the \(\text {TrapGen}\) algorithm and the leftover hash lemma, we conclude that \(\textbf{Game}_{\varvec{0}}\) and \(\textbf{Game}_{\varvec{1}}\) are statistically indistinguishable from the adversary’s view.
\(\textbf{Game}_{\varvec{2}}\): This game is analogous to the previous game except the generationed of the public parameter \(\textbf{y}\) during the setup phase. In this game, the vector \(\textbf{y}\) is generated by \(\text {TrapGen}(\lambda )\) instead of being randomly sampled. The indistinguishably between \(\textbf{Game}_{\varvec{1}}\) and \(\textbf{Game}_{\varvec{2}}\) follows from the good properties of the \(\text {TrapGen}\left( \cdot \right)\) algorithm.
\(\textbf{Game}_{\varvec{3}}\): In this game, we change the way the secret keys \(\left\{ sk_{\theta } \right\} _{\theta \in N}\) and update keys \(\left\{ ku_{\theta ,t} \right\} _{\theta \in N}\) are generated during the global setup phase. According to the key query restrictions on the two cases in the security model, we make the following changes:
\({Case\ I}\): If the adversary \(\mathcal {A}\) query an identity id whose attribute set \(\textbf{S}\) does not satisfy the access policy \(\mathbb {W^{*}}\), for all \(\theta \in N\) and \(t = t^{*}\), \(\mathcal {B}\) chooses \(\left\{ \textbf{k}_{\textbf{A}_{\theta }, \alpha , 2},\textbf{k}_{\textbf{A}_{\theta },4} \right\} \leftarrow \mathcal {R}_{q}^{ m}\) and computes \(u_{A_{\theta }, 4}=\textbf{A}_{\theta }\textbf{k}_{\textbf{A}_{\theta }, 4}+u_{A_{\theta }, 3}\). Then it computes \(u_{A_{\theta }, \alpha , 2}= \left( \textbf{A}_{\theta }\mid \textbf{A}_{\theta }\textbf{R}_{\theta ,1}\right) \textbf{k}_{\textbf{A}_{\theta }, \alpha , 2}+u_{A_{\theta }, 4}r_{t^{*}}-u_{A_{\theta }, 5}\) and store them in node. Next, for any \(t \ne t^{*}\), \(\mathcal {B}\) samples \(\textbf{k}_{\textbf{A}_{\theta }, \alpha , 2} \leftarrow \text{ SampleRight } (\textbf{A}_{\theta }, \textbf{A}_{\theta }\textbf{R}_{\theta ,1} - \textbf{H}_{t^{*}} + \textbf{H}_{t}, \textbf{T}_{\textbf{A}_{\varvec{\theta }}}, u_{A_{\theta },\alpha , 2}-u_{A_{\theta }, 4}\left( r_{t}-r_{t^{*}}\right) +u_{A_{\theta }, 5})\). For secret key query, \(\mathcal {B}\) chooses \(\textbf{k}_{\textbf{A}_{\theta }, \alpha , 1}\leftarrow \mathcal {R}_{q}^{1\times m}\) and computes \(u_{A_{\theta }, \alpha , 1}=\textbf{A}_{\theta }\textbf{k}_{\textbf{A}_{\theta }, \alpha , 1}\) for all \(\theta \in N\). Since \(\textbf{S}\) does not satisfy \(\mathbb {W^{*}}\), \(\mathcal {B}\) must knows at least one \(\textbf{T}_{\textbf{B}_{\theta ,j}}^{+}\) or \(\textbf{T}_{\textbf{B}_{\theta ,j}}^{-}\). Then, \(\mathcal {B}\) calculates \(u_{\theta , i} \leftarrow \textbf{B}_{\theta ,i}^{-} \textbf{k}_{\theta , i}\) for each \(i \in \textbf{S},\,i \ne j\) and samples \(\textbf{k}_{\theta , j} \leftarrow \text{ SamplePre }\left( \textbf{B}_{\theta ,j}^{*}, \textbf{T}_{\textbf{B}_{\theta ,\textbf{j}}}^{*}, u_{\theta , j}, \sigma , \sigma _{s}\right)\), where \(u_{\theta , j}=\beta _{\theta }-u_{A_{\theta }, \alpha , 1}-u_{A_{\theta , \alpha , 2}}-\sum _{i \in l_{\theta },i \ne j} u_{\theta , i}\).
\({Case\ II}\): If the adversary \(\mathcal {A}\) query an identity id whose attribute set \(\textbf{S}\) does satisfy the access policy \(\mathbb {W^{*}}\), then the identity id have been revoked before a time \(t^{*}\). For each \(\theta \in N\) and \(\alpha \in Path(id) \cap \text {KUNodes}(st,rl,t)\), \(\mathcal {B}\) chooses \(\textbf{k}_{\textbf{A}_{\theta }, \alpha , 1}\leftarrow \mathcal {R}_{q}^{m}\) and computes \(u_{A_{\theta }, \alpha , 1}=\textbf{A}_{\theta }\textbf{k}_{\textbf{A}_{\theta }, \alpha , 1}\). Then, \(\mathcal {B}\) computes \(u_{A_{\theta , \alpha , 2}}=\beta _{\theta }-u_{A_{\theta }, \alpha , 1}-\sum _{i \in l_{\theta }} u_{\theta , i}\) and store them in the node.
The indistinguishably between \(\textbf{Game}_{\varvec{2}}\) and \(\textbf{Game}_{\varvec{3}}\) follows from the good sampling property of \(\text {SamplePre}\left( \cdot \right)\) algorithm.
\(\textbf{Game}_{\varvec{4}}\): This game is identical to \(\textbf{Game}_{\varvec{3}}\), except that the challenge ciphertext is generated. In this game, for all \(\theta \in N,\,i \in l_{\theta }\setminus \mathbb {W}^{*}\), the challenger \(\mathcal {B}\) sets \(\left\{ \textbf{C}_{\textbf{A}_{\theta }},\textbf{C}_{\theta ,i},\textbf{C}_{\theta ,i}^{\pm } \right\} \leftarrow \mathcal {R}_{q}^{m}\), \(\textbf{C}_{\theta ,t,1}=\textbf{R}_{\theta ,1}\textbf{C}_{\textbf{A}_{\theta }}\), and \(\textbf{C}_{\theta ,t,2}=\textbf{R}_{\theta ,2}\textbf{C}_{\textbf{A}_{\theta }}\). The indistinguishably between \(\textbf{Game}_{\varvec{3}}\) and \(\textbf{Game}_{\varvec{4}}\) follows from the RLWE problem. Since the challenge ciphertext is a random element in the ciphertext space, the advantage of adversary \(\mathcal {A}\) in this game is negligible.