When proving a Crypto scheme security under random oracle model, is the random oracle always controlled by the challenger?

What if the Hash is only used by the adversary?

  • $\begingroup$ What do you mean by "control"? Do you mean programmability that allows a challenger to program the table of the hash function? Or, observability? $\endgroup$ – xagawa Mar 24 '14 at 6:34
  • $\begingroup$ @xagawa Thx for your question, maybe you can see this paper.In this paper page11, line19, "and H1 is a random oracle controlled by B as describred above".I say "controll"just alike with that. $\endgroup$ – Jiangtao LI Mar 24 '14 at 13:11

As @xagawa mentioned in his comment, it depends on what you mean by "controled".

In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are consistent (identical answers to identical queries) and that the distribution of the answers are uniformly random to the adversary.

Such reductions are the ones typically used for reductionists proofs in the ROM, as it nicely allows the reduction to embed a problem instance into the adversaries queries to make the reduction work.

Typically, the random oracle is also observable, i.e., besides the programmability, the reduction "sees" all oracle queries and thus knows how much queries the adversary has made to the random oracle.

There are also works investigating non-observable reductions, where the random oracle is external to the adversary and the reduction. But they still can provide some means of programmability as the reduction can decide on the turing-machine that is used for the external oracle. In the linked paper you find some results for non-observable but programmable random oracles and also some examples for reductions in the ROM that also work if the observability is removed.

There is also the possibiltiy to have reductions in the ROM which are non-programmable and non-observable, but this enormously reduces the power that the ROM provides you in reductionists proofs.

| improve this answer | |
  • $\begingroup$ There are lots of instances in which the reduction "decides about ... oracle query". $\:$ However, I've never seen an instance in which the challenger "decides about ... oracle query". $\;\;\;\;$ $\endgroup$ – user991 Mar 24 '14 at 10:14
  • $\begingroup$ @RickyDemer Thats a bit imprecise in my answer. I mean the simulation of the challenger in the reduction. Thx, I will correct it to reduction. $\endgroup$ – DrLecter Mar 24 '14 at 10:15
  • $\begingroup$ Why "reduction" in brackets ? "In the case of using a programmable random oracle, yes, the challenger (reduction) decides about what to return as answer to an oracle query". A reduction is not an algorithm that allows to build an adversary ? $\endgroup$ – Dingo13 Mar 24 '14 at 10:18
  • $\begingroup$ Please feel free to edit the question if there is a clearer wording. $\endgroup$ – DrLecter Mar 24 '14 at 10:23

Firstly, I should clarify: I am just referring to the standard definition of a random oracle. There are other scenario's (better discussed in DrL's answer), but these tend to be explicitly referred to. That is, if you have a standard 'random oracle', this answer should hold. On the other hand, if you have a different type of oracle, this won't hold.

A random oracle is an oracle that, when presented with a bitstring $x$, returns a bitstring $y$ that is either randomly generated (if $x$ is new) or the same as it returned last time $x$ was queried.

It is not controlled by either party, but in most games both parties are allowed to query it. Because of the way it generates it's output, the two parties do not learn anything about what the other has asked the oracle (unless your game explicitly tells them).

| improve this answer | |
  • 1
    $\begingroup$ Even in those other scenarios, "the two parties do not learn anything about what the other has asked the oracle". $\:$ Those scenarios usually allow the reduction to know what the adversary asks the oracle, and sometimes allow the reduction to provide the responses instead of the oracle. $\;\;\;\;$ $\endgroup$ – user991 Mar 24 '14 at 10:39
  • $\begingroup$ True enough (used for purposes such as counting internal collisions at later stages in an algorithm). $\endgroup$ – Cryptographeur Mar 24 '14 at 10:39
  • $\begingroup$ @figlesquidge thks very much for your answer, actually I mean that we always see that the adv can make oracle queries to the challenger, and the challenger can decide what to return to the adv. I don't know why the challenger can decide what the adv get from the oracle. $\endgroup$ – Jiangtao LI Mar 24 '14 at 13:04

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.