5
$\begingroup$

Suppose that there is a place in a security proof where the behavior of an oracle differs from the corresponding real execution (for example, the decryption oracle rejects certain types of ciphertexts but in the real world the decryption function accepts them). Let us assume also that the probability of this situation is not negligible (i.e., the adversary can force this easily).

My understanding is that this automatically means that the proof is incorrect, although I cannot justify it further than stating that "there is a difference between oracle behavior and real execution".

First of all, am I right? If so, is there a more profound explanation? Do you have some authoritative reference on this matter?

Update: The only example I can find on this respect is a paper from Bellare and Ristenpart, which discusses the proof of Waters' IBE scheme. This proof is tricky:

But A can make Extract queries that force any conceivable simulator to fail, i.e. have to abort. This means that the advantage against DBDH is conditioned on A not causing an abort, and so it could be the case that A achieves $\varepsilon$ advantage in the normal IND-CPA experiment but almost always causes aborts for the simulator. In this (hypothetical) case, the simulator could not effectively make use of the adversary, and the proof fails. (...) To compensate, Waters’ introduced “artificial aborts”

Although I grasp the meaning in the remarked sentence, I would like to have a deeper explanation

$\endgroup$

1 Answer 1

5
+50
$\begingroup$

The point why a simulation must not deviate too much from the real game is due to the following reasoning. You assume you have an adversary that wins the original game, but you do not know how the adversary acts if you deviate from the behaviour of the real game and the adversary can notice this. Exactly because you make no assumption whatsoever about the adversaries behaviour when encountering a behaviour in the simulation that is not covered by the real game. If the adversary can now always force your simulation to deviate from the real game, then you cannot use the adversary anymore as you cannot predicts its behaviour anymore (e.g., you simply have to abort the simulation every time since you cannot answer queries of the adversary and you do not know what the adversary does if you can not answer a query).

If your simulation fails with a probability that is non-negligible, then this is not a problem per se. What you need is to estimate the probability that an adversary causes a simulation to fail. Typically, proofs try to somehow partition the set of potential queries into those that are answerable and those that force the simulation to abort. For instance, assume that this partition is randomly defined according to some distribution and the simulation does not leak any information on which queries would be bad, then the adversary has no better strategy than "accidentially hitting" a query in the wrong partition and you can easily estimate its probability (as it is independent of the adversaries behaviour).

For instance assume you as a simulation have to guess that the adversary does not query 1 in $n$ possible things, because you cannot answer this one query. Think for instance (i.e,. you have partitioned such that you have $n-1$ queries that are good and 1 bad query). Now, if you randomly choose $i\in [n]$, then the adversary has no better strategy than accidentially hitting $i$ (i.e., the simulation is exactly as in the real game except the unwanted event happens and let us assume that this event is independent from the other things the adversary sees in the simulation). Then for every query the probability of an abort is $1/n$ and if the adversary makes a polynomial number of queries you just loose tightness in the reduction (you condition on the event that the adversary does not hit bad in all queries). Now, the simulation will always abort with the same probability irrespective of the adversaries strategy and you are fine. A nice brief discussion on how to formally model this can be found in Alex Dent's A Note On Game-Hopping Proofs. But actually the reasoning and the calculations are very simple. Note that also here there is a difference in the behaviour of the oracle in the real and simulated game and this does not mean that the proof does not make a sense.

However, if any adversary can always force the simulation to abort, then you have a problem. The problem as with Waters proof is that the probability of the adversary causing an abort of the simulation is not independent of the adversaries behaviour (as above). So he cannot relate the winning probability of the adversary and the reduction meaningfulle. Thus, he has to introduce this complicated artificial abort technique. As you already mention, can be avoided when using the strategy of Bellare and Ristenpart.

If you have a problem with a specific proof it may be easier to ask a specific question. I am not sure if my edit helps you.

$\endgroup$
5
  • $\begingroup$ I am talking specifically about this case: "If the adversary can now always force your simulation to deviate from the real game, then you cannot use the adversary anymore as you cannot predicts its behaviour anymore (e.g., you simply have to abort the simulation every time since you cannot answer queries of the adversary and you do not know what the adversary does if you can not answer a query)." For the example given in my question, assume that the ciphertext that the decryption oracle rejects can be created with probability 1 (e.g., by creating an invalid ciphertext ) $\endgroup$
    – cygnusv
    Oct 27, 2015 at 22:20
  • $\begingroup$ @cygnusv I edited my answer. Sorry but I do not have much time at the moment. $\endgroup$
    – DrLecter
    Oct 29, 2015 at 11:49
  • $\begingroup$ Thanks for your answer! If I understand correctly, the problem is neither that there is a difference between simulation and real execution, nor that the probability of such event is non-negligible. Now I realize I didn't state the question correctly. My actual question is concerning security proofs where it is not possible to bound the probability that the adversary force the abort. In the example from my previous comment, the simulation is aborted every time the adversary makes a query using an invalid ciphertext (this behavior does not depend on any random choice, and can be deterministic) $\endgroup$
    – cygnusv
    Nov 3, 2015 at 14:23
  • $\begingroup$ I'm not going to change the question, since, technically, you have already answered correctly, but maybe you can help me here $\endgroup$
    – cygnusv
    Nov 3, 2015 at 14:32
  • $\begingroup$ @cygnusv I have the impression that you will have problems in using such a proof as you are simply not able (in any case) to simulate the game. But it may be easier to ask a new question with the concrete scheme and your proof strategy. $\endgroup$
    – DrLecter
    Nov 8, 2015 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.