Consider there is a protocol in real world calling a random oracle $\mathcal{H}$ for a priavte input $k$. Then in the ideal world, after the calling of $r \leftarrow \mathcal{H}(k)$ by a honest party, can the simulator extract $k$ from $r$, if the behavior of $\mathcal{H}$ is as follows:

  • When $k$ is new, record $(k, r \leftarrow_R \{0,1\}^\lambda)$ in the inner storage and then return $r$;
  • When $k$ has been asked (by checking the inner storage), return the corresponding $r$.

I envisage to extract $k$ from $r$ also by checking the inner storage, but is it a correct usage of random oracle?


Yes, that is standard usage of a random oracle. The simulator gets to simulate the interface to the random oracle so it can record all queries made by the adversary and use this information to "invert" the random oracle.

In your example you must be sure that the simulation does something reasonable when the adversary outputs a value $r$ that is not the result of any call to the oracle.


Your Answer

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

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