Crypto '11 (belated): Invited talk - FlipIt

(The distractions of the conference kept me from finishing this post at the time, but since it has proved such a frequent topic of conversation over the past week I decided it was worth belated coverage).

Ron Rivest began his invited talk with a quote from Abraham Lincoln: "How many legs does a dog have if you call the tail a leg? Four; calling a tail a leg doesn't make it a leg". Likewise, a "secret" key is not secret by virtue of its name alone. We seek schemes which provide some sort of guarantee of secrecy or security within a particular adversarial scenario. But it is hard to perfectly model real-life threats so that, in practice, provably secure schemes can at best be supposed to be difficult or costly to compromise.

FlipIt is a game-based approach to modeling security which embraces this limitation and addresses the challenge of finding the best strategy for managing (over time) a secure system in a cost-efficient way. The ongoing, continuous-time game comprises two players - an adversary and a defender - who can, by turns, compromise and restore security (for example, by finding and respectively resetting the secret key). There are distinct costs associated with each move, and likewise a payoff to each player for time spent in the preferred 'state' (the adversary benefits when the system is compromised, the defender when it is secure). However, the players do not know the true state until they make a move, at which point they get to see the entire history of moves to date. Of course, neither wants to expend on needless moves and so is faced with a strategy selection problem which can be solved by a cost-benefit analysis.

The optimal strategy will depend on the distribution of the opponent's moves and on the particular costs and payoffs involved. Non-adaptive strategies include periodic (fixed time interval moves), exponential (memoryless moves at a certain fixed rate), and renewal (a more general process by which the distribution changes after each move). Adaptive strategies are more complicated, and use the feedback information from the revealed history to inform future moves. Rivest performed cost-benefit analyses for some illustrative examples and discussed the conditions for various different equilibria to be achieved.

It was interesting to see an alternative perspective on the challenge of security and the way in which cross-disciplinary research can be used to build multi-faceted responses to multi-faceted problems. Whilst the elimination of vulnerabilities is clearly important, such endeavours should be complemented with efforts to mitigate the damage done by 'inevitable' compromise.

Peter Schmidt-Nielsen gave a rump session talk (which I regret to have missed) in which he applied the Cramer-Rao Bound in addressing one of the open problems: "What's the optimal non-adaptive strategy against an adaptive opponent". (Slides here (pdf)).