Security Games

I know, after seeing the title of this post, you probably expected me to be ranting about things like this, or this. And these are important topics, for sure.

But that's not the sort of "security games" that I've been thinking about lately.

We're solidly into the 5th module of Dan Boneh's excellent online cryptography course, which means that, by some measure, I'm about halfway through with the class. I'm starting to feel comfortable with the material presented in the class; more encouragingly, I'm starting to feel confident about broadening and deepening my studies in this area beyond the material in the class.

The online cryptography class is aiming for a substantial degree of rigor and precision. One of the topics that comes up routinely in the class involves proofs of various results.

The notion of "proof" in modern cryptography is somewhat complex. The types of cryptographic algorithms that we are discussing and studying are random, probabilistic algorithms, so the proofs have a lot to do with analysis of probability.

That is, we are often trying to make a rigorous and exact assessment of just how likely a particular event is.

For example, the event might be a collision in a hash algorithm, guessing a key in a symmetric encryption algorithm, predicting the next value of a random generator algorithm, etc.

The proof technique that Professor Boneh uses for analyzing these probability distributions and forming conclusions about the behavior of algorithms is structured around the notion of a "security game". One of the clearest descriptions of this proof technique can be found in Victor Shoup's paper: Sequences of games: a tool for taming complexity in security proofs. From the introduction:

Security for cryptograptic primitives is typically defined as an attack game played between an adversary and some benign entity, which we call the challenger. Both adversary and challenger are probabilstic processes that communicate with each other, and so we can model the game as a probability space. Typically, the definition of security is tied to some particular event S. Security means that for every “efficient” adversary, the probability that event S occurs is “very close to” some specified “target probabilty”: typically, either 0, 1/2, or the probability of some event T in some other game in which the same adversary is interacting with a different challenger.

The popularization of this proof technique, as far as I can tell, is credited to Phillip Rogaway, and in particular to the paper he wrote with Joe Kilian: How to Protect DES Against Exhaustive Key Search (An Analysis of DESX). In the paper, the authors analyze the advantage that a security attacker might be able to gain against the DESX algorithm by constructing a series of games that model the attacks that the adversary might choose.

(As an unrelated aside, my good friend John Black, who is now Professor of Computer Science at the University of Colorado at Boulder, was one of Professor Rogaway's early students. Hi John!)

Although I was initially uncomfortable with the security games technique, Professor Boneh's use of the approach is very clear, and after several times seeing these proofs applied, I have become much more comfortable with how they work. I think that there is just a fundamental complexity to constructing the analysis of a probabilistic random algorithm, and I've come to feel that the security games approach for working with these algorithms is an excellent way to illustrate their properties.

If, like me, your computer science background was primarily in deterministic algorithms, and modern cryptography is one of your first exposures to random and probabilistic behaviors, hopefully following some of these links and reading Professor Shoup's tutorial on the games approach will help you get more comfortable with these algorithms and techniques.