Some misunderstanding on the Security Proof with Oracle

filter hash

4/16/23, 1:15 PM

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}$?

0 + 0

cryptanalysis

provable-security

Score:0

Crypto

Ievgeni

4/16/23, 1:21 PM

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

0 + 0

filter hash

4/16/23, 1:25 PM

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.

Ievgeni

4/16/23, 1:29 PM

No it depends about your proof about the inequality work.

filter hash

4/16/23, 1:37 PM

Thanks. As I understood, sometimes B is broken, and sometimes B is still secure. Is there an example?

Ievgeni

4/16/23, 1:53 PM

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).

filter hash

4/17/23, 1:28 AM

Thanks. I will find some examples.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Some misunderstanding on the Security Proof with Oracle

TH: ความเข้าใจผิดบางประการเกี่ยวกับ Security Proof กับ Oracle

RO: O neînțelegere cu privire la dovada de securitate cu Oracle

RU: Некоторое недопонимание в отношении Security Proof с Oracle

VI: Một số hiểu lầm về Chứng minh bảo mật với Oracle

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.