### Native CP-ABE by accessing control tree
#### 1. Setup.
The setup algorithm will choose a bilinear group $\mathbb{G}_0$ of prime order $p$ with generator $g$. Next it will choose two random exponents $\alpha, \beta \in \mathbb{Z}_p$. The public key is published as:
$$
\mathrm{PK}=\mathbb{G}_0, g, h=g^\beta, f=g^{1 / \beta}, e(g, g)^\alpha
$$
and the master key MK is $\left(\beta, g^\alpha\right)$. (Note that $f$ is used only for delegation.)
#### 2. Encrypt$(\mathbf{P K}, M, \mathcal{T})$.
The encryption algorithm encrypts a message $M$ under the tree access structure $\mathcal{T}$. The algorithm first chooses a polynomial $q_x$ for each node $x$ (including the leaves) in the tree $\mathcal{T}$. These polynomials are chosen in the following way in a topdown manner, starting from the root node $R$. For each node $x$ in the tree, set the degree $d_x$ of the polynomial $q_x$ to be one less than the threshold value $k_x$ of that node, that is, $d_x=k_x-1$

Starting with the root node $R$ the algorithm chooses a random $s \in \mathbb{Z}_p$ and sets $q_R(0)=s$. Then, it chooses $d_R$ other points of the polynomial $q_R$ randomly to define it completely. For any other node $x$, it sets $q_x(0)=q_{\text {parent }(x)}($ index $(x))$ and chooses $d_x$ other points randomly to completely define $q_x$.

Let, $Y$ be the set of leaf nodes in $\mathcal{T}$. The ciphertext is then constructed by giving the tree access structure $\mathcal{T}$ and computing
$$
\begin{aligned}
\mathrm{CT}= & \left(\mathcal{T}, \tilde{C}=M e(g, g)^{\alpha s}, C=h^s\right. \\
& \left.\forall y \in Y: \quad C_y=g^{q_y(0)}, C_y^{\prime}=H(\operatorname{att}(y))^{q_y(0)}\right)
\end{aligned}
$$
#### 3. KeyGen$(\mathbf{M K}, S)$.
The key generation algorithm will take as input a set of attributes $S$ and output a key that identifies with that set. The algorithm first chooses a random $r \in \mathbb{Z}_p$, and then random $r_j \in \mathbb{Z}_p$ for each attribute $j \in S$. Then it computes the key as
$$
\begin{aligned}
\mathrm{SK}= & \left(D=g^{(\alpha+r) / \beta},\right. \\
& \left.\forall j \in S: \quad D_j=g^r \cdot H(j)^{r_j}, D_j^{\prime}=g^{r_j}\right) .
\end{aligned}
$$
#### 4. Delegate(SK, $\tilde{S})$.
The delegation algorithm takes in a secret key SK, which is for a set $S$ of attributes, and another set $\tilde{S}$ such that $\tilde{S} \subseteq S$. The secret key is of the form $\mathrm{SK}=\left(D, \forall j \in S: D_j, D_j^{\prime}\right)$. The algorithm chooses random $\tilde{r}$ and $\tilde{r}_k \forall k \in \tilde{S}$. Then it creates a new secret key as
$$
\begin{aligned}
& \mathrm{SK}=\left(\tilde{D}=D f^{\tilde{r}},\right. \\
&\left.\forall k \in \tilde{S}: \quad \tilde{D}_k=D_k g^{\tilde{r}} H(k)^{\tilde{r}_k}, \tilde{D}_k^{\prime}=D_k^{\prime} g^{\tilde{r}_k}\right)
\end{aligned}
$$
The resulting secret key SK is a secret key for the set $\tilde{S}$. Since the algorithm re-randomizes the key, a delegated key is equivalent to one received directly from the authority.

#### 5. Decrypt(CT, SK).
We specify our decryption procedure as a recursive algorithm. For ease of exposition we present the simplest form of the decryption algorithm and discuss potential performance improvements in the next subsection.

We first define a recursive algorithm DecryptNode $(\mathrm{CT}, \mathrm{SK}, x)$ that takes as input a ciphertext $\mathrm{CT}=\left(\mathcal{T}, \tilde{C}, C, \forall y \in Y: C_y, C_y^{\prime}\right)$, a private key SK, which is associated with a set $S$ of attributes, and a node $x$ from $\mathcal{T}$.

If the node $x$ is a leaf node then we let $i=\operatorname{att}(x)$ and define as follows: If $i \in S$, then
$$
\begin{aligned}
\text { DecryptNode }(\mathrm{CT}, \mathrm{SK}, x) & =\frac{e\left(D_i, C_x\right)}{e\left(D_i^{\prime}, C_x^{\prime}\right)} \\
& =\frac{e\left(g^r \cdot H(i)^{r_i}, h^{q_x(0)}\right)}{e\left(g^{r_i}, H(i)^{q_x(0)}\right)} \\
& =e(g, g)^{r q_x(0)} .
\end{aligned}
$$
If $i \notin S$, then we define DecryptNode(CT, SK, $x)=\perp$.
We now consider the recursive case when $x$ is a non-leaf node. The algorithm DecryptNode(CT, SK, $x)$ then proceeds as follows: For all nodes $z$ that are children of $x$, it calls DecryptNode $(C T, \mathrm{SK}, z)$ and stores the output as $F_z$. Let $S_x$ be an arbitrary $k_x$-sized set of child nodes $z$ such that $F_z \neq \perp$. If no such set exists then the node was not satisfied and the function returns $\perp$.
Otherwise, we compute
$$
\begin{aligned}
& F_x=\prod_{z \in S_x} F_z^{\Delta_{i, S_x^{\prime}}(0)}, \quad \text { where }{ }_{S_x^{\prime}=\left\{\operatorname{index}(z): z \in S_x\right\}}^{i=\operatorname{index}(z)} \\
& =\prod_{z \in S_x}\left(e(g, g)^{r \cdot q_z(0)}\right)^{\Delta_{i, S_x^{\prime}}(0)} \\
& =\prod_{z \in S_x}\left(e(g, g)^{r \cdot q_{\mathrm{parent}(z)}(\operatorname{index}(z))}\right)^{\Delta_{i, s_x^{\prime}}(0)} \text { (by construction) } \\
& =\prod_{z \in S_x} e(g, g)^{r \cdot q_x(i) \cdot \Delta_{i, S_x^{\prime}}(0)} \\
& =e(g, g)^{r \cdot q_x(0)} \quad \text { (using polynomial interpolation) } \\
&
\end{aligned}
$$
and return the result.

