<p>The technique of "hopping" from one game to another, and proving the security through a "sequence of games" is <strong>not</strong> new. In particular, there are several papers which discuss these techniques, and exemplify them through various security proofs. The famous examples are:</p>

<ul>
<li><a href="http://eprint.iacr.org/2004/332.pdf">Sequences of Games; A Tool for Taming Complexity in Security Proofs</a> by <strong>Victor Shoup</strong> (2006)</li>
<li><a href="http://eprint.iacr.org/2004/331.pdf">Code-Based Game-Playing Proofs and the Security of Triple Encryption</a> by <strong>Mihir Bellare</strong> and <strong>Phillip Rogaway</strong> (2008). <em>Side note:</em> This paper is a bit hard to grasp, so don't start with this one! The extended abstract of this paper is published in <strong>Eurocrypt 2006</strong> under the name <strong>The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs</strong>.</li>
<li><a href="http://eprint.iacr.org/2006/260.pdf">A Note on Game-Hopping Proofs</a> by <strong>Alexander W. Dent</strong> (2007). <em>Side note:</em> This paper introduces another famous technique which was omitted from the above two papers.</li>
</ul>

<p>Regarding your question, I use a quote from the last paper cited above:</p>

<blockquote>
  <p>In a game hopping proof, we observe that an attacker running in a particular attack environment has an unknown probability of success. We then slowly alter the attack environment until the attacker’s success probability can be computed. We also bound the increase in the attacker’s success probability caused by the changes to the attack
  environment. Thus, we can deduce a bound for the attacker’s success probability
  in the original environment.</p>
</blockquote>

<p>Thus, the reason for using several games is that in each game, we simplify the computation of some unknown probability, without altering it in a significant way. This continues until we reach a game in which the computation of the probability is easy enough.</p>

