4
$\begingroup$

I am analyzing the Bethencourt CP-ABE model to understand the math behind it. If a data user is able to satisfy the access policy attached to the ciphertext, that user is able to decrypt the encrypted message.

This is made possible because the data user can calculate:

$$e(g,g)^{rq_{x}(0)}$$

We know that:

$$q_{x}(0) = s$$

Where:

$$s \in Z_P$$

Is it in any way possible for the data user to calculate the value of this secret $s$ if he/she can satisfy the access policy or is it made so that the data user can never be able to obtain this value?

$\endgroup$
  • $\begingroup$ It depends on the scheme. I think I've seen schemes where it is possible (if I remember correctly, those used CNF/DNF policies instead of tree policies). I don't think it's possible in the Bethencourt scheme. $\endgroup$ – Artjom B. Dec 11 '16 at 19:19
  • $\begingroup$ @ArtjomB. I tried calculating (๐‘’(๐ถ,๐ท))/(๐‘’(๐‘”,๐‘”)^(๐‘Ÿ๐‘  ) ) which would then result with ๐‘’(๐‘”, ๐‘”)^(๐›ผ๐‘  ) and since we already publicly know ๐‘’(๐‘”, ๐‘”)^(๐›ผ) can't we from there calculate s as ๐‘’(๐‘”, ๐‘”)^(๐›ผ๐‘ ) / ln [๐‘’(๐‘”, ๐‘”)^(๐›ผ)]. I am not sure though if this is actually going to work, but the math seems right. $\endgroup$ – user40428 Dec 11 '16 at 20:17
  • $\begingroup$ No, you can't. This is actually the discrete logarithm problem. You can compute $e(g, g)^s$ but you cannot easily compute $s$ from that. $\endgroup$ – Artjom B. Dec 11 '16 at 20:27
1
$\begingroup$

Extracting $s$ in this case would seem to be equivalent for the discrete log problem in the bilinear group $\mathbb{G}_0$, using the Bethencourt CP-ABE paper notation.

To see this, first consider that if you can solve DLP in $\mathbb{G}_0$, then obviously you can solve $s$ from the ciphertext component $C=h^s$, as $h$ is already known (part of the public key).

The other direction follows from that if we assume an algorithm $\mathcal A$ capable of extracting $s$, given the global public key $PK$, ciphertext $CT$, and a secret key $SK$ capable of decrypting $CT$ according to the scheme, we can also use this algorithm to compute a discrete logarithm in $\mathbb{G}_0$.

We can use $\mathcal A$ as follows:

  • First assume that we know, which message, attribute-set and policy-formula $\mathcal A$ is able to "break". Call these $M,S$ and $\mathcal{T}$, respectively.
  • Assume $\mathcal A$ takes as input a set $\{PK, CT, SK\}$, and outputs $s \in \mathbb{Z}_P$
  • Now, given $g, g^s \in \mathbb{G}_0$, where $s$ is unknown, and $g$ is a generator of $\mathbb{G}_0$, we can construct $PK=\{g,g^\beta, g^{1/\beta}, e(g,g)^\alpha \}$ simply by passing $g$ as such and selecting $\alpha, \beta \in \mathbb{Z}_P$ randomly, as stated by the scheme. We can also construct $SK=\{g^{(\alpha+r)\beta},\{g^rH(j)^{r_j},g^{r_j}\}_{j \in S}\}$ similarly, as we have already selected $\alpha, \beta$. We also select randomly $r$ and $r_j$ to match $S$.
  • Constructing $CT$ is trickier, since it involves handling $s$, which is unknown to us, but needs to be conformant to the scheme in the eyes of $\mathcal A$. First part of $CT$ is $\mathcal{T}$, which we simply replace from what we know of $\mathcal A$. The second part is $C^o=Me(g,g)^{\alpha s}$, which we can construct, since we know $g,\alpha, g^s$ and $e(g^\alpha,g^s)=e(g,g)^{\alpha s}$. The third part is $C=h^s = (g^s)^\beta$, again elements we know or have created. The fourth part, $\{C_y,C'_y\}_{j \in S}$ (leaf-node shares in the exponents of both $g$ and the attribute hashes) requires knowing the (secret) shares for $s$. Constructing this depends on the realization that the shares and their polynomials per each node are created randomly, independently of $s$. They are only tied to $s$ by making, for example, $q_{x_1}(0)=q_R(1)$, where $q_R()$ is the polynomial of the root node (and $q_R(0)=s$) and $q_{x_1}()$ is the polynomial for the root's child $x_1$. We can then freely select other polynomial interpolation points randomly and calculate the required $C_y=g^{q_y(0)}$ and $C'_y=H(att(y))^{q_y(0)}$. It doesn't matter that we don't know $s$, as $\mathcal A$ is responsible for the possible decryption, and the interpolation points are selected independently of $s$, even though they are later connected to $s$.
$\endgroup$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy