<p>One paper that deals with the issue is <a href="http://www.andrew.cmu.edu/user/danupam/ddmrs-tcc06.pdf" rel="nofollow">Games and the impossibility of Realizable Ideal Functionality</a> 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). </p>

<p>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. <a href="http://www.wisdom.weizmann.ac.il/~feige/thesis.ps" rel="nofollow">Feige's PhD</a>), 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).</p>

CC BY-SA 2.5
2010-11-16T08:55:40.837Z
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.
Sadeq Dousti
CC BY-SA 2.5
2010-11-16T15:51:39.173Z
Thank you! Exactly what I was looking for. 
@Sadegh: Thank you too. You are acting as my editor :D
Yasser Sobhdel
CC BY-SA 2.5
2010-11-16T08:39:34.613Z
2010-11-16T09:32:52.893Z
2010-11-16T09:32:52.893Z
Alon Rosen
<p>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). </p>

<blockquote>
  <p><strong>Question</strong>: 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?</p>
</blockquote>

<p>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.</p>

CC BY-SA 2.5
2010-11-15T19:55:01.463Z
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?
Dave Clarke
CC BY-SA 2.5
2010-11-16T08:27:41.760Z
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).
Alon Rosen
<cc.complexity-theory><cr.crypto-security>
Using game-based proofs in simulation-based proofs
Yasser Sobhdel
# Using game-based proofs in simulation-based proofs

(Asked by: username_0 on 2010-11-15)

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.

**Tags:** cc.complexity-theory, cr.crypto-security
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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).  

---

## 1 answers

### Answer by username_2 on 2010-11-16. Score: 6 | Accepted answer

One paper that deals with the issue is [Games and the impossibility of Realizable Ideal Functionality](http://www.andrew.cmu.edu/user/danupam/ddmrs-tcc06.pdf) 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](http://www.wisdom.weizmann.ac.il/~feige/thesis.ps)), 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).

> **Comments:**
> **username_3**: 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.  
> **username_0**: Thank you! Exactly what I was looking for.  @Sadegh: Thank you too. You are acting as my editor :D  

---

