C.1.1 Preliminaries of Bilinear Map

The foundation of ABE-type algorithms is pairing computation. In this appendix, we adopt the design from [297] in terms of algebraic structure. Suppose we have two groups: an additive group $G_0$ and a multiplicative group $G_1$ with the same order $n=s{p}^{\prime }{q}^{\prime }$, where $p^{\prime }$ and $q^{\prime }$ are two large prime numbers. We define a bilinear map $e:{\mathbb{G}}_0\times {\mathbb{G}}_0\to {\mathbb{G}}_1$. This map has three properties:

•  Bilinearity. $e(aP,bQ)=e{(P,Q)}^{ab}$, for any $P,Q\in {\mathbb{G}}_0$ and $a,b\in {\mathbb{Z}}_p$;

•  Nondegeneracy. $e(g,h)\ne 1$, where g and h are generators of ${\mathbb{G}}_0$;

•  Efficiency. Computing the pairing can be efficiently achieved.

C.1.2 ABE Security Model

As mentioned in Section 7.2.1, the proposed solution includes an upper-level ontology-based attribute management scheme and a lower-level ABE-based naming scheme. The upper-level is only focused on the relationship between attributes, which has little to do with security. In this section, we only focus on the naming scheme, which can be modeled in the form of a game between a challenger and an adversary. The challenger simulates the operations of the TTP and the attribute authorities, while the adversary tries to impersonate as a number of normal network nodes. The game consists of the following five steps:

•  Setup. The challenger runs the GlobalSetup algorithm and returns to the adversary the parameters.

•  Phase 1. The adversary can ask for an arbitrary number of user keys from the challenger. The challenger runs the NodeJoin algorithm for each user involved in the requests and returns the corresponding secret information. The adversary then plays the roles of these users to request for attributes from the challenger. The challenger runs the AuthoritySetup algorithm to create parameters for authorities and runs the KeyGen algorithm to generate keys on behalf of the authorities and the TTP.

•  Challenge. The adversary provides two messages $M_0$ and $M_1$ to the challenger, together with an access policy A such that none of the users created by the challenger has attributes satisfying A. The challenger flips a coin b and encrypts $M_b$ using A. It sends the ciphertext back to the adversary.

•  Phase 2. The adversary can ask for more attributes and users from the challenger. But if any single user can gain satisfactory attribute combinations for A, the challenger aborts the game.

•  Guess. The adversary makes a guess $b^{\prime }$ for the real value of b.

The adversary's advantage in this game can be defined as $ADV=P[b^{\prime }=b]-\frac{1}{2}$. The proposed scheme is secure if for all the polynomial time adversaries, the advantage is at most negligible in the game.

C.1.3 ABE-Based Naming Scheme

In this section, we use a composite order group $G_0$ with an order $n=p^2{q}^2$, where p and q are two large prime numbers. In other words, we fix the composite value s in Section C.1.1 as equal to pq. We also choose two subgroups $G_s$ and $G_t$ of $G_0$ such that $s=pq$, $t=pq$, and $G_s$ is orthogonal to $G_t$. We deliberately choose such composite-order group configuration mainly because the proposed scheme is designed to support attribute rankings in $G_s$. It follows RSA conditions to enforce one-direction deduction between attribute values. This is why the values of s and t are set to be products of two large prime numbers. Details of such process will be illustrated in Section C.1.4.

Attributes of an entity can be any value in strings. In our scheme, each attribute string $A_i$ corresponds to a triplet $(I_i,k_i,h_i)$, where $I_i,k_i,h_i\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$. $S_i$ and $T_i$ are assigned by the TTP. The mapping from a string to such a triplet is determined by the authority of attribute $A_i$. An access policy can be expressed in Disjunctive Normal Form (DNF) of attributes. In each conjunctive clause of the DNF, the sequence of attributes is determined by the encrypter. The sequence encrypting a conjunctive clause (encryption sequence) is opposite to the decryption sequence. We define a public attribute $A_{Pub}$ in the scheme. Unlike other attributes, $A_{Pub}$ is associated with a triplet $(S_{Pub},T_{Pub},I_{Pub})$. For each conjunctive clause, the encrypter adds $A_{Pub}$ at the end of the encryption sequence. In other words, the special attribute $A_{Pub}$ is always the last attribute in encryption and the first attribute in decryption.

