What I understand about the random oracle game:

The adversary can query the oracle polynomial many times with the same (secret but unknown) key. From the output returned by the oracle, the adversary has to tell whether the oracle has chosen RANDOM or CIPHER (with probability more than .5).

Now, how does that stop adversary from replay attack? Say, the adversary has told the oracle to keep the same key twice. Both the times the adversary queries the with same message. Now, if oracle has chosen RANDOM, both the outputs will be different with very high probability. Whereas, if oracle has chosen CIPHER, both the outputs from oracle will match.

How the safe-guard is given from the trivial attack?

One idea came to my mind: The oracle has an infinitly large memory. Everytime the oracle is queried, it checks if the same input has be supplied previously. If so, it returns an error/ returns a valid output only when the input is not found in its memory. Is this idea meaningful?

  • $\begingroup$ This question was being put on top by the community user. I think it has been answered, but I see that you haven't accepted answers for three questions in a row. Please accept answers or indicate what is missing from the answers. $\endgroup$
    – Maarten Bodewes
    Dec 18, 2019 at 17:03

1 Answer 1


As far as I know, the "random oracle game" doesn't exist. What your are speaking (I think) is about pseudo-random functions. And when the challenger (not the oracle) is in the "RANDOM" mode, he could keep in memory the pair input/output, according to previous queries. Then it doesn't need to output "error", he could return the same output as in the previous query.




  • $\begingroup$ ... but if he returns the same output, wouldn't the Adversary get that the Challenger chose RANDOM? $\endgroup$
    – hola
    Nov 18, 2019 at 11:28
  • $\begingroup$ In both modes "RANDOM" or "CIPHER": The function is supposed to be deterministic, id est: if you query twice the image of one input, it will answer you twice the same output. That's why it's completely usefulness to query twice the image of one input. $\endgroup$
    – Ievgeni
    Nov 18, 2019 at 11:43
  • $\begingroup$ OK... understood! $\endgroup$
    – hola
    Nov 18, 2019 at 11:50
  • $\begingroup$ Could you give a comprehensive reference to this topic? $\endgroup$
    – hola
    Nov 18, 2019 at 11:51
  • $\begingroup$ I've added the references in my answer. $\endgroup$
    – Ievgeni
    Nov 18, 2019 at 12:49

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.