Now that we have defined our function DecryptNode, we can define the decryption algorithm. The algorithm begins by simply calling the function on the root node $R$ of the tree $\mathcal{T}$. If the tree is satisfied by $S$ we set $A=$ DecryptNode(CT, SK, $r)=$ $e(g, g)^{r q_R(0)}=e(g, g)^{r s}$. The algorithm now decrypts by computing
$$
\tilde{C} /(e(C, D) / A)=\tilde{C} /\left(e\left(h^s, g^{(\alpha+r) / \beta}\right) / e(g, g)^{r s}\right)=M \text {. }
$$

### Variant Keygen using threshold scheme
1. Setup.
user are responsible for the first setup, and the PK is
$$
\mathrm{PK}=\mathbb{G}_0, g, h=g^\beta, e(g, g)^\alpha
$$

the master key MK is $\left(\beta, g^\alpha\right)$. (removing $f$ to stop derivation of child key)

2. Delegate
user use tss $\frac{t \ threshold}{n \ party}$ scheme to calculate party number shares of threshold usage $1/ \beta$, and party number shares of $\alpha$. That is to say after preparation t parties will hold shares whose sum will be $\alpha$ or $1/ \beta$.

The share of party $i$ is defined as $\alpha_i$ and ${(1/ \beta)}_i$, where $i \in 0,1,2\cdots,t$.

3. KeyGen
#### preparation
* Buyer $B$ select $t$ party as manager node set $T$ and send them his $PK$.
* Each manager node $i$ prepares and get their $\alpha_i$ and ${(1/ \beta)}_i$.
* Each manager node $i$ select master major key randomness vector $R_{mi}=\{r_{ik}: k \in T\}$.
* Each manager node $i$ select attribute randomness vector $R_{si}=\{r_{ijk}:j \in S, k \in T\}$
#### calculate $(\alpha + r)*(1/\beta)$ share
* Each manager node swap $r_{mi}$ to fomulize $r_i$, for party $i$ we have:
$$
r_i = \sum_{j \in T}{r_{ji}}
$$
* all $r_i$ sum are considered to be origin $r$ in the native scheme of CP-ABE.
* Each manager node $i$ get $\theta_i$ by adding $\alpha_i$ and $r_i$, we have $\theta_i = \alpha_i + r_i$ . And $\theta = \sum\theta_i$.

* note that fomula exists:
$$
\theta*(1/\beta) = \sum_{i=1}^t\theta_i(1/ \beta)_i + \sum_{i \ne j, i \in T, j \in T}\theta_i(1/ \beta)_j
$$

* using $MTA$ each manager node $i$ can get a share of $\theta*(1/\beta)$ which we define as $\gamma_i$.

#### send major key to buyer
* Each manager node send $enc(g^{\gamma_i})$ to buyer, using an encryption by buyers' $PK$.
* buyer decrypt each manager node's response, and adding the $g^{\gamma_i}$ to form the $g^\gamma$ which is to say $g^{\theta/\beta}$ which is to say $g^{(\alpha+r)/\beta}$ as $D$ in $SK$.

#### calculate $g^{r_j}$ share
* Each manager node $i$ communicate with each node with their $r_si$, for example $r_{i00}$ is representing share of $attribute \ 0$ and sent to $manager \ node \ 0$.
* Each manager node $i$ calc $\sum_{q \in T} g^{r_{qji}}$ as $\delta_{ij}$ and send to buyer.

#### send attribute key to buyer
* Each manager node send $enc(\delta_{ij})$ to buyer, using an encryption by buyers' $PK$.
* for each attribute $j \in S$, buyer $B$ sums $\delta_{ij}$ to get the $g^{r_j}$ as $D_j^{\prime}$.

#### calculate $g^r \cdot H(attr(y))^{r_j}$ share
* Each manager node $i$ communicate with each node with their $r_si$, for example $r_{i00}$ is representing share of $attribute \ 0$ and sent to $manager \ node \ 0$.
* Each manager node $i$ calc $\sum_{q \in T} H(attr(y))^{r_{qji}} \cdot g^{r_i}$ as $\epsilon_{ij}$.

#### send attribute key to buyer
* Each manager node send $enc(\epsilon_{ij})$ to buyer, using an encryption by buyers' $PK$.
* for each attribute $j \in S$, buyer $B$ sums $\epsilon_{ij}$ to get the $g^r \cdot H(attr(y))^{r_j}$ as $D_j$.