In the proposed scheme, GlobalSetup algorithm is run by the TTP to generate global parameters for the system. For each node joining in the network, the TTP runs NodeJoin algorithm once to generate a unique secret for the node. For each attribute, the authority in charge runs AuthoritySetup algorithm to generate secrets associated with that attribute. Besides, this naming scheme includes the other three basic algorithms: KeyGen, Encrypt, and Decrypt. Once set up, the authority of an attribute runs KeyGen for each node carrying this attribute to allocate the inherent attribute secrets. Encrypt and Decrypt are respectively used by encrypters and decrypters for message passing.

The GlobalSetup algorithm generates global parameters {${\mathbb{G}}_s$, ${\mathbb{G}}_t$, φ, ψ, ${\phi }^{\beta }$, $e{(\phi ,\psi )}^{\alpha }$, $En{c}_k(\cdot )$, $De{c}_k(\cdot )$, $(P_{Pub},S_{Pub},T_{Pub})$, $ROOT$}, and global secrets {β, $g^{\alpha }$}, where α and β are random values and $En{c}_k(\cdot )$, $De{c}_k(\cdot )$ are a pair of symmetric encryption algorithms.

The NodeJoin algorithm is given in Algorithm C.2.

Each individual authority that manages an attribute $A_i$ will have to run AuthoritySetup to set up attribute secrets.

The KeyGen algorithm generates the private keys corresponding to each attribute for each node holding this attribute. It is defined in Algorithm C.4. When the node receives the keys from the authority, it checks if $L_{UID}^{P_{UID}}=T_{Pub}$ is true. If it's true, it updates $P_{UID}$ with $P_{UID}^2$ and accepts the keys. This update is intended to prevent from replay attack on $L_{UID}$. Otherwise, it will discard the keys.

The Encrypt algorithm works following the encryption sequence of each clause, by denoting each attribute from $I_1$ to $I_m$, where m is the number of attributes in the clause. In the example of Fig. 7.6, $I_1=MRI$, $I_2=Physician$, $I_3=HospitalA$, $I_4=A_{Pub}$, $m=4$. Choose a random value $s\in Z_p$, set $I_0=s$, and follow Algorithm C.5.

The Decrypt algorithm works in the decryption sequence. Note that the first attribute in a decryption sequence is always $A_{Pub}$. The decrypter follows Algorithm C.6.

When Decrypt algorithm succeeds, $S_k$ is the random data encrypting key embedded in C.

C.1.4 Attribute Rankings

The proposed ABE scheme extends the capabilities of traditional ABE schemes and is able to support a comparison between the values of the same attribute. In a real world scenario, this means, for instance, that two values, $Physician$ and $Nurse$, of attribute Occupation can be compared and have the relationship $Physician>Nurse$, meaning that the $Physician$ attribute subsumes all the privileges that the $Nurse$ has, but the $Nurse$ does not have any of the additional privileges the $Physician$ has. Such capability is applicable when capabilities of the lower-ranking role ($Nurse$) is a subset of that of the higher-ranking role ($Physician$). In traditional ABE solutions, each attribute value ($Physician$ and $Nurse$ in the above example) corresponds to a set of cryptographic components that are designated for that specific attribute (Occupation in the example) of a specific user. Components for different values of the same attribute are not related. In other words, the key components of $Physician$ are independent of those of $Nurse$. To establish ranking relations between attribute values, certain connections need to be created between the corresponding key components. Specifically, a one-direction relation between values of the same attribute is supported in the proposed scheme. It allows a higher-ranking user ($Physician$) to be able to legally derive the corresponding lower-ranking role ($Nurse$) key components for himself. However, the lower-ranking role cannot derive anything regarding the higher-ranking role.

