New constructions for multicast re-keying schemes using perfect hash families

A secure multicast scheme allows a group controller (or a centre) to send messages securely over a multicast channel to a dynamically changing group of users. In this paper we show efficient methods of establishing a common key among dynamic subgroups of a multicast group such that collusion of up to w malicious users cannot have information about the established key. We call this re-keying problem. We propose two basic constructions, called AND and OR schemes, for multicast re-keying problem using perfect hash families. We show that one scheme is most efficient when the subgroup size is close to the full group, and the other when the subgroup size is very small. Both schemes require O(log n) keys storage for both the group controller and the user, and achieve O(log n) communication complexity in their optimal applications. We further show how to improve communication efficiency of the basic OR scheme using erasure codes. Finally we extend the model of the single controller to dynamic controller in which any user of the group can establish a common key with a subgroup of the original group, and give extensions of AND and OR schemes for this case.