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


$$\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.


1 Answer 1


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.