Such capability can be achieved by deliberately assigning appropriate values in KeyGen algorithm. We assign $h_P$ for $Physician$ and $h_N$ for $Nurse$ such that $h_P=h^{{\alpha }_P}$, $h_N=h^{{\alpha }_N}$, $h\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$, and ${\alpha }_P<{\alpha }_N$. Thus, we have $S_P={\phi }^{h_P}$ and $S_N={\phi }^{h_N}$. This is different from traditional ABE scheme, where both $S_P$ and $S_N$ are randomly chosen. This is the connection we establish between comparable values ($Physician$ and $Nurse$) of the same attribute (Occupation). Recall that when we defined the order of ${\mathbb{G}}_s$, it was written as $n^{\prime }=pq$, where p and q are two large prime numbers. In other words, $n^{\prime }$ is a composite number satisfying RSA algorithm requirements. If a user $U_P$ is assigned $S_P={\phi }^{h^{{\alpha }_P}}$, i.e., the key for $Physician$, it is able to calculate the corresponding key $S_N$ for $Nurse$ as long as ${\alpha }_P<{\alpha }_N$. This can be done as

$S_N={\phi }^{h^{{\alpha }_N}}={({\phi }^{h^{{\alpha }_P}})}^{h^{{\alpha }_N-{\alpha }_P}}={(S_P)}^{h^{{\alpha }_N-{\alpha }_P}}.$

This means that when we assign attributes to $U_P$, we can choose to assign the value $h^{{\alpha }_N-{\alpha }_P}$ to the user together with $S_P$. Thus, when the user needs to decode some message dedicated for $Nurse$, he can easily calculate $S_N$ following equation (C.1). However, if another user $U_N$ has the attribute $Nurse$, he cannot deduce $S_P$ following the same equation in a similar way. This is because in this case, ${\alpha }_P-{\alpha }_N<0$. Under RSA assumption, $h^{-1}$ cannot be efficiently computed due to the secrecy of $n^{\prime }$. A benefit of such extension to our original scheme is that it allows the ranking relations among attributes without incurring too much workload on the TTP side. Only eligible users, $Physician$ owners in this example, can use such capability, and the value $h^{{\alpha }_N-{\alpha }_P}$ is only useful to eligible users.

With such a knowledge, the TTP can assign two more values, Δh and Δr, to user $U_P$ in KeyGen algorithms. When needed, the user can derive his key values corresponding to attribute $Nurse$ afterwards. The modified step 3 of KeyGen is as follows:

$\begin{array}{c}\hfill X_{P,UID}={\phi }^{r_{UID}}{S}_P^{r_P},\hfill \\ \hfill Y_P={\phi }^{r_P},\hfill \\ \hfill Z_{P,UID}=e{(\phi ,\psi )}^{r_{UID}{I}_P},\hfill \\ \hfill L_{UID}=T_{Pub}^{1/P_{UID}},\hfill \\ \hfill \mathrm{\Delta }h=h^{({\alpha }_N-{\alpha }_P)r_P},\hfill \\ \hfill \mathrm{\Delta }r=\mathrm{\Delta }h{I}_N/I_P.\hfill \end{array}$

Thus, the $r_{UID}$ for $U_P$'s $Nurse$ attribute is changed to $r_{UID}^{\prime }=r_{UID}\mathrm{\Delta }h$. Correspondingly, we have:

$\begin{array}{c}\hfill X_{N,UID}={(X_{P,UID})}^{\mathrm{\Delta }h}={\phi }^{r_{UID}\mathrm{\Delta }h}{S}_N^{r_P}={\phi }^{r_{UID}^{\prime }}{S}_N^{r_P},\hfill \\ \hfill Y_N=Y_P,\hfill \\ \hfill Z_{N,UID}={(Z_{P,UID})}^{\mathrm{\Delta }r}={(e{(\phi ,\psi )}^{r_{UID}{I}_P})}^{\mathrm{\Delta }h{I}_N/I_P}\hfill \\ \hfill =e{(\phi ,\psi )}^{r_{UID}\mathrm{\Delta }h{I}_P}=e{(\phi ,\psi )}^{r_{UID}^{\prime }{I}_P},\hfill \\ \hfill L_{UID}^{\prime }=L_{UID}.\hfill \end{array}$

