Reducing the cost of the critical path in secure multicast for dynamic groups

In this paper we focus on the problem of secure multicast in dynamic groups. In this problem, a group of users communicate using a shared key. Due to the dynamic nature of these groups, to preserve secrecy, it is necessary to change the group key whenever the group membership changes. While the group key, is being changed, the group communication needs to be interrupted until the rekeying is complete. This interruption is especially necessary if the rekeying is done because a user has left (or is removed). We split the rekeying cost into two parts: the cost of the critical path-where each user receives the new group key, and the cost of the non-critical path-where each user receives any other keys that it needs to obtain. We present two algorithms that show the trade off between the cost of the critical path and the cost of the non-critical path. We also compare our algorithms to previous algorithms and show that our algorithms reduce the cost of the critical path while keeping the total cost manageable.