CC BY-SA 3.0
2011-10-12T07:51:09.740Z
Thank u for the references!! i will comment after studying through these papers for a better picture. But to keep it more abstract, can such sequential game based proofs be converted to a single game proof and calculate the probability as a whole?
Maverickgugu
CC BY-SA 3.0
2011-10-12T14:49:25.330Z
@Maverickgugu: You're welcome! Regrading your question: Sometimes it is possible to convert several games into one, but the proof gets more complicated. (If I remember correctly, the first or the second reference cited in my answer mentions one such game.) But in general, such a proof can get highly complex, and even impossible to be carried out. I think you can work this out by trying to merge the 6 games in the Boneh-Lynn-Shacham proof, and seeing for yourself where the problem arises.
Sadeq Dousti
CC BY-SA 3.0
2011-10-30T09:28:29.117Z
@Sadiq Dousti: In Shoup's paper he mentioned "Moreover, even when this technique is applicable, it is only a tool for organizing a proof — the actual ideas for a cryptographic construction and security analysis must come from elsewhere." 
With that argument, I tried to condense the 6 games to 1 in the Boneh-Lynn-Shacham proof and am not able to find any difficulties in the merging. I felt it was just clearly combining all the extra conditions and failure events which gives the end probability. Can you please help me with any subtle information which I am missing out?
Maverickgugu
CC BY-SA 3.0
2011-10-30T15:25:27.070Z
@Maverickgugu: Please send me the merged proof via email. You can find my contact information [here](http://cstheory.stackexchange.com/users/873/sadeq-dousti).
Sadeq Dousti
CC BY-SA 3.0
2011-10-10T09:20:12.200Z
2011-10-10T16:02:42.127Z
2011-10-10T16:02:42.127Z
Sadeq Dousti
<p>The idea of using a sequence of games as part of a reductionist proof of security predates the given references (it is implicit in work dating back to the early '80s if not earlier, and explicit at least by the late '90s).</p>

CC BY-SA 3.0
2011-10-12T07:22:58.603Z
If I may suggest an improvement, you can add some examples as works in which the idea of "sequence of games" is implicit (my answer already covers some of the explicit examples).
Sadeq Dousti
CC BY-SA 3.0
2011-10-12T03:37:55.970Z
2011-10-12T03:37:55.970Z
user6584
<p>In paper "Short signatures from the Weil pairing" by Boneh, Lynn and Shacham, I was going through the security proof just like any other signature.</p>

<p>But the technique used in this paper is quite unique. Rather than using the normal challenger and adversary interaction, they have divided the proof into 6 games where each game is extended sequentially from the previous games. </p>

<p>I am not sure why they have used this approach instead of the normal game. Does this kind of security proof aid in reducing the probability easier or have they just given it from an "easy to read and understand" point of view?</p>

<p>Thanks!</p>

<reference-request><cr.crypto-security>
On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures
Maverickgugu
# On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures

(Asked by: username_0 on 2011-10-10)

In paper "Short signatures from the Weil pairing" by Boneh, Lynn and Shacham, I was going through the security proof just like any other signature.

But the technique used in this paper is quite unique. Rather than using the normal challenger and adversary interaction, they have divided the proof into 6 games where each game is extended sequentially from the previous games.

I am not sure why they have used this approach instead of the normal game. Does this kind of security proof aid in reducing the probability easier or have they just given it from an "easy to read and understand" point of view?

Thanks!

**Tags:** reference-request, cr.crypto-security


---

## 2 answers

### Answer by username_1 on 2011-10-10. Score: 11

The technique of "hopping" from one game to another, and proving the security through a "sequence of games" is **not** new. In particular, there are several papers which discuss these techniques, and exemplify them through various security proofs. The famous examples are:

* [Sequences of Games; A Tool for Taming Complexity in Security Proofs](http://eprint.iacr.org/2004/332.pdf) by **Victor Shoup** (2006)
* [Code-Based Game-Playing Proofs and the Security of Triple Encryption](http://eprint.iacr.org/2004/331.pdf) by **Mihir Bellare** and **Phillip Rogaway** (2008). *Side note:* This paper is a bit hard to grasp, so don't start with this one! The extended abstract of this paper is published in **Eurocrypt 2006** under the name **The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs**.
* [A Note on Game-Hopping Proofs](http://eprint.iacr.org/2006/260.pdf) by **Alexander W. Dent** (2007). *Side note:* This paper introduces another famous technique which was omitted from the above two papers.

Regarding your question, I use a quote from the last paper cited above:

> In a game hopping proof, we observe that an attacker running in a particular attack environment has an unknown probability of success. We then slowly alter the attack environment until the attacker’s success probability can be computed. We also bound the increase in the attacker’s success probability caused by the changes to the attack
> environment. Thus, we can deduce a bound for the attacker’s success probability
> in the original environment.

Thus, the reason for using several games is that in each game, we simplify the computation of some unknown probability, without altering it in a significant way. This continues until we reach a game in which the computation of the probability is easy enough.

> **Comments:**
> **username_0**: Thank u for the references!! i will comment after studying through these papers for a better picture. But to keep it more abstract, can such sequential game based proofs be converted to a single game proof and calculate the probability as a whole?  
> **username_1**: @username_0: You're welcome! Regrading your question: Sometimes it is possible to convert several games into one, but the proof gets more complicated. (If I remember correctly, the first or the second reference cited in my answer mentions one such game.) But in general, such a proof can get highly complex, and even impossible to be carried out. I think you can work this out by trying to merge the 6 games in the Boneh-Lynn-Shacham proof, and seeing for yourself where the problem arises.  
> **username_0**: @Sadiq Dousti: In Shoup's paper he mentioned "Moreover, even when this technique is applicable, it is only a tool for organizing a proof — the actual ideas for a cryptographic construction and security analysis must come from elsewhere."  With that argument, I tried to condense the 6 games to 1 in the Boneh-Lynn-Shacham proof and am not able to find any difficulties in the merging. I felt it was just clearly combining all the extra conditions and failure events which gives the end probability. Can you please help me with any subtle information which I am missing out?  
> **username_1**: @username_0: Please send me the merged proof via email. You can find my contact information [here](http://cstheory.stackexchange.com/users/873/sadeq-dousti).  

---

### Answer by username_2 on 2011-10-12. Score: 2

The idea of using a sequence of games as part of a reductionist proof of security predates the given references (it is implicit in work dating back to the early '80s if not earlier, and explicit at least by the late '90s).

> **Comments:**
> **username_1**: If I may suggest an improvement, you can add some examples as works in which the idea of "sequence of games" is implicit (my answer already covers some of the explicit examples).  

---