Here, we need to point out that to make sure that the values of h for two comparable attributes are the same, comparable attributes need to be managed by the same authority. This means that one single authority defines the relative order between these attributes. This requirement makes sense in a real-world scenario since in most cases a single authority (the hospital in this example) defines values of the same attribute (job position).

C.1.5 Security Proof Sketch

In this section, we provide a sketch of security proof following the structure in [63]. Before going into details of the proof, we firstly modify the security game described in Section C.1.2. This modification follows the same idea as in [63] and it is intended to change from differentiating two random messages $M_0,M_1$ to differentiating $e{(\phi ,\psi )}^{\alpha s_j},e{(\phi ,\psi )}^{{\theta }_j}$ so that the generated intermediate results can be represented using the four mappings introduced in Section C.1.5.2. The goal of such modification is essentially to facilitate the following security proof. To differentiate these two games, we call the one in Section C.1.2 as Game1 and the modified game as Game2.

C.1.5.2 Security Guarantee in the Modified Game

In this section, we follow the generic group model introduced in [247] and use a simulator to model the modified security game between the challenger and the adversary. The simulator chooses random generators $\phi \in G_s$ and $\psi \in G_t$. It then encodes any member in $G_s$ and $G_t$ to a random string following two mappings: $f_0,f_1:{\mathbb{Z}}_{n^{\prime }}\to {\{0,1\}}^{\lceil \log n^{\prime }\rceil }$. It also encodes any member in $G_1$ to a random string in a similar way: $f_2:{\mathbb{Z}}_n\to {\{0,1\}}^{\lceil \log n\rceil }$. One additional mapping $f_3$ is used to convert elements in ${\mathbb{Z}}_{n^{\prime }}^{⁎}$ to string representations: $f_3:{\mathbb{Z}}_{n^{\prime }}^{⁎}\to {\{0,1\}}^{\lceil \log n^{\prime }\rceil }$. The four mappings should be invertible so that the simulator and the adversary can map between the strings and the elements of corresponding algebraic structures in both directions. Four oracles are provided to the adversary by the simulator to simulate the group operations in $G_s$, $G_t$, $G_1$, and the pairing. Only the string representations can be applied to the oracles. The results are returned from the simulator in the string representations as well. The oracles will strictly accept inputs from the same group. The simulator plays the role as the challenger in the modified game.

•  Setup. The simulator chooses $G_s$, $G_t$, $G_1$, e, φ, ψ, and random values α, β. It also defines the mappings $f_0$, $f_1$, $f_2$ and the four oracles mentioned above. The simulator chooses the public attribute parameters $I_{Pub}\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$, $S_{Pub}=f_0(\mu )\in G_s$, $T_{Pub}=f_1(\lambda )\in G_t$, and $ROOT\in G_1$, where λ and μ are random strings. The public parameters are $G_s$, $G_t$, $\phi :=f_0(1)$, $\psi :=f_1(1)$, ${\phi }^{\beta }:=f_0(\beta )$, $e{(\phi ,\psi )}^{\alpha }:=f_2(\alpha )$, $(S_{Pub},T_{Pub},I_{Pub})$, and $ROOT$.

