Key trees and the security of interval multicast

A key tree is a distributed data structure of security keys that can be used by a group of users. In this paper we describe how any user in the group can use the different keys in the key tree to securely multicast data to different subgroups within the group. The cost of securely multicasting data to a subgroup whose users are "consecutive" is O(log n) encryptions, where n is the total number of users in the group. The cost of securely multicasting data to an arbitrary subgroup is O(n/2) encryptions. However this cost can be reduced to one encryption by introducing an additional key tree to the group.