The security proof for Key Policy Attribute Based Encryption

Question

My question relates to the original KP-ABE paper:

http://research.microsoft.com/en-us/um/people/vipul/abe.pdf

I'm having trouble understanding the proof (pages 10–13) that the scheme is secure in the Selective Set Model:

Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\epsilon/2$. The simulation proceeds as follows:

We first let the challenger set the groups G1 and G2 with an efficient bilinear map, e and generator g. The challenger fips a fair binary coin $\mu$, outside of B's view. If $\mu = 0$, the challenger sets $(A, B, C, Z) = (g^a,g^b,g^c,e(g,g)^{abc})$, otherwise it sets $(A, B, C, Z) =(g^a, g^b, g^c, e(g,g)^z)$ for random $a, b, c, z$. We assume the universe, U is defined.

...

Phase 1 A adaptively makes requests for the keys corresponding to any access structures T such that the challenge set $\gamma$ does not satisfy T . Suppose A makes a request for the secret key for an access structure T where $T(\gamma) = 0$. To generate the secret key, B needs to assign a polynomial $Q_x$ of degree $d_x$ for every node in the access tree T .

We first define the following two procedures: PolySat and PolyUnsat.

PolySat$(T_x,\gamma,{\lambda_x})$ : ....

PolyUnsat$(T_x,\gamma, g^{\lambda_x})$: This procedure sets up the polynomials for the nodes of an access tree with unsatisfied root node, that is, $T_x(\gamma) = 0$. The procedure takes an access tree $T_x$ (with root node x) as input along with a set of attributes $\gamma$ and an element $g^{\lambda_x} \in G1$ (where $\lambda_x \in Z_p$). It first defines a polynomial $q_x$ of degree $d_x$ for the root node $x$ such that $q_x(0) = \lambda_x$. Because $T_x(\gamma) = 0$, no more than $d_x$ children of $x$ are satisfied. Let $h_x \leq d_x$ be the number of satisfied children of $x$. For each satisfied child $x'$ of $x$, the procedure chooses a random point $\lambda_{x'} \in Z_p$ and sets $q_x(index(x')) = \lambda_{x'}$. It then fixes the remaining $d_x - h_x$ points of $q_x$ randomly to completely define $q_x$.

...

To give keys for access structure $T$, simulator first run PolyUnsat$(T,\gamma,A)$ to define a polynomial $q_x$ for each node $x$ of $T$.

...

My question is relating to the last (bold) paragraph: How is it possible to define such $q_x$, since the simulator cannot learn $\lambda_{x}$ from $g^{\lambda_x}$ unless he can compute discrete log?

Answer 1

Because the simulator picked $\gamma$ to generate $g^\gamma$. He acts as an ABE authority for an attacker who breaks the Selective Set Model security game so he can use the attacker to solve the Decisional Bilinear Diffie-Hellman problem .

As a result of being the ABE authority, the simulator knows the master secrets and all other secrets created by the ABE authority. Remember, that for normal ABE, the authority knows everything, including user's private keys (attributes).

Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\frac{\epsilon}{2}$. The simulation proceeds as follows:

We first let the challenger set the groups G1 and G2 with an efcient bilinear map, e and generator g. The challenger flips a fair binary coin $\mu$, outside of B's view. If $\mu$ = 0, the challenger sets $(A; B; C; Z) = (g^a, g^b, g^c, e(g, g)^{abc} )$ otherwise it sets $(A; B, C,Z) = (g^a, g^b,g^c, e(g, g)^z)$ for random $a, b, c, z$. We assume the universe, $U$ is defined.

The simulator, then, gets to set up an ABE system so he can use the attacker

The simulator B runs A. A chooses the set of attributes $\gamma$ it wishes to be challenged upon

$\gamma$ has nothing to do with the DBLDH assumption.

Answer 2

I have managed to figure out the answer to my own question, so I thought I would share it here, in case someone else would encounter the same problem.

The set-up of the simulator $B$ is so that it simulates a challenger in the game with $A$, in which the challenger has the master secret $ab$, where $g^a, g^b$ are given as inputs of the BDDH game. Now of course $B$ cannot learn $a$, $b$, or $ab$, but it can construct private key for an access tree $T$ that implicitly shares the secret $ab$.

The PolyUnsat$(T_x,\gamma,g^a)$ is called to split the secret $a$ to shares such that their combination that satisifies $T_x$ will recover $a$. Notice that $T_x(\gamma)=0$.

It first defines a polynomial $q_x$ of degree $d_x$ for the root node x such that $q_x(0)=a$

Now that is easy, because $g^{q_x(0)}=g^a$ which is given as input. To completely define $q_x$, it needs another $d_x$ points. It can do that by assigning: $g^{q_x(i)}=g^{\alpha_i}$ for a random $\alpha_i \in Z_q$. Notice that $B$ does not knows $q_x$, but defining it this way makes sure that it can compute $g^{q_x(j)}$ for any $j$ (using Lagrange interpolation), and that $g^{q_x(0)} = g^a$. So implicitly, it has split the secret $a$ (unknown to itself) to shares so that they can be combined to recover $g^a$.

For each child node $x'$ which is not a satisfied node, the algorithm calls $PolyUnsat(T_{x'},\gamma,g^{q_x(index(x'))})$

Now this can be easily done, because $g^{q_x(index(x'))}$ can be computed from $\{g^a, g^{q_x(0)}, g^{q_x(1)}, ..\}$ using interpolation.

The key corresponding the each leaf node is given using its polynomial as follows:

$D_x = g^{b.q_x(0)/r_i}$ if $x \in \gamma$

In this case, $B$ knows $q_x(0)$ but does not know $b$. However, $D_x = (g^b)^{q_x(0)/r_i}$ can be computed because $g^b$ is given and that $q_x(0)/r_i$ is known since $1/r_i$ is known in $Z_q$.

$D_x = g^{q_x(0)/\beta_i}$ if $x \notin \gamma$

This is also computable, since $g^{q_x(0)}$ is known (not $q_x(0)$), and so is $1/\beta_i$.

These share are valid, because for any secret $s$, we can have the following valid ciphertext: $E = \langle\gamma, E' = m.e(g^a,g^b)^s, \{E_i = g^{s.r_i} | i \in \gamma\} \ \cup \ \{E_i = (g^b)^{s.\beta_i} | i \notin \gamma\}\rangle$. Furthermore, all $D_x$ are uniformly distributed, so they have the same distribution as in the original game.

Finally, to simulate the BDDH game, upon a challenge $\{m_0,m_1\}$, the simulator will toss the coin and set $E' = g^h, \{E_i = (g^c)^{r_i}\}$. If $A$ guesses it correctly, then $g^h = g^{abc}$, and the simulator wins the BDDH game.