CNS - 45 - CP-ABE

In this new scheme we have:

• Public key (PK):

  \[\text{PK} = (g, g^{\beta}, e(g, g)^{\alpha})\]

• Master Private Key (MSK):

  \[\text{MSK} = (\beta, g^{\alpha})\]

where \(\alpha, \beta \in \mathbb{Z}_p\) are choosen randomly.

Every attribute is given as a string \(x_1, x_2, \ldots, x_n \in \{0, 1\}^*\), and for each attribute a random quantity is generated as well as another single random value \(r, r_{x_1}, r_{x_2}, \ldots, r_{x_n} \in \mathbb{Z}_p\). The idea is to use such value \(r\) to bind these attributes together, so that you cannot mix attributes from different keys.

The private key generates is the following

\[\begin{split} \text{SK} = \Big( &g^{(\alpha + r)/\beta}, \\ &\,\,\, g^{r} \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}, \\ &\,\,\, \vdots \\ &\,\,\, g^{r} \cdot H(x_n)^{r_{x_n}}, g^{r_{x_n}}\Big) \\ \end{split}\]

Consider now that someone wants to encrypt some data and wants to make such that that data can be decrypted only by those who have both \(x_1\) and \(x_2\) in their attributes.

The idea is to generate two random values \(s\) and \(d\) and two shares, \(s_1 = s - d\) and \(s_2 = d\) and for each attribute \(x_j\) the following ciphertext is created

\[C_j = g^{s_j}, H(x_j)^{s_j}\]

Then, for the whole message I compute

\[C = g^{\beta \cdot s}, \,\,\, \tilde{C} = M \cdot e(g, g)^{\alpha \cdot s}\]

Suppose now we want to decrypt and let us assume that we have all the attributes required to do so. For each attribute the user has we have that:

• In the ciphertext there is

  \[C_j = g^{s_j}, H(x_j)^{s_j}\]

• In the secret key of the user there is instead

  \[D_j = g^{r_{x_j}}, g^r \cdot H(x_j)^{r_{x_j}}\]

This means that we can do the following

\[\frac{e(g^r \cdot H(x_j)^{r_{x_j}}, \,\,\,\, g^{s_j})}{e(g^{r_{x_j}}, \,\,\,\, H(x_j)^{s_j})} g= \frac{e(g^{r}, \,\,\, g^{s_j}) \cdot e(H(x_j)^{r_{x_j}}, \,\,\,\, g^{s_j})}{e(g^{r_{x_j}}, \,\,\, H(x_j)^{s_j})} = e(g, g)^{r \cdot s_j}\]

since

\[\begin{split} e(a \cdot b, g) &= e(g^{\alpha} \cdot g^{\beta}, g) \\ &= e(g, g)^{\alpha + \beta} \\ &= e(g, g)^{\alpha} \cdot e(g, g)^{\beta} \\ &= e(g^{\alpha}, g) \cdot e(g^{\beta}, g) \\ &= e(a, g) \cdot e(b, g) \\ \end{split}\]

Notice that at the end of this step we came out with \(e(g, g)^{r \cdot s_j}\), which is a value that depends on a value related to the user \((r)\) and on one share of the secret \((s_j)\). Now that we have extracted the share of the secret associated to the attribute \(x_j\), to put these shares together in the case of a simple AND policy we can just multiply terms

\[A = \prod e(g, g)^{r \cdot s_j} = e(g, g)^{r \cdot (s - d)} \cdot e(g, g)^{r \cdot d} = e(g, g)^{r \cdot s}\]

For more general policies we can simply use the access matrix we discussed in a previous lecture regarding linear secret sharing techniques.

To continue our decryption, since our message was encrypted was \(M \cdot e(g, g)^{\alpha \cdot s}\), and since we only have \(e(g, g)^{r \cdot s}\), we now need to replace the exponent from \(r\) to \(\alpha\). Notice however that our user doesn't know \(r\), for otherwise he/she could cheat and give his/her own \(r\) to another person. To do this we use the two global informations \(C\) and \(\tilde{C}\) and the value present in our private key \(D = g^{(\alpha + r)/\beta}\). By combining these values we get

\[\begin{split} \frac{\tilde{C}}{e(C, D)/A} &= \frac{M \cdot e(g, g)^{\alpha s}}{e(g^{\beta s}, g^{(\alpha + r)/\beta})/ e(g, g)^{r s}} \\ &= M \cdot \frac{e(g, g)^{\alpha s}}{e(g, g)^{\beta s (\alpha + r) / \beta} / e(g, g)^{r s}} \\ &= M \cdot \frac{e(g, g)^{\alpha s}}{e(g, g)^{s \alpha} \cdot e(g, g)^{s r} / e(g, g^{r s})} \\ &= M \cdot \frac{\cancel{e(g, g)^{\alpha s}}}{\cancel{e(g, g)^{s \alpha}} \cdot \cancel{e(g, g)^{s r}} / \cancel{e(g, g^{r s})}} \\ &= M \end{split}\]