Key tree optimization

In the applications where a group of people share some service such as teleconferencing and online TV, the most important security problem is to ensure that only the authorized users can enjoy the service. One popular way to enforce the security is to encrypt the service content using a group key and update it whenever users leave or join. The key tree model is proposed for the purpose of managing key updates. Sometimes, the system manager knows the user behavior related to the group and therefore hopes to reduce the number of encryptions needed to update keys. For example, in applications where the resource is limited and there are always users waiting to join the group, the system manager may decide to update the keys whenever k users leave (and hence k new users join) the group. There are also scenarios where there are some users who never leave the group (loyal users), but others will leave the group with a certain probability before the system manager decides to rekey. In all these and other similar scenarios, finding a tree which requires minimum number of encryptions to update the keys will be of great interest to the system manager because encryptions usually take quite some time. In this chapter, the relevant results in this area will be surveyed.