2007: Technical Summary

Scalable group rekeying schemes proposed in the literature can be classified into two categories: stateful schemes, e.g., logical key hierarchy (LKH) based approaches, and stateless schemes, e.g., subset difference based member revocation (SDR) mechanism. They differ mainly on the interdependency of rekey messages and messaging overhead in rekeying. SDR messaging overhead in rekeying is dependent on the membership during an entire multicast session whereas LKH messaging overhead is dependent on membership of the group during a rekeying instance. In this paper, we study the advantages and applicability of stateful and stateless rekeying algorithms to different groups and multicast security applications. We analytically compare the storage cost and the rekeying cost (number of encrypted keys) of LKH and SDR in immediate and batch rekeying scenarios. Our simulation studies show that LKH performs better in immediate rekeying and small batch rekeying, whereas stateless rekeying performs better as we process membership changes in larger batches. In some cases, stateless rekeying is observed to be as inefficient as encrypting the group key separately for each member of the group. We also report on the effect of member adjacency on SDR rekeying cost that it seems to have more impact on rekeying cost than the number of membership changes. We further show that the analysis of SDR rekeying cost in [12] is incomplete and present a better result. Key words