•  Phase 1. When the adversary runs NodeJoin for a new user with UID, the simulator generates a random number $r_{UID}\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$. It returns to the adversary with $D_{UID}=f_1((\alpha +r_{UID})/\beta )$, $X_{Pub,UID}=f_0(r_{UID})f_0(\mu r_{Pub,UID})=f_0(r_{UID}+\mu r_{Pub,UID})$, $Y_{Pub}=f_0(r_{Pub})$, and $Z_{Pub,UID}=f_2(r_{UID}{I}_{Pub})$, here $r_{Pub,UID}\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$ is a random number chosen by the simulator. When the adversary requests a new attribute $A_i$ that has not been used before, the simulator randomly chooses $I_i,k_i,h_i\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$ and $S_i=f_0(h_i)\in G_s$, $T_i=f_1(h_i)\in G_t$ to simulate the process for setting up an attribute authority. For each attribute key request made from the adversary, the simulator computes $X_{i,UID}={\phi }^{r_{UID}}{S}_i^{r_i}=f_0(r_{UID}+h_i{r}_i)$, $Y_i={\phi }^{r_i}=f_0(r_i)$, and $Z_{i,UID}=e{(\phi ,\psi )}^{r_{UID}{I}_i}=f_2(r_{UID}{I}_i)$, where $r_i$ is a random number chosen from ${\mathbb{Z}}_{n^{\prime }}^{⁎}$. The simulator passes all these values to the adversary as the attribute keys associated with $A_i$.

•  Challenge. When the adversary asks for a challenge, the simulator flips a coin b and chooses a random value $s\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$. If $b=1$, the simulator calculates $C=f_2(\alpha s)$; if $b=0$, it picks a random value $s^{\prime }\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$ and calculates $C=f_2(s^{\prime })$. In addition, it calculates $C^{\prime }={\phi }^{\beta s}$ and $C^{″}=En{c}_K(ROOT)$. It also computes other components of the ciphertext following Encrypt: $C_{1,n}=f_1((I_{n-1}-I_n)l_n)$, $C_{2,n}=f_1(h_n(I_{n-1}-I_n)l_n)$, and $C_{3,n}=f_3({(k_n{t}_n)}^{-1})$, where $h_n\in {\mathbb{Z}}_{n^{\prime }}^{⁎}$ is a random number chosen by the simulator.

•  Phase 2. The simulator interacts with the adversary similar as in Phase 1 with the exception that the adversary cannot acquire attribute keys enabling a single user to satisfy the access policy $\mathbb{A}$. The output of this step is similar to that of Phase 1 except that the simulator acquires more user IDs and attributes in this step.

From the above game, we can see that the adversary only acquires the string representation of random values in ${\mathbb{Z}}_{n^{\prime }}^{⁎}$, ${\mathbb{Z}}_n$ and combinations of the values. We can model all the queries as rational functions and further assume that different terms always result in different string representations [63]. As shown in [63], the probability that two terms share the same string representation is $O(q^2/n)$, where q is the number of queries made by the adversary. We assume in the rest of the proof that no such collision happens.

Now we argue that the adversary's views are identically distributed between the two cases when $C=f_1(\alpha s)(b=1)$ and when $C=f_1(s^{\prime })(b=0)$. As a matter of fact, what the adversary can view from the modified game with the simulator are independent elements that are uniformly chosen and the only operation that the adversary can do on these elements is to test if two of them are equal or not. Thus, the situation that the views of the adversary differ can only happen when there are two different terms ${\nu }_1$ and ${\nu }_2$ that are equal when $b=1$. Since αs and $s^{\prime }$ only occur in group $G_1$, the results from $f_1$ cannot be paired. Queries by the adversary can only be in the form of additive terms. Then we have ${\nu }_1-{\nu }_2=\gamma \alpha s-{\gamma }^{\prime }{s}^{\prime }$, where γ is a constant. By transformation, we have ${\nu }_1-{\nu }_2+{\gamma }^{\prime }{s}^{\prime }=\gamma \alpha s$. This implies that by deliberately constructing a query ${\nu }_1-{\nu }_2+{\gamma }^{\prime }{s}^{\prime }$, the adversary may be able to get the value of $e{(g,g)}^{\gamma \alpha s}$. Now we prove that such a query cannot be constructed by the adversary based on the information it gets from the game.

