8
$\begingroup$

Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to prove security of some parts of the protocol. For example, to assess the security of a protocol for round complexity or total messages exchanged during execution of the protocol, a game-baed approach is taken, but the security of the protocol itself regarding the framework (in my study the UC framework) is proven by Ideal/Real paradigm (i.e., simulation based approach).

Question: Under what circumstances can we use a game-based approach to prove security of a part of the protocol or the whole protocol when the protocol design must conform to a simulation approach? Can we use this approach at any point for any reason as long as it is not relevant to security of the whole protocol regarding the simulation-based framework?

Let me explain it through an example: I am studying a group key exchange protocol over UC framework (simulation-based), but the protocol uses encryption schemes which are CCA-Secure (proven by a game between adversary and some oracles) or CCA2-secure (proven by a game-based approach too), signatures must be existentially unforgeable (game-based approach too) and finally the communication cost of the protocol is calculated and analysis of the protocol security is done through 10 or 11 games between adversary and simulator. Finally proofs are made to show that the protocol conforms to UC regulations.

Improve this question
$\endgroup$
2
  • $\begingroup$ This is an interesting question. Again, I'm out of my field, but it is surprising to me that a simulation-based approach is more powerful than a game-based approach. Do you have a reference for this or any intuition? $\endgroup$
    – Dave Clarke
    Nov 15, 2010 at 19:55
  • 5
    $\begingroup$ Dave, it is not at all surprising that simulation-based definitions are stronger than game-based ones. In a simulation-based definition it is required that nothing is learned from the interaction (besides the intended functionality), whereas in a game-based one the security requirement is explicit (think of unforgeability of digital signatures). So in principle one can learn something from interacting with a scheme that is game-based secure, as long as this doesn't violate the explicit security requirement (e.g. learning some secret info that does not help in forging the signature). $\endgroup$
    – Alon Rosen
    Nov 16, 2010 at 8:27

1 Answer 1

Reset to default
6
$\begingroup$

One paper that deals with the issue is Games and the impossibility of Realizable Ideal Functionality by Datta et al, but it does't seem to address the issue in full generality. I am not aware of any general statement that guarantees simulation-based security of the whole protodol based on specific game-based security properties of its sub-protocols (unless of course the game-based definitions imply simulation based security, in which case the generic composition theorems by Canetti should apply).

However, there do exist specific instances in which one can obtain simulation-based security from game based security. The most telling example in my view is a constant-round zero-knowledge (ZK) argument for NP by Feige and Shamir (see e.g. Feige's PhD), which builds on witness indistinguishabille (WI) and witness-hiding (WH) sub-protocols. Both WI and WH are (arguably) game-based definitions, and yet the entire protocol can be proved to be ZK (which is the mother of all simulation-based definitions, at least for interactive protocols).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Well said! I suggest reading Feige-Shamir paper (Zero Knowledge Proofs of Knowledge in Two Rounds) instead of Feige's thesis, since it is much more to the point. $\endgroup$
    – Sadeq Dousti
    Nov 16, 2010 at 8:55
  • $\begingroup$ Thank you! Exactly what I was looking for. @Sadegh: Thank you too. You are acting as my editor :D $\endgroup$
    – Yasser Sobhdel
    Nov 16, 2010 at 15:51

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.