What are the differences between proofs based on simulation and proofs based on games?

Question

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

Answer 1

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.

I have written a tutorial on how to write simulation proofs. This should help.

Answer 2

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 http://eprint.iacr.org/2002/002.pdf : 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.

Answer 3

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.