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}
  &amp;= \frac12\Pr[\textbf{abort}] + \Pr[\beta' = 1|\overline{\textbf{abort}}]\Pr[\overline{\textbf{abort}}] \\
  &amp;= \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}}]
  &amp;= \Pr[\overline{\textbf{abort}}] \\
  &amp;= (\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)
  &amp;= \left(\frac{B}{B + C} - \frac12\right)(B + C) \\
  &amp;= \left(\frac{2B - B - C}{2B + 2C}\right)(B + C) \\
  &amp;= \frac12(B - C)
\end{align*}$$
and there you go!