Simulation aborted because the adversary doesn't use the random oracle

I'm trying to construct a proof for an encryption scheme in the Random Oracle model. This encryption scheme is like a PKE scheme but with an additional function that kind of "alters" ciphertexts without changing the underlying message using some special keys (I don't want to go into the scheme details for not diverting attention from the actual question; let's call this function "Alteration", for simplicity). In principle, the scheme is designed in such a way that in order to create valid ciphertexts, you have to use a hash function $H$ at some moment during the encryption. I later use this fact in the proof to construct the decryption oracle: assuming that $H$ is a random oracle, I use the random oracle table to extract the necessary information for answering the decryption query, and if the adversary has not used $H$, then it outputs $\perp$. The adversary cannot distinguish this behavior from a real-world execution. So far so good.

The problem I'm facing right now is with the Alteration oracle. Everything goes smoothly as long as the adversary uses the random oracle. However, the adversary may query the Alteration oracle with a ciphertext constructed without using the random oracle, but the real-world version of the Alteration function is unable to detect such situation and simply outputs the altered ciphertext correctly. In the proof, the simulator cannot respond to the query since the adversary has not used the random oracles and the simulator does not have the required special key. The thing is that I don't see that these queries are beneficial at all to the adversary: the resulting ciphertexts would also be not valid, as the original ones, so their decryption would fail.

Therefore, in order to avoid a situation where the adversary could detect a difference between the simulation world and the real world, the only think I can think of at the moment is to abort the simulation in such situation. Of course, simply letting the proof go this way would invalidate it, since the adversary could make these problematic queries arbitrarily. I was thinking in trying something similar to the "artificial abort" technique used in the Waters IBE scheme. However, before continuing in that direction, I have the following questions.

Do proofs in the Random Oracle model generally require to handle the situation when the adversary is not using the Random Oracle (e.g., producing invalid ciphertexts)? If not, do you know any example of a scheme defined in the RO model where a similar situation occurs?

• Good question. I hope someone here can answer. From the adversary's point of view, given a specific input is the output of the alteration oracle predictable? If not, could you just return a random "ciphertext"? – mikeazo Jun 30 '15 at 12:04
• @mikeazo The problem is that the output is predictable, so a random ciphertext is not a viable solution (the simulation wouldn't be perfect then) – cygnusv Jun 30 '15 at 12:55
• So it is predictable even without the special key? But impossible for the simulator to generate something that follows the predictability? In the real world, can one detect that the ciphertext is does not use the correct hash function? – mikeazo Jun 30 '15 at 13:07
• @mikeazo If you put it that way, it doesn't sound good :P ... Yes, it is not only predictable but, in fact, deterministic: there is only one possible output. And wrt to the last question, no. The only way is during the decryption (both in the real world and the simulation), because one reconstructs the ciphertexts, checking this way whether the hash function was used or not. But that is not possible during alteration... – cygnusv Jun 30 '15 at 13:25
• Do you really need perfect simulation? $\:$ (For general PKE purposes, computational simulation is enough.) $\;\;$ – user991 Jun 30 '15 at 14:00

• The problem is that the Alteration oracle cannot respond to "invalid" queries with an error symbol $\perp$ because that would differ from the real-world execution, since this function does not output $\perp$ in the real world, and this would allow the adversary to distinguish the simulation from the real-world. – cygnusv Jun 30 '15 at 20:35