PSA: An Efficient Group Key Updating Algorithm in Secure Multicast

Secure multicast uses a group key shared by all group members to encrypt group communication. To ensure security, key server should update the group key (rekey) when an existing member leaves the group or a new member joins the group. Key tree approach is widely used to achieve logarithmic rekeying cost, but the key tree structure has to be kept balanced, otherwise the communication cost in the worst cast will be O(n). In this article a new algorithm named PSA (Path Shuffling Algorithm) is proposed based on key tree. PSA can scatter the balanced operations in normal rekeying operations, so it reduces the restructuring cost and thus improves the performance. Theoretical analysis gives the average updating cost, and experiments show that PSA algorithm has better average-case rekeying performance than other group key updating algorithms.