On rekey policies for secure group applications

Secure distribution of information to authorized recipients is an important prerequisite for group applications with commercial potential. Typically in such applications data traffic is encrypted using a single key; that key in turn is distributed securely to the group using one of several mechanisms that rely on each member having a unique set of "key encryption" keys. As users join and leave the group, members' keysets have to be changed according to a rekey policy. The rekey policy is important because it determines the security properties provided to the application (e.g. forward/backward secrecy). In this paper we present a general model of rekey policies for large-scale applications, and use it to compare the effectiveness of policies proposed in the literature for various applications. Unlike prior work, which has focused on the cost of rekeying, our model also accounts for the cost of not rekeying. We cast existing policies in terms of our model and then propose a more flexible policy that we call exposure-oriented rekeying. We present simulation results showing that our new policy reduces the peak and variation in cost to achieve a given level of security, compared with periodic or batch-oriented rekeying policies.