Take the 2-minute tour ×
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
add comment

2 Answers

up vote 3 down vote accepted

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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.