New constructions for multicast re-keying schemes using perfect hash families
Reihaneh Safavi–Naini, Huaxiong Wang · 2000
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 eÆcient 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.W e call this re-keying problem.We proposetwo basic constructions, called AND and OR schemes, for multicast re-keying problem using perfect hash families.We show that one scheme is most eÆcient 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 h o w to improve communication eÆciency of the basic OR scheme using erasure codes.Finally we extend the model of the single controller to dynamic controller in which a n y 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.