Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states:

Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A simulator is constructed that can distinguish a DBDH element from a random element with advantage $\frac{\varepsilon}{2}$.

Why is the advantage of the simulator ($\frac{\varepsilon}{2}$) half of that the adversary ($\varepsilon$)?

  • $\begingroup$ The link to your second paper is broken. Did you mean this one? In the first link, I didn't see the bound explicitly listed, but I did in this paper which has a similar title. Is this right? $\endgroup$ – user47922 Jun 3 '17 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.