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

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.

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.