I think that likely the answer to the first question, "Do proofs in the Random Oracle model generally require to handle the situation when the adversary is not using the Random Oracle", is likely yes.

In a lot of simulation based proofs I've read from the MPC literature, we assume that the simulator has blackbox access to the adversary's code.

Not sure if that helps in this scenario, though.

@cygnusv In your setup, what security property are you trying to prove? CCA, CCA2? Something else?

Pretend for a minute that the adversary is guaranteed to use the random oracle. The adversary submits a ciphertext to the simulator. What does the simulator do with it?

Hi @mikeazo, thanks for creating the chatroom and taking the time

Wrt to your very last question, if the adversary is guaranteed to use the random oracle everything in the proof goes smoothly, since I can use the random oracle tables to compute everything

in other words, the simulation would be perfect in that case

I'm actually try to prove a notion related to CCA2

of course it is not the canonical CCA2 since it would not be compatible with altered ciphertexts

but in this case, the alteration is completely deterministic, i.e., for each ciphertext there is only one possible altered version, so we can deal with that

it is a notion similar to Relaxed CCA, stronger, in fact

sorry, Replayable CCA

So attacker sends ciphertext he generated to simulator. What does simulator do with the ciphertext? Assuming attacker uses RO.

basically, the simulator search in the random oracle table for a query that is related to the input ciphertext

if we assume A uses RO, then it is guaranteed that we will find an entry in the table

(I guess I forgot to mention that the simulator provides the random oracle to the attacker so he has access to all previous RO queries)

okay, that makes sense then.

using this information, we can do everything we want

So who is running "Alteration" in the real world?

Alteration would be executed by an entity who possess this "special key" I mention in the question

this special key is computed from the secret key

But the special keys have nothing to do with the hash function modeled as a RO?

yes, nothing to do

actually, the hash function is used as a sort of consistency check of the ciphertext

the alteration function is guaranteed to alter the ciphertext without breaking the hash

I mean, without breaking this check

I guess I still don't see why the simulator can't run the same function that the entities run for "Alteration"

the idea of the alteration function is to perform the alteration without learning anything about the underlying message

the special key is required for this process

since this key is derived from the secret key, and the simulator doesn't know it, he can't compute the special key, and cannot perform any alteration

however, he can if the adversary uses the random oracle

on the other hand, the adversary can compute the alteration because he knows all the original input used for creating the ciphertext on the first place

the alteration is deterministic, so he knows how to compute it

@cygnusv That makes sense.

I think I understand the problem now.

Unfortunately, I don't know how to solve it :(

that's OK, it's always good to try to explain the problem...it oftens help to find the solution

:)

anyway, my question is not about how to respond the queries...I know it is not possible

the thing is that I don't see how these problematic queries are useful for the adversary, so I'm asking if I can get rid of them (i.e., by aborting the simulation), even if it has a cost in the tightness of the reduction

If you can't abort them in the real life protocol, I don't see how you can abort them in the simulation. But then again, this isn't really my area of expertise.

In MPC proofs where were are working in the UC Framework, there is an ideal functionality that would have access to the secret key.

So for queries for which the RO has not been accessed, I'd probably forward them to the ideal functionality, let it do its thing. And return the result through the simulator. Then I'd have to show that (either computationally or information-theoretically) this does not leak useful information.

I don't know if this applies here though.

I see...I'm not familiar with UC proofs

this a game-based proof

technically, I shouldn't have used the term "simulator", but "challenger" :P

well, I really hope you get an answer. There are a few users on here who are likely advanced enough to know how to help.

@mikeazo thanks anyway for your time!

hope to catch the attention of any of them then

I'll definitely give it some more thought.

Maybe you should do a UC proof :)

@mikeazo thanks for your interest :D

and BTW, congrats!