In fact, the information that an adversary can acquire from this game can be listed as in Table C.1. This table excludes values related to $L_{UID}$ as it has nothing related to αs. To construct the desired value, the adversary can map two elements from $G_s$ and $G_t$ into one element in $G_1$. He can also use elements in $Z_n$ to change the exponentials. From this table, we can easily see that to obtain a value containing αs, the adversary can pair βs and $(\alpha +r_{UID})/\beta$ to get $\alpha s+r_{UID}s$ in $G_1$. In fact, this is the only way to get a term containing αs. But it is not feasible in that both βs and $(\alpha +r_{UID})/\beta$ belong to $G_t$ while the pairing requires one element from $G_s$ and $G_t$ each.

Table C.1

Query information accessible to the adversary

μ	β	$r_{UID}+\mu r_{Pub,UID}$
r Pub	h i	rUID + hiri
r i	(In−1 − In)hn	tn(In−1 − In)hn
λ	(α + rUID)/β	βs
h i
α	r UID I Pub	r UID I i
I Pub	I i	k i
${(k_n{t}_n)}^{-1}$	h i

Therefore, based on the information an adversary can get from the proposed scheme, the attacker cannot differentiate a random ciphertext from an authentic one. The security of the proposed scheme is proved. □

C.2.1 System Setup and Key Generation

The TA first runs Setup to initiate the P-CP-ABE system by choosing a bilinear map: $e:{\mathbb{G}}_0\times {\mathbb{G}}_0\to {\mathbb{G}}_1$ of prime order p with the generator g. Then, TA chooses two random α, β $\in {\mathbb{Z}}_p$. The public parameters are published as

$PK=\langle {\mathbb{G}}_0,g,h=g^{\beta },e{(g,g)}^{\alpha }\rangle .$

The master key is $MK=(\beta ,g^{\alpha })$, which is only known by the TA.

Each user needs to register with the TA, who authenticates the user's attributes and generates proper private keys for the user. An attribute can be any descriptive string that defines, classifies, or annotates the user to which it is assigned. The key generation algorithm takes as input a set of attributes S assigned to the user, and outputs a set of private key components corresponds to each of attributes in S. The GenKey algorithm performs the following operations:

1.  Chooses a random $r\in {\mathbb{Z}}_p$;

2.  Chooses a random $r_j\in {\mathbb{Z}}_p$ for each attribute $j\in S$;

3.  Computes the private key as:

$\begin{array}{cc}\hfill SK& =\langle D=g^{(\alpha +r)/\beta };\hfill \\ \hfill & \forall j\in S:D_j=g^r\times H{(j)}^{r_j};D_j^{\prime }=g^{r_j}\rangle ;\hfill \end{array}$

4.  Sends SK to the DO through a secure channel.

C.2.2 P-CP-ABE Encryption

To outsource the computation of Encryption and preserve the data privacy, a DO needs to specify a policy tree $\mathcal{T}={\mathcal{T}}_{ESP}\bigwedge {\mathcal{T}}_{DO}$, where ⋀ is an AND logic operator connecting two subtrees ${\mathcal{T}}_{ESP}$ and ${\mathcal{T}}_{DO}$. ${\mathcal{T}}_{ESP}$ is the data access policy that will be performed by the ESP and ${\mathcal{T}}_{DO}$ is a DO controlled data access policy. ${\mathcal{T}}_{DO}$ usually has a small number of attributes to reduce the computation overhead at the DO, in which it can be a subtree with just one attribute (see the example shown in Fig. C.1).

In practice, if ${\mathcal{T}}_{DO}$ has one attribute, DO can randomly specify a 1-degree polynomial $q_R(x)$ and sets $s=q_R(0)$, $s_1=q_R(1)$, and $s_2=q_R(2)$. Then DO sends $\{s_1,{\mathcal{T}}_{ESP}\}$ to ESP, which is denoted as

$DO\stackrel{\{s_1,{\mathcal{T}}_{ESP}\}}{\to }ESP.$

Here, we must note that sending $s_1$ and ${\mathcal{T}}_{ESP}$ will not expose any secret of our solution.

