Random oracle : Replay

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?

• 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. – Maarten Bodewes Dec 18 '19 at 17:03

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.

references:

en.wikipedia.org/wiki/Pseudorandom_function_family

https://crypto.stanford.edu/pbc/notes/crypto/prf.html

• ... but if he returns the same output, wouldn't the Adversary get that the Challenger chose RANDOM? – hola Nov 18 '19 at 11:28
• 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. – Ievgeni Nov 18 '19 at 11:43
• OK... understood! – hola Nov 18 '19 at 11:50
• Could you give a comprehensive reference to this topic? – hola Nov 18 '19 at 11:51
• I've added the references in my answer. – Ievgeni Nov 18 '19 at 12:49