# Question on Waters IBE

I'm reading “Efficient Identity-Based Encryption Without Random Oracles” by Brent Waters.

In Page 9, I don't know how $$\mathcal{P}_{BDH}=\Pr[\beta'=1]=\Pr[\beta'=1|\textbf{abort}]\Pr[\textbf{abort}]+\Pr[\beta'=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}]$$

becomes $$\mathcal{P}_{BDH}=\frac{1}{2}+\frac{1}{2}(\Pr[\overline{\textbf{abort}}|\gamma'=\gamma]\Pr[\gamma'=\gamma]-\Pr[\overline{\textbf{abort}}|\gamma'\neq\gamma]\Pr[\gamma'\neq\gamma])$$  Since

$$\Pr[\beta'=1|\textbf{abort}]=\frac{1}{2},$$

$$\mathcal{P}_{BDH}=\frac{1}{2}\Pr[\textbf{abort}]+\Pr[\beta'=1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}]$$ I can't not follow after that. Please help me to understand what Waters said.

It's been a while since I've read this paper, and I remember having a lot of trouble with this derivation. I'm sure there is an easy way to see it, but I don't see it, so I'll just brute force through with the algabra.

First, some context:

When the simulator is given a random element as the last term in the tuple the simulator will either abort (and guess $\beta' = 1$ with probability $\frac12$) or guess $\beta' = 1$ [exactly] when the adversary is correct in guessing $\gamma$. However, the $\gamma$ will be completely hidden from the adversary in this case so the adversary will be correct with probability $\frac12$.

I have added the word exactly because actually if the simulator doesn't abort, then $\beta' = 1$ iff $\gamma = \gamma'$. This is seen in the simulator description at the end of section 5.1.

We'll start from your simplified expression for $\mathcal{P}_{BDH}$. We then have \begin{align*} \mathcal{P}_{BDH} &= \frac12\Pr[\textbf{abort}] + \Pr[\beta' = 1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] \\ &= \frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\Pr[\overline{\textbf{abort}}] \end{align*}

For the non-aborting case, we know that $\beta' = 1$ if $\gamma = \gamma'$. So if split the case $\overline{\textbf{abort}}$ into two, $(\overline{\textbf{abort}} \land \gamma = \gamma')$ and $(\overline{\textbf{abort}} \land \gamma \neq \gamma')$, we get

\begin{align*} \Pr[\overline{\textbf{abort}}] &= \Pr[\overline{\textbf{abort}}] \\ &= (\Pr[\overline{\textbf{abort}}|\gamma = \gamma']\Pr[\gamma = \gamma'] + \Pr[\overline{\textbf{abort}}|\gamma\neq\gamma']\Pr[\gamma\neq\gamma']) \end{align*}

Since the adversary has no knowledge of $\gamma$, we may set $\Pr[\gamma=\gamma'] = \frac12 +\epsilon$ (and therefore $\Pr[\gamma\neq\gamma'] = \frac12-\epsilon$). This gets us $$\Pr[\textbf{abort}] = \Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon) + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)$$ so our total probability is $$\frac12 + \left(\Pr[\beta' = 1|\overline{\textbf{abort}}] - \frac12\right)\left(\Pr[\overline{\textbf{abort}}|\gamma = \gamma'](\frac12 + \epsilon) + \Pr[\overline{\textbf{abort}}|\gamma \neq \gamma'](\frac12 - \epsilon)\right)$$

So far so good. Here's where the silly algebra comes in: let's rename these big terms as $$\frac12 + (A - \frac12)(B + C)$$ and notice that the desired form, with these new names, is $$\frac12 + \frac12(B - C)$$

Next, notice that $$A = \Pr[\beta' = 1|\overline{\textbf{abort}}] = \frac{\Pr[\beta' = 1 \land \overline{\textbf{abort}}]}{\Pr[\overline{\textbf{abort}}]} = \frac{B}{B + C}$$ so that \begin{align*} (A - \frac12)(B + C) &= \left(\frac{B}{B + C} - \frac12\right)(B + C) \\ &= \left(\frac{2B - B - C}{2B + 2C}\right)(B + C) \\ &= \frac12(B - C) \end{align*} and there you go!