ESP then runs the $\mathbf{Encrypt}(s_1,{\mathcal{T}}_{ESP})$ algorithm, which is described below:

1.  $\forall x\in {\mathcal{T}}_{ESP}$, randomly choose a polynomial $q_x$ with degree $d_x=k_x-1$, where $k_x$ is the secret sharing threshold value:

(a)  For the root node of ${\mathcal{T}}_{ESP}$, i.e., $R_{ESP}$, choose a $d_{R_{ESP}}$-degree polynomial with $q_{R_{ESP}}(0)=s_1$.

(b)  $\forall x\in {\mathcal{T}}_{ESP}\setminus R_{ESP}$ set $d_x$-degree polynomial with $q_x(0)=q_{\mathbf{parent}(x)}(\mathbf{index}(x))$.

2.  Generate a temporal ciphertext:

$C{T}_{ESP}=\{\forall y\in Y_{ESP}:C_y=g^{q_y(0)},C_y^{\prime }=H{(att(y))}^{q_y(0)}\},$

where $Y_{ESP}$ is the set of leaf nodes in ${\mathcal{T}}_{ESP}$.

At the meantime, the DO performs the following operations:

1.  Perform $\mathbf{Encrypt}(s_2,{\mathcal{T}}_{DO})$ and derive:

$C{T}_{DO}=\{\forall y\in Y_{DO}:C_y=g^{q_y(0)},C_y^{\prime }=H{(att(y))}^{q_y(0)}\}.$

2.  Compute $\tilde{C}=Me{(g,g)}^{\alpha s}$ and $C=h^s$, where M is the message.

3.  Send $C{T}_{DO},\tilde{C},C$ to the ESP:

$DO\stackrel{\{C{T}_{DO},\tilde{C},C\}}{\to }ESP.$

On receiving the message from the DO, ESP generates the following ciphertext:

$\begin{array}{cc}\hfill & CT=\langle \mathcal{T}={\mathcal{T}}_{ESP}\bigwedge {\mathcal{T}}_{DO};\tilde{C}=Me{(g,g)}^{\alpha s};C=h^s;\hfill \\ \hfill & \forall y\in Y_{ESP}\bigcup Y_{DO}:C_y=g^{q_y(0)};C_y^{\prime }=H{(\mathbf{att}(y))}^{q_y(0)}\rangle .\hfill \end{array}$

Finally, the ESP sends CT to the SSP.

C.2.3 Outsourcing Decryption

CP-ABE decryption algorithm is computationally expensive since bilinear pairing is an expensive operation. P-CP-ABE addresses this computation issue by outsourcing the expensive Pairing operations to the DSP. Again, the outsourcing will not expose the data content of the ciphertext to the DSP.

To protect the data content, the DO first blinds its private key by choosing a random $t\in {\mathbb{Z}}_p$ and then calculates $\tilde{D}=D^t=g^{t(\alpha +r)/\beta }$. We denote the blinded private key as $\widetilde{SK}$:

$\begin{array}{ccc}\hfill \widetilde{SK}& \hfill =\hfill & \langle \tilde{D}=g^{t(\alpha +r)/\beta },\hfill \\ \hfill & \hfill \hfill & \forall j\in S:D_j=g^r\cdot H{(j)}^{r_j},D_j^{\prime }=g^{r_j}\rangle .\hfill \end{array}$

Before invoking the DSP, the DO first checks whether its owned attributes satisfy the access policy $\mathcal{T}$. If so, the DO sends $\{\widetilde{SK}\}$ to the DSP, and requests the SSP to send the ciphertext to the DSP. On receiving the request, the SSP sends $C{T}^{\prime }=\{\mathcal{T};C=h^s;\forall y\in Y_1\bigcup Y_2:C_y=g^{q_y(0)};C_y^{\prime }=H{(\mathbf{att}(y))}^{q_y(0)}\}$ and $C{T}^{\prime }\subset CT$ to the DSP:

