4
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • $\begingroup$ 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"? $\endgroup$
    – mikeazo
    Commented Jun 30, 2015 at 12:04
  • $\begingroup$ @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) $\endgroup$
    – cygnusv
    Commented Jun 30, 2015 at 12:55
  • $\begingroup$ 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? $\endgroup$
    – mikeazo
    Commented Jun 30, 2015 at 13:07
  • $\begingroup$ @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... $\endgroup$
    – cygnusv
    Commented Jun 30, 2015 at 13:25
  • $\begingroup$ Do you really need perfect simulation? $\:$ (For general PKE purposes, computational simulation is enough.) $\;\;$ $\endgroup$
    – user991
    Commented Jun 30, 2015 at 14:00

1 Answer 1

Reset to default
4
$\begingroup$

Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query.

However, if you can't prove this, then you may have to go back to the construction and change it. This reminds me of the double-encrypt-plus-NIZK way of getting CCA-secure encryption in the standard model. In that construction, the NIZK is needed since the simulator can only decrypt one of the two ciphertexts in the reduction, and cannot tell that the other is an encryption to the same. However, if it's not an encryption of the same, then in the real world this would decrypt to invalid. Nevertheless, you can't get rid of the NIZK. The simulator has to know what would happen in the real execution. Sorry for the pessimism.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – cygnusv
    Commented Jun 30, 2015 at 20:35
  • $\begingroup$ "Your proof certainly has to work even if the adversary doesn't use the random oracle." OK, I see. I was wondering if I could use a similar argument to the one used in Waters' IBE proof, where he introduces artificial aborts to deal precisely with adversaries that make queries that the simulator cannot respond. BTW, in this chat room I think I have explained better the problem. You are invited to join, of course :) $\endgroup$
    – cygnusv
    Commented Jun 30, 2015 at 20:42
  • 3
    $\begingroup$ @Yehuda Welcome to the site. I've read a number of your papers in the past. Glad to have you here. $\endgroup$
    – mikeazo
    Commented Jun 30, 2015 at 20:45
  • $\begingroup$ Yeah, I'm honored to have attracted Yehuda Lindell's attention...I have just checked his book this morning. @YehudaLindell Welcome to the site, I believe a lot of people here would be very happy to count with your participation $\endgroup$
    – cygnusv
    Commented Jun 30, 2015 at 20:49
  • $\begingroup$ Thanks for the warm welcome. Regarding the question: why does the simulator need to answer the Alteration oracle with an error symbol? I thought that the problem is what the simulator should do with a decryption query. Won't it work to have the simulator answer the Alteration oracle like in the real world, but record the result and know to answer the decryption query with an error symbol if it's every queried? $\endgroup$
    – Yehuda Lindell
    Commented Jun 30, 2015 at 22:16

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.