In "Simulation without the artificial abort: Simplified proof and improved concrete security for Waters' IBE scheme", Bellare and Ristenpart present a new proof for Waters' IBE scheme that does not use the artificial abort technique. As in the original proof, the authors define an adversary $\mathcal B$ that breaks the DBDH problem using an adversary $\mathcal A$ that wins the IND-CPA security game of Waters' IBE scheme.

I'm studying the proposed security proof, and in page 10 it states the following:

We note that our adversary in fact never aborts. Sometimes, it is clearly returning incorrect answers (namely $\perp$) to $\mathcal A$’s queries. Adversary $\mathcal A$ will recognize this, and all bets are off as to what it will do. Nonetheless, $\mathcal B$ continues the execution of $\mathcal A$. Our analysis will show that $\mathcal B$ has the claimed properties regardless.

I don't understand how if adversary $\mathcal A$ can detect sometimes that the answers to her queries are incorrect, this does not imply that $\mathcal B$ cannot use $\mathcal A$ anymore.

In general, what is the implication of an adversary detecting incorrect answers from the simulator, assuming that this happens with non-negligible probability?

  • $\begingroup$ I have not studied this particular proof (hence this is not an answer), but it not uncommon to run an algorithm on an input without knowing what its output will be; another context where this happens is in the hybrid method (see for example the proof that a pseudorandom generator with expansion factor $n+1$ is sufficient to construct a pseudorandom generator with any polynomial expansion factor). The idea is that the analysis remains valid no matter what $\mathcal{A}$ outputs, so the fact that we do not know what it outputs is not a problem. $\endgroup$ – fkraiem Jun 30 '16 at 9:56
  • 1
    $\begingroup$ Note that in a reduction to an underlying primitive, B doesn't have to succeed with the same probability as A, and may sometimes fail. This may be what is happening here. $\endgroup$ – Yehuda Lindell Jun 30 '16 at 18:48

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.