I have a question about the security proof. Suppose that I proved the following relations. That is, I proved that $Adv_A \le Adv_A^{O} \le Adv_B$, where A,B are some cryptographic schemes and O is an oracle. I also suppose that the oracle O has a very strong property. For example, the O can solve DLP in polynomial time.

On the other hand, there is an attacker $\mathcal{A}$ which can break the scheme A. That is, $Adv_A$ is not negligible in the security parameter.

Even though $Adv_B$ is also non-negligible, but we do not have the oracle O. In this setup, how to break the scheme B using $\mathcal{A}$?


1 Answer 1


You have to look in more details the proof of the inequality $Adv^{O}_A \leq Adv_B$.

The proof will give you explicitly how to construct $\mathcal{B}$ from $\mathcal{A}^O$. It should be written how to simulate the experiment with $A$ and the powerful oracle $O$, by only having interaction with the experiment with $B$. And how to use the output of $\mathcal{A}$ to win the game against $B$.

  • $\begingroup$ You mean that it depends on how to construct the game? I do not have the concrete example. I am just curious about this case. $\endgroup$ Dec 16, 2021 at 13:25
  • $\begingroup$ No it depends about your proof about the inequality work. $\endgroup$
    – Ievgeni
    Dec 16, 2021 at 13:29
  • $\begingroup$ Thanks. As I understood, sometimes B is broken, and sometimes B is still secure. Is there an example? $\endgroup$ Dec 16, 2021 at 13:37
  • $\begingroup$ No, if A is broken then B is also broken, but the way to Break B depends about the proof of the inequality (and the way to break A). $\endgroup$
    – Ievgeni
    Dec 16, 2021 at 13:53
  • $\begingroup$ Thanks. I will find some examples. $\endgroup$ Dec 17, 2021 at 1:28

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.