# On the Proof Technique of Boneh-Lynn-Shacham Gap Signatures

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!

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:

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.

• 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? Commented Oct 12, 2011 at 7:51
• @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. Commented Oct 12, 2011 at 14:49
• @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? Commented Oct 30, 2011 at 9:28
• @Maverickgugu: Please send me the merged proof via email. You can find my contact information here. Commented Oct 30, 2011 at 15:25

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).

• 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). Commented Oct 12, 2011 at 7:22