Sequence of Games: A Technique for Taming Complexity in Security Proofs
Victor Shoup
NYU

Abstract:

Over the past few years, some researchers in cryptography have 
been organizing some of their security proofs as sequences of 
games. In certain circumstances, this has proved to be a very 
useful tool in taming the complexity of security proofs that 
might otherwise become so messy, complicated, and subtle as to 
be nearly impossible to verify. This paper is meant to serve 
as a brief tutorial on this technique. At the outset, it 
should be noted that this technique is certainly not applicable 
to all security proofs. 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.