$SSP\stackrel{\{C{T}^{\prime }\}}{\to }DSP.$

Once the DSP receives both $\{\widetilde{SK}\}$ and $C{T}^{\prime }$, it then runs the $\mathbf{Decrypt}(\widetilde{SK},C{T}^{\prime })$ algorithm as follows:

1.  $\forall y\in Y=Y_{ESP}\bigcup Y_{DO}$, the DSP runs a recursive function $\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{r}\mathrm{y}\mathrm{p}\mathrm{t}\mathrm{N}\mathrm{o}\mathrm{d}\mathrm{e}(\mathrm{C}{\mathrm{T}}^{\prime },\widetilde{\mathrm{SK}},\mathrm{R})$, where R is the root of $\mathcal{T}$. The recursion function is the same as defined in [63] and $\mathrm{DecryptNode}(C{T}^{\prime },\widetilde{SK},y)$ is proceeded as follows:

$\begin{array}{cc}\hfill \mathrm{DecryptNode}(C{T}^{\prime },\widetilde{SK},y)& =\frac{e(D_i,C_y)}{e(D_i^{\prime },C_y^{\prime })}\hfill \\ \hfill & =\frac{e(g^r\cdot H{(i)}^{r_i},g^{q_y(0)})}{e(g^{r_i},H{(i)}^{q_y(0)})}\hfill \\ \hfill & =e{(g,g)}^{r{q}_y(0)}\hfill \\ \hfill & =F_y.\hfill \end{array}$

The recursion is processed as follows: ∀y which is a child of x, it calls $DecryptNode(C{T}^{\prime };\widetilde{SK};y)$ and stores the output as $F_y$. Let $S_x$ be an arbitrary $k_x$-sized set of children nodes y, the DSP computes:

$\begin{array}{cc}\hfill F_x& =\prod _{y\in S_x}{F}_y^{{\mathrm{\Delta }}_{i,S_x^{\prime }(0)}}\hfill \\ \hfill & =\prod _{y\in S_x}{(e{(g;g)}^{r\cdot q_y(0)})}^{{\mathrm{\Delta }}_{i;S_x^{\prime }}(0)}\hfill \\ \hfill & =\prod _{y\in S_x}{(e{(g;g)}^{r\cdot q_{\mathbf{parent}(y)(\mathbf{index}(y))}})}^{{\mathrm{\Delta }}_{i;S_x^{\prime }}(0)}\hfill \\ \hfill & =\prod _{y\in S_x}(e{(g;g)}^{r\cdot qx(i)\cdot {\mathrm{\Delta }}_{i;S_x^{\prime }}(0)}\hfill \\ \hfill & =e{(g,g)}^{r{q}_x(0)},\hfill \end{array}$

where $i=\mathbf{index}(z)$ and $S_x^{\prime }=\{\mathbf{index}(z):z\in S_x\}$, ${\mathrm{\Delta }}_{i;S_x^{\prime }}(0)$ is the Lagrange coefficient. Finally, the recursive algorithm returns $A=e{(g,g)}^{rs}$.

2.  Then, one computes

$e(C,\tilde{D})=e(h^s,g^{t(\alpha +r)/\beta })=e{(g,g)}^{trs}\cdot e{(g,g)}^{t\alpha s}.$

3.  And sends $\{A=e{(g,g)}^{rs},B=e(C,\tilde{D})=e{(g,g)}^{trs}\cdot e{(g,g)}^{t\alpha s}\}$ to the DO:

$DSP\stackrel{\{A,B\}}{\to }DO.$

On receiving $\{A,B\}$, DO calculates $B^{\prime }=B^{1/t}=e{(g,g)}^{rs}\cdot e{(g,g)}^{\alpha s}$ and then it recovers the message:

$M=\frac{\tilde{C}}{(B^{\prime }/A)}=\frac{Me{(g,g)}^{\alpha s}}{(e{(g,g)}^{rs}\cdot e{(g,g)}^{\alpha s})/e{(g,g)}^{rs}}.$