Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

what are the main pros and cons of proving the "security" of a crypto scheme under simulation proofs instead of game based proofs?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

As the other answers already state here, game-based definitions are easier to write proofs for, but simulation-based definitions are often clearer in terms of the security guarantee that you get. The best example of this is IND-CPA (game-based definition) versus semantic security (simulation-based definition). Note that IND-CPA is really not a convincing definition: why does not being able to distinguish between an encryption of 2 ciphertexts guarantee that you can't learn any partial information? It is only once you prove equivalence to semantic security that it becomes clear (both because semantic security is clear, and because the proof of equivalence is very illuminating).

Unfortunately, in most cases, the game-based and simulation-based definitions are not equivalent. So, which is better? It depends on the situation. However, there is one very important thing that simulation gives you that game-based definitions do not, and that is security under composition. The stand-alone simulation-based definitions give you security under sequential composition, and universal composability and its variants give you security under concurrent composition. Note, that this security is not only concurrent executions of the same protocol (since this is also often guaranteed in a game-based definition), but concurrent executions with arbitrary other protocols. This is not guaranteed by any game-based definition (to the best of my knowledge). Even when considering the stand-alone definition, it is much easier to plug your protocol into something larger and prove its security, using the modular sequential composition theorem. In short, these composition theorems let you analyze a larger protocol while relating to the subprotocol as an ideal functionality call. This greatly simplifies things.

I believe that simulation-based definitions are qualitatively better, in most cases. The guarantees are clear and composition is guaranteed. This does not mean that game-based definitions are not good, and in fact, they are often the way to go (especially for lower-level primitives). But, it really depends on the case.

share|improve this answer
Thank you. But, in sb proofs there is a pre-agreed leakage in the ideal evironment. From my point of view and maybe i am wrong the question is and what is missing from sb proofs: How this leakage does not affect the security definition. And i am saying that because in the sb proofs that i have seen the point of interest is to show that the two worlds behave equivalently and not how the leakage affects the scheme. So it seems on me that this is the negative part with sb proofs. And as you correctly pointed out with game based there is no connection from IND-CPA to semantic security –  curious Sep 25 at 7:46
This is a misconception. Simulation-based definitions allow you to formalize some "leakage" or "defect". They certainly do not require you to do this. A standard ideal functionality definition (which is what you do for most tasks) has no "leakage", but you can if you need it to get security. (But the more complicated the ideal functionality, the less satisfying it is.) Regarding IND-CPA and semantic security, I don't know why you say there is no connect; there is a full proof of equivalence. –  Yehuda Lindell Sep 25 at 10:55

Proponents of simulation-based proofs will tell you that their notions are easier to understand and it's clearer what exactly the notion gives you. Compare Jens Groth in : his introduction (page 2) is a clearer answer to the "pros" in your question than I can come up with here.

However, if you're actually trying to construct a proof of security of a given scheme, while simulation gives you nicer notions I find that it makes the proofs themselves less intuitive and harder to understand. YMMV.

share|improve this answer

I'm not sure that I understand the question completely, as there are plenty of proofs of real-ideal simulation-based definitions that are proved in a "sequence of games" style. So, I think that the question being asked might be either of the following:

  1. Rather than comparing proofs, perhaps the question is about definitions. Specifically: what are the main pros and cons of proving the security of a scheme based on a simulation-based definition versus an indistinguishability-based definition?

  2. On the other hand, perhaps the question is about proofs after all, in which case it might be: when writing a cryptographic proof (of a property with any definition style), what is the value of writing the proof as a sequence of games as opposed to any other manner?

I'm going to assume that the question being asked is #1. In that case, my answer would be that it depends on the problem, as the "preferred" approach should be the one that illuminates the exact security goals (and non-goals) the clearest.

I would argue that a definition should "stand on its own" even if the reader doesn't bother with reading the proof details. Along those lines:

  • A simulation-based definition has the flavor "I'm claiming that X is an idealized model representing the best that we could do with this type of problem, and my system is close to X." Assume for now that the proof is correct. Then, the statement left for the reader to determine is his or her belief that X really does model the "best" that one could do.

  • An indistinguishability-based definition has the flavor of "I'm claiming that my system is as good as Y." The statement left for the reader to determine is whether Y really would satisfy the security properties that the reader wants.

Since both of these "remaining statements" are usually far from easy, it's probably best just to go with the definition for which the "X" or "Y" can be as simple as possible. This way, the reader can clearly identify the threat model that you're considering and determine if it's appropriate for any given use case.

share|improve this answer
Can you point out some "good" simulation based proofs where "X model the best that one could do"? Yes you clearly defined what i wanted to say in question 1 but question 2 contains some valuable info as well if it can be answered... –  curious Jan 29 '13 at 10:44
Also it seems that simulation based definitions are completely different with game based and more abstract. As in simulation you are trying to prove that the idealized model is the best model that a security construction "must" follow in its security proof. So as i first step you have a simulation definition for the best things someone should prove and them with games and indistinguishability you prove that your construction is very close to the idealized one. Am i correct? –  curious Jan 29 '